Einen schönen Sonntag.
Ich komme gleich zur Sache:

Ich habe eine Gruppe von [b]n[/b] Punkten auf einem 2D-Feld.
-Jeder dieser Punkte weiß wo er liegt. Sprich er kennt seine X/Y-Koordinaten.
-Jeder dieser Punkte merkt sich in einer Liste 2 bis [b]n[/b] Verknüpfungen zu anderen Punkten.

Als Verständnishilfe:
[img]http://www.tachoron.de/2d3d.JPG[/img]

Ich suche nun nach einer Möglichkeit aus diesen Informationen zu erkennen
welche Punkte jeweils eine - [b]in sich geschlossene[/b] - Fläche aufspannen.
In sich geschlossen bedeutet: Keine weiteren Flächen innerhalb dieser Fläche.
Sprich in dem Beispiel:
-1+2+5
-2+3+5
-3+4+5
-4+1+5
Nicht:
-1+2+3+4

Wichtig: Die Flächen sollen dabei aus beliebig vielen Punkten bestehen und alle Formen aufspannen können.

Ich suche nun schon seit Tagen nach einer Lösung.
Vielleicht kann da einer von euch helfen.
Wäre super

Ich hoffe das ich soweit alles erklärt habe (aber warscheinlich nicht).

Mit freundlichen Grüßen
Tachoron

Tachoron schrieb:

Hier liegt vermutlich die Lösung. Das ist ein WEGE-Problem. Du musst genau hier eine Information hinzufügen, und zwar könnte das mit einer Sortierung der Punkteliste im Gegenuhrzeigersinn gehen. Bei einem Polygon geht man immer linksherum.
Traude

Hi,

ich hab da nu ne Weile drübernachgegrübelt aber so recht bringt mich das zu keinem weiteren Ansatz.
In wiefern sollen mir die Informationen dabei helfen?

Mit freundlichen Grüßen
Tachoron

Hallo Tachoron,
Nicht lange nachgrübeln, einfach nachfragen.


Ich würde die Nachbar-Liste, die jeder Punkt sich merkt, sortieren, und zwar so, dass die Punkte im Gegenuhrzeigersinn vorliegen. Die Sortierung stellt eine zusätzliche Information dar.

Wenn wir z.B. von Deinem Punkt 4 ausgehen, sind seine Nachbarn im Gegenuhrzeigersinn sortiert:
3-5-1. (Ist nur eine Annahme, welcher der Punkte der erste ist, Hauptsache sie sind sortiert, könnte also auch 5-1-3 sein)

Um eine aufgespannte Fläche zu finden, musst Du sie umrunden können, also Du gehst vom Punkt 4 aus und trachtest danach, wieder zu ihm zurückzukommen.

Zu diesem Zweck nehmen wir die sortierte Liste her und probieren mal den ersten Punkt, also Punkt 3. Punkt 3 hat seine Nachbarn natürlich ebenfalls aufgelistet:
2-5-4.
Nach Punkt 4 zurückzugehen, wenn man von ihm gerade kommt, sollte das Programm ausschließen. Daher haben wir jetzt nur mehr zwei Optionen, nämlich 2 und 5. Jetzt kommt die Sortierung ins Spiel. Der nächste Punkt, zu dem ich gehe, sollte ein Nachbar von dem Punkt sein, wo ich herkomme (ein Vorgänger in der Liste oder ein Nachfolger in der Liste von 4). Ich habe daher keine andere Wahl, als nach 5 zu gehen.

Punkt 5 hat die Liste
4-3-2-1

Und schließlich ist 4 unser Ziel, der Punkt, auf den wir zustreben, denn damit können wir die Schleife schließen und haben eine gültige Fläche gefunden.

Unser Weg war: 4->3->5->4.


Nur weil ich neugierig bin: was machst Du denn da, schreibst Du einen Triangulierer?

ohne jetzt lange drüber nachzudenken werfe ich einfach mal ein:

1) Alle Punkte nacheinander durchgehen.
2) Von Punkt X den abstand zu allen Punkten berechnen.
3) die 2 Punkte mit dem kleinsten Abstand zu X suchen

das sollte funktionieren so lange du nicht sowas wie 1-5-3-4 auch zulassen willst.

[Edit:]
funktioniert so nicht seh ich grad...
das einzige was dir das gibt sind Dreiecke in denen kein anderer Punkt liegt

Das kann man mit einen Tesselierungsalgo lösen.
Meine Lösung würde so ausehen.
1. Liste(S) mit allen Punkten erstellen
2. Letzten Punkt(P) aus der Liste(S) wählen
3. N1 und N2 sind die 2 anderen Punkte der neuen Fläche, wobei N1 der erste Nachbar(der nicht in Done ist) von P zugewiesen wird
4. Suche in der Nachbarliste von N1 und P einen gemeinsammen Punkt, der nicht in Liste(Tmp) ist und weise ihn N2 zu
4a. erstelle Fläche P,N1,N2
4b. füge N2 in eine Liste(Tmp) hinzu
5. gehe zu 4. bis N2=0
6. füge N1 zu einer Liste(Done)
7. gehe zu 3 bis Done.length=P.Nachtbarn.length
8. entferne P aus S und gehe zu 2 bis S leer ist

