搜索和排序立方体区域的算法

Question

搜索和排序立方体区域的算法

3

我正在尝试找出一种算法，用于对立方体区域进行排序（例如由（0,0,0）定义到（1,1,1）），并在给定坐标时尽可能快地返回该区域。数据结构包含区域：（0,0,0）到（100,100,100），（1000,1000,1000）到（1010,1010,1010）和（-50，-50，-50）到（60，-60，60）。因此，在搜索10，10，10时会返回区域1，在搜索（1001,1001,1001）时会返回区域2等。排序、添加、删除时间可能很长。我需要快速的搜索时间；我们可以假设只有整数将被搜索，并且不使用填充每个单元格以引用区域的3D网格解决方案是不可接受的，因为我没有3TB的内存可以用于这个方案:P。我们还可以假设区域不会重叠，如果这能帮助任何人。如果有人有想法，请告诉我。谢谢各位。- Olivier-编辑：仍然太慢了，使用一个结构来保存minX，minY，minZ，maxX，maxY，maxZ以表示一个区域，并将所有这些区域放置在一个列表中，按顺序逐个搜索（通过检查坐标是否大于minX但小于maxX，以及对于每个坐标相同），这仍然太慢O（N）。目前，我正在探索按x，y，z排序的n元树的思路，但我不知道是否是一个好方法。

- user2475269

在分割空间时要特别小心。如果你不幸的话，一个子立方体可能属于许多分区。你要么不平等地分割它（每个分区的大小都不同），要么将子立方体添加到它所属的所有分区中（这是更好的解决方案，我认为）。 - Petr Janeček

4个回答

4

您不想"排序"立方体区域，而是需要一种空间索引结构，例如k-d树，八叉树或其他。 K-d树是一个特别好的选择，因为您已经在讨论具有轴对齐表面且不重叠的形状（子立方体）。值得一提的是，在计算机游戏中查找广相方法时可能会很有用，因为它们经常使用数据结构来非常快速地检测具有现有轴对齐框的任意交集。（例如Bullet物理引擎。）

大多数上述提到的空间索引技术对于执行点查询而言是O(log n)。已经有许多K-d树的实现存在。

- Kaganar

0

我会先实现一个简单的盒子碰撞方法。然后你只需要对每个区域运行它。

我的问题是，如果搜索跨越多个区域怎么办？

- 75inchpianist

其实我会有不止一个区域。 - user2475269

-1

你应该从这里列出的算法中选择一个。如果你的数据允许，你可以尝试使用整数排序算法，它们具有比基于比较的算法更低的理论迭代次数。

- David Jashi

1

这个回答如何确切地回答了这个问题？应该排序什么，你如何使用排序后的数据呢？ - Petr Janeček

他请求帮助选择最快的排序算法。 - David Jashi

1

实际上，从问题的其余上下文来看，我认为他本意是写“搜索立方体区域”的算法，而问题中的“排序”是一个打字错误。 - Petr Janeček

从他的评论上下文来看，很明显他对他目前和拟议的排序算法不满意。 - David Jashi

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Bob Cross · Accepted Answer

这是一个简单的边界框问题。

线性搜索：

每个区域都由最小角 (x_min, y_min, z_min) 和最大角 (x_max, y_max, z_max) 定义。如果你正在搜索特定的目标点 (target_x, target_y, target_z)，你可以遍历所有的区域。如果你找到一个区域：

x_min <= target_x <= x_max
y_min <= target_y <= y_max
z_min <= target_z <= z_max

如果你正在搜索的区域是由 {(x_min, y_min, z_min), (x_max, y_max, z_max)} 定义的，则该算法将运行于 O(N)。如果你收集了与目标匹配的区域列表，那么你也可以处理重叠的区域。

八叉树空间细分：

如果你有大量的区域，你可以创建一个预计算的层次结构，也称为八叉树：

八叉树是一种树形数据结构，其中每个内部节点恰好有八个子节点。八叉树最常用于通过递归地将三维空间细分成八个八分之一来对其进行分区。八叉树是四叉树的三维模拟。名称由 oct + tree 组成，但请注意，通常只写为“八叉树”一个“t”。八叉树经常用于 3D 图形和 3D 游戏引擎。

因此，在该层次结构的每个级别上，您将空间划分为八个子立方体。

如果一个子立方体内没有任何搜索区域，则其成为空叶节点（也就是说，“没找到，继续往下走”）。

如果一个子立方体中有足够少的搜索区域（即一些数量为M，其中M << N），则可以对该目标数字应用上述线性搜索算法。

如果一个子立方体仍然有相对较多的搜索区域，请继续在该子立方体上进行细分过程。

如果你愿意花时间计算八叉树，这将产生一个性能为O（logN）+ O（M）的搜索算法。