Was ist der schnellste Weg, um den kürzesten kartesischen Abstand zwischen zwei Polygone zu finden

https://stackoverflow.com/questions/84034

01-07-2019
|

Frage

Ich habe 1 roter Polygon sagen und 50 zufällig platziert blau Polygonen - sie geografisch liegen 2D-Raum . Was ist der schnellste / schnellste algorithmus die die kürzesten Abstand zwischen einem roten Polygon und seinem nächsten blauen Polygon zu finden?

Beachten Sie, dass es nicht ein einfacher Fall ist, die Punkte zu nehmen, die die Eckpunkte des Polygons als Wert für Abstand zu testen bilden, da sie nicht unbedingt die nächsten Punkte sein.

Also am Ende -. Die Antwort sollte den nächsten blauen Polygon auf den Singular roten zurückgeben

Das ist schwieriger als es klingt!

Lösung

Ich bezweifle, gibt es bessere Lösung als die Entfernung zwischen dem roten Berechnung und jedem blauen und Sortieren dieser durch Länge.

Sortierung In Bezug auf in der Regel QuickSort schwer ist, in der Leistung zu schlagen (eine eine optimierte, dass abschneidet Rekursion, wenn Größe unter 7 Artikel geht und schaltet auf so etwas wie InsertionSort, vielleicht ShellSort).

So denke ich, die Frage ist, wie schnell die Entfernung zwischen zwei Polygone zu berechnen, schließlich müssen Sie diese Berechnung 50 mal machen.

Der folgende Ansatz wird auch für die 3D-Arbeit, aber es ist wahrscheinlich nicht der schnellste:

Mindest Polygon Entfernung im 2D-Raum

Die Frage ist, sind Sie bereit, Genauigkeit für Geschwindigkeit zu handeln? Z.B. Sie können alle Polygone in Bounding Box packen, wo die Seiten der Schachteln zu den Koordinatensystemachsen parallel sind. 3D-Spiele verwenden, ziemlich oft diesen Ansatz. Dafür müssen Sie die Maximal- und Minimalwerte für jede Koordinate (x, y, z) finden, den virtuellen Begrenzungsrahmen zu konstruieren. Die Berechnung der Abstände dieser Begrenzungskästen ist dann eine ziemlich triviale Aufgabe.

Hier ist ein Beispiel Bild von fortgeschritteneren Begrenzungsbox, die auf das Koordinatensystem nicht parallel sind, Achsen:

Oriented Bounding Boxes - OBB

Dies macht jedoch die Entfernungsberechnung weniger trivial. Es wird für die Kollisionserkennung verwendet, da sie, dass die Distanz nicht wissen müssen, Sie wissen müssen, wenn eine Kante eines Begrenzungsrahmens in einem anderen Begrenzungsrahmen liegt.

Die folgende Abbildung zeigt eine Achse ausgerichtet Begrenzungsbox:

Achsen Aligned Bounding Box - AABB

OOBs sind genauer, AABBs sind schneller. Vielleicht möchten Sie diesen Artikel lesen:

Erweiterte Collision Detection Techniques

Dies wird immer vorausgesetzt, dass Sie bereit sind, für die Geschwindigkeit Präzision zu handeln. Wenn Präzision wichtiger als Geschwindigkeit ist, können Sie eine erweiterte Technik benötigen.

Andere Tipps

Sie könnten in der Lage, das Problem zu reduzieren, und dann auf einer kleinen Gruppe eine intensive Suche.

Prozess jedes Polygon zuerst von der Suche nach:

Zentrum von Polygon
Maximalradius Polygon (das heißt, Punkt auf der Kante / Oberfläche / Scheitelpunkt des Polygons weitesten vom Zentrum definiert)

Jetzt können Sie, sagen wir, die 10.05 am nächsten Polygone zu dem roten (Finden Sie den Abstand von Mitte zu Mitte, den Radius subtrahieren, sortieren Sie die Liste und nehmen Sie die Top-5) sammeln und führen Sie dann eine viel ausführlichere Routine.

Für Polygonformen mit einer angemessenen Anzahl von Grenzpunkten wie in einer GIS oder Spiele-Anwendung kann es schneller einfacher sein, eine Reihe von Tests zu tun.

