find the outline of a roughly 2D mesh

0
votes

I have a roughly planar mesh that I would like to find the outline of. To find the outline, I loop through all the triangles of the mesh and count the number of occurrences of each edge (represented by an unordered pair of vertices).

After examining all the triangles, there are only two possible values for each edge.

  • edge count = 1 : the edge belongs to a single triangle and so it is an outer edge
  • edge count = 2 : the edge is shared between two triangles and so it is an inner border

Edges belonging to a single triangle (edge count = 1) define the mesh outline.

This strategy works pretty well, if it weren't for a problem, which I will try to illustrate with an example. Suppose we want to find the outline of the following mesh.

enter image description here

If we apply the strategy described above to this mesh, it will find the seven edges that define the outline - i.e. (0,1), (1,4), (4,7), (6,7), (5,6), (2,5) and (0,2) - but it will also find three inner edges, i.e. (2,3), (3,4) and (2,4), which belong to only one triangle each, respectively (2,3,6), (3,4,7) and (0,2,4).

I have thought of the following solution to solve the problem. As far as I can think, the issue can only arise when there are three vertices that lie on the same line as in the example above. The two short edges that connect the three vertices can be replaced by a single longer edge that connects the two outer vertices. This new edge is added to the list of edges or if already present its counter will be increased by one, reaching value 2. Iterating the procedure (following the path defined by the edges), I should simplify the list of edges and finally only those on the mesh outline should have count 1.

What do you think of my approach? Thanks.

1
algorithmgraphgraphicsgeometrycomputational-geometry
Simplest solution imo is to make a list of n-gons, with shared edges, then a shared edge with only 1 n-gon attached is a border-edge. Just use n-gons instead of triangles. – Flutterish
That's one reason why many people try to avoid such t-junctions. Are you restricted to the mesh at hand or can you modify it (by either introducing quads as @Flutterish suggested or by splitting the triangle)? – Nico Schertler

1 Answers

0
votes

The 2-3-4 configuration is "pathological" as it breaks the graph structure. In fact, this can be seen as a triangular hole in the mesh.

A possible way to handle is to list all single edges, detect the ones that overlap, and ignore them.