Zum Inhalt springen

Empfohlene Beiträge

Geschrieben (bearbeitet)

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 von droge
Geschrieben

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

Geschrieben

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.

Geschrieben
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

Geschrieben

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.

Geschrieben

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

Dein Kommentar

Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.

Gast
Auf dieses Thema antworten...

×   Du hast formatierten Text eingefügt.   Formatierung wiederherstellen

  Nur 75 Emojis sind erlaubt.

×   Dein Link wurde automatisch eingebettet.   Einbetten rückgängig machen und als Link darstellen

×   Dein vorheriger Inhalt wurde wiederhergestellt.   Editor leeren

×   Du kannst Bilder nicht direkt einfügen. Lade Bilder hoch oder lade sie von einer URL.

Fachinformatiker.de, 2024 by SE Internet Services

fidelogo_small.png

Schicke uns eine Nachricht!

Fachinformatiker.de ist die größte IT-Community
rund um Ausbildung, Job, Weiterbildung für IT-Fachkräfte.

Fachinformatiker.de App

Download on the App Store
Get it on Google Play

Kontakt

Hier werben?
Oder sende eine E-Mail an

Social media u. feeds

Jobboard für Fachinformatiker und IT-Fachkräfte

×
×
  • Neu erstellen...