3

我想解构以下以蓝色显示的多边形，从多边形中删除所有导致凹面的点。

替代文字

目前，我一直在尝试做的是：

  • 从多边形中取出每个点
  • 测试该点以查看它是否落在集合的其余部分创建的多边形内
  • 如果为真，则删除该点
  • 如果是假的，保持这一点

这在大多数情况下都有效，但在前一种情况下，(2,3) 和 (2,4) 处的点不会都被删除。在这两种情况下，其中一个点都将被删除，但另一个点将不取决于传入数组的顺序。

我想知道的是：

  1. 有什么方法可以测试我正在处理的多边形是否恰好有这些情况之一（即：连续 3 个故障点？）
    或
  2. 有没有一种更有效的方法来创建凸多边形？

谢谢你。

4

4 回答 4

6

我想也许你正在寻找凸包？

想到的第一个算法是 QuickHull。最初，取最左边和最右边的点 l 和 r。它们必须在船体上。

在船体上构建第一个猜测，即两个向外的面，一个从 l 到 r，一个从 r 到 l。所以你有一个体积为零的多边形。

将所有剩余的点划分为 lr 前面的点和 rl 前面的点。

从那时起，当任何脸在它前面有任何点时：

  • 找到离脸最远的点
  • 删除这条边并用两条边替换它，一条从原始起点到最远点，一条从最远点到原始终点
  • 在旧面孔前面的所有点中，将您添加的第一个新面孔前面的点放入其前面的集合中，将第二个前面的点放入其前面的集合中，不要保留对现在内部的任何引用

最后，您将拥有凸包。

于 2010-11-13T19:18:56.013 回答
1

为什么不简单地计算点的凸包？

这是一个经过深入研究的问题，其中包含书籍和在线中的许多算法。“扫角”的方法特别常见，例如。

http://courses.csail.mit.edu/6.854/06/scribe/s25-rasmu-sweepline.pdf

于 2010-11-13T19:16:28.780 回答
0

您正在寻找的东西被称为“凸包”发现。在 wikipedia上查看此问题的算法。“礼品包装”算法很容易实现。当您找到船体时，只需删除不属于船体的所有点。

于 2010-11-13T19:22:10.273 回答
0

请注意，Convex Hull 已经在某些语言/环境中实现。

Mathematica 中的示例：

<< ComputationalGeometry`; 
   data2D = {{4.4, 14}, {6.7, 15.25}, {6.9,12.8}, {2.1, 11.1}, {9.5, 14.9}, 
             {13.2, 11.9}, {10.3, 12.3}, {6.8, 9.5}, {3.3, 7.7}, {0.6, 5.1}, 
             {5.3, 2.4}, {8.45, 4.7}, {11.5,9.6}, {13.8, 7.3}, {12.9, 3.1}, 
             {11, 1.1}};

PlanarGraphPlot[data2D, ConvexHull[data2D]]

输出：

替代文字

于 2010-11-13T22:11:10.007 回答