我现在有一个点的矢量

vector<Point> corners;

在那里我有previously存储在一个给定的多边形的角点。鉴于此，我知道肯定的点构成一个简单的多边形不包含任何自相交的边缘。然而，在存储这些顶点的过程中，它们彼此连接的命令不是preserved

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.

我现在有一个函数，给定一个点的载体，连接它们，并绘制了我一个封闭的数字。然而，我需要给该功能的点列中，他们需要连接的顺序。任何人都可以提出一个方法，我可以这些点以正确的顺序排序？他们形成了一个非常简单的凹多边形，而不是一个凸包。一个算法来找到所有的（7）点之间的中点也将是有益的：）

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 :)

推荐答案

有没有独特的解决方案，所以没有简单的算法。你可以尝试以某种方式模仿你的直觉。

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.

将一个随机点开始，每个点连接到其最近的邻居。然后将最后一个点连接到第一个。 选择一个点及其最亲密的邻居，并开始由线连接起来。现在反复再添点。始终选择其最小化的最后的线段和新加入的线段之间的角度的点。

这两种方法都没有真正的工作在一般情况下，他们甚至不保证，以避免交叉点。你可以尝试解决这个由回溯，如果你发现一个明显的错误（例如一个路口），再原路返回到决策的最后一点，并采取了退而求其次的做法相反，......

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.

的平均点为顶点容易计算。只需添加所有的点一起，通过您刚才添加的点数分，这是平均水平。在质心的意义上的中心点是什么，你可能更感兴趣的是，见下文。

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.

要确定的重心首先必须定义形状。这意味着你必须做一些像第1步

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.

将一个边框周围的多边形。 随机生成的边框内点。 对于每一点确定它是否边框内，如果没有，那么把它扔掉。要确定一个点是一个任意多边形使用内部线检查。 对于您保存，应用方法2.这些点的平均点是一个很好的近似中心点的所有点。 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.