Der Titel ist das meiste Problem. Ich habe eine Reihe von Kreisen, die jeweils durch ein Zentrum C und Radius r gegeben sind. Der Abstand zwischen zwei Kreisen ist der euklidische Abstand zwischen ihren Zentren abzüglich ihrer beiden Radien. Für Kreise a und b,
d_ab = | C_a - C_b | - r_a - r_b.
Beachten Sie, dass dies negativ sein kann, wenn sich die Kreise überlappen.
Was ist dann die schnellste Datenstruktur für die Suche nach dem nächsten Nachbarn (Mindestabstand) eines gegebenen Kreises in der Menge?
Das Hinzufügen und Löschen von Kreisen mit "find nearest" -Abfragen, die in beliebiger Reihenfolge verschachtelt sind, muss unterstützt werden. Über die geometrische Verteilung der Menge ist im Voraus nichts bekannt.
Dies ist das Herz eines Systems, in dem eine typische Anzahl von Kreisen 50.000 und zehntausende von Abfragen, Einfügungen und Löschungen benötigt werden, idealerweise mit Benutzerinteraktionsgeschwindigkeit (eine Sekunde oder weniger) an einem High-End Tablet-Gerät.
Der Punkt nächste Nachbar wurde zu Tode untersucht, aber diese Version mit Kreisen erscheint etwas schwieriger.
Ich habe kd-Bäume, Quad-Bäume, r-Bäume und einige Variationen davon angeschaut. Sowohl Ratschläge, welche davon am besten geeignet sind, als auch neue Vorschläge wären eine großartige Hilfe.
Danke an @David Eisenstadt für die Idee einer 3D-Suchstruktur. Dies ist Teil der besten Antwort, obwohl seine seltsame Metrik nicht benötigt wird.
Der Schlüssel besteht darin, genau zu untersuchen, wie die nächste Nachbarsuche funktioniert. Ich werde das für Vierer zeigen. Kd-Bäume mit k = 3 sind ähnlich. Hier ist Pseudocode:
%Vor% Wenn dies geschehen ist, enthält nearest_info den nächsten Nachbarn und seine Entfernung.
Der Schlüssel ist if S contains any point P where dist(P,T) < nearest_info.distance . In einem 3D-Raum von (x,y,r) triple, die Kreise beschreiben, haben wir
Hier ist P ein beliebiger Punkt in einem Oktanten eines Octree-Quaders. Wie berücksichtigt man alle Punkte im Quader? Beachten Sie, dass alle Komponenten von T für eine bestimmte Suche effektiv fixiert sind. Daher ist es klarer, wenn wir das Ziel als konstanten Punkt (a, b, c) :
Wo wir c = T.r vollständig weggelassen haben, weil es nach Abschluss des Algorithmus aus der Mindestdistanz subtrahiert werden kann. Mit anderen Worten beeinflusst der Radius des Ziels das Ergebnis nicht.
Damit ist es ziemlich einfach zu sehen, dass die P , die wir benötigen, um den Mindestabstand zum Quader zu erhalten, euklidisch am nächsten zum Ziel in Bezug auf x und y und mit dem max dargestellten Radius ist. Dies ist sehr einfach und schnell zu berechnen: ein 2D-Punkt-Rechteck-Abstand und ein 1% max -Betrieb.
Im Nachhinein ist das alles offensichtlich, aber es hat eine Weile gedauert, um es von der richtigen Seite zu sehen. Danke für die Ideen.
Cover-Bäume sind eine weitere Möglichkeit für eine Proximity-Struktur. Sie unterstützen keine Löschungen (?), Aber Sie können im Hintergrund weich löschen und neu aufbauen, damit sich der Müll nicht anhäuft, was eine nützliche Technik für die anderen Strukturen sein kann.
Es gibt eine Reduzierung von dem 2D-Kreisproblem zu dem 3D-Punktproblem mit einer funkigen Metrik, die so läuft. (Die Näherungsstrukturen, die Sie genannt haben, sollten anpassungsfähig sein.) Ordnen Sie einen Kreis um (x, y) mit Radius r dem Punkt (x, y, r) zu. Definieren Sie die Länge eines Vektors (dx, dy, dz) als sqrt (dx ** 2 + dy ** 2) + abs (dz). Dies induziert eine Metrik. Um den Kreis zu finden, der einem Mittelpunkt am nächsten liegt (x, y) (der Radius des Abfragekreises ist nicht relevant), führen Sie eine Näherungssuche bei (x, y, R) durch, wobei R größer oder gleich dem maximalen Radius von ist ein Kreis (es kann möglich sein, Ihre Näherungsstruktur zu ändern, so dass es nicht notwendig ist, R zu verfolgen).
Aus meiner Erfahrung mit der Implementierung von kd-Bäumen und Voronoi-Diagrammen in Punkten wird es wesentlich einfacher sein, kd-Bäume von Grund auf zu implementieren. Selbst wenn Sie die robusten geometrischen Primitive einer anderen Person wiederverwenden (und tun Sie dies, um Ihre geistige Gesundheit zu bewahren, wenn Sie diesen Weg gehen), brauchen die entarteten Kantenfälle von Voronoi / Punkt-Ort Zeit, um richtig zu kommen.
Ich schlage die folgende Heuristik vor, die einen KD-Baum oder etwas anderes verwendet, das O (log N) nächsten Nachbarn erlaubt. Anstatt einen einzelnen Punkt und einen Radius zu verwenden, um einen Kreis darzustellen. Verwenden Sie k äquidistante Punkte auf einem Kreis selbst, plus die Mitte des Kreises, andernfalls könnten Probleme mit einem kleinen Kreis innerhalb eines großen Kreises auftreten . Es ist die gleiche Idee wie die Verwendung eines regelmäßigen Polygons von k Knoten, um einen Kreis darzustellen. Es ist dann möglich, einen Scheitelpunkt zu nehmen und seinen nächsten Nachbarn zu finden (wobei die Scheitelpunkte auf demselben Kreis ignoriert werden), um eine Näherung dafür zu finden, welcher Kreis auf der Grundlage des nächsten regelmäßigen Polygons am nächsten ist.
Die Aufführungen sind wie folgt:
Erzeuge den KD-Baum: O (kN log kN)
Entfernen / Hinzufügen eines Kreises zum KD-Baum: O (k log kN) -Add oder entfernen Sie alle k Punkte eines Kreises innerhalb der KD-Struktur
Abfrage des nächsten Kreises (Kreis): O (k log kN) Dies geschieht, indem zuerst alle k Punkte des Kreises (O (k log kN)) entfernt werden, da es nicht besonders nützlich ist, herauszufinden, dass der nächste Nachbar eines Kreises nicht überraschend ist, der Kreis selbst. Finde dann für jeden k Punkt im Kreis den nächsten Nachbarn (O (k log kN)). Sobald die nächsten Nachbarn gefunden sind, ist der nächstgelegene (innerhalb eines Fehlers) derjenige mit dem kleinsten Abstand (nach Berechnung der wahren Entfernung basierend auf Punkt und Radius) (O (1)).
Ich würde vorschlagen, entweder k = log (N) zu verwenden, wenn Sie es vorziehen, schnell zu sein, oder k = sqrt (N), wenn Sie es vorziehen, genau zu sein.
Es ist auch möglich, dass ich keinen speziellen Fall in Betracht gezogen habe, der Probleme verursacht, also pass auf sie auf.
Wenn es eine Garantie gibt, dass Kreise keinen großen Radius haben, ist zumindest der maximale Radius (R) wesentlich kleiner als der Bereich, in dem Kreise positioniert sind, als ich denke, dass er mit Standardraumpartitionierung und Nearest Neighbor-Suche abgedeckt werden kann .
Bei der Suche nach einem Kreis in einer Menge, die einen minimalen Abstand zum gegebenen Kreis hat, ist der Radius des gegebenen Kreises egal (Abstandsdefinition). Daher ist es gleich, wenn nur der Mittelpunkt mit der Menge der Kreise verglichen wird .
Damit ist es genug, die Kreise in der Raumpartitionsstruktur nur durch deren Zentren zu speichern (Punktmenge). Das Hinzufügen und Löschen von Kreisen erfolgt auf standardmäßige Weise für Punkte. Das Finden des nächsten Kreises zu einem gegebenen Punkt kann in zwei Schritten erfolgen:
Es ist möglich, die Suche zu optimieren, indem Sie diese beiden Schritte kombinieren. Im ersten Schritt werden einige der interessanten Partitionen bereits besucht. Durch das Speichern der besuchten Partitionen und den Kreis mit minimaler Entfernung in diesen Partitionen kann die Suche im zweiten Schritt reduziert werden.
Tags und Links algorithm language-agnostic computational-geometry