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.

  • \$\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 '19 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\$ Jan 10 '19 at 9:13

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

In pseudo code:

    V = PT - MID
    ANG = ATAN2F( PT.Y, PT.X )
  • \$\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\$ Jan 10 '19 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 '19 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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