logo标签列表

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

geometrycomputational-geometryconvex-optimizationconvex-polygon
3
我想拆分以下所示的蓝色多边形，从多边形中删除所有导致凹度的点。
目前，我一直在尝试做以下事情：
- 将每个点从多边形中取出 - 测试该点是否落在剩余集合创建的多边形内 - 如果为真，则删除该点 - 如果为假，则保留该点
这在大多数情况下都有效，但在先前的情况下，(2,3)和(2,4)处的点都不会被移除。在数组传递的顺序不同的情况下，其中一个点将被删除，而另一个点将保留。
我想知道的是：
1. 是否有一种方法可以测试我正在处理的多边形是否具有这些情况之一（例如：连续3个失败点）？ 2. 或者是否有更有效的创建凸多边形的方法？
谢谢。
4个回答
6

我认为你可能在寻找凸包？

首先想到的算法是QuickHull。最初，取最左和最右的点l和r。它们必须在凸壳上。

构建一个第一次猜测的凸壳，它有两个外向面，一个从l到r，一个从r到l。所以你有一个体积为零的多边形。

将所有剩余点分成在lr前面和在rl前面的点。

从此开始，只要任何面前面有任何点：

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

最后，您将拥有凸包。

1
0

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

例如在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

0
你所需要的是寻找“凸包”的算法。可以在维基百科上查找相关算法。其中“礼品包装”算法比较容易实现。当你找到凸包后，只需移除不属于凸包的所有点即可。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接