查找到统一网格上的点云中最近点的距离

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

假设有A，B和C是相当大的相对于d，给人的也许500x500x500一个网格，将有大约1万点。

另外假设，如果到最近点的距离超出距离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

基本上是：把点水桶和做一个径向向外搜索，直到找到每个网格点一个百分点。这是解决问题的好方法，还是有更好/更快的方法？优选用于平行化的解决方案。

来源

2010-04-29 erik

我认为@Mark强调了一个非常重要的观点：这是一次性计算还是云计算会在每个步骤之间进行并发生相同的计算？一个易于更新的结构将是至关重要的，如果多个计算将被链接，因此它将形成解决方案... – 2010-04-29 11:10:23

对不起，我错过了指出。点云确实会移动，计算必须在每个时间步重新进行。 – erik 2010-04-29 14:12:13

其实，我觉得我有一个更好的方式去，作为网格点的数量比采样点的数量大得多。让|网格| = N，| Samples | = M，那么最近的邻居搜索算法将会像O（N lg M）那样，因为你需要查找所有N个网格点，并且每个查找是（最好的情况下）O（lg M）。

取而代之，循环遍历采样点。为每个网格点存储迄今为止找到的最接近的采样点。对于每个采样点，只需检查样本距离D内的所有网格点，以查看当前样本是否比任何之前处理的样本更近。

运行时间是O（N +（D/d）^ 3 M），当D/d很小时应该更好。

即使D/d较大，如果可以制定一个临界策略，您仍然可以确定。例如，如果我们正在检查样本中的网格点距离5，并且该网格点已被标记为距前一个样本的距离为1，则不需要检查网格点之外的所有网格点因为前一个样本保证比我们正在处理的当前样本更近。你所要做的就是（我不认为这很容易，但应该是可行的），定义“超越”意味着什么，并找出如何遍历网格，以避免在这些网格点之外的区域做任何工作。

来源

2010-05-01 17:27:43

看看octrees。它们是一种数据结构，通常用于有效分割三维空间，从而提高在空间上彼此接近的对象的查找效率。

来源

2010-04-29 06:26:57 Amber

一种方法，这可能会或可能不适合你的应用程序，是重铸自己的思想，并确定每个网格“点”是其中将您的空间分成细胞立方体的中心。然后你有一个这样的单元格的3D数组，并将点存储在单元格中 - 选择最合适的数据结构。要使用你自己的话，首先把分数。

我猜你可能正在运行的某种大规模仿真的，我建议的方法是不是在这些应用中不寻常的。在每个时间步骤（如果我猜对了），你必须重新计算从细胞到最近点的距离，并将点从细胞移动到细胞。这将很容易并行。

编辑：谷歌搜索周围颗粒与颗粒和粒子粒子颗粒目可以扔了一些想法给你。

来源

2010-04-29 06:27:59

也搜索“3d voronoi图”。 – starblue 2010-04-29 07:27:46

@starblue由于OP在格上工作，我不明白Voronoi图的相关性。 – 2010-04-29 14:22:16

OP具有格点和采样点。你可以用样本点创建一个Voronoi图并用格点查询它。但3D Voronoi图很昂贵，不确定这是最好的策略。 – 2010-04-29 15:55:01

您可以在样本点建立nearest neighbor search structure（维基百科），然后问它为每个网格点。 Wikipedia页面上提到了一些算法。也许八叉树，kd树或R树是合适的。

来源

2010-04-29 06:51:30

关于Keith Randall方法的注释，在起点周围扩展壳或立方体：
可以按各种顺序展开。下面是一些蟒蛇风格的伪代码：

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

“停止从早期扩张”是在一维精细（左邦克，邦克右）; 但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）的角落

也有fwiw，和erik的数字，每个样本点平均有500^3/1M〜2^7〜5^3个空容量。所以我起初以为1M周围样本点为的5x5x5立方体会覆盖整个网格的大部分。不是这样，约1/e的格点保持空 - 泊松分布。

来源

2010-05-14 10:49:41 denis

查找到统一网格上的点云中最近点的距离

回答

相关问题