Joining points of polygon in correct order

Question

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.

Image1:

Image2:

Answer 1

Start from the leftmost point $x_0$ (the one with minimum $x$-coordinate). If there are ties break them in favor of the point with minimum $y$ coordinate.

Suppose for simplicity that there are no two points that are collinear with $x_0$ (this case can be handled by suitably breaking ties).

Shoot a ray vertically at an angle of $-\frac{\pi}{2}$ radians. Sweep the plane by rotating the ray anticlockwise up to an angle of $\frac{\pi}{2}$ radians. Whenever the ray intersects a vertex, let this vertex be $x_{i+1}$ where $i$ is the number of intersected vertices so far. Connect $x_{i}$ to $x_{i+1}$. Finally, connect the last encountered vertex back to $x_0$.

In practice this boils down to writing all points in polar coordinates from $x_0$, then sorting them by their angle, and connecting them in order.