如何确定一组矩形是否包含有重叠区域的两个矩形？

Question

struct Rect
{
double left, right, top, bottom;
};

std::vector<Rect> vec;

现在我们有N(N > 1000)个矩形，有一个高效的算法来确定它们中是否有任意两个重叠吗？

更新： 所有这些矩形都平行于坐标系。

- user2609926

---

@Maple：我不同意。这里的问题是要避免O(n^2)的行为。 - Cheers and hth. - Alf

你还有其他的见解可以分享吗？它们的大小是否相同或相似，还是差异巨大且随机？它们倾向于聚集在附近还是均匀地分散在你的坐标空间中？边缘坐标是否都是某个特定数字的倍数？它们是否有任何排列成行或列的倾向？如果没有，那很好 - 只是想知道这些问题可能会带来优化机会。 - Tony Delroy

当然。由于一开始问题有点模糊，我假设它并不特别关注最大效率，而是关注碰撞检测的基础知识。 - Maple

这篇论文似乎是你想要的，但我现在没有时间提供比链接更多的内容，所以我不认为这算是一个答案。 - Mike Precup

@Mike Precup，你的链接看起来很有帮助，非常感谢~ - user2609926

Answer 1

您可以用两条线段表示矩形：从(x1,y1)到(x1,y2)的开放线段和从(x2,y1)到(x2,y2)的闭合线段，其中x1 < x2且y1 < y2。

首先，我们可以按其x坐标在O(nlogn)时间内对所有这些线段进行排序。

其次，我们逐个处理每个线段，如果遇到开放线段，则将该线段中的区间(y1, y2)添加到区间树中，如果遇到关闭线段，则将其从树中移除。对于我们添加的每个线段，我们可以查询树以查看有多少线段与此线段重叠，这也是与此矩形的开放线段重叠的矩形数量。每次查询的时间复杂度为O(logn)。

因此，我们将拥有一个O(nlogn)算法。

- Pham Trung

---

非常感谢您提供详细的算法。点赞！ - user2609926

Answer 2

一个简单的方法是将坐标空间划分为一个 D * D 的网格，然后创建一个二维数组，其中包含重叠每个区域的矩形向量：

std::vector<Rect*> grid[D][D];

例如，您可能有一个20x20的网格，其中1000多个矩形中的一些内部位于单个网格坐标中，而其他矩形则重叠在许多网格元素上。尽管如此，通过对D进行一些试错调整，您可能可以获得每个vector中平均5-50个矩形（取决于它们在大小上的差异），然后可以对它们进行暴力搜索以查找重叠。

如果您想进一步优化此过程：

• 如果任何矩形完全覆盖网格区域，则可以在向量中保留单个nullptr，从而绕过每个矩形的比较
• 您可以尝试为不同大小的矩形使用单独的网格-完全覆盖网格坐标的较大矩形将知道如果vector不是empty()，则存在重叠

值得注意的是，如果您有一组矩形，并且要重复添加新矩形以测试每个矩形与任何先前矩形的重叠情况，则值得投入的排序、合并/简化重叠矩形、索引等工作量大不相同。想要确切知道哪些矩形重叠是另一个复杂性（暴力步骤可以满足这个问题）。我理解这个问题的意思是，有一组未排序的矩形需要进行一次真/假的是否存在重叠的答案。

- Tony Delroy

Answer 3

一个想法是维护一个水平使用范围的集合和一个垂直使用范围的集合。添加一个新矩形，将其与水平方向上重叠的矩形称为H，垂直方向上重叠的矩形称为V。如果集合H和V的交集非空，则这些矩形是它在二维中重叠的矩形。

在第一个二维重叠之前，我认为这将以O(n log n)的速度执行，前提是范围得到适当的表示，某种排序结构。

- Cheers and hth. - Alf

Answer 4

我感到有必要提到RH Güting和W Schilling的论文《矩形交问题的实用分治算法》，发表于1987年的《信息科学》杂志。Pham Trung在他的回答中采用的策略（平面扫描）更可能对于集合问题具有更快的实现，而分治则与适用于“在线查询”的数据结构密切相关，例如，“对于给定的轴对齐矩形集，与此相交的子集是什么？”

- greybeard

---

您的信息很重要，能否提供一个下载链接，以获取《矩形交问题的实用分治算法》（Information Sciences 42 (1987)）？ - user2609926

@user2609926 只需在您喜爱的搜索引擎中输入标题即可。 - Raymond Chen

我在原始帖子的评论中提供的论文指出了一些例子，其中Güting和Schilling提出的算法返回了不正确的结果。我不知道它是否已经更新，所以如果您使用它，请务必进行彻底的测试。 - Mike Precup