CODEWITHSUNDEEP
algorithmgeometrypolygonconvex-hullconcave
phalanx
phalanx

Reputation: 21

Create concave polygon passing through all given points

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:

example

Upvotes: 2

Views: 2237

Answers (1)

shouston
shouston

Reputation: 641

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.

Perimeter detected using 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.

Upvotes: 1

Related Questions