Funtzt aber nur für 3Ecke.

_________________
"Wer die Freiheit aufgibt um Sicherheit zu gewinnen, der wird am Ende beides verlieren"
Benjamin Franklin

Projekte: https://github.com/tak2004

Hi, danke erstmal für eure vielen Antworten.
Wollte an sich schon eher darauf antworten, wurde aber leider bei meinem letzten Versuch (in der Uni) unterbrochen.

@TAK2004 leider habe ich nicht nur dreiecke sondern beliebige Vielecke.

@Billi Berserker: Genau mein Ansatz gewesen (War auch schon implementiert), aber eben genau das Problem was du sagtest



Nein, ich schreibe ein kleines Tool das 2D-Bilder in 3D-Modelle konvertiert, in dem es wichtige Punkte erkennen soll.
Aber deine Version klingt mir auf jeden Fall so aus dem Stehgreif heraus nun sehr einleuchtend.
Muss nun noch im Kopf für mich durchspielen ob das für jedes Vieleck funktioniert.
Wäre dann aber super!

MfG Tachoron

Hey das bringt mich auf eine IRRE Idee: Wavelets können Konturen erkennen. Wenn man die Konturen mal hat, kann man sie auch rotieren lassen (man könnte dann aus einen Kreis eine Kugel erzeugen). Könnte aber nur bei solchen Objektien wie einer Vase oder so funktionieren, ein menschliches Modell würde ein wenig merkwürdig aussehen.
Traude

Hi Traude, ich bin dein Beispiel nocheinmal durchgegangen.

Nun wenn ich das nun so anwende und von jedem Punkt den ich habe versuche zb. mit den Uhrzeigersinn eine solche Fläche aufzuspannen,
dann würde ich ja nicht nur von Punkt 4 nach Punkt 3 gehen, wie in deinem Beispiel und mich dann halt im UHrzeigersinn um die FLäche zu bwewegen, sondern
auch von Punkt 4 nach Punkt 1 gehen und das gleiche zu versuchen.

Das wäre dann (im Uhrzeigersinn):

4 - 1 - 2 -3

Und das wäre eine Fläche die eben kein richtige Fläche ist.

Hallo Tachoron,
OK, da oben hab ich einen Fehler gemacht. Ich habe aber hier eine Algorithmus, der ist ganz kurz und stur, und der scheint immer zu funktionieren, er schneidet konsequent ein Polygon nach dem anderen heraus.... Vielleicht bin ich aber jetzt bloss zu müde, um Fehler zu erkennen... Ich habs in einem Netzwerk mit Vierecken und Sechsecken probiert.

Ich habe vorausgesetzt, dass die Punkte-Listen gegen den Uhrzeigersinn sortiert sind (counter clockwise = CCW).

Pascal-PseudoCode:

Funktion NächsterPunkt(Parameter: AnfangsPunkt,VorigerPunkt,AktuellerPunkt): Punkt
Result:= NIL;

Wenn (AnfangsPunkt <> VorigerPunkt) Und (AnfangsPunkt ist in der Liste des aktuellen Punktes)
Then Result:= Anfangspunkt
Else Result:= NachfolgerVon(VorigerPunkt);



Die Funktion "NachfolgerVon" sucht den Nachfolger von "VorigerPunkt" in der Liste des aktuellen Punktes (der Nachfolger des letzten Punktes ist der erste Punkt, weil die Liste als Ring anzusehen ist).

Zunächst sucht man sich irgendeinen Anfangspunkt und wählt irgendeinen Nachbarn als aktuellen Punkt aus. Dann wird die obige Funktion so oft ausgeführt, bis als Funktionsergebnis wieder der Anfangspunkt herauskommt.

Traude

Ja eben diese Lösung hatt ich auch umgesetzt.

Aber wenn wir den Psuedocode nun zb. auf

anwenden.

Wir gehen zb. von Punkt 4 aus:
Wenn wir nach Punkt 1 gehen funktioniert der Spaß und
wir bekommen:
4 - 1 -5, alles Korrekt!
Wenn wir nach Punkt 5 gehen geht es auch:
4 - 5 - 3, alles Korrekt!
Wenn wir aber nach Punkt 3 gehen (und wir müssen ja von jedem Pkt. zu jedem Pkt gehen):
4 - 3 -2 - 1
Und das geht dann nicht: Wir bekommen zwar eine Fläche, aber diese beinhaltet andere Flächen und ist für sich genommen keine Fläche und ich wüsste zb. net wie man die rausfiltern könnte.

MfG Tachoron

Hi Tachoron,
Ich gaube ich bin draufgekommen, was das Probem ist. In einem solchen "Netzwerk" gibt es zwei verschiedene Arten von Punkten:

1) Innere Punkte: ein innerer Punkt ist dadurch gekennzeichnet, dass er von einen Ring von Punkten umgeben ist, auf denen man ihn ganz umrunden kann. Seine Punkteliste ist ein Ring. Das wäre in Deinem Beispiel nur der Punkt 5.

2) Randpunkte: ein Randpunkt hat diese Eigenschaft nicht, seine Punkte-Liste ist KEIN Ring. Das wären in Deinem Beispiel die Punkte 1,2,3,4.

Der Punkt 3 sollte daher eine sortierte Liste haben, die diese Tatsache berücksichtigt. Wenn ich festlege, dass die Punkte-Liste gegen den Uhrzeiger sortiert werden muss, dann lautet die Liste des Punktes 3: 2-5-4.

Angenommen, wir stehen auf dem Punkt 3 und sind gerade von 4 gekommen. 4 ist aber das letzte Listenelement.
Weil der aktuelle Punkt 3 ein Randpunkt ist hat sein letzter Listenpunkt 4 daher auch keinen gültigen Nachfolger (das ist auch visuell deutlich zu erkennen). Einzige mögliche Lösung die ich sehe: Man muss den Vorgänger von 4 nehmen, und das ist 5.

Weg: 4=> 3 => 5 => 4.

Traude

Ja, aber wie willst du das denn erkennen das du den weg nehmen musst?
WIeso ist 5 der Vorgänger von 4 wenn man bei 4 startet?

Klar ist das Visuell sichtbar, aber wie will das der Algo wissen?

Irgendwie ist mir das so noch nicht ganz schlüssig, zumindest nicht lösbar,
aber evtl. verstehe ich was auch noch nicht richtig.

Hallo, Tachoron


Wenn ich es sehen kann, kann ich es immer auch in einen Algorithmus verpacken.


Genauere Beschreibung des Algo:

1) Festlegung einer Drehrichtung: Gegen den Uhrzeigersinn, CCW

2) Untersuchung aller vorhandenen Punkte und Zuordnung der Punkte zu den Gruppen "innere Punkte" und "RandPunkte".

*** Zuerst muss der Punkt alle seine unmittelbaren Nachbarn in einer Liste sammeln
*** Dann muss er sie gemäß der Drehrichtung sortieren, indem er sie der Reihe nach "besucht". Damit meine ich, dass er seine Nachbarpunkte abklappert, und zwar nur in der CCW-Richtung, ungefähr so wie in einem Kreisverkehr, hier darf man auch nur immer in einer Richtung herumfahren. Wir "fahren" hier sozusagen immer um den Punkt.
*** Anläßlich dieses "Besuchs" kann er auch gleich feststellen, ob er zu seinem Ausgangspunkt zurückkommt, wenn er immer seine Laufrichtung beibehält.
** JA, er kommt wieder zu seinem Ausgangspunkt zurück: es ist ein innerer Punkt
** NEIN, er kommt nicht zurück: es ist ein Randpunkt.
Der Punkt muss entsprechend gekennzeichnet werden, damit der nachfolgende Algorithmus einwandfrei erkennen kann, zu welcher Gruppe er gehört.


3) Alle Punkte mit dem "Schneidalgo" durchgehen und Polygone herausschneiden:

Ich nehme das Beispiel nochmal: von Punkt 4 nach Punkt 3

Aktueller Punkt 3 hat die sortierte Liste 2 => 5 => 4
Frage 1: Ist der Ausgangspunkt 4 vom aktuellen Punkt 3 aus sichtbar? JA
Frage 2: Kommt der Punkt 4 als nächster Punkt in Frage? NEIN, weil wir grade von ihm gekommen sind (sonst wärs ja ein Zweieck )
Frage 3: Gibt es einen unmittelbaren Nachfolger des Punktes 4 in der aktuellen Punkteliste des Punktes 3? NEIN (BITTE GENAU LESEN: ich meine hier nicht etwa den Nachfolger im Netzwerk, sondern den Nachfolger in der Punkteliste. Das ist etwas GANZ ANDERES)
Frage 4: Dürfen wir als Nachfolger des (letzten) Punktes 4 den ersten Punkt 2 heranziehen? NEIN, weil der aktuelle Punkt 3 ein Randpunkt ist, dessen Liste KEIN Ring ist.
LÖSUNG des ganzen: wir müssen statt des Nachfolgers von 4 (den es nicht gibt) den Vorgänger von 4 nemen. Eigentlich ändern wir hier die Laufrichtung, weil wir keine andere Wahl haben.

Wenn man die Punkteliste ansieht, ist der Vorgänger des Punktes 4 der Punkt 5. Und dorthin gehen wir jetzt.

Hier wiederholt sich das Spielchen, nur haben wir es beim Punkt 5 leichter, weil er ein regulärer innerer Punkt ist. Es kommen aber gar nicht zu Frage 3 (siehe oben). Denn die erste Frage lautet (ebenfalls siehe oben):

1) Ist der Ausgangspunkt 4 vom aktuellen Punkt 5 aus sichtbar? JA
2) Kommt er als nächster Punkt in Frage? JA, weil wir jetzt schon ein Dreieck haben.

Denn er fragt IMMER zuerst, ob man den Ausgangspunkt von hier aus sehen kann. Bei einem Polygon ist es erst zulässig, zum Ausgangspunkt zurückzukehren, wenn man sicher ist, das das "abgeklapperte" Polygon zumindest drei Punkte hat.
Traude