我目前有一个积分 vector

vector<Point> corners;

我以前存储给定多边形的角点的位置。鉴于此,我可以确定这些点形成了一个简单的多边形,其中不包含任何自相交的边。但是,在存储这些顶点的过程中,没有保留它们彼此连接的顺序。

我现在有一个函数,给定一个点 vector ,将它们连接起来并绘制一个封闭的图形。但是,我需要将此功能按需要连接的点顺序排列。谁能建议我以正确的顺序对这些点进行排序的方法?它们形成一个非常简单的凹多边形,而不是凸包。在所有(7)个点中找到中心点的算法也将很有帮助:)

最佳答案

1.启发式确定形状

没有唯一的解决方案,因此没有简单的算法。您可以尝试以某种方式模仿您的直觉​​。

  • 从一个随机点开始,并将每个点连接到其最近的邻居。然后将最后一个点连接到第一个点。
  • 首先选择一个点及其最近的邻居,然后用一条线将它们连接起来。现在迭代添加另一点。始终选择使最后一个线段和新添加的线段之间的角度最小的点。

  • 这两种方法通常并没有真正起作用,甚至不能保证避免交叉。您可以尝试通过回溯来解决此问题,如果您发现明显的错误(例如交叉路口),则可以回溯到决策的最后一点,而采用“次优”的方法...。

    但是,由于解决方案不是唯一的,因此不要对这些启发式方法抱有太大期望。

    2.顶点的平均值

    顶点的平均点很容易计算。只需将所有点相加,然后除以您刚刚添加的点数即可,这是平均值。您可能更感兴趣的是“质心”意义上的中心点,请参见下文。

    3.中心点

    要确定质心,首先必须定义形状。这意味着您必须执行类似步骤1的操作。

    一个给定多边形的简单易行的方法来计算中心点。
  • 在多边形周围放置一个边界框。
  • 在边界框内随机生成点。
  • 对于每个点,确定它是否在边界框内,如果不在边界框内,则将其丢弃。要确定点是否在任意多边形内,请使用ray test
  • 对于保留的所有点,应用方法2。这些点的“平均”点很好地近似于中心点。
  • 07-24 09:44
    查看更多