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

algorithmccomputational-geometrygeometry

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 🙂

Best Answer

There is no unique solution for a concave polygon:

enter image description here

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

Related Topic