查找到統一網格上的點雲中最近點的距離

我有一個大小爲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

查找到統一網格上的點雲中最近點的距離

回答

相關問題