首页 文章

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

提问于
浏览 次
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）

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

performance algorithm sorting search

4 回答

  • 5

    你不想"sort"立方区域，你想要一个空间索引结构，如k-d tree，octree或otherwise . K-d树是一个特别好的选择，因为你已经在讨论具有轴对齐表面的形状（子长方体），这些表面不重叠 . 在计算机游戏中查找方法可能是值得的，因为它们经常使用数据结构来检测对齐框与现有对齐框的任意交叉非常快 . （例如Bullet物理引擎 . ）

    上面提到的大多数空间索引技术都是 O(log n) 用于执行点查询 . 有很多K-d树的实现already in existence .

    回复于
  • 0

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

    Linear search:

    您的每个区域都由最小角 (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 spatial subdivision:

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

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

    因此，在此层次结构的每个级别，您将空间细分为八个子多维数据集 .

    如果其中一个子立方体中没有任何搜索区域，它就会变成一个空叶子节点（也就是说，你可以说“不，这里什么都没有，沿着移动”） .

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

    如果子多维数据集中仍包含相对大量的搜索区域，请继续该子多维数据集上的细分过程 .

    如果您愿意花时间计算八叉树，这将产生一个搜索算法，其性能大约为O（logN）O（M） .

    回复于
  • -1

    我将从实现一个简单的Box碰撞方法开始 . 然后你就可以针对你的每个区域运行它 .

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

    回复于
  • 4

    您应该从列出here的算法中选择一种 . 如果您的数据允许，您可以尝试integer sorting算法，它们具有较低的理论迭代次数，然后是基于比较的算法 .

    回复于

相关问题