algorithm - 检测直角棱镜的重叠

Question

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

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

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

Answer 1

适用于大型数据集的出色算法

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

有一些用于 R-Trees 的 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 中数据库，可以使用很少的代码行在文件或内存中创建(有 many java implementations )。创建名为 prisms 的表，其列为 id、min_x、min_y、min_z 、max_x、max_y、max_z。索引每一行。

插入是 O(1)，检查交集遵循 Magnus Skog's approach , 给定 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)