一种对非凸多边形顶点进行排序的鲁棒算法

计算科学 计算几何 正则 非凸的 排序
2021-12-25 21:06:39

让v_{0},...,v_{N-1}定义闭合多边形顶点的笛卡尔xy平面中的N个点（即v_{N} = v_{0}）。让一个位于多边形内的点，即先验P_{0}未知的点。

我正在寻找一种强大的算法来对列表进行v_{0},...,v_{N-1}顺时针/逆时针排序P_{0}。我知道，如果多边形是凸的，则以下算法效果很好：

  1. 计算P_{0}为 的平均值v_{0},...,v_{N-1}；
  2. 计算atan2 = (y_i-y_0/x_i-x_0)每个顶点定义的角度并将其保存到数组中；
  3. 使用角度数组作为键对顶点进行排序。

我想知道是否存在一种能够处理各种多边形的算法，也是非凸的。

1个回答

正如@HighPerformanceMark 在评论中提到的，如果顶点集是您拥有的关于非凸多边形的唯一信息，您并没有唯一地定义它。可以找到定义的非凸多边形，但不是那个。V={v0,…,vN−1}V

下面是由完全相同的一组顶点定义的两个不同六边形多边形的示例（当然不是最小的，但这是我画的第一个）。在多边形中，顶点是逆时针排列的，而就没那么幸运了。SASB

在此处输入图像描述

因此，为了使算法起作用，您将得到一些非凸多边形（在本例中，；但是，，但），但我很难想象允许非唯一性的应用程序。或者提供一些关于你“想要的”非凸多边形的额外信息——边的列表会立刻浮现在脑海中。当边缘列表存在时，您可能首先不需要该算法，或者通过遍历边缘列表重新排序变得微不足道。P0∈SA,SBP1∈SBP1∉SA

其它你可能感兴趣的问题
上一篇对于这种非凸场景，是否有收敛的优化方案/算法，但具有一些特殊属性 下一篇Fokker-Planck 方程的数值积分允许负漂移？