代码之家 › 专栏 › 技术社区 › Simon Nickerson

如何确定一个点位于哪个长方体中而不重复它们?

space-partitioning fuzzy-search geometry language-agnostic search

Simon Nickerson · 技术社区 · 16 年前

x y z 坐标(因此它们与主轴平行)。

10.5 <= x <= 39.4,  90.73 <= y <= 110.2, 90.23 <= z <= 95.87
20.1 <= x <= 30.05,  9.4  <= y <=  37.6,  0.1  <= z <= 91.2
10.2 <= x <= 10.3,   0.1  <= y <=  99.8, 23.7  <= z <= 24.9

(25.3,10.2,90.65)

显然,我可以迭代所有的长方体,但可能有数百万个,我需要这个比简单迭代更快(O(log n)或更好的东西会更好)。
Apache Lucene range queries 但这似乎是反过来的(在长方体中找到一个点,而不是包含一个点的长方体)。
使事情进一步复杂化的是,维度的数目可能大于3(可以增加20);也就是说,我可能在寻找“超立方体”而不是长方体。

2 回复 | 直到 14 年前

Community CDub 8 年前

加速此查询的一个简单方法是构造以下内容 均匀网格 作为预处理步骤的数据结构(通常称为bin):将 n x n x n (在3D中)网格覆盖场景,对于网格中的每个单元格,存储一个指向与该单元格相交的所有长方体的指针。现在,对于一个查询点,您可以直接计算它在统一网格中的哪个单元格,然后您只需要检查与该单元格关联的长方体,而不是所有的长方体。

根据空间大小和长方体大小的不同,这种方法可能不是很有效,因为你可能很难选择一种好的方法。 n 足够加速的分辨率,不需要大量的电池。为了克服这一点,您可能需要尝试寻找更适合的方法来划分空间,例如 KD树 (kd-trees at wikipedia) 它基本上是二叉树,用轴对齐的平面来划分空间:请看这里的一个例子,其中红色平面将盒子分成两部分,然后绿色部分分成更小的部分,然后蓝色部分……

使用kd树的查询首先遍历到查询点所在的kd树的叶,然后检查该单元中的本地长方体。 其他空间分区数据结构 可以找到选项 here .

另一个选择是使用 层次包围盒 ,将对象分组到边界体积中,然后将边界体积分组到较大的边界体积中,依此类推…以获取边界体积的层次。它们更适合场景,也更容易处理对象移动的场景,但我认为对于您的设置,空间分区可以很好地工作…无论如何,有关更多详细信息,请参见 this book chapter .

Phill 16 年前

你进入了“二元空间划分”和“碰撞检测”的领域;本质上,这些想法基本上是将长方体存储到树型结构中,将它们所占的空间划分为整洁的小盒子。在插入树结构的过程中,决定每个长方体所占的“部分空间”。

在八叉树上进行谷歌搜索。

有效地划分三维空间,其中包含的物体是计算机科学的很大一部分;主要用于计算机游戏的开发。有些算法考虑了时间因素,即对象在分区空间之间移动。