0
\$\begingroup\$

I'm having troubles trying to rearrange a set of points where each point is part of the edge of a concave polygone. My set of points is not sorted in any order, they are just randomly put in an array. See the example right below : enter image description here

My goal is to rearrange these points to be able to build a polygon correctly where the next index in the array is the next point to draw : enter image description here

I don't know how to do it fast, sometime arrays are made of 200 points, and I have like 20 of these arrays (I would use this to draw islands)

Thank you in advance.

\$\endgroup\$
  • \$\begingroup\$ I don't think this is a well defined problem. E.g. in your example, going from I to B to A to C is an equally valid convex polygon as going I , A, B, C. \$\endgroup\$ – Bram Jan 10 at 1:25
  • \$\begingroup\$ Yes but it's not a problem as I want to find one of the concave polygone that may be build out of a set of points. \$\endgroup\$ – Fosheus Badabu Jan 10 at 9:13
0
\$\begingroup\$

Maybe sort them on angle of vector from average to point?

In pseudo code:

MID = AVERAGE(PTS)
ANGLES = []
FOR EACH PT:
    V = PT - MID
    ANG = ATAN2F( PT.Y, PT.X )
    ANGLES.APPEND( (ANG, PT ) )
SORT( ANGLES )
FOR ANG,PT IN ANGLES:
   OUTPUT(PT)
\$\endgroup\$
  • \$\begingroup\$ Thank you for your answer but I think this méthod does not work with concave polygon as I already tried it and it builds a convex polygon out of these points. In the example I provided it's not that easy to see. \$\endgroup\$ – Fosheus Badabu Jan 10 at 9:10
  • \$\begingroup\$ This looks workable to me if we can reliably place the center point in the polygon's interior, though I think we need some additional sorting by distance when we encounter a run of 3 or more points along a ray from our centroid (all at the same angle, to within some tolerance). If the average point lies outside the expected polygon (think of a very skinny crescent moon with narrow tips that almost wrap around) we'll get a less desirable result. This method implicitly assumes the polygon is "star-shaped" in the mathematical sense, which covers non-convex cases but not every concave polygon. \$\endgroup\$ – DMGregory Jan 10 at 12:37

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.