Für jede Ecke im roten Polygon um den Abstand zu jedem Eckpunkt in dem blauen Polygone berechnen und den nächsten finden (Tipp, vergleicht Abstand ^ 2, so müssen Sie nicht über die sqrt ()) Finden Sie die nächsten, dann überprüfen Sie den Scheitelpunkt auf jeder Seite der gefundenen roten und blauen Ecke, die Liniensegmente zu entscheiden, am nächsten sind und dann die nächste Annäherung zwischen zwei Liniensegmenten finden.

Siehe http://local.wasp.uwa.edu. au / ~ pbourke / Geometrie / lineline3d / (es ist einfach zu einfach für den 2D-Fall)

Diese Screening-Technik soll die Anzahl der Entfernungsberechnungen Sie im durchschnittlichen Fall ausführen müssen, reduzieren, ohne die Genauigkeit des Ergebnisses zu gefährden. Es funktioniert auf konvexen und konkaven Polygonen.

Hier finden Sie die den Mindestabstand zwischen jedem Paar von Eckpunkten, so dass man einen roten Scheitel ist und man ist ein blau. Nennen Sie es r . Der Abstand zwischen den Polygonen ist höchstens r . Konstrukt einen neuen Bereichs von dem roten Polygons, wobei jedes Liniensegment bewegt wird, nach außen von r und ist mit seinen Nachbarn durch einen Bogen mit einem Radius verbunden r ist am Scheitelpunkt zentriert ist. Finden den Abstand von jedem Scheitelpunkt innerhalb dieser Region zu jedem Liniensegment der anderen Farbe, die diese Region überschneidet.

Natürlich können Sie eine ungefähre Methode hinzufügen, wie beispielsweise Begrenzungskästen, welche der blauen Polygonen schnell feststellen kann möglicherweise nicht mit dem roten Bereich schneiden.

Vielleicht ist die Frechet Entfernung, was Sie suchen?

die Berechnung der Fréchet Abstand zwischen zwei polygonalen Kurven
Berechnung der Fréchet Abstand zwischen einfachen Polygonen

Ich weiß, Sie sagte: „Die kürzeste Entfernung“, aber sie bedeutet wirklich die optimale Lösung oder eine „gut / sehr gut“ Lösung für Ihr Problem in Ordnung?

Weil, wenn Sie die optimale Lösung zu finden, müssen Sie den Abstand zwischen allen Ihren Quell- und Ziel poligon Grenzen (nicht nur Scheiteln) zu berechnen haben. Wenn Sie im 3D-Raum sind, dann ist jede Grenze ein Flugzeug. Das kann ein großes Problem sein (O (n ^ 2)), je nachdem, wie viele Scheitel Sie haben.

Wenn Sie also Zählung Vertex haben, der macht, dass Quadrate auf eine scarry Nummer und eine „gut / sehr gut“ Lösung für Sie in Ordnung ist, gehen Sie für eine heuristische Lösung oder Annäherung.

Sie könnten Voronoi Culling suchen. Papier und Video hier:

http://www.cs.unc.edu/~geom/DVD/

würde ich durch begrenzende alle Polygone durch einen Begrenzungskreis beginnen und dann eine obere Grenze des minimalen Abstand zu finden. Dann würde ich einfach überprüfen Sie die Kanten aller blau Polygonen, deren unteren dem Abstandes gebunden ist niedriger als die obere Grenze des Mindestabstandes gegen alle Kanten des roten Polygons.

