我正在寻找一种方法来检查矩形的集合（Java TreeSet） - 由使用谷歌番石榴范围的“可比”Java 类实现 x 和 y 范围 - 交叉点和孔。我知道一个选项可能是使用 kd-trees，但我不知道如何构建这样一个 kd-tree（对于矩形，它应该是 4d，不是吗？）以及如何解决问题（交叉点，孔）。
排序将 x 轴优先于 y 轴。
编辑：（尝试重述问题）：用例是创建任意表（由 2 或 3 个矩形块“标题”、“前列”、“数据”组成）。我必须保证每个块中没有交叉点和漏洞（即由无效的 html 或其他表格数据源提供）（除此之外，块必须组合在一起）。目前（刚刚有了一个想法）我尝试保存一个二维数组，其中位置（x，y）被占用。最后，所有位置必须恰好被占用一次。
有很多方法可以解决这类问题，每种方法都有不同的优缺点。这里是其中的一些：
矩形对交点 + 面积总和
查看每一对矩形 - 如果两个矩形相交，则存在重叠。将矩形区域相加并检查总和是否与画布区域匹配 - 如果区域不匹配，则存在间隙。
绘画
这是您提到的方法：创建一个具有画布尺寸的二维数组。然后，遍历矩形并将它们“绘制”到数组中。
这种方法的一种优化是坐标压缩。假设您有矩形 [(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大批。
扫描线算法
从左到右扫过一条线，停在“有趣”的点，并跟踪哪些区域被占用。
二维范围树
一种可以在矩形范围内有效执行查询的数据结构。
选择哪一个？
这取决于您拥有的矩形的数量，它们在该区域中的分布方式，您的算法必须有多快，您愿意承担多少复杂性等等。我提到的前两种算法比后者简单得多二，所以我建议从那里开始。
更多信息
如果您想了解有关这些算法的更多信息，请尝试在线搜索“矩形联合”。最有效的解决方案是扫描线算法。
以下是有关扫描线算法的一些参考资料：
参考文献3.通常是作为矩形并集的线扫算法的原始来源给出的，但我不得不承认我实际上并没有在网上找到该论文，可能是因为它是“未发表”...