Datenstruktur zum Verlegen von Polygonsegmenten in Haskell?

Bevor wir nach Ecken suchen, machen wir einen Schritt zurück. Was versuchst du zu tun?

  

Ich habe eine ungeordnete Liste von horizontalen / vertikalen Segmenten der Länge 1, die ein oder mehrere Polygone bilden. Ich muss jetzt die Liste aller verbundenen Ecken in jedem Polygon finden.

"Suchen" und "ungeordnete Listen" passen nicht wirklich zusammen, wie du sicher weißt! Dies gilt auch für einfache Lookups, aber für das, was Sie tun, ist es sogar noch schlimmer. Das liegt konzeptionell näher an der Suche nach Duplikaten, weil es Elemente der Collection miteinander korrelieren muss, anstatt sie einzeln zu untersuchen.

Also, du wirst definitiv etwas mit mehr Struktur dazu haben wollen. Eine Option wäre eine semantisch aussagekräftigere Darstellung in Form von vollständigen Polygonen, die eine einfache Durchquerung eines ungebrochenen Umfangs ermöglichen würde, aber ich nehme an, dass Sie diese Informationen nicht zur Verfügung haben (zum Beispiel, wenn Sie versuchen, Erstelle eine solche Struktur hier).

Nun, in einem Kommentar hast du gesagt:

  

Der Grund dafür ist, dass die Segmente zuvor in "Set" s gespeichert wurden, um überlappende Segmente zu entfernen. Diese Darstellung garantiert, dass es nur ein Segment (x, y) - (x + 1, y) gibt.

Dies ist weitere Überlegungen wert. Wie funktioniert Data.Set und warum ist es besser, Duplikate zu entfernen als eine ungeordnete Liste? Das letzte Bit ist eine Art Give-Away, denn Data.Set ist genau eine geordnete Sammlung. Wenn Sie also jedem Element eine eindeutig sortierende Darstellung geben, erhalten Sie die kombinierten Vorteile des automatischen Entfernens von Duplikaten und schneller Suche .

Wie oben erwähnt, ist Ihr tatsächliches Problem konzeptionell ähnlich dem Auffinden von Duplikaten; Anstatt überlappende Segmente zu finden, möchten Sie benachbarte Segmente. Kann dir Data.Set auch hier helfen?

Leider kann es nicht. Um zu sehen, warum, überlegen Sie, wie die Sortierung funktioniert. Bei zwei gegebenen Punkten X und Y gibt es drei mögliche Vergleiche: X & lt; Y, X == Y oder X & gt; Y. Wenn unterschiedliche Elemente voneinander abweichen, unterscheiden sich benachbarte Elemente um den minimal möglichen Wert. Sie können also nur Elemente, die in der sortierten Auflistung benachbart sind, sicher untersuchen. Dies kann jedoch aus mehreren Gründen nicht auf Liniensegmente verallgemeinert werden. Das einfachste ist, dass bis zu vier verschiedene Elemente nebeneinander liegen können, die nicht in einer sortierten Reihenfolge beschrieben werden können.

Hoffentlich bin ich mit meinen Hinweisen so hartnäckig gewesen, dass Sie sich jetzt fragen, was eine sortierte Sammlung, die erlaubt, dass vier verschiedene Elemente nebeneinander liegen, aussehen würde und ob es erlaubt wäre Einfaches Suchen nach Data.Set .

Die Antwort auf letzteres ist ja, absolut , und die Antwort auf das erste ist, dass es ein höherdimensionaler Suchbaum wäre. Ein einfacher binärer Suchbaum sieht ungefähr so ​​aus:

... wo Sie sicherstellen, dass bei jeder Verzweigung alle Blattwerte in der linken Hälfte kleiner sind als in der rechten. Ein einfacher zweidimensionaler Suchbaum würde stattdessen in etwa so aussehen:

... wobei jeder Zweig einen Quadranten darstellt, der durch unabhängiges Vergleichen auf den beiden Achsen sortiert wird. Ansonsten funktioniert es wie vertraute eindimensionale Suchbäume, mit einfachen Übersetzungen vieler Standardalgorithmen und mit einem bestimmten Liniensegment können Sie schnell nach benachbarten Segmenten suchen.

Bearbeiten : Im Nachhinein habe ich mich etwas zu sehr in die Ausstellung eingearbeitet und vergessen, Referenzen zu geben. Dies ist keineswegs ein neuartiger Begriff und hat viele Variationen:

• Was ich beschrieben habe, würde man Punkt Quadtree nennen und wäre eine einfache Erweiterung von binären Suchbäumen, wie Data.Set .

• Dasselbe Konzept kann mit Regionen anstelle von diskreten Punkten durchgeführt werden, wobei Nachschlagevorgänge bei Regionen enden, die entweder vollständig eingeschlossen oder ausgeschlossen sind. Dies sind ähnliche Erweiterungen von Versuchen , wie Data.IntSet .

• Eine Variante namens R-Bäume ähneln B-Bäumen und haben nützliche Leistungsmerkmale für einige Zwecke.

Die Konzepte erstrecken sich ebenso auf höhere Dimensionen. Datenstrukturen entlang dieser Linien werden für das Rendering und die Kollisionserkennung in Simulationen und Videospielen, räumliche Datenbanken mit "Nearest Neighbour" -Suchen sowie abstraktere Anwendungen, an die Sie normalerweise nicht geometrisch denken würden, verwendet, wo spärliche Datenpunkte entlang sortiert werden können mehrere Achsen und einige kombinierte Begriffe von "Entfernung" sind sinnvoll.

Seltsamerweise konnte ich keine Implementierung solcher Datenstrukturen auf Hackage finden, abgesehen von einem unvollständigen und scheinbar verlassenen Paket.

Wenn ich die Problembeschreibung richtig verstanden habe, kann jedes Segment an bis zu vier möglichen Ecken teilnehmen, die jeweils ein bestimmtes komplementäres Segment identifizieren. Bei einer Liste von Segmenten können wir dann die Liste durchgehen, um zu sehen, welche möglichen Zwei-Segment-Ecken vorhanden sind, und dann herausfinden, wo sich diese Segmente treffen. Dies ist ein sehr langsamer Ansatz aufgrund der wiederholten Listendurchläufe, aber wenn Sie nur mit Handvoll von Segmenten zu tun haben, ist es zumindest ziemlich knapp.