我有许多长方体，其位置和大小由最小和最大 x、y 和 z 坐标给出（因此它们是平行的）到主轴）。
例如，我可能有以下 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）； 即我可能正在寻找“超长方体”而不是长方体。）
I have a number of cuboids whose positions and sizes are given with minimum and maximum x, y and z co-ordinates (so they are parallel to the main axes).
e.g. I might have the following 3 cuboids:
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
If I then give a point (e.g. (25.3,10.2,90.65)), is there a way to quickly determine which cuboid(s) I'm in?
-
Obviously I could just iterate over all the cuboids, but there are potentially millions of them, and I need this to go faster than simple iteration (something O(log n) or better would be great).
-
This sounds to me like a "fuzzy matching" type problem, and I notice that Apache Lucene supports range queries, but this seems to work the opposite way round (finding a point in a cuboid rather than a cuboid containing a point).
-
To slightly complicate matters further, the number of dimensions might be larger than 3 (it could be up 20); i.e. I might be looking for "hypercuboids" rather than cuboids.)
发布评论
评论（2）
加速此查询的一种直接方法是构建以下统一网格数据结构（通常称为 bin）作为预处理步骤：将
nxnx n（3d 形式）网格放在上面您的场景以及网格的每个单元都存储一个指向与该单元相交的所有长方体的指针。 现在，对于查询点，您可以直接计算它位于统一网格中的哪个单元格中，然后您只需检查与该单元格关联的长方体，而不是所有长方体。根据空间有多大以及长方体大小的变化程度，此方法可能不是很有效，因为您可能很难选择一个好的
n分辨率来足够加速并且不需要大量的单元。 为了克服这个问题，您可能需要尝试寻找更具适应性的方法来划分空间，例如kd-trees （维基百科上的 kd-trees），基本上是用轴对齐平面划分空间的二叉树：请参阅此处的示例，其中红色平面将框分为两部分，然后是较小部分的绿色，然后是蓝色...使用 kd-tree 的查询将首先向下遍历到查询点所在的 kd-tree 的叶子，然后检查该单元中的本地长方体。 其他空间分区数据结构选项可以在此处找到。
另一种选择是使用包围体层次结构，它将对象分组到包围体中，然后将包围体分组为更大的包围体，依此类推......以获得包围体的层次结构。 这些可以更好地适应场景，并且可以更轻松地处理对象移动的场景，但我认为对于您的设置空间分区可以很好地工作......无论如何，有关更多详细信息，请参阅本书章节。
One straightforward way to accelerate this query is by constructing the following uniform grid data structure (often called bins) as a preprocessing step: Put an
n x n x n(in 3d) grid over your scene and for every cell of the grid store a pointer to all the cuboids intersecting that cell. Now, for a query point you can compute directly in which cell it is in the uniform grid, and then you have to check only the cuboids associated to that cell, and not all the cuboids.Depending how big the space is and how varying the cuboid sizes are this method might not be very efficient because you it might be difficult to chose a good
nresolution to accelerate enough and not need an enormous amount of cells. To overcome this you might want to try to look into more adaptive ways to partition the space, such as kd-trees (kd-trees at wikipedia), which are basically binary trees partitioning the space with axis aligned planes: See for an example here where the red plane divides the box into two parts and then the green in smaller parts, then the blue...A query using kd-tree would first traverse down to the leaf of the kd-tree where the the query point is located and then check with the local cuboids in that cell. Other space partitioning data structure options can be found here.
Another option would be to use bounding volume hierarchies, which group objects together in bounding volumes, and then group bounding volumes into larger bounding volumes and so on... to get a hierarchy of bounding volumes. These adapt better to a scene and can easier handle scenes where the objects move, but I would think for your setting space partitioning could work well... Anyways, for more details see this book chapter.
您即将进入“二元空间分区”和“碰撞检测”的领域； 本质上，这些想法基本上是将长方体存储到树型结构中，将它们占据的空间划分成整齐的小盒子。 每个长方体占据哪个“空间部分”的决定是在插入树结构期间做出的。
在八叉树上进行谷歌搜索。
有效地划分 3D 空间，以及该空间中包含的对象是计算机科学的很大一部分； 主要用于电脑游戏的开发。 一些算法考虑了时间因素，即对象在分区空间之间移动。
you verging into the territory of "Binary Space Partitioning" and "Collision Detection"; essentially the ideas are basically storing the cuboids into a tree type structure, which divides the space they occupy into neat little boxes. The decision about which "part of space" each cuboid occupies is made during the insertion into the tree strucutre.
Do a google search on Octrees.
Efficently dividing 3D space, and the objects contained within that space is quite a big portion of computer science; mostly used in the development of computer games. Some of the algorithms take into consideration a time factor, i.e. that the objects move between partition spaces.