尋找最近的鄰居與莫頓代碼

我已經實施decode/encode方法將2d點轉化爲各自的morton code。尋找最近的鄰居與莫頓代碼

我在尋找什麼是找到最近的鄰居（下min_distance）因此，例如，這樣的事情：

points=[(200,300),(500,150),(100,50)] 
mortonCodes = {} 
for p in points: 
    mortonCodes[encode(p)] = p 

nearest = findNearestNeighbor(mortonCodes, (201,305)) 
print(nearest) # ---> should return (200,300)

這可能嗎？

來源

2017-05-15 greedsin

您可以執行以下操作使用min_distance，例如120：使用您的查詢點qp=(201,305)並通過減去建立最低和最高點/添加的距離：min=(81, 185)和max=(321,425)。現在，您爲這兩點創建morton代碼。

距離（210,305）的120的距離內的所有積分將有一個morton代碼mcWithin120和mortonCode(min) <= mcWithin120 <= mortonCode(max)。如果你有一個由morton代碼定購的點的列表，這應該縮小搜索區域的範圍。

請注意，範圍將包含誤報！並非所有morton代碼在最小值和最大值之間的點都在給定距離120內，因此您必須檢查範圍內的所有點，無論它們「實際上」是否在正確的距離內。

如果您對空間搜索感興趣，請查看PH-Tree這是一個類似於四叉樹的空間索引，它使用morton命令來優化樹結構和搜索。

來源

2017-05-16 07:15:07 TilmannZ

是的，你是對的，我會upvote，因爲我不知道PH-Tree，我認爲這將是更好的解決方案！ – greedsin

也有看看這個[回覆]（http://stackoverflow.com/questions/4260002/benefits-of-nearest-neighbor-search-with-morton-order?rq=1），尤其是參考的評論kNN搜索的PDF與morton命令。 – TilmannZ

尋找最近的鄰居與莫頓代碼

回答

相關問題