How can I order a list of Points so that no lines drawn intersect?

Question

I am getting a List of Points from the user clicking on the screen.

And I want to draw a polygon based on this points. The problem is that the user might not be clicking in the right order (no intersecting segments) to form a correct polygon, therefor I'm looking for a code snippet which would sort that List and arrange the points in the right order to form a good polygon...

Thanks!

picture = BAD POLY!

-

picture = GOOD POLY!

Answer 1

If you want to "wrap" the points in a polygon, you can use any number convex hull finding algorithms.

Answer 2

Dude i had the same problem, but i found a code that helped me. I think this resolve your problem .

See this link: http://jsfiddle.net/9DHSf/3/

Answer 3

You could take the centroid of all the points, then taking the dot product of each point to the centre with a reference point (say the first in the list) to the centre, get the angle of each point in your list from an arbitrary reference vector. Then order that list on the angle. That'll give you the points in a (eg) clockwise winding order, so your line is just p1 -> p2, p2 -> p3 etc...