Re: outline polygon of overlapping triangles

"Martin Henne" <martin.henne@xxxxxx> wrote in message
news:ea0gcj$kjv$1@xxxxxxxxxxxx

can someone help me with an url or something
where I can get an algorithm that creates
an outline polygon from overlapping triangles?

If you want the polygon that is the union of the
triangles, the suggestion to use Alan Murtha's
library is a good one.

If all you want is the *outermost bounding polygon*
(which is not the union), take a look at my sample
application "MeshEnvelope". At my web site, select
the "Source Code" tab, then the "Applications" tab,
and then the "Miscellaneous Samples" link. Scroll
down to the item "Compute the envelope...".

All of the intersections between triangle edges are
computed using a sort-and-sweep algorithm for
speed. A graph of edges/subedges is created.
Starting with the leftmost-bottommost vertex of
this graph, a traversal is made around the bounding
polygon. This amounts to examining each vertex for
the appropriate edge to continue the traversal, which
involves sorting the edges by angle about the vertex.

I use this algorithm for computing the boundary
polygons of obstacles in pathfinding systems. The
3D obstacles are triangle meshes. The triangles are
projected to the ground plane. Because I can afford
no topological errors due to numerical round-off
errors, the code uses exact rational arithmetic.

--
Dave Eberly
http://www.geometrictools.com


.

Relevant Pages

  • Re: Is there any fast algorithm to get the intersection of the mesh and a polygon?
    ... But the triangles are convex, so as Ken pointed out, you can break the polygon into individual lines and use the previous algorithm to find their intersections with the triangles. ...
    (comp.soft-sys.matlab)
  • Area of Polygon on a Sphere - Algorithm
    ... Given a polygon with N edges, each of which is a segment of a great ... algorithm, latitude and longitude are expressed in radians. ... involving inverse tangents of square roots ... The planar "square" was a rectangle with width equal to the side ...
    (comp.infosystems.gis)
  • Re: Smallest 4-sided polygon surrounding convex hull ( smallest convex quadrilateral)
    ... "Finally the smallest 4-sided polygon surrounding the segmented code [ ... This is a special case of convex hull ... And I can't find an algorithm for that, ... I believe I'm looking for the minimal enclosing quadrilateral ...
    (comp.graphics.algorithms)
  • Re: Determining if a point on a 2D polygon is hidden
    ... > and the ray before the ray reaches your point. ... This is an Oalgorithm, which is reasonable for a small number ... of polygon vertices, ... The topic of "visibility graphs" is covered in Joseph O'Rourke's book ...
    (comp.graphics.algorithms)
  • Re: RFC: wideline algorithm
    ... > Have you considered using an algorithm for drawing convex ... > necessarily parallel to the x and y axes, so polygon algorithms ... Sure, a thickline is just a rectangle, but how do I go ... dungeon is composed of tiles which are either ...
    (comp.programming)