How to sort arbitrary points so that when a line is drawn through them, a polygon is obtained sequentially?

Question

Geometry

There are several points in two-dimensional space, completely arbitrary can be (but cannot be the same).
You need to sort them so that when you draw a line through all these points in succession, you get a non-self-intersecting polygon.
How to do it? Is there even an algorithm capable of doing this?
Well, or some library in C # or C ++ is suitable, which will simply take it and do it.

Answer 1

Points connected in any order will form a polygon. It can be self-intersecting or non-convex, but you have no restrictions in your problem.

Answer 2

A banal-kneed version: we find the arithmetic mean coordinate, recalculate the coordinates of all points into radial relative to this mean, sort by angle (and if the angles are equal, by distance) - and connect in this very order.

Answer 3

If it is necessary without self-intersections, then a simplified version of the convex hull algorithm will do - just sort by the angle relative to the leftmost point, and that's it.

Answer 4

Possible algorithm.
Stage 1.
We build a convex hull. The used points are discarded. Using the remaining ones, we again build a convex hull... As a result, we get several nested non-intersecting hulls and, possibly, 1-2 points inside the innermost one.
Stage 2.
We connect each of the shells with the nearest outer one. Why we are looking for two pairs of neighboring vertices, one on each of the shells, such that the quadrangle formed by them does not intersect with any of these shells, and accordingly we replace the edges formed by these pairs with edges that are another pair of sides of the quadrangle. If at the first stage there are 1-2 internal points left, then we simply attach them to the internal shell so as not to get self-intersections.
The result is a non-self-intersecting polygon. We go around it in any direction from any of the vertices - the resulting list is the required answer.

Answer 5

The most correct way is to find the geometric center of the cluster, and from it go to radial coordinates, moving in a circle to connect all the points.
The second, and it seems to me an order of magnitude simpler option - we find the geometric center of the cluster, divide the area into 4 parts by the x and y axes, then go through each of them from top to bottom, connecting each underlying one with the previous one (linear scanning). We connect the extreme points of the regions - profit.