我目前有一个积分 vector
vector<Point> corners;
我以前存储给定多边形的角点的位置。鉴于此,我可以确定这些点形成了一个简单的多边形,其中不包含任何自相交的边。但是,在存储这些顶点的过程中,没有保留它们彼此连接的顺序。
我现在有一个函数,给定一个点 vector ,将它们连接起来并绘制一个封闭的图形。但是,我需要将此功能按需要连接的点顺序排列。谁能建议我以正确的顺序对这些点进行排序的方法?它们形成一个非常简单的凹多边形,而不是凸包。在所有(7)个点中找到中心点的算法也将很有帮助:)
最佳答案
1.启发式确定形状
没有唯一的解决方案,因此没有简单的算法。您可以尝试以某种方式模仿您的直觉。
这两种方法通常并没有真正起作用,甚至不能保证避免交叉。您可以尝试通过回溯来解决此问题,如果您发现明显的错误(例如交叉路口),则可以回溯到决策的最后一点,而采用“次优”的方法...。
但是,由于解决方案不是唯一的,因此不要对这些启发式方法抱有太大期望。
2.顶点的平均值
顶点的平均点很容易计算。只需将所有点相加,然后除以您刚刚添加的点数即可,这是平均值。您可能更感兴趣的是“质心”意义上的中心点,请参见下文。
3.中心点
要确定质心,首先必须定义形状。这意味着您必须执行类似步骤1的操作。
一个给定多边形的简单易行的方法来计算中心点。