Algorithm for creating a polygon from a group of adjacent triangles

Question

Suppose you have a set of triangles, like the one shown in the image below, where black is a triangle edge, red is a triangle point, green is the polygon that needs to be found, and blue is the polygon's points.

The polygon described may or may not be concave. The triangles in it will always be adjacent (share all three points with the other triangles in the set). What sort of algorithms exist to generate the polygon that such a set of triangles describes? The polygon should be in the form of a list of points in clockwise or counter-clockwise order.

Unless you split the lowest "big" triangle to connect all the loose vertices on its edge, your question is basically undefined — Amit, Aug 21 '15 at 23:12
http://stackoverflow.com/questions/2667748/how-do-i-combine-complex-polygons — Ross Presser, Aug 21 '15 at 23:12
Just make a set of all triangle edges that aren't colinear with an edge of another triangle. That's your list of polygon edges. — samgak, Aug 22 '15 at 10:16
Are the corners of the triangles known by coordinate or is there an array of vertices referred to by three indices per triangle ? — BrunoLevy, Aug 27 '15 at 19:44

score 1 · Accepted Answer · answered Sep 02 '15 at 15:30

1

How About Following A simple GrahamScan Algo... That's should Do the Trick.

answered Sep 02 '15 at 15:30

Ansh David

654
1
10
26

Shape isn't necessarily convex, so I can't use any of the convex hull algorithms. – Stefan Dimitrov Sep 02 '15 at 17:43

fang · Answer 2 · 2015-08-23T02:25:56.937

Assume you have N distinct points Pi and M triangles. We define each triangle by 3 indices i, j and k to the points. Each triangle will have 3 edges defined as E(i,j), E(j,k) and E(i,k). The way to find the "polygon" is as follows:

1) Loop thru all triangles. For each triangle, add the 3 edges into a set. Edges with two identical point indices should be considered as the same edge. Namely, E(i,j) = E(j,i). Once encounter such case, remove both E(i,j) and E(j,i) from the set as these are the interior edges.
2) The remaining edges in the set should be the edges forming the polygon.
3) Sort the edges in the set by the point indices as follows:

(3a) Pick any edge from the set, say E(i,j).
(3b) Add indices i and j into a std::vector, then remove E(i,j) from the set.
(3c) Find the edge from the set that shares the last point index in the std::vector (which is j now). Denote this edge as E(j,k). Add index k into the std::vector and remove E(j,k) from the set.
(3d) Repeat step (3c) until the set contains no edges. The point indices in the std::vector will be the points order for the polygon.

If you only have M triangles and 3*M (x, y) values for the triangle vertices, then you will need to do some pre-processing to remove identical points and re-define the triangles in terms of the point indices as stated above.

Algorithm for creating a polygon from a group of adjacent triangles

2 Answers2