Universit
¨
at Stuttgart
Fakult
¨
at Bauingenieur- und Vermessungswesen
Graphisch interaktive Eingabe und Darstellung eines
Gel
¨
andemodells mittels Delaunay-Triangulierung
cand.-Ing. Nico Rosenbusch
cand.-Ing. Gerd Schleupen
13. Dezember 2001
Informationsverarbeitung im konstruktiven Ingenieurbau
http://www.uni-stuttgart.de/iv-kib/
c
Informationsverarbeitung im konstruktiven Ingenieurbau
Die Verteilung dieses Dokuments in elektronischer oder gedruckter Form ist gestattet, solange
sein Inhalt einschließlich Autoren- und Copyright-Angabe unver
¨
andert bleibt und die
Verteilung kostenlos erfolgt, abgesehen von einer Geb
¨
uhr f
¨
ur den Datentr
¨
ager, den
Kopiervorgang usw.
Informationsverarbeitung im konstruktiven Ingenieurbau
Pfaffenwaldring 7
70550 Stuttgart
Tel.: (+49 711) 685-7048
Fax: (+49 711) 685-6602
http://www.uni-stuttgart.de/iv-kib/
INHALTSVERZEICHNIS I
Inhaltsverzeichnis
1 Einleitung 1
1.1 Die Vorlesung
”
Informatik im Bauwesen“ . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Darstellung von Gel
¨
andemodellen in der Geod
¨
asie . . . . . . . . . . . . . . . . . 1
2 Delaunay Triangulation 3
2.1 Idee der Delaunay Triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.1 Dreieck . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.2 Umkreiskriterium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Berechnung einzelner Dreiecke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.1 Werkzeug Richtungswinkel . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.2 Umlaufsinn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.3 Umkreisradius und Umkreismittelpunkt . . . . . . . . . . . . . . . . . . . 7
2.3 Vernetzung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.1 Sonderfall erstes Dreiecks . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.2 Abfrage ob Neupunkt innerhalb oder außerhalb des Netzes liegt . . . . . . 11
2.3.3 Abfrage nach s chon vorhandenem Punkt . . . . . . . . . . . . . . . . . . . 13
2.3.4 Neupunkt innerhalb des Netzes . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3.5 Neupunkt außerhalb des Netz es, aber in keinem Umkreis . . . . . . . . . 14
2.3.6 Neupunkt außerhalb des Netz es, aber mindestens in einem Umkreis . . . 15
3 GUI-Programmierung 19
3.1 MVC-Paradigma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 wxWindows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3 OpenGL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.1 Was ist OpenGL? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.2 Wie funktioniert OpenGL? . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4 Programmerl
¨
auterung 25
4.1 Aufbau und Programmstruktur . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1.1 DelaunayApp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1.2 DelaunayFrame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1.3 DelaunayView . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1.4 DelaunayModel und SimCom . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.1.5 Simplex2 und Simplex0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.1.6 DelaunayDialog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.1.7 MyGLFrame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.1.8 MyGLCanvas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2 Bedienung und Funktionsumfang . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2.1 Das Hauptfenster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.2.2 DelaunayLog - das Log Window . . . . . . . . . . . . . . . . . . . . . . . 31
4.2.3 Das Fenster Coordinates . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.2.4 Das Fenster OpenGL Frame . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5 Anhang A: Literaturverzeichnis 33
6 Anhang B: Programmcode 34
Autoren
Kapitel 1, 3, 4: Nico Rosenbusch
Kapitel 2: Gerd Schleupe n
1. Einleitung 1
1 Einleitung
1.1 Die Vorlesung
”
Informatik im Bauwesen“
Die hier vorliegende und b es chriebene Projektarbeit entstand im Rahmen der Vorlesung
”
Infor-
matik im Bauwe sen“ des Fachgebietes
”
Informationsverarbeitung im Konstruktiven Ingenieur-
bau“ unter der Leitung von Prof. Dr.-Ing. Stefan M. Holzer.
Ziel der Vorlesung die speziell angehende Programmentwickler ansprechen soll, ist es,
”
ein
kleines FE-Berechnungsprogramm zu entwickeln und dabei die Programmiersprache C/C++
kennenzulernen. Neben der Vorstellung numerischer Algorithmen werden Strategien zur Mo-
dellierung des Problems und z ur effizie nten Speicherung von Daten angeboten.“
1
Inhalt der Vorlesung im Sommersemester 2001 war die Graphentheorie sowie die damit ver-
bundene schrittweise Erstellung eines Programmes zur K
¨
urzeste-Wege-Suche am Beispiel des
Straßen- und St
¨
adtenetzes Deutschlands. Hierbei wurden u. a. die Algorithmen von
”
Dikstra“
und
”
Branch and Bound “ kennengelernt und umgesetzt. Aufbauend auf die in den praktischen
¨
Ubungen gewonnenen Kenntnisse im Umgang mit der objektorientierten Programmiersprache
C++ wurden anschließend von den Studenten Projektarbeiten zu ausgew
¨
ahlten Themen des
Ingenieurbaus erstellt. Das im Bereich der Vermessungskunde angesiedelte Thema unserer Pro-
jektarbeit ist die graphisch interaktive Eingabe und Darstellung eines Gel
¨
andemodells mit dem
Verfahren der Delaunay-Triangulierung.
Unserem Betreuer, He rrn Dipl-Ing. Martin Bernreuther, der uns w
¨
ahrend der Entwick-
lung des Programms f
¨
ur Fragen stets mit Antworten und L
¨
osungsvorschl
¨
agen zur Seite stand,
m
¨
ochten wir an dieser Stelle herzlich danken. Seinen interessanten Impulsen zur Weiterent-
wicklung einzelner Programmteile (z. B. OpenGL) wird in, auf diesem Programm aufbauenden,
Projekten nachgegangen.
1.2 Darstellung von Gel
¨
andemodellen in der Geo d
¨
asie
Ein allgemeiner Wunsch vieler Ingenieurwissenschaften wie z. B. dem Bauingenieurwesen oder
der Luft- und Raumfahrttechnik ist es heute, die Erdoberfl
¨
ache f
¨
ur verschiedene Ziele m
¨
oglichst
genau darzustellen. Die Realisierung von Computeranwendungen zur virtuellen Planung von
Infrastrukturmaßnahmen oder f
¨
ur ferngesteuerte und automatisierte Navigation im Straßen-,
Schiffs- und Luftverkehr nehmen mit der Weiterentwicklung leistungsf
¨
ahiger Rechensysteme
auch zuk
¨
unftig immer mehr an Bedeutung zu. Daraus resultiert nat
¨
urlich der Bedarf an Daten
zur komplexen und dreidimensionalen Beschreibung, sowie zur Visualisierung der topographi-
schen Gegebenheiten der Erdoberfl
¨
ache, einschließlich vorhandener Bebauung, Gew
¨
assern und
Verkehrsnetzen.
Als Methoden zur Datengewinnung mittels 3D-Vermessung seien hier nur kurz die weit-
gehend automatisierten Techniken Tachymetrie, Photogrammetrie und die Satellitengeod
¨
asie
(GPS-Positionierung) erw
¨
ahnt. Auf deren exakte Beschreibung wird hier jedoch verzichtet und
auf ausf
¨
uhrliche B ehandlungen in entsprechender Literatur verwiesen.
Heutzutage gibt es, bedingt durch die Entwicklung der Informationstechnologie, neben den
seit vielen Jahrzehnten genutzten analogen Verfahren zum Erstellen von Abbildern der Erd-
oberfl
¨
ache weitaus effektivere digitale M
¨
oglichkeiten.
Bei der analogen Darstellung von Gel
¨
andemodellen in Form von topographischen Pl
¨
anen
und Landkarten gibt es f
¨
ur die Visualisierung der dritten Koordinate (H
¨
ohenko ordinate) ver-
schiedene Verfahren. Bei den H
¨
ohenkoten sind die H
¨
ohendaten an ausgew
¨
ahlten Punkten des
Gel
¨
andes angegeben. Die zweite M
¨
oglichkeit stellen die sogenannten B
¨
oschungsschraffen dar.
Dabei wird durch Schattenwirkungen, verbunden mit speziellen Farbgebungen, ein plastischer
Eindruck der Szenerie vermittelt. Eine weitere einfache und gebr
¨
auchliche Art der H
¨
ohendar-
stellung in Karten ist die Verwendung von H
¨
ohenlinien. Wie die Bezeichnung schon erahnen
l
¨
aßt, werden dabei Gel
¨
andepunkte, die sich auf gleicher H
¨
ohe befinden, mit Linien verbunden.
Sollen bei der analogen Darstellung weitere Punkte durch großfl
¨
achige manuelle Interpolation
bestimmt werden, stellen sich die oben genannten Verfahren meist als sehr zeit- und kostenin-
tensiv heraus. Bei der elektronischen Erfassung und Darstellung von Erdoberfl
¨
achen benutzt
1
Vorlesungen und Lehrveranstaltungen des IV-KIB im Internet: http://www.uni-stuttgart.de/iv-kib/
1. Einleitung 2
man heute Digitale Gel
¨
andemodelle, die genau wie die analogen Formen eine idealisierte Dar-
stellung der realen Welt bieten und konkretisierend in H
¨
ohen- und Situationsmodell unterteilt
werden k
¨
onnen. Im Zusammenhang mit dem Digitalen Situationsmodell (DSM), das vor allem
die als Grundriss bezeichneten Informationen speichert, sei der Lese r auf die stadtplanerischen
Aspekte der Nutzung von Gel
¨
andemodellen hingewiesen.
Definition nach [RB96]: Als Digitales
Gel
¨
andemodell (DGM) bezeichnet man die
Menge der digital gespeicherten dreidimensio-
nalen Koordinaten der Punkte sowie der Al-
gorithmen zum
¨
Ubergang von den diskreten
Punkten auf Kurven und Fl
¨
achen.
Bei der Erstellung von Digitalen Gel
¨
andemodellen kann im Prinzip von einer Einteilung in
zwei Gruppen, der Gittermethode und der Dreiecksmethode ausgegangen werden. Bei der Git-
termethode wird ausgehend von den ungleichm
¨
aßig verteilten vorhandenen Daten durch hoch-
wertige Interpolation ein regelm
¨
aßiges Gitter erstellt. Die Dreiecksmethode wiederum nutzt
die Prim
¨
ardaten selbst zur Dreiecksvermaschung, an die verschiedene Anforderungen gestellt
sein k
¨
onnen.
”
So kann gefordert werden, dass die Summe aller Dreiecksseiten zum Minimum
wird oder dass innerhalb des Umkreises um drei Punkte, die ein Dreieck bilden, kein weiterer
Punkt liegt. Ebenso sind andere Forderungen denkbar. Am bekanntesten ist die Delaunay-
Triangulation, die ein eindeutiges Dreiecksnetz ergibt.“ [RB96]
