Aussenlienine einer Gitterform finden
-
Also in etwa so?:
Durch Alle Linien Loopen{
Normale der Line herausfinden
Prüfen ob auf beiden seiten punkte sind
wenn nein{
zu liste hinzufügen
}
}
Ok, könnte funktionieren, aber wie sortier ich sie, damit es ein aussenpfad wird?
-
SOrry das erwähnst du ja schon, habs ubersehen, sry, danke vielmals
-
Quowe schrieb:
Normale der Line herausfinden
Prüfen ob auf beiden seiten punkte sindNein, viel zu kompliziert. Und scheitert wahrscheinlich an verrückten Formen. Bei einem Dreiecksgitter würde ich dies benutzen: Eine Linie ist die direkte Verbindung zwischen zwei Punkten. Bei einer Außenlinie gibt es nur höchstens eine andere Verbindung zwischen den Punkten mit nur einer Zwischenstation. Bei einer Innenlinie gibt es hingegen immer zwei. Also:
-Punkt A nehmen
-Einen der Nachbarpunkte, B, wählen
-Alle anderen Nachbarpunkte von A durchgucken, ob sie auch Nachbarn von B sind
-Findet man man 1 oder weniger, so ist AB eine Außenlinie
-
OK, macht sinn, danke nochmals, ich probiers mal aus
-
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.
-
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.
-
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.
-
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?
-
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.
-
Ach das meinst du. Ich bin von Gittern ohne Schnittpunkten ausgegangen, wie im Beispiel des TE.
-
Ja, der graph ist planar. Jetzt tellst du dich aber grad ein bissel an, oder?
-
edit:
-
Klar geworden oder soll ich ein Bild malen?
-
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.
-
Jester schrieb:
Klar geworden oder soll ich ein Bild malen?
Ja. Peinlich, da dran nicht gedacht zu haben.
-
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 <=>.
-
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.
-
Wahrscheinlich ist es am einfachsten einen modifizierten Flood-Fill-Algorithmus zu verwenden.
-
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?
-
Ich glaube die zentrale Frage bleibt: Was ist die Eingabe?
Ein Bild oder ein Graph mit gegebenem Layout?
