Querverweise in Listen mit leicht unterschiedlichen Koordinaten

Question

ich etwas sehr ähnlich zu der Frage tun, wollen hier gefragt:

Comparing two lists of coordinates in python and using coordinate values to assign values

Das heißt, ich habe zwei Listen von Koordinaten (sagen wir, x und y) , und ich möchte eine Menge aus Liste 2 extrahieren, wenn die (x, y) -Koordinaten mit den (x, y) -Koordinaten in Liste 1 übereinstimmen.

Nun sind die Antworten in der oben verlinkten Frage gut dafür geeignet solange die Koordinaten übereinstimmen genau

Allerdings möchte ich eventuell geringfügige Abweichungen berücksichtigen. Angenommen, es gibt eine kleine Abweichung dx oder dy in beiden Koordinaten. Und angenommen, ich sage: "Für dx<R halte ich diese Koordinaten für gleich." Wie würde ich das in den Code einbringen - unter Berücksichtigung der Lösung, die bereits oben im Link angegeben wurde (oder natürlich eine andere kreative Lösung).

Hinweis: Für die schnelle und schmutzige Lösung (eine doppelte For-Schleife) ist dies relativ einfach. Es ist schwieriger mit der O (n) -Lösung, die in der akzeptierten Antwort gegeben ist, wonach ich suche.

Answer 1

Dies ist definitiv ein Computeralgorithmus. Sie können es wie folgt neu formulieren: Bei einer Menge von Punkten in einer Ebene finden Sie für alle Punkte P die Menge aller Punkte in einer Entfernung <= R (in Bezug auf die Chebyshev distance, sofern die Bedingungen dx <= R und dy <= R erfüllt sein müssen).

Die Lösung in quadratischer Zeit ist einfach: Sie müssen nur prüfen, ob ein Punkt in einem gegebenen Quadrat liegt. Trotzdem glaube ich nicht, dass die auf Hash-Tabelle basierende Methode (die in Mittelwert linearer Zeit läuft) einfach angepasst werden kann. Es ist jedoch eine Lösung in O(n log n) denkbar (obwohl sie durch die Anzahl der Punkte in jedem Quadrat dominiert sein kann): Ich nehme an, R ist sehr klein, so dass es im Durchschnitt nur eine konstante Anzahl von Punkten in einem gegebenen Quadrat gibt).

Dazu können Sie eine sweep-line algorithm anpassen. Zuerst können Sie Koordinaten "diskretisieren", indem Sie nur x und y entsprechend einem gegebenen Punkt in der Eingabe berücksichtigen (dies wird verwendet, um Anfragen auf Koordinaten statt Punkte, während eine Komplexität nur basierend auf der Anzahl der Punkte in der Eingabe).

Danach können Sie Ihre Punkte z. nach ihrer x Koordinate. In der Tat wäre es besser, auch die "Ereignisse" unter x+r und x-r hinzuzufügen (Sie können auch ein Ereignis auf x setzen, um jeden Punkt zu betrachten, anstatt in einer bestimmten Datenstruktur zu suchen) für jeden Punkt, der dem linken entspricht und zur rechten Ecke des Platzes. Durchstreichen Sie diese Ereignisse und fügen Sie Punkte hinzu, wenn eine linke Ecke in einem binären Suchbaum angetroffen wird, sortiert nach y Koordinate (*), und entfernen Sie sie, wenn Sie ein Event in der rechten Ecke lesen.

Somit enthält Ihr Baum zu einem bestimmten Zeitpunkt genau die Punkte (x, y) mit |x-xcurrent| <= R in Bezug auf das aktuelle Ereignis. Wenn Sie einen Punkt erhalten, müssen Sie nur alle Punkte in der Menge (x, y) überprüfen |y-ycurrent| <= R in Bezug auf das aktuelle Ereignis.

(*) In der Tat könnte es möglich sein, Datenstrukturen wie Fenwick trees zu verwenden, die einfacher "von Grund auf" zu codieren sind und niedrigere Konstanten als komplexe Datenstrukturen wie binäre Suchbäume ergeben.