检测矩形棱柱的重叠

Question

给定一个三维坐标系和长方体棱柱，其具有非负起点和非负大小（例如，起点为（0,2,5），大小为（9,20,5）），如何最好地检查另一个长方体棱柱是否与已在坐标系统中的其中一个相交？最终目标是对所有存在的棱柱执行此检查，能够测试一个棱柱就足以完成此任务。

信息：起点和大小是非负长整数的3元组。我正在寻找一种优雅且速度适中的解决方案。

我的项目使用Java，但任何数学公式、伪代码或描述都足够了。

- Samuel

---

棱镜可以旋转吗？或者我们可以假设所有面都与坐标轴正交/平行吗？ - Jeroen

Answer 1

大数据集的优秀算法方法

将棱柱存储在R-Tree中。对于矩形轴向棱柱，搜索和插入应按顺序进行log(n)。

有一些Python包可用于R-Trees。使用Rtree 0.6.0，您的代码将非常简单：

>>> from rtree import Rtree
>>> idx = Rtree()
>>> minx, miny, maxx, maxy = (0.0, 0.0, 1.0, 1.0)
>>> idx.add(0, (minx, miny, maxx, maxy))
>>> list(idx.intersection((1.0, 1.0, 2.0, 2.0)))
[0L]
>>> list(idx.intersection((1.0000001, 1.0000001, 2.0, 2.0)))
[]

实用且快速的方法

将数据存储在一个sqlite数据库中，可以使用非常少的代码行在文件或内存中创建它（有许多Java实现）。创建一个名为prisms的表，其列应为id、min_x、min_y、min_z、max_x、max_y和max_z。索引每一行。

插入的时间复杂度为O(1)，检查交集遵循Magnus Skog的方法，给定new_min_x, new_min_y, new_min_z, new_max_x, new_max_y, new_max_z：

SELECT COUNT(*) FROM prisms
   WHERE (new_min_x BETWEEN min_x and max_x OR new_max_x BETWEEN min_x and max_x)
   AND   (new_min_y BETWEEN min_y and max_y OR new_max_y BETWEEN min_y and max_y)
   AND   (new_min_z BETWEEN min_z and max_z OR new_max_z BETWEEN min_z and max_z)

- Adam Matan

---

@Samuel：是否使用R树取决于您的数据集有多大（以及它的速度或是否会发生变化）。 - ypercubeᵀᴹ

还要注意的是，R树被用于空间数据库中，因此这也是一个选择（将对象存储在空间数据库中，让数据库回答您的查询）。 - ypercubeᵀᴹ

@ypercube 确实，但我认为像PostgreSQL+PostGIS这样的东西对于这个问题来说是一个非常困难的选择。 - Adam Matan

@Adam：要么是@Magnus的条件，要么是我的条件比你（最后三行）使用“OR”和“BETWEEN”的复杂条件更简单。 - ypercubeᵀᴹ

@ypercube：我认为Magnus Skog的公式是不正确的：考虑A=[(0,0,0), (1,1,1)]，B=[(1.5, 10, 10), (2.5, 20, 20)]。这些棱柱不相交。 - Adam Matan

Answer 2

假设你有两个棱镜A和B。如果B与A相交，那么它就不完全在右侧、左侧、上方、下方等方向上，这是否定的情况。

if not (B.x > A.x+A.dx or B.x+B.dx < A.x or
        B.y > A.y+A.dy or B.y+B.dy < A.y or
        B.z > A.z+A.dz or B.z+B.dz < A.z)
        // B intersects A

- ralphtheninja

---

检查每个现有的棱镜可能在大数据集中不太有效率。 - Adam Matan

@Adam：我明白你的意思 :) 当然这是一个权衡。随着效率需求的增加，算法的复杂性也会增加。 - ralphtheninja

我在我的评论中解释了我的决定，我只是想知道从stackoverflow的角度来看，我应该将这个作为答案，因为我会使用它，还是将Adam的答案作为未来查看此问题的用户的答案？ - Samuel

@Magnus Skog并不是要挑剔，权衡是正确的。 - Adam Matan

@Adam：我并没有把它当作挑剔，没问题 :) - ralphtheninja

@Samuel：就我个人而言，我会选择解决我的具体问题的答案。如果其他答案同样正确或提供更多信息，它们很可能会得到许多赞，这些信息仍然可以供其他读者自由使用 :) - ralphtheninja

Answer 3

起点为(0, 2, 5)，大小为(9, 20, 5)的棱镜在(9, 22, 10)结束。

要检查重叠的棱镜（A和B），请使用它们的起点和终点。这两个棱镜必须在所有维度上重叠。

要检查X维度上的重叠，请使用以下内容：

If (A.startX <= B.endX) and (B.startX <= A.endX) 

因此：

If 
      (A.startX <= B.endX) and (B.startX <= A.endX) 
  and (A.startY <= B.endY) and (B.startY <= A.endY) 
  and (A.startZ <= B.endZ) and (B.startZ <= A.endZ) 
Then
    (A and B overlap)

上述检查将在两个棱镜仅有一个公共点时返回True。如果您不想要这样，而是希望重叠空间不仅仅是一个点、线段或矩形表面，而是一个棱柱，则将“<=”替换为“<”。

- ypercubeᵀᴹ

---

感谢您的贡献！ - Samuel

Answer 4

与检查线段上的分段方式相同。如果B的起点或终点在A的起点和终点之间，则它们重叠。

唯一的区别是它们必须在所有三个维度上重叠。

- SJuan76

---

如果B的起始或结束时间在A的起始和结束时间之间，则它们重叠。这是正确的，但反过来不一定成立！如果它们重叠，则B的起始或结束时间不必在A的起始和结束时间之间。 - ypercubeᵀᴹ