upper bound of min distance = min {distance(red's center, current blue's center) + current blue's radius}

for every blue polygon where distance(red's center, current blue's center) - current blue's radius < upper bound of min distance
    check distance of edges and vertices

Aber es hängt alles von Ihren Daten. Wenn die blauen Polygonen relativ klein sind im Vergleich zu den Abständen zwischen ihnen und dem roten Polygon, dann sollte dieser Ansatz gut funktionieren, aber wenn sie ganz in der Nähe sind, werden Sie nichts speichern (viele von ihnen werden nah genug sein). Und noch etwas -. Wenn diese Polygone haben nicht viele Ecken (wie wenn die meisten von ihnen waren Dreiecke), dann könnte es fast so schnell sein, nur jede rote Kante überprüfen gegen jeden blauen Rand

hoffen, es hilft

Wie andere haben mit Begrenzungs genannten Bereichen (Boxen, Kreise) kann Ihnen erlauben, einige Polygon-Polygon-Interaktionen zu verwerfen. Es gibt verschiedene Strategien für diese, z.

Wählen Sie jedes blaue Polygon und den Abstand von dem roten finden. Nun andere Polygon wählen. Wenn der Mindestabstand zwischen den begrenzenden Flächen größer als der bereits gefundenen Abstand ist, können Sie dieses Polygon ignorieren. Weiter für alle Polygone.
Finden Sie den Mindestabstand / Schwerpunkt Abstand zwischen dem roten Polygon und all blau Polygonen. Ordnen Sie die Abstände und betrachten zunächst den kleinsten Abstand. Berechnen Sie den tatsächlichen Mindestabstand und weiter durch die sortierte Liste, bis der maximale Abstand zwischen den Polygonen größer als der Mindestabstand bisher gefunden.

Die Wahl der Kreise / axial ausgerichteten Boxen oder orientiertem Boxen kann eine große auf die Leistung des Algorithmus, abhängig von der tatsächlichen Anordnung der Eingangs Polygone auswirken.

Für die eigentliche Berechnung Mindestabstand Sie Yang et al des ‚verwenden könnte Ein neuer schneller Algorithmus zur Berechnung der Distanz zwischen zwei disjunkte konvexen Polygonen basierend auf Voronoi-Diagramm ‘, die O (log n log + m) ist.

Muss ich zu einer Beerdigung in einer Sekunde ablaufen, aber wenn Sie Ihre Polygone nach unten in konvexe subpolies brechen, gibt es einige Optimierungen Sie tun können. Sie können auf jeder Poly ein Binärsuchen tun, um den am nächsten Scheitelpunkt zu finden, und dann I glaube der nächste Punkt sollte entweder der Scheitel sein, oder eine benachbarte Kante. Das heißt, Sie sollten in der Lage sein, in log(log m * n) zu tun, wo m die durchschnittliche Anzahl von Eckpunkten auf einem Poly, und n ist die Anzahl der polies. Dies ist eine Art von Hastey, so könnte es falsch sein. Werden später weitere Informationen geben, wenn gewünscht.

Sie konnten durch den Vergleich der Abstand zwischen den Begrenzungsrahmen beginnen. den Abstand zwischen Rechtecke Testen ist einfacher als der Abstand zwischen den Polygonen zu testen, und Sie können sofort alle Polygone beseitigen, die mehr als nearest_rect sind + its_diagonal weg (möglicherweise können Sie, dass noch mehr verfeinern). Dann können Sie die verbleibenden Polygone testen Sie die nächste Polygon zu finden.

Es gibt Algorithmen für die Suche nach Polygon Nähe - ich bin sicher, dass Wikipedia eine gute Bewertung von sich hat. Wenn ich mich richtig erinnere, sind wesentlich schneller diejenigen, die nur konvexe Polygone ermöglichen.

Ich glaube, für das, was Sie suchen, die A * -Algorithmus ist, seine in Wegfindung verwendet.

Der naive Ansatz ist, den Abstand zwischen dem roten und 50 blauen Objekten zu finden - so Sie suchen bei 50 3d Pythagoreische Berechnungen Sortierung + die Antwort zu finden. Das würde den Abstand zwischen den Mittelpunkten allerdings nur wirklich arbeiten zu finden.

Wenn Sie beliebige Polygone wollen, vielleicht die besten am besten ist eine Raytracing-Lösung, die Strahlen, die von der Oberfläche des roten Polygons in Bezug auf den normalen emittiert und meldet, wenn ein anderes Polygon getroffen wird.

Ein Hybrid funktionieren könnte - wir den Abstand von den Mittelpunkten finden konnten, gehen wir eine Vorstellung von der relativen Größe der blauen Polygonen hatten wir das Ergebnis auf die nächste unter denjenigen gesetzt keulen könnte, dann Raytracing verwenden zu verengen auf dem wirklich am nächsten Polygon (s).

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow