1

我有许多长方体，它们的位置和大小用 minimum 和 maximum和x坐标给出（所以它们平行于主轴）。yz

例如，我可能有以下 3 个长方体：

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支持范围查询，但这似乎以相反的方式工作（在长方体中找到一个点，而不是在包含一个点的长方体中找到一个点）。

  • 稍微复杂一点的是，维度的数量可能大于 3（可能高达 20）；即我可能正在寻找“超长方体”而不是长方体。）

4

2 回答 2

2

你即将进入“二进制空间分区”和“碰撞检测”的领域；本质上，这些想法基本上是将长方体存储在树型结构中，将它们占据的空间划分为整齐的小盒子。每个长方体占据哪个“空间部分”的决定是在插入树结构的过程中做出的。

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

有效划分 3D 空间，以及包含在该空间中的对象是计算机科学的很大一部分；主要用于电脑游戏的开发。一些算法考虑了时间因素，即对象在分区空间之间移动。

于 2009-07-21T12:50:36.757 回答
1

加速此查询的一种直接方法是构建以下统一的网格数据结构（通常称为 bin）作为预处理步骤：n x n x n在场景上放置一个（3d）网格，并为网格的每个单元存储一个指向所有长方体的指针与该单元格相交。现在，对于查询点，您可以直接计算它在统一网格中的哪个单元格中，然后您只需检查与该单元格关联的长方体，而不是所有长方体。

根据空间的大小以及长方体大小的变化程度，这种方法可能不是很有效，因为您可能很难选择一个好的n分辨率来充分加速并且不需要大量的细胞。为了克服这个问题，您可能想尝试寻找更自适应的空间分区方法，例如kd-trees （维基百科上的 kd-trees），它们基本上是用轴对齐平面划分空间的二叉树：请参阅此处的示例红色平面将盒子分成两部分，然后将绿色分成更小的部分，然后是蓝色......

kd树

使用 kd-tree 的查询将首先向下遍历查询点所在的 kd-tree 的叶子，然后检查该单元中的本地长方体。其他空间分区数据结构选项可以在这里找到。

另一种选择是使用包围体层次结构，它将对象组合在包围体中，然后将包围体组合成更大的包围体，依此类推......以获得包围体的层次结构。这些更适合场景，并且可以更轻松地处理对象移动的场景，但我认为对于您的设置空间分区可以很好地工作......无论如何，有关更多详细信息，请参阅本书章节。

于 2009-07-21T13:38:42.113 回答