java - 如何检查一组矩形的孔洞和相互作用？

Question

我正在寻找一种方法来检查矩形的集合 (Java TreeSet) - 由一个“可比较的”Java 类实现，使用 google guavas Range for x 和 y range - 交叉点和孔。我知道可以选择使用 kd-trees，但我不知道如何构建这样的 kd-tree(对于矩形，它应该是 4d，不是吗？)以及如何解决问题(交叉点，洞)。

排序使 x 轴优先于 y 轴。

编辑:(尝试重述问题):用例是创建任意表(由 2 或 3 个矩形 block “标题”、“前列”、“数据”组成) .我必须保证每个 block 中没有交叉点和孔(即由无效的 html 或其他表格数据源提供)(除此之外， block 必须放在一起)。目前(只是有一个想法)我试图在一个二维数组中保存哪些位置(x，y)被占用。最后，所有位置必须恰好被占用一次。

Answer 1

解决此类问题的方法有很多种，每种方法各有利弊。以下是其中一些:

矩形对交集 + 面积和

查看每一对矩形 - 如果两个矩形相交，则存在重叠。将矩形区域相加并检查总和是否与 Canvas 区域匹配 - 如果区域不匹配，则存在间隙。

绘画

这就是您提到的方法:创建一个具有 Canvas 尺寸的二维数组。然后，遍历矩形并将它们“绘制”到数组中。

此方法的一个优化是坐标压缩。假设您有矩形 [(10,20), (15,25)] 和 [(7,3), (15, 25)]。您可以查看不同的 x 坐标 (7, 10, 15) 并将它们重新映射到 (0, 1, 2)，以及不同的 y 坐标 (3, 20, 25) 并将它们重新映射到 (0, 1, 2).然后，剩下矩形 [(1, 1), (2, 2)] 和 [(0,0), (2,2)]，所以你只需要一个 3x3 数组来绘制，而不是 26x26数组。

扫描线算法

从左到右扫描一条线，停在“有趣”的点，并跟踪哪些区域被占用。

二维范围树

一种可以在矩形范围内高效执行查询的数据结构。

选择哪一个？

这取决于你拥有的矩形的数量，它们在该区域的分布方式，你的算法必须有多快，你愿意承担多少复杂性等等。我提到的前两个算法要简单得多而不是后两者，所以我建议从那里开始。

更多信息

如果您想详细了解这些算法，请尝试在线搜索“矩形联合”。最有效的解决方案是扫描线算法。

这里有一些关于扫描线算法的引用资料:

1. What is an Efficient algorithm to find Area of Overlapping Rectangles
2. http://compgeom.cs.uiuc.edu/~jeffe/open/klee.html
3. J. L. Bentley，Klee 矩形问题的算法。未发表的笔记，卡内基梅隆大学计算机科学系，1977 年

引用文献 3. 通常作为 rectangle union 的线扫描算法的原始来源给出，但我不得不承认我实际上并没有在网上找到这篇论文，也许是因为它是“未发表的”......