2

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

L777
  • 7,719
  • 3
  • 38
  • 63
phalanx
  • 21
  • 2
  • ...what set of points? – L777 Apr 07 '16 at 16:43
  • a set of points that defines the borders of the concave polygon. – phalanx Apr 07 '16 at 16:45
  • see SO [Create non-intersecting polygon passing through all given points](http://stackoverflow.com/questions/14263284/create-non-intersecting-polygon-passing-through-all-given-points) – stefan Apr 08 '16 at 19:38
  • 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 Apr 13 '16 at 17:52

1 Answers1

1

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.

shouston
  • 641
  • 4
  • 7
  • Thanks. I actually have a large number of datasets, and I cannot guarantee that for each data set, the distance between perimeter vertices will be less than the distance between edges of the perimeter. Is there an approach that doesn't assume this? – phalanx Apr 08 '16 at 19:15
  • The answer to this question discusses some of the problems with a more general solution: http://stackoverflow.com/questions/20141812/ordering-concave-polygon-vertices-in-counterclockwise – shouston Apr 08 '16 at 20:05