Efficient algorithm to create polygons from a 2D mesh? (vertices+edges)

Question

Given a mesh consisting of a list of vertices (2D coordinates) and edges (as vertex pairs), like so:

So the edges are defined like this:

a: 2,3 
b: 3,4
c: 4,8
d: 5,8
e: 6,7
etc..

Edges are orientation-neutral, i.e. the order of any two vertices that define an edge is random (edges are not clockwise or counter clockwise).

Polygons may be convex or concave, but they never overlap or self-intersect (edges never cross eachother).

Question: how do I generate a list of all polygons?

More specifically, in the above example I would need 4 polygons, like so:

(a,b,c,d,i)
(d,g,h)
(f,i,j,k)
(e,h,k)

The polygons have no orientation either, clockwise or counterclockwise does not apply, and in fact the order of the edges that define a polygon may be random as well. For example (a,i,d,b,c) for the 5-sided one would be fine as well.

Instead of defining polygons as a list of edges, it could also be a list of connected vertices, like so:

(2,3,4,8,5)
(6,5,8)
(2,5,7,1)
(7,6,5)

In this case, the order of the vertices cannot be random (the list of vertices should be a circular sequence) but orientation (clockwise or counterclockwise) is still irrelevant. So the 4-sided polygon could also be (5,2,1,7) or (1,7,5,2) et cetera.

What is an efficient (fast) way to construct a list of polygons, defined in either edges or vertices?

I see many more polygons than the listed four. (j,i,h,e,f) (a,b,c,g,h,i) etc. How do you reject those ? — Some Guy
Can a polygon contain a hole? E.g. (7,1,3,6,7) and (7,2,5,7) - is that considered one polygon with a hole, or two overlapping polygons? — Andrew Williamson
Here is an idea, start a depth first search from a given node and when you hit that node in the path again, you have found a polygon ! Add the path to a global list of polygons. When you are done searching from a node (ex. node 1), mark it, you have found all possible polygons involving that node and subsequent searches originating at any node should not visit an already marked node. Repeat this process for all nodes in your graph and you should have all possible polygons. — Some Guy
@RandomGuy Those polygons would be separated by internal edges. As long as a polygon can be divided up into smaller polygons, I want to include only the smaller ones in my resulting list. — RocketNuts

David Eisenstat David Eisenstat · Accepted Answer · 2016-02-17T22:45:47

For each edge vw, generate two half-edges v->w and w->v. Partition these by head (the head of x->y is y). Within each partition, sort by angle (if you use a comparison sort, then there's a way to avoid trig).

For your sample graph, the result is

7->1, 2->1
1->2, 5->2, 3->2
2->3, 4->3
8->4, 3->4
7->5, 6->5, 8->5, 2->5
8->6, 5->6, 7->6
6->7, 5->7, 1->7
5->8, 6->8, 4->8

. Now, define a permutation where v->w maps to the half-edge following w->v in the list containing w->v (wrapping around if necessary). The cycles of this permutation are the polygons.

For example, 5->8 maps to 2->5 (after 8->5) maps to 3->2 (after 5->2) maps to 4->3 (after 2->3) maps to 8->4 (after 3->4) maps to 5->8 (after 4->8).

Efficient algorithm to create polygons from a 2D mesh? (vertices+edges)

1 Answers