Sortierproblem

[droge]

Ich komme einfach nicht weiter

Ich habe folgende Datenstruktur:

Ein Array mit "Segmenten", jedes Segment beinhaltet eine StartID und eine EndID und repräsentiert ein Teilstück einer Außenkante eines Polygons.

Allerdings ist die liste nicht so geordnet daß ich damit etwas anfangen kann, im endeffekt muss die liste so geordnet sein:

5;14 -> 14;4 -> 4;9 -> 9;27 -> ...

Daß heißt jede ID kommt genau 2 mal vor, kann aber 2mal als StartID, 2mal als EndID oder als End- und StartID vorkommen.

Räumlich gesehen ergeben dann die Punkte die hinter den IDs liegen einen Polygonzug der das Polygon bildet. Die ID ansich hat aber keine Bedeutung für die Lage im Polygonzug.

Ich habs schon mit Hashtable und Arraylist versucht aber komme einfach auf keinen grünen zweig.

Als Programmeirsprache nutze ich c#.net

Bearbeitet 30. Oktober 2009 von droge

[flashpixx]

Ein Polygonzug ist erst mal nichts anderes als ein gerichteter / ungerichteter Graph. Ich würde hier nicht "punktweise / knotenweise" arbeiten, sondern Kantenweise. D.h. Du hast eine Matrix mit n*n Einträgen. Du setzt dort eine 1 / true rein, wenn Knoten verbunden sind.

Am Beispiel von drei Punkten: (1,2) -> (2,3) -> (3,1) wäre Deine Notation.

Als Matrix hättest Du

011

101

110

Wie Du hier sehen kannst, ist die Matrix bei einem ungerichteten Graphen symmetrisch zur Hauptdiagonalen, die Du wahlweise generell auf 1 oder 0 setzen kannst, ob jeder Punkt mit sich selbst verbunden sein soll, musst Du Dir überlegen. Bei einem gerichteten Graphen wäre sie dann eben nicht symmetrisch.

Nun kannst Du ganz einfach zeilen- oder spaltenweise durch die Matrix laufen und eben das Polygon verarbeiten. Wenn ich hier die erste Zeile nehme, dann ist der Punkt 1 sowohl mit 2 wie auch mit 3 verbunden

Hoffe es ist verständlich :-P

[droge]

Ist ja prinzipiell keine schlechte Idee, aber daß Problem liegt ja eher dabei die Daten aus dem Segment-array in diese Matrix-Form zu bekommen.

[flashpixx]

Wo ist das Problem !?

Du hast Tupel aus Koordinaten und kannst daraus die Dimensionen der Matrix ermitteln

[droge]

die matrix geht von 0;0 bis n;n , die ID gehen von a bist z und daß ncihtmal durchgehend.

Hab daß jetzt mit einem wirren Schleifenkonstrukt und einer Arraylist aus der ich die segment-IDs in ein neues array übetrage und aus dem alten lösche, sobald die ID daß 2. mal vorkommt.

[flashpixx]

die matrix geht von 0;0 bis n;n , die ID gehen von a bist z und daß ncihtmal durchgehend.

Nein, die Matrix läuft von dem Minium Deiner Tupel bis zum Maximum Deiner Tupel, bei einer MxN-Matrix min(erste Komponente Typel) bis max(erste Komponente Tupel), für N, die zweite Komponente.

Die Tupel sind nur die Koodinaten der Kanten, die miteinander vernetzt sind.

5;14 -> 14;4 -> 4;9 -> 9;27

Knoten (5,14) ist mit Knoten (4,14) verbunden, (4,14) mit (4,9) und dieser mit (27,9).

Wenn Du einfach sequentiell Deine Tupel in die Matrix schreibst, die Matrix dann mit der transponierten Matrix addierst, kannst Du Deinen Polygonzug einfach so auslesen, dass, wenn ein Matrixeintrag ungleich 0 ist, die beiden Kanten verbunden sind.

Da Du durch die Addition einen ungerichteten Graphen aufbaust ist es egal, ob Du (3,1) oder (1,3) verwendest, da die Verbindung in beide Richtungen existiert. Zur Visualisierung kann man Graphviz verwenden

[droge]

Mhhh... da müsste ich aber ziemlich viele additionen durchführen.

In meinem Anwendungsfall hab ich polygone mit über 1000 knoten, könnte zu viel zeit verschlingen.

Muss ich bei gelegenheit mal mit meinem algorithmus vergleichen was schneller ist.

[flashpixx]

Man würde auch keine Matrix mit 1000x1000 Elementen speichern, sondern diese als sparse matrices speichern, wobei Du bei einem ungerichteten Graph nur die obere oder untere Dreiecksmatrix benötigst, da die Matrix symmetrisch zu Hauptdiagonalen ist. Sowohl für die Datenstruktur, wie auch die Algorithmen gibt es entsprechende Methoden