多边形分解 - 去除凹点以形成凸多边形

StackOverflow https://stackoverflow.com/questions/4174209

题

我想解构以蓝色所示的以下多边形，从而从多边形去除引起凹的所有点。

alt text

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

  • 从多边形中取出每个点
  • 测试点，看看它是否属于集合的其余部分产生的多边形
  • 如果true删除点
  • 如果false保持重点

在大多数情况下，这起作用，但是在以前的情况下，（2,3）和（2,4）的点不会删除。在这两种情况下，这两个点都将被删除，但另一个将不取决于数组的传递顺序。

我想知道的是：

  1. 是否有一些方法可以测试我要处理的多边形是否碰巧有一种情况（即连续3点失败点？）
    或者
  2. 是否只是创建凸多边形的更有效的方法？

谢谢你。

有帮助吗？

解决方案

我想也许您正在寻找 凸壳?

想到的第一种算法是QuickHull。最初，以最左侧和最右点为l和r。他们必须在船体上。

在船体上构建第一个猜测，是两个向外的脸，一个从L到R，一个从R到L。因此，您的多边形量为零。

将所有剩余的点分为LR前面和RL前面的点。

从那时起，虽然任何脸部都有任何要点：

  • 从脸上找到最远的点
  • 删除此边缘并用两个边替换它，一个从原始起点到最远的点，一个从最远的点到原始终点
  • 在旧面前的所有要点中保留对现在内部的任何引用

最后，您将拥有凸船体。

其他提示

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

这是一个精心研究的问题，其中有许多书籍和在线算法。一种“扫角”的方法特别普遍，例如。

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

您要寻找的是“凸船体”发现。看 在维基百科 对于此问题的算法。这 “礼品包装” 算法易于实现。当您找到船体时，只需删除所有不属于船体的点即可。

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

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]]

输出：

alt text

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top