computational-geometry - 查找重叠的凸多边形

Question

我有一组边数适中的凸多边形（比如从 4 到 30）。有十分之几的多边形，比如 100 到 1000。它们中的大多数是孤立的，但少数形成了 2 到 10 个在它们之间重叠的小组。

我需要有效地识别这些重叠多边形组。

有经典算法吗？（我正在考虑一种扫描线方法，但也许有更好的方法？）在检测之前将多边形包围在盒子中是否有益？

下面，一个有代表性的案例。

Answer 1

在二维中用于此类问题的一种传统方法是构建四叉树，它将您的二维空间分层划分为连续更小的桶，直到每个桶中有少量对象。

您的重叠检测将遍历四叉树，直到您找到与对象相交的存储桶或存储桶集，然后您将对较小的对象集执行重叠检测。

这里有一个关于构建和使用它们进行碰撞检测的简单介绍：快速提示：使用四叉树检测 2D 空间中的可能碰撞

一种更简单但计算成本更高的方法是做一些有点像使用 z 缓冲区来确定一个多边形是否遮挡另一个多边形的方法：

• 为每个多边形分配一个唯一编号（它的深度）
• 将每个多边形光栅化到缓冲区，检查每次写入缓冲区以查看是否已遮挡已设置的像素。如果是这样，深度标识您已遮挡的多边形以及您写入已遮挡它的多边形的新值。