For a point vector (possibly out of order) find a polygon (not a convex hull)

Question

I currently have a point vector

vector<Point> corners; 

where I previously stored the corner points of a given polygon. Given this, I know for sure that the points form a simple polygon that does not contain self-intersecting edges. However, during the storage of these vertices, the order in which they connect to each other was not preserved.

Now I have a function that, given the vector of points, connects them and draws a closed shape. However, I need to give this function a sequence of points in the order in which they should be connected. Can anyone suggest a way so that I can sort these points in the correct order? They form a very simple concave polygon, not a convex body. An algorithm for finding the center point among all (7) points would also be useful :)

Answer 1

1. Heuristics for determining the shape

There is no single solution, so there is no simple algorithm. You might try to imitate your intuition in some way.

• start with a random point and connect each point with its closest neighbor. Then connect the last point to the first.
• start by selecting the point and the nearest neighbor and connect them in a row. Now iteratively add another point. Always select a point that minimizes the angle between the last line segment and the newly added line segment.

Both methods really do not work at all; they do not even guarantee avoidance of intersections. You can try to solve this problem by backtracking if you find a clear mistake (such as an intersection), then step back to the last decision point and take the “second best” approach instead ...

But then again, since the solution is not unique, do not expect too much from these heuristics.

2. The average number of vertices

The midpoint for the vertices is easy to calculate. Just add all the points together and divide the number of points added, this is the average value. What you are probably more interested in is the central point in the sense of the "Center of Mass", see below.

3. Center point

To determine the center of mass, you must first determine the shape. This means you should do something like step 1.

An easy-to-implement method for calculating a center point defined for a polygon.

• Place a bounding box around the polygon.
• Arbitrary creation of points within the bounding box.
• For each of these points, determine if it is inside the bounding box, and if not, discard it. To determine if a point is inside an arbitrary polygon, use the ray test .
• For all points that you have saved, use approach 2. The midpoint of these points is a good approximation to the center point.

Answer 2

There is no single solution for a concave polygon:

A convex polygon can be found uniquely as a convex hull of points (if you know that points build a convex polygon).

Answer 3

This set of points, as a rule, can be connected in many ways to form a non-self-intersecting polygon. You may not be lucky if you have more information about the types of polygons that can represent points.