Aussenlienine einer Gitterform finden
-
Ich bracuhe einen Weg, die bei einer Gitterform die punkte der Aussenlienine zu finden. Also wenn ich diese form hier habe:
http://cdlab2.fluid.tuwien.ac.at/LEHRE/TURB/Fluent.Inc/gambit2.1/help/html/modeling_guide/mgimage/fig_m_face_tripave.gifWie kann ich alle Punkte finden, die ich verbinden muss, um das ganze zu umschliessen? (möglichst in der korrekten Reihenfolge)
-
Das mag jetzt trivial klingen, aber: Eine Außenlinie zeichnet sich dadurch aus, dass auf einer Seite kein Teil der Form ist. Wenn du erst einmal eine Außenlinie hast, so grenzt (bei "normalen" Topologien) das nächste Element der Außenlinie an dieses.
Damit hat man es doch schon oder verstehe ich dein Problem nicht richtig?
-
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.
