扩展凸包以减少边数

Question

扩展凸包以减少边数

geometrycomputational-geometry

3

我们有一组标记点，它们的凸包不重叠。凸包之间有一些空白区域。

给定一个未标记的点且不在我们的数据中，我们想要近似确定它位于哪个凸包内。

为了加快计算速度，我们希望减少凸包上的边数（从而略微扩展凸包，但不要太多）。

有哪些算法可以使用？

更新：理想情况下，我们希望在不与给定附近的多边形相交的约束条件下进行扩展。（这一约束的动机是我有几个不相交的凸包，想要减少它们所有的边数，同时仍保持它们不相交。但请将其作为插入说明处理，因为我不想进行联合修改。我很乐意在保持其他凸包不变的情况下修改一个凸包。我很高兴将这个简单的情况改进为迭代式联合修改。）

- Real Geek N

你的意思是说，你的凸包不会严格意义上的是“船壳”，因为它们比必要的大吗？从数学上讲，对于一组点来说，只有一个可能的凸包。 - Daniel Möller

1

@Daniel 是的，没错。我想要减少多边形的边数（有时候变成三角形或正方形），同时放弃“紧密度”的要求。好处是可以更轻松、更快速地测试成员资格。感谢您考虑这个问题。我还更新了问题，加入了一个额外的限制条件，以便我可以对多个不相交的凸壳进行操作。 - Real Geek N

为什么问题陈述中使用了“处理一个额外的点”这样的术语？这是因为那个未标记的点事先不知道，后来才到达吗？还是因为你下意识地采用了一种增量处理方法（逐点处理），并试图强制我们采用这种方法？这是一个重要的区别，可能会对算法选择产生关键影响。所有数据点是否都提前可用？还是它们一个接一个地到达？ - AnT stands with Russia

@AnT 对于那些标签已知的数据点是提前可用的。其他未标记的数据点相对较少，它们的标记（无论我们如何做）都不会具有权威性。它们是一个接一个到达还是同时到达并不重要。 - Real Geek N

4个回答

2

“凸多边形上的点”测试并不昂贵，因为可以通过二分法（用一条直线将多边形分成两部分，递归执行直到只剩下一个三角形）在Lg(N)次比较中完成。N是多边形的边数。实际上，一个27（或130）边形的成本将是一个三角形的两倍（三倍）。

如果有很多壳体，对每个壳体进行详尽的比较是浪费的。有更好的方法，如使用单调子区域，可以将搜索时间降低到O(Log(M))查询时间，总共有M个边，在预处理后进行。

- user1196549

谢谢你的见解。我终于可以点赞了，所以我们开始吧！ - Real Geek N

2

看起来你的最终目标并不是凸包，而是解决点定位问题（https://en.wikipedia.org/wiki/Point_location）。你似乎决定通过简单地迭代检查你的点是否在一些凸包内来解决这个问题。虽然我理解凸包的来源（它们实际上代表一组点），但这并不是直接在算法中使用它们的原因。点定位问题可以通过许多更有效的算法（如基于梯形分解的搜索树）来解决，这些算法对你的凸包中边的数量不太敏感。

- AnT stands with Russia

谢谢你的回答。我现在很忙，但在漫长的周末里会仔细理解它。 - Real Geek N

嗯...具体应用是我们有一些从未指定的不相交凸多边形中采样的点。每个点都有多边形标签，但多边形本身未指定。从这些数据中，我们想要为另一组未标记的点分配多边形标签。近似答案也可以。----我看不出如何将我的用例映射到“点位置”问题。不过还是谢谢你的回答。 - Real Geek N

在这种情况下，它听起来更像是聚类分析问题，而不是点定位问题。然而，您的原始帖子让人感觉好像点是一个接一个地到达的（即并非所有点都事先知道）。您最新评论中的描述不再提及此细节，看起来好像所有点都是事先知道的。这是一个关键的细节。您的所有点是否都是事先知道的？ - AnT stands with Russia

预先知道标记点。未标记的点一个接一个地到来，我需要根据原始标记数据集尽力对它们进行标记。 - Real Geek N

1

我不会感到惊讶，如果在你的粗略阶段包含检查中少处理一条边所节省的处理量被膨胀的凸壳的误报率所抵消。实际上，你甚至可能会为自己创造更多工作 - 每个通过粗略阶段检查的点都必须与真正的凸壳进行检查。

与其试图减少 O(n) 包含检查中的 n，我更倾向于直接使用某些摊销的 O(1) 方法进行粗略检查：

1. 第一遍 - 与轴对齐的边界框（AABB）进行检查。这可以快速拒绝绝大多数在多边形外部的点。 2. 第二遍 - 将 AABB 划分为网格，其中每个网格四方均处于三种状态之一：完全在凸壳外、与凸壳边相交或完全在凸壳内。如果你的点位于“内”或“外”网格中，则可以在此停止。 3. 第三遍 - 任何位于与多边形相交的网格四方中的点都将按照正常方式检查凸壳。

网格的状态可以提前计算出来：

将每个网格的四边形初始设为凸包外部。
使用链接于this answer中的算法来跟踪凸包在网格上的边缘，并设置所有相交的四边形。
现在，该网格包含凸包的轮廓，因此可以使用简单的floodfill或scanline方法来查找并设置凸包内部的所有四边形。

网格的分辨率可以变化以在内存成本（每个四边形2比特）和误报率（低分辨率网格会导致更多的O(n)传统凸包检查）之间进行权衡。

- ryanm

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Joseph O'Rourke · Accepted Answer

也许这值得一试。找到凸包A'和凸包B'，分别是A联合x和B联合x的凸包。选择其中增加凸包面积最少的那个。在下面的示例中，A'是获胜者。

根据评论添加：一种方法是通过“最小外接k-gons”：

Mictchell等人：2006年“最小周长包含k-gon”（CiteSeer链接）
Aggarwal等人：1985年“最小面积包围多边形”（CiteSeer链接）
O'Rourke等人：1986年“查找最小外接三角形的最优算法”，Algorithmica（ACM链接）

然而，这些算法非常复杂，不太可能有所帮助。