3

我有一个大小为 AxBxC 的 3D 网格，网格中的点之间的距离 d 相等。给定多个点，给定以下假设，找到每个网格点到最近点的距离的最佳方法是什么（每个网格点都应该包含到点云中最近点的距离）？

假设 A、B 和 C 相对于 d 相当大，给出一个大概 500x500x500 的网格，大约有 100 万个点。

还假设如果到最近点的距离超过 D 的距离，我们不关心最近点的距离，它可以安全地设置为某个较大的数字（D ​​可能是 d 的 2 到 10 倍）

由于将有大量的网格点和要搜索的点，因此简单详尽：

for each grid point:
   for each point:
     if distance between points < minDistance:
       minDistance = distance between points

不是一个好的选择。

我正在考虑按照以下方式做一些事情：

create a container of size A*B*C where each element holds a container of points
for each point:
  define indexX = round((point position x - grid min position x)/d)
  // same for y and z
  add the point to the correct index of the container

for each grid point:
  search the container of that grid point and find the closest point
  if no points in container and D > 0.5d:
    search the 26 container indices nearest to the grid point for a closest point
  .. continue with next layer until a point is found or the distance to that layer 
        is greater than D

基本上：将点放入桶中并向外进行径向搜索，直到为每个网格点找到一个点。这是解决问题的好方法，还是有更好/更快的方法？首选有利于并行化的解决方案。

4

5 回答 5

2

看看八叉树。它们是一种数据结构，通常用于有效地划分 3d 空间，以提高查找在空间上彼此靠近的对象的效率。

于 2010-04-29T06:26:57.440 回答
2

您可以在您的样本点上构建一个最近邻搜索结构（维基百科），然后为您的每个网格点询问它。维基百科页面上提到了一堆算法。也许 octtrees、kd-trees 或 R-trees 是合适的。

于 2010-04-29T06:51:30.260 回答
2

实际上，我认为我有更好的方法，因为网格点的数量远远大于样本点的数量。让 |网格| = N, |样本| = M，那么最近邻搜索算法将类似于 O(N lg M)，因为您需要查找所有 N 个网格点，并且每次查找（最佳情况）为 O(lg M)。

相反，循环采样点。为每个网格点存储到目前为止找到的最近的采样点。对于每个样本点，只需检查样本距离 D 内的所有网格点，以查看当前样本是否比任何先前处理的样本更接近。

运行时间为 O(N + (D/d)^3 M)，当 D/d 较小时应该会更好。

即使 D/d 较大，如果你能制定一个截止策略，你可能仍然可以。例如，如果我们正在检查距样本距离为 5 的网格点，并且该网格点已被标记为距前一个样本的距离 1，则不需要检查“超出”该网格点的所有网格点因为之前的样本保证比我们正在处理的当前样本更接近。您所要做的就是（我认为这并不容易，但应该可行）定义“超出”的含义并弄清楚如何遍历网格以避免对“超出”此类网格点的区域进行任何工作.

于 2010-05-01T17:27:43.907 回答
1

一种可能适合或不适合您的应用程序的方法是重新定义您的想法并将每个网格“点”定义为将空间划分为单元格的立方体的中心。然后，您将拥有此类单元格的 3D 数组并将点存储在单元格中——选择最合适的数据结构。用你自己的话来说，首先把分数放在桶里。

我猜您可能正在运行某种大规模模拟，而我建议的方法在此类应用程序中并不罕见。在每个时间步（如果我猜对了），您必须重新计算从单元格到最近点的距离，并将点从单元格移动到单元格。这将很容易并行化。

编辑：谷歌搜索粒子粒子和粒子粒子粒子网格可能会给你一些想法。

于 2010-04-29T06:27:59.450 回答
1

关于 Keith Randall 方法的注释，围绕起点展开壳或立方体：
可以按各种顺序展开。这是一些python风格的伪代码：

S = set of 1m startpoints
near = grid 500x500x500 -> nearest s in S
    initially s for s in S, else 0
for r in 1 .. D:
    for s in S:
        nnew = 0 
        for p in shell of radius r around s:
            if near[p] == 0:
                near[p] = s
                nnew += 1
        if nnew == 0:
            remove s from S  # bonk, stop expanding from s

“从 s 早期停止扩展”在 1d 中很好（bonk left，bonk right）；但是 2d / 3d 贝壳是不规则的。
一次完成整个立方体更容易/更快：

near = grid 500x500x500 -> { dist, nearest s in S }
    initially { 0, s } for s in self, else { infinity, 0 }
for s in S:
    for p in approximatecube of radius D around s:
        if |p - s| < near[p].dist:  # is s nearer ?
            near[p] = { |p - s|, s }

这里的“approximatecube”可能是一个完整的 DxDxD 立方体，或者你可以像（这里是 2d）那样剪掉角落

0 1 2 3 4 
1 1 2 3 4 
2 2 3 4 4
3 3 4 4
4 4 4

同样，根据 erik 的数据，每个采样点平均有 500^3/1M ~ 2^7 ~ 5^3 空。所以我起初认为 1M 样本点周围的 5x5x5 立方体将覆盖整个网格的大部分。不是这样，大约 1/e 的网格点保持空白——泊松分布。

于 2010-05-14T10:49:41.087 回答