Sorting random x,y spots on circularly closed line in order to calculate properly the perimeter and the area of the polygonal shape.

I want to sort random x,y spots on circularly closed line in order to calculate properly the perimeter and the area of the polygonal shape. I haved attached the images which i hope help me to be more specific:

• random spots

• after the unsorted line created from them

• the sorted line from matlab which of course not help us

• and the human sort plot that i make the sort by myself and the target sort

Is there any way to sort them like that or i need to recreate the way i was collected them and i was stored?

[Fangjun Jiang]

From the first plot, visually I can see multiple ways to connect them that are different than your manual solution. How do you deal with that?

[ALEXANDROS]

My example is try to catch as many posibilities of shape as can. After that are too many spots on my real problem so the ways of the line in order to create the polygonal we want is theoretically specific!

[Fangjun Jiang]

Please re-examine your comment. I don't understand it.

[ALEXANDROS]

yes i was try to edited in order to be more specific but anyway... the shape of random spots plot that i showed it was an extremely example of my problem. The route that the line make the closed loop usually is only one, so the only problem is a way to sort them in order to follow a circularly line loop.

[ALEXANDROS]

Answer 1

[Bruno Luong]

Formulate as TSP and solve with intlinprog as showed here

[John D'Errico]

@Bruno Luong - you failed to give a link

[Fangjun Jiang]

I am not sure if it can be formulated as the TSP probelm. My understanding is tha the OP is asking for a way to connect all the dots without any lines crossing each other. It doesn't care whether the traveling distance is the shortest.

[John D'Errico]

@Fangjun Jiang

Actually, a TSP solver will not cross edges. Why not?

Suppose you have some configuration of points where you think the solution has crossed edges? Then you can always change the sequence in a way that has the edges uncrossed, AND has a lower total distance.

A TSP is the correct way to solve this problem, at least if the goal is to find the minimal polygon connecting the points.

[Fangjun Jiang]

@John D'Errico, okay thanks. Good to learn that. I didn't know that.