Given a vector of points (possibly out of order), find polygon (not convex hull)

Question

I currently have a vector of points

vector<Point> corners;

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

I now have a function that, given a vector of points, connects them and draws me a closed figure. However, I need to give this function the sequence of points in the order they need to be connected. Can anyone suggest a way that I could sort these points in the correct order? They form a very simple concave polygon, not a convex hull. An algorithm to find the center point among all the (7) points would also be helpful :)

Answer 1

There is no unique solution for a concave polygon:

The convex polygon could be find uniquelly as the convex hull of the points (if you know that the points build a convex polygon).

Answer 2

A given set of points can generally be joined up many ways to form a non-self-intersecting polygon. You may be out of luck unless you have more information about the kinds of polygons the points could represent.

Answer 3

1. Heuristic to determine the shape

There is no unique solution so there is no simple algorithm. You could try to somehow mimic your intuition.

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

Both methods don't really work in general, they don't even guarantee to avoid intersections. You can try to address this by backtracking, if you detect an obvious error (e.g. an intersection) then backtrack to the last point of decision and take the "second best" approach instead, ....

But again as the solution is not unique, don't expect too much from those heuristics.

2. Average of the vertices

The average point for the vertices is easy to compute. Just add all points together and divide through the number of points you just added, this is the average. What you are probably more interested is the center point in the sense of "Center of mass", see below.

3. Center point

To determine the center of mass you first have to define the shape. That means you have to do something like step 1.

An easily implemented method to compute the center point given the polygon is.

• Put a bounding box around the polygon.
• Randomly generate points inside the bounding box.
• For each of those points determine if it is inside the bounding box, if not, then throw it away. To determine if a point is inside an arbitrary polygon use a ray test.
• For all points that you kept, apply approach 2. The Average point of those points is a good approximation to the center point.