检测矩形棱柱的重叠

Question

给定一个 3D 坐标系和具有非负起点和非负尺寸的直角棱柱（例如，从 (0, 2, 5) 开始，尺寸为 (9, 20, 5))：如何最好地检查另一个直角棱镜是否与坐标系中已有的棱镜之一相交？最终，目标是对存在的所有棱镜执行此检查，能够测试一个棱镜应该足以完成此任务。

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

我的项目是用java编写的，但是任何数学公式、伪代码或描述都绰绰有余。

Answer 1

适用于大型数据集的良好算法方法

将棱镜存储在 R-Tree 中。对于直角同轴棱镜，搜索和插入的顺序应为log(n)。

有一些用于 R-Tree 的 Python 包。使用 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)

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

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结果。如果您不希望这样，并且希望重叠空间不仅仅是一个点、一条线段或一个矩形表面，而是一个棱柱，则将 <= 替换为 < ; .

Answer 4

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

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