Create concave polygon passing through all given points

Question

Given a set of points, I want to create a concave non-intersecting polygon using these points. A convex hull would negate the concave part, while arranging them by x/y coordinates or angles from centre would create spiky artefacts. Is there a simple way to do this?

An example of the kind of polygon I want to create:

a set of points that defines the borders of the concave polygon. — phalanx
see SO Create non-intersecting polygon passing through all given points — stefan
Your problem is underconstrained, there are many concave non-intersecting polygons that will fit your example points. Perhaps you also want the polygon with the minimum perimeter length? — atb

shouston shouston · Accepted Answer · 2016-04-08T19:00:39

If you only have the perimeter vertices and can guarantee that the distance between perimeter vertices will be less than the distance between edges of the perimeter then you could use a minimum spanning tree.

The top example shows where a MST works (with the first and last vertices in the resulting polyline joined)

The bottom example is what happens if edges of the perimeter get too close.

Create concave polygon passing through all given points

1 Answers