Geri - Do 01.10.09 12:47
Titel: Suche von zusammenhängenden Strecken

---

Hallo

Ich habe eine Vektorgrafik (Gelesen aus HPGL-File) mit n Strecken, welche in einer Liste abgelegt sind. Die Strecken können an den Endpunkten miteinander verbunden sein.

Wenn man die verbundenen Strecken zeichnet, dann ergeben sich also

1.) einzelne Strecken,
2.) offene Polygonzüge,
3.) geschlossene Polygonzüge,
4.) Netze (mehrere Strecken haben einen gleichen Endpunkt).

Nun suche ich nach einem passenden Algorithmus, welcher als Ergebnis eine Liste mit allen miteinander verbundenen Strecken, wie unter Punkt 1 bis 4 beschrieben, zurücklidefert. Ebenso wäre gut, wenn aufeinanderfolgnde Strecken bereits richtig sortiert sind.

Fallen euch hierzu vielleicht ein paar Stichworte ein.

Was habe ich schon erreicht:
Bisher habe ich eine Knotenliste (Klasse TNodeList) angelegt. Ein Knotenliste enthält alle Knoten. Ein Knoten mit einer bestimmten Koordinate exisiert also nur einmal.
Jeder Knoten (TNode) verwaltet wiederum eine Liste mit Referenzen zu den Strecken (Klasse TLine). TLine hält für seinen Start und Endpunkt je eine Referenz auf einen TNode.

Die Grfik sollte das Ganze nochmals ein wenig veranschaulichen.

In der Sprache der Graphentheorie ausgedrückt kenne ich also alle Knoten und Kanten.

Beste Grüsse und vielen Dank für Anregungen

Geri

Thorsten83 - Do 01.10.09 15:40

---

Hey,

wonach genau willst du sortieren?

Allgemein kannst du zusammenhängende Teilgraphen wahlweise mit Breiten- oder Tiefensuche finden, wenn du dir dabei merkst welche Knoten du schon besucht hast kannst du dann weitere Teilgraphen finden, indem du die Suche an einem noch nicht besuchten Knoten neustartest, bis alle Konten besucht wurden.

Geri - Do 01.10.09 16:21

---

Hallo Thorsten

Die Klasse TLine hat eine Flag sfVisited.

Ich möchte als Ergbnis alle zusammenhängenden Grafikobjekte. Jedes Grafikobjekt könnte in einer eigenen Liste abgelegt werden. Sofern möglich sollten die Elemente (TLine) eines Grafikobjektes nacheinander folgen (Das verstehe ich unter Sortierreihenfolge). Also alle Pfade der Teilgraphen.

Für das Beispiel, welches im Bild dargestellt habe sähe ein gutes Ergebnis folgendermassen aus:

Liste 0: L0, L6, L1, L7
Liste 1: L5, L2, L3
Liste 2: L8, L9, L10
Liste 3: L4


Ich denke, es handelt sich hier um ein Stanardproblem aus der Graphentheorie. Ich bin nur noch nicht draufgekommen welche effizienten Algorithmen es dafür gibt:)

Ein Algorithmus in einer Art Tiefensuche habe ich bereits implementiert. Wie würde aber die Rechenvorschrift aus Deiner Sicht bitte aussehen?


Beste Grüsse

Geri

Thorsten83 - Do 01.10.09 16:54

---

Geri hat folgendes geschrieben :

Ich denke, es handelt sich hier um ein Stanardproblem aus der Graphentheorie. Ich bin nur noch nicht draufgekommen welche effizienten Algorithmen es dafür gibt:) Ein Algorithmus in einer Art Tiefensuche habe ich bereits implementiert. Wie würde aber die Rechenvorschrift aus Deiner Sicht bitte aussehen?

Ich würde eine Liste von Listen erstellen, jede dieser Listen enthält dann zusammenhängende Knoten.

Den Algorithmus könnte man z.B. so formulieren:


und die benutzte Funktion:

Geri - Fr 02.10.09 15:57

---

Hallo Thorsten

Vielen Dank für Deine Hinweise.

Ich werde mir deinen Lösungsweg, werde ihn mir mal durchdenken.

Bisher habe ich es ähnlich gemacht. Ich führe auch eine Liste mit Listen. Allerdings eine Liste aller Knoten wobe jeder Knoten n Kanten hält:) - also alle Katen die mit ihm in Verbindung stehen. Das dürfte in die gleiche Richtung gehen. Die Suche erfolgt bei mir allerdings iterativ.

Beste Grüsse und nochmals vielen Dank

Geri