Create non-intersecting polygon passing through al

Question

Suppose I have an array of points in random order, and I need to find a polygon (by sorting them, such that every adjacent pair represents a side) which passes through all of the points, and its sides are non-intersecting of course.

I tried to do it by selecting a point, and adding all points to the final array which are below it, sorted left to right. Then, adding all points which are above it, sorted right to left.

I've been told that I can add an additional point and sort naturally to avoid self-intersections.. I am unable to figure out that though. What's a simple way to do this?

Answer 1

Well, if you don't actually care about minimality or anything like that, you can just place new point inside the convex hull and then order the other points by angle to this new point. You'll get a non-intersecting polygon.