モートンコードで最近傍を見つける

Question

2d点をそれぞれmorton codeに変換するためにdecode/encodeメソッドを実装しました。

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) 

はこれが可能である：私は探しています何

だから、このような例を何かのため （min_distance下）最近傍を見つけることですか？

Answer 1

あなたはたとえば120のために、min_distanceを使用して、次の操作を行うことができます あなたのクエリ点qp=(201,305)を使用し、距離の追加/ substractingで最小と最大のポイントを作成します。min=(81, 185)とmax=(321,425)を。 ここで、これら2つのポイントのモルトンコードを作成します。

（210,305）の120の範囲内にあるすべての点は、とmortonCode(min) <= mcWithin120 <= mortonCode(max)のモルモンコードを持ちます。 モルモンコードで注文されたポイントのリストがある場合、これは検索エリアをかなり絞り込む必要があります。

この範囲には誤検出が含まれることに注意してください。 minとmaxの間にあるmortonコードのポイントはすべて、指定された距離120にあるわけではありませんので、範囲内のすべてのポイントを '実際に'正しい距離内にあるかどうかチェックする必要があります。

空間検索に興味がある場合は、PH-Treeを参照してください。四分木に似た空間インデックスです。これは、モルモンの順序を使用してツリー構造と検索を最適化します。