How to get all polygons from a set of points

Question

I need to get all polygon combinations (convex and concave) from a set of points and don't see the way to do it.

I'm thinking in this two approaches

• Check for each combination to be a planar graph having all nodes grade 2
• Check for each combination not have intersecting vertex (solving equation systems)

Am I right, or absolutely lost?

Thanks in advance

Answer 1

I assume that all points have to be in polygon.

On first I would implement backtracking approach. Start from one point, add edge to non visited point if it doesn't intersect edges of current path, and repeat while all points are visited. At last, check does edge from first to last path point intersect path.

There are other checks that can be done to remove next edge possible candidates. Find convex hull of all points. Use one point of convex hull as a starting point, and assume that path (polygon) is directed. That means that polygon interior is to the left of the path. Than points on convex hull have to be visited in positive order. That means that last path point can't be connected to convex point except one after (anti-clockwise directed) last visited. With this check, input set of points where all points are convex hull points (e.g. regular n-gon), will produce search tree of width 1 (list). Since it is not possible to create concave polygon if all points are on convex hull, because any connection between two non-neighbors split set of points in the way that there can't be edge between these two parts without intersecting that edge.