Geri - Mo 30.06.08 12:49
Titel: Algorithmus zum Erkennen von Polygonzügen

---

Hallo

Ich habe eine Vektorgrafik, bestehend aus Geraden und Kreisbögen. Teilweise sind diese Objekte miteineander an den Endpunkten verbunden und bilden so einen Linienzug (z.B. ein Rechteck, ein Polygon, teilweise auch komplexe Polygone).

Nun möchte ich die zusammenhängenden Objekte erkennen.

Ich kann mir vorstellen, dieses Problem tritt oft auf und wurde bereits ausreichend in einen effizienten Algorithmus umgesetzt. Bei meinen Recherchen bin ich allerdings noch nicht fündig geworden. Vielleicht auch deshalb, weil mir der richtige Suchbegriff fehlte:)

Habe ihr hier vielleicht eine Idee?

Beste Grüsse und vielen Dank

Geri

BenBE - Mo 30.06.08 13:12

---

In welcher Form sind deine Eingabe-Daten gegeben?

Müssen spezielle Konstellationen oder allgemein vorhandene (zusammenhängende) Objekte erkannt werden?

Liegt die Eingabe aus der Vektor-Grafik rasterisiert vor, oder liegen die vorhandenen Linienzüge und Bögen als Beschreibungen einzeln vor?

Geri - Mo 30.06.08 13:29

---

Hallo

Die Daten liegen im Vektorformat vor. Z.B. Linien und Kreisbögen vor, von allen Objekten hat man die Start und Endpunkte sowie die bei Kreisbögen den Mittelpunkt. Anbei ein Beispiel.

Die Objekte sind in einer TListe unsortiert.

Ziel ist es nun, die zusammenhängenden Objekte zu erkennen. Im gezeigten Beispiel wäre das Ergebnis drei Linienzüge.

Beste Grüsse

Geri

Moderiert von Narses: Überzähligen Dateianhang gelöscht

BenBE - Mo 30.06.08 14:21

---

Für dich könnte das Thema Pathfinding in ungerichteten Graphen interessant sein (Breitensuche).

Dazu speicherst Du Anfang und Endpunkt jedes Objektes in eine Liste, sortierst diese Liste nach den Koordinaten (nicht notwendig, aber hilft u.U. beim Verbessern der Performance) und entfernst aus dieser Liste jegliche Objekte (und merkt sich diese gesondert), die an diesem Punkt anliegen.

Geri - Mo 30.06.08 16:37

---

Hallo

Ich glaube auch, dass eine theoretische Basis in der Graphentheorie gefunden werden kann. Die Pathfinding-Algorithmen gehen für mich aber eher in die Richtung Optimierung (z.B. shortest path), wenn man man mal z.B. von der Breitensuch absieht.


Prinzipiell kann ich mir aktuell folgendes Vorgehen vorstellen:

1.) Aufbau des Graphen
2.) Analyse des Graphen (Bestimmung der Komplexität)
3.) Verketten der Kanten zu Linienzügen


Wie man das aber effizient macht, das würde mich mal interessieren...

Beste Grüsse

Geri

alzaimar - Mo 30.06.08 20:09

---

Ich würde das so lösen:
1. Schnapp Dir ein Objekt (X) mit den Endpunkten Px0 und Px1.
2. Finde ein Objekt Y mit Endpunkten Py0 und Py1, das X an Px0 oder Px1 berührt.
2.1 Gibt es ein solches Objekt, verbinde es mit X und ersetze Px0 bzw. Px1 durch den freien Endpunkt von Y. Das neue Objekt sei 'X'.
2.2 Entferne Y aus der Liste der Objekte (damit man es nicht nochmal findet) und Goto 2
3. Das Objekt X ist geschlossen gdw, Px0=Px1
4. Goto 1

Das funktioniert in O(N), wenn man die Objekte vorher geeignet in eine Hashmap packt. sodaß man schnell nach passenden Objekten (mit Berührungspunkten) suchen kann.

BenBE - Mo 30.06.08 20:16

---

Man nehme einen Knoten. Dieser ist in Objekt X, nun suche man über Breitensuche alle Knoten, die man von diesem Knoten aus erreichen kann und entferne sie.

Man wiederhole diesen Schritt solange, bis keine Knoten mehr da sind

Was ist daran so schwer?

alzaimar - Mo 30.06.08 20:25

---

BenBE hat folgendes geschrieben:

Was ist daran so schwer?

Das man dann immer noch nicht weiss, ob die Polygonzüge geschlossen sind.

BenBE - Mo 30.06.08 20:31

---

Dazu muss man einzig prüfen, ob der Graph nicht kreisfrei ist ;-)

alzaimar - Mo 30.06.08 20:34

---

Und schon wirds kompisiert. :hair: