Finde nächsten Nachbarn mit Morton Code

Ich habe eine decode/encode Methode zur Umwandlung von 2d Punkte in ihre jeweiligen morton code implementiert.Finde nächsten Nachbarn mit Morton Code

Was ich gesucht habe ist, die nächsten Nachbarn zu finden (unter min_distance) So zum Beispiel so etwas wie diese:

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)

Ist das möglich?

Quelle

2017-05-15 greedsin

Sie können die folgenden mit min_distance tun, zum Beispiel 120: Verwenden Sie Ihre Abfrage Punkt qp=(201,305) und die minimalen und maximalen Punkte schaffen durch Subtraktion/Addition der Entfernung: min=(81, 185) und max=(321,425). Jetzt erstellen Sie die Morton Codes für diese beiden Punkte.

Alle Punkte, die sich in einer Entfernung von 120 von (210,305) befinden, haben einen Mortoncode mcWithin120 mit mortonCode(min) <= mcWithin120 <= mortonCode(max). Wenn Sie eine nach Morton-Code geordnete Liste von Punkten haben, sollte dies den Suchbereich ein wenig eingrenzen.

Beachten Sie, dass der Bereich falsch positive Ergebnisse enthält! Nicht alle Punkte mit Morton-Code zwischen min und max befinden sich in der angegebenen Entfernung 120, also musst du alle Punkte in der Reihe überprüfen, ob sie "tatsächlich" innerhalb der richtigen Entfernung sind.

Wenn Sie sich für räumliche Suche interessieren, werfen Sie einen Blick auf die Es ist ein räumlicher Index, ähnlich wie Quadtree, der Morton Reihenfolge verwendet, um Baumstruktur und Suchvorgänge zu optimieren.

Quelle

2017-05-16 07:15:07 TilmannZ

Ja, Sie haben Recht, ich werde upvote, weil ich nicht über den PH-Baum wusste, und ich denke, das wird die bessere Lösung sein! – greedsin

Schauen Sie sich auch diese [Antwort] (http://stackoverflow.com/questions/4260002/benefits-of-nearest-neigbor-search-with-morton-order?rq=1), vor allem die Kommentare, die Referenz die PDFs auf kNN suchen mit morton order. – TilmannZ

Finde nächsten Nachbarn mit Morton Code

Antwort

Verwandte Themen