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。我们也可以假设区域不会重叠，如果这对任何人都有帮助

如果有人有想法，我会很高兴听到

多谢你们

-奥利维尔-

编辑：使用包含 minX、minY、minZ、maxX、maxY、maxZ 的结构来表示一个区域，并将所有这些区域放在一个列表中，您可以在其中一一搜索（通过检查坐标是否大于 minX 但小于 maxX , 每个坐标都一样 ) 仍然太慢 O(N)

目前，我正在探索使用 n 叉树进行排序的想法，按 x 排序，然后按 y，然后按 z，但我不知道它是否会是一个好的

4

4 回答 4

4

您不想对立方区域进行“排序”，您需要一个空间索引结构，例如kd 树、八叉树或其他。Kd 树是一个特别好的选择，因为您已经在讨论具有不重叠的轴对齐表面的形状（子长方体）。在计算机游戏中寻找广泛阶段的方法可能是值得的，因为它们经常使用数据结构，检测对齐框与现有对齐框的任意交叉点非常快。（例如子弹物理引擎。）

上面提到的大多数空间索引技术都是O(log n)用于执行点查询。已经存在许多 Kd 树的实现。

于 2013-06-11T16:10:26.330 回答
4

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

线性搜索：

您的每个区域都由最小角(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)}。

如果 N 是您的边界区域数，则此算法将以 O(N) 运行。如果您收集与目标匹配的区域列表，您还可以处理重叠区域。

八叉树空间细分：

如果您有大量区域，则可以创建一个预先计算的层次结构，也称为octree：

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

因此，在此层次结构的每一层，您都将空间细分为八个子立方体。

如果其中一个子立方体内部没有任何搜索区域，则它成为一个空的叶节点（即，您可以说“不，这里什么都没有，继续前进”）。

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

如果一个子立方体内仍有较大数量的搜索区域，则继续对该子立方体的细分过程。

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

于 2013-06-11T16:03:06.403 回答
0

我将从实现一个简单的 Box 碰撞方法开始。然后你只需对你的每个区域运行这个。

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

于 2013-06-11T16:03:22.593 回答
-1

您应该从此处列出的一种算法中进行选择。如果您的数据允许，您可以尝试 整数排序算法，它具有较低的理论迭代次数，然后是基于比较的算法。

于 2013-06-11T16:03:11.367 回答