Aussenlienine einer Gitterform finden

OK, macht sinn, danke nochmals, ich probiers mal aus

otze

In deinem Beispiel gilt:

x ist Randpunkt => x hat weniger als 6 Nachbarn. Also erstmal alle Punkte mit 6 Nacbarn raushauen. Alternativ auch: die Winkelsumme zwischen den Verbindungen zu allen nachbarn hin ist < 360°. Dann bleiben nur die Randpunkte über.

Jester

Meine erste Frage wäre: was hast du genau gegeben? Das netz als graph? Dann kannst du einfach den Rand der Facette ablaufen zum beispiel imgegen-uhrzeigersinn: laufen, nächste kante im gegen-uzs nehmen usw. Damit alle facetten ablaufen, und die äußere wählen.

@SeppJ: dein kriterium für ne Randkante ist falsch, es kann beliebig viele solcher verbindungen geben.

Gregor

otze schrieb:

In deinem Beispiel gilt:

x ist Randpunkt => x hat weniger als 6 Nachbarn.

Nein. Zum Beispiel der Punkt direkt links unterhalb des Eckpunkts ganz rechts in der Mitte: Der hat nur 5 Nachbarn und ist kein Randpunkt.

Ich weiß nicht, ob folgende Idee schon genannt wurde:

Alle Dreiecke auflisten. Die Kanten, die nur zu einem Dreieck beitragen, sind Randkanten.

SeppJ

Jester schrieb:

@SeppJ: dein kriterium für ne Randkante ist falsch, es kann beliebig viele solcher verbindungen geben.

Wir reden schon von 2D-Dreiecksgittern, oder?

Jester

Ja klar. Man kann ja auch 5 oder 17 solcher verbindungen haben. Als kleines beispiel betrachte den vollständigen graphen mit vier knoten und bau noch was dazu, sodass nur noch eine seiner kanten außen liegt.

SeppJ

Ach das meinst du. Ich bin von Gittern ohne Schnittpunkten ausgegangen, wie im Beispiel des TE.

Jester

Ja, der graph ist planar. Jetzt tellst du dich aber grad ein bissel an, oder?

SeppJ

edit:

Jester

Klar geworden oder soll ich ein Bild malen?

knivil

Als kleines beispiel betrachte den vollständigen graphen mit vier knoten und bau noch was dazu, sodass nur noch eine seiner kanten außen liegt ... Klar geworden oder soll ich ein Bild malen?

Das Bild suggeriert eine Triangulierung, wobei Kanten gerade Strecken sind. Male mir doch mal das Bild mit einer einzigen Aussenkante. Alle Knoten sollten erreichbar sein.

Angenommen es handelt sich um eine Delaunay-Triangulierung, dann haben Randpunkte eine Voronio-Zelle (Dual zu Delaunay), die sich ins unendliche erstreckt. ... Nee, falsch, mist.

SeppJ

Jester schrieb:

Klar geworden oder soll ich ein Bild malen?

Ja. Peinlich, da dran nicht gedacht zu haben.

otze

Gregor schrieb:

otze schrieb:

In deinem Beispiel gilt:

x ist Randpunkt => x hat weniger als 6 Nachbarn.

Nein. Zum Beispiel der Punkt direkt links unterhalb des Eckpunkts ganz rechts in der Mitte: Der hat nur 5 Nachbarn und ist kein Randpunkt.

Deswegen steht dort => und nicht <=>.

Gregor

otze schrieb:

Gregor schrieb:

otze schrieb:

In deinem Beispiel gilt:

x ist Randpunkt => x hat weniger als 6 Nachbarn.

Nein. Zum Beispiel der Punkt direkt links unterhalb des Eckpunkts ganz rechts in der Mitte: Der hat nur 5 Nachbarn und ist kein Randpunkt.

Deswegen steht dort => und nicht <=>.

Oh, sorry, habe da die falsche Message reininterpretiert. Zumindest kannst Du über die Anzahl der Nachbarn die Randpunkte nicht direkt von den anderen Punkten trennen.

knivil

Wahrscheinlich ist es am einfachsten einen modifizierten Flood-Fill-Algorithmus zu verwenden.

Jester

knivil schrieb:

Als kleines beispiel betrachte den vollständigen graphen mit vier knoten und bau noch was dazu, sodass nur noch eine seiner kanten außen liegt ... Klar geworden oder soll ich ein Bild malen?

Das Bild suggeriert eine Triangulierung, wobei Kanten gerade Strecken sind. Male mir doch mal das Bild mit einer einzigen Aussenkante. Alle Knoten sollten erreichbar sein.

So langsam mache ich mir Sorgen. Ich schrieb, dass er Sachen dazubauen soll, sodass nur noch eine *seiner* Kanten (also eine der Kanten des vollständigen Graphen mit vier Knoten) außen liegt. Dadurch entstehen natürlich andere, neue Randkanten. Die sind aber nicht weiter von Belang.

Mal Hand aufs Herz: wenn Du jetzt einfach mal davon ausgegangen wärest, dass an meinem Einwand was dran ist, dann hättest Du das aus obigem Text schon rauslesen können, oder?

Jester

Ich glaube die zentrale Frage bleibt: Was ist die Eingabe?

Ein Bild oder ein Graph mit gegebenem Layout?

knivil

So langsam mache ich mir Sorgen.

Das mit dem dazubauen habe ich verstanden, wie ihm das helfen soll noch nicht. Klar meinn Defizit, aber ich habe so eine Ahnung ...

Also hier nach nochmaligem Nachdenken mein Vorschlag, der wahrscheinlich schon mal genannt wurde:

gegeben:
- Graph G als Menge von Knoten und Kanten
- G ist planar und "zusammenhaengend" (zwei zusammenhaengende Teilgraphen besitzen mind. eine gemeinsame Kante)
- Kanten entsprechen Strecken im 2D
gesucht: Pfad entlang der ausseren Begrenzung

Nehme eine Kante, die garantiert aussen liegt (leicht). Waehle Start- und Endpunkt (S,E) so, dass aussen links von (S,E) liegt. Suche aus den Kanten ausgehend von E jene Kante (E, P), bei der der Winkel zw. ES und EP maximal ist (0..360 Grad). Jener Punkt P bzw. Kante (E,P) ist wieder Aussenkante. Wiederhole bis S wieder erreicht wurde.

Sollte es sich beim Gegebenen doch um ein Bild handeln, der Algorithmus nicht. Funktioniert fuer Pixel aber aehnlich.

Jester

das sollte auch nicht helfen sondern stellte die Beschreibung eines Gegenbeispiels für das von SeppJ vorgeschlagene Kriterium dar, nicht mehr und nicht weniger.

Wenn man wirklich den Graphen hat, dann betrachtet man die kombinatorische Einbettung (zyklische Ordnung der Kanten um die Knoten) -> google-Stichwort! Nun kann man ganz einfach Facetten ablaufen, indem man immer eine Kante entlangläuft und die nächste ausgehende (im Gegenuhrzeigersinn) entlangläuft. Wenn man wieder bei der Startkante ankommt ist man eine Facette abgelaufen. Im vorliegenden Fall ist wahrscheinlich die größte Facette ein guter Kandidat für die äußere.

Oder eben wie Du vorschlägst irgendwoher eine äußere Kante finden und dann mit dem beschriebenen Vorgehen die Facette ablaufen.

volkard

knivil schrieb:

gegeben:
- Graph G als Menge von Knoten und Kanten
- G ist planar und "zusammenhaengend" (zwei zusammenhaengende Teilgraphen besitzen mind. eine gemeinsame Kante)
- Kanten entsprechen Strecken im 2D
gesucht: Pfad entlang der ausseren Begrenzung

Das reicht nicht.

knivil schrieb:

Nehme eine Kante, die garantiert aussen liegt (leicht).

Unmöglich.

knivil schrieb:

Suche aus den Kanten ausgehend von E jene Kante (E, P), bei der der Winkel zw. ES und EP maximal ist (0..360 Grad).

Winkel? Aha, Du hast also die Koordinaten der Punkte alle. Ja, dann gehts einfach.