I have a point's array of some 2d shape(polygon). The polygon could be either crossed or convex, I don't know it. And I want to join those points in the correct order.
My first thought was to take some point as an origin and start looking for the closest one and so on. But this approach doesn't work for some crossed polygons, for example: on Image1, it would go from x3
to x5
because it is closer than to x4
, but what I really want is to join x1-x2-x3-x4-x5-x6
.
After some thinking, I've realized that my requirement correct order
is very unclear because on Image2 red lines are in the correct order too. So let's add the requirement that polygon lines shouldn't at least cross.
I really confused, can someone point me in what direction I should move? Maybe it's some famous algorithm but I just don't know how to google it properly. Thanks.