检测矩形棱镜的重叠

Question

给定一个三维坐标系和矩形棱镜,具有非负起点和非负尺寸(例如从起点开始(0, 2, 5)并具有大小(9, 20, 5)):我怎样才能最好地检查另一个矩形棱镜是否与其中一个棱镜相交坐标系？最终,目标是对所有存在的棱镜执行此检查,能够测试一个应该足以完成此任务.

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

我的项目是在java中,但任何数学公式,伪代码或描述都绰绰有余.

Answer 1

适用于大型数据集的优秀算法方法

将棱镜存放在R树中.对于矩形同轴棱镜,搜索和插入应按顺序排列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数据库中,数据库可以使用非常少的代码行在文件或内存中创建(有许多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