Post on 06-Apr-2016
transcript
Geländemodelle
Constraint Delaunay Triangulations
Martin Buhlmann
Erinnerung
Über Voronoi zu Delaunay
• Voronoi-Diagramme
• Delaunay-Triangulation
• empty-circle-Kriterium
Voronoi/Delaunay-Konstruieren
MotivationBeispiel eines DGM mit Constrained Delaunay Triangulation
Ausschnitt
Constrained Delaunay
Ziel ist eine dynamische Fortführung eines triangulierten digitalen Geländemodells
• zB Landkarten müssen aufgrund geomorphologischer Gegebenheiten neu trianguliert werden
• diese können „Grenzen“, die die Triangulation nicht schneiden sollte, definieren (vgl Bsp letzter Vortrag, Strassenkante)
• Lösung: Einfügen vordefinierter Kanten mit Bedingungen
Triangulation erfolgt nicht mehr allein über eine Punktmenge, sondern zusätzlich über vordefinierte Kanten!
Anwendung in digitalen Geländemodellen:
- geologische Verwerfungen
- Entwässerungskanäle
- Strassenkanten
- ...
Constrained triangulations(bedingte Triangulation)
Einfaches Beispiel:
Bergkamm - Talkante
• wegen Delaunay-Eigenschaft immer Bergkamm
• für Talkante muss eine vordefinierte Kante festgelegt werden
• annähernde Gleichwinkligkeit der Dreiecke nicht mehr garantiert
• ist die Menge der vordefinierten Kanten leer, entspricht die bedingte Delaunay-Triangulation der „einfachen“
• visibility (Sichtbarkeit)
• positive Eigenschaften der Delaunay-Triangulation bleiben erhalten, werden nur an vordefinierten Kanten abgeschwächt
Eigenschaften
Def.: ein Punkt heisst sichtbar zu einem anderen Punkt, falls das geschlossene Liniensegment zwischen diesen beiden Punkten keine vordefinierte Kante schneidet
• Vordefinierte Kanten sind also „Sichthindernisse“
• wichtig für empty-circle-Kriterium
• erfüllt, auch wenn nicht sichtbarer Punkt im Umkreis
Sichtbarkeit
sichtbar
nicht sichtbar
Beispiel bedingte Delaunay-Triangulation aus einem Planaren Graph
Constrained Delaunay
Beispiele
• Auch Polygone mit bedingten Kanten als Grenzen möglich
• Triangulation innerhalb der Polygone nicht dargestellt
• Bsp Flurstück
Zusammenhang beschränkte Voronoi-Diagramme und Constrained-Delaunay
Konstruktion: 2 Punkte werden genau dann durch eine Kante miteinander verbunden, wenn die beschränkten Voronoi-Regionen dieser Punkte eine gemeinsame Kante teilen. Ausgenommen sind die vordefinierten Kanten (sowohl für das Voronoi-Diagramm als auch für die Triangulation vorgegeben)
Problem: die rot dargestellten Kanten der Triangulation werden darüber aber nicht erfasst!
=> das beschränkte Voronoi-Diagramm definiert damit lediglich eine Teilmenge der Constrained Delaunay-Triangulation
Beschränkte Voronoi-Diagramme
Bedingte Voronoi-Diagramme• eindeutige Konstruktion nicht möglich
• Lösung: bedingte Voronoi-Diagramme
• dazu Erweiterung der Definition der Nachbarschafts-regionen nötig
• dadurch Überschneidung der Regionen möglich
Das durch den einzufügenden Punkt beeinflußte Gebiet wird hier über das lokale empty-circle-Kriterium unter Berücksichtigung der Sichtbarkeit bestimmt.
Retriangulierung bei Einfügen eines Punktes
• Einfügen von geländeorientierten oder benutzerdefinierten Kanten
• Beeinflußt alle Dreiecke, die von der bedingten Kante geschnitten werden
• Das lokale empty-circle-Kriterium anderer Dreiecke wird nicht verletzt
• einfaches Beispiel mit Methoden zum Einfügen und retriangulieren:
Einfügen bedingter Kanten
Einfügen einer bedingten Kante1. Insert-Constraint
2. First-Intersected-Triangle
3. Next-Intersected-Triangle
Einfügen einer bedingten Kante
4. Nicht konvexes Viereck!
5. Retriangulation trotz Schneidens der bedingten Kante
6. Auch hier noch mehrere Schritte nötig
Einfügen einer bedingten Kante
7. - 9. Weitere Retriangulationsschritte
10. Methode Optimize stellt die Delaunay-Eigenschaft wieder her
Löschen bedingter Kanten
• In der Literatur nicht erwähnt
• warum auch vordefinierte Kanten löschen?
• Aber zur konsistenten Fortführung nötig
Problem:
bedingte Kanten haben kein Bezug zum lokalen Delaunay-Kriterium! Daher keine rekursive Retriangulation möglich
• Vordefinierte Kanten können zu nicht tragbaren Qualitätsverlusten führen!
• treten z.B. bei einer als politische Grenze vordefinierten Kante auf!
• Grenzen repräsentieren selten morphologische Kanten, => schnell unscharfe oder gar falsche Darstellungen
• komplexere Modellierungen führen zu grösseren Ungenauigkeiten
Nachteile der CDT
Beispiel
Man erkennt in der 3-D-Darstellung, dass die bedingte Kante ein Tal offenbart (d) wo in der Natur keines ist (c)
Lösungsansatz(konforme Delaunay-Triangulation)
• Zerlegung der vordefinierten Kante in kleinere Segmente
• dadurch Einfügen zusätzlicher Punkte nötig
• allgemein als Steiner-Punkte bezeichnet