Mathematik
Dieses Kapitel zeigt, welche mathematischen Verfahren hinter CaveRenderPro stecken – von der Messzug-Berechnung über die 3D-Darstellung bis zum Ringschlussausgleich. Für die Bedienung des Programms musst du davon nichts wissen; wer verstehen möchte, was im Hintergrund passiert, findet hier die Verfahren mit Quellenangaben.
Messzug-Berechnung
Der erste Messpunkt einer Höhle wird aus den Höhlendaten berechnet – aus Breite, Länge und Höhe des Eingangs:
Alle weiteren Messpunkte ergeben sich aus den Daten der Messzüge: Länge, Azimut und Neigung, jeweils bezogen auf den Referenzpunkt:
Die einzelnen Darstellungen (Grundriss, Längsschnitt, Profil, Perspektive) bedienen sich anschließend nur noch der so berechneten Werte:
Siehe Berechnung & Qualität → Messzug-Berechnung.
Perspektivische Darstellung
Mit Hilfe einer Reihe von Transformationen werden die Höhlen- in Bildschirmkoordinaten umgerechnet:
Jede Transformation wird in einer 4×4-Matrix definiert, die zu einer Transformations-Matrix multipliziert werden:
Alle Messpunkt-Vektoren werden mit der Transformations-Matrix multipliziert. An dieser Stelle sind keine trigonometrischen Berechnungen mehr erforderlich:
Zum Schluss wird mit der Division durch w die Perspektive eingerechnet und die Punkte können am Bildschirm angezeigt werden:
Siehe Visualisierung → Darstellungstypen.
Kameraflug mit kubischen Splines
Für einen Kameraflug können Kamerapositionen festgelegt werden. Die Parameter (X, Y, Z, Azimut, Neigung, Abstand) dienen als Stützstellen für die kubischen Splines:
Benachbarte Splines schneiden die gemeinsame Stützstelle und besitzen dort gleiche Steigung und Krümmung:
Durch die Lösung eines linearen Gleichungssystems können die Koeffizienten der kubischen Gleichung ermittelt und alle Werte zwischen den Stützstellen berechnet werden:
Weitere Infos: Kubische Splines (arndt-bruenner.de)
Siehe Visualisierung → Animation.
Horizontale Ausdehnung
Zur performanten Berechnung der horizontalen Ausdehnung einer Höhle wird die konvexe Hülle mit dem Jarvis-March-Algorithmus (Gift-Wrapping) ermittelt:
Quelle: Gift-Wrapping-Algorithmus (Wikipedia)
Die längste Verbindung zwischen den Eckpunkten der konvexen Hülle ergibt die Ausdehnung der Höhle:
Siehe Berechnung & Qualität → Auswertung.
Kurven zeichnen
Per Maus oder Tablet gezeichnete Linien werden effizient als Polygone gespeichert und als wohlgeformte Kurven ausgegeben:
Die eingegebenen Linien werden mit dem Ramer-Douglas-Peucker-Algorithmus gefiltert und geglättet. Dadurch wird die zu speichernde Datenmenge minimiert:
Quelle: Douglas-Peucker-Algorithmus (Wikipedia)
Aus den Polygonen werden die Stütz- und Kontrollpunkte für kubische Bézierkurven berechnet. Die Kurven werden durch die grafische Oberfläche interpoliert und ausgegeben:
Quelle: Bézier-Interpolation
Siehe Zeichnungen & Pläne → Elemente zeichnen.
Schraffuren
Um den Höhlenplan als Vektorgrafik zu erhalten, müssen Schraffuren durch einzelne Schraffurlinien dargestellt werden:
Dazu werden alle Schnittpunkte zwischen den Umrandungslinien (blau) und einer Schar von Linien (hellblau) berechnet:
Im Beispielfall schneidet die rote Linie viermal die Umrandung. Jeweils zwei Schnittpunkte bilden eine Schraffurlinie (fett).
Siehe Zeichnungen & Pläne → Wasser und Gewässer.
Muster
Um einen Höhlenplan als Vektorgrafik zu erhalten, müssen Muster durch Symbole dargestellt werden:
Durch den Punkt-in-Polygon-Test nach Jordan wird ermittelt, wie viele Schnittpunkte zwischen einem Strahl und den Umrandungslinien bestehen:
Ist die Anzahl der Schnittpunkte ungerade, so wird das Symbol in das Muster aufgenommen.
Weitere Infos: Punkt-in-Polygon-Test nach Jordan (Wikipedia)
Siehe Zeichnungen & Pläne → Muster.
Ringschlussausgleich
Um den Ringschlussausgleich zu berechnen, muss zur Minimierung der quadratischen Fehler ein überbestimmtes lineares Gleichungssystem gelöst werden:
Pro Referenzpunkt und Messlinie wird eine Gleichung aufgestellt (hier für die x-Koordinaten):
Die Koeffizienten der Gleichungen werden in eine Matrix übernommen:
Zur Berechnung der neuen x-Koordinaten wird das lineare Gleichungssystem mit einer dünn besetzten QR-Zerlegung (Givens-Rotationen) gelöst. Nur die tatsächlich verbundenen Messpunkte gehen in die Rechnung ein, dadurch bleibt der Aufwand auch bei großen Netzen gering. Die Berechnung der weiteren Koordinaten (y, z, l, p) erfolgt analog.
Weitere Infos: Überbestimmte Gleichungssysteme (tm-mathe.de)
Siehe Berechnung & Qualität → Ausgleich.
Graphentheorie
Versteht man das Höhlennetz als ungerichteten Graphen – Messpunkte als Knoten, Messlinien als Kanten –, lassen sich zwei Verfahren einsetzen:
Brückensuche
Sie ermittelt für den Messzug-Ausgleich diejenigen Messlinien, die Teil von Zyklen sind oder auf der Strecke zwischen Eingang und weiteren Referenzpunkten liegen. Eine Messlinie liegt genau dann in einem Zyklus, wenn sie keine Brücke des Graphen ist:
Weitere Infos: Zyklus (Wikipedia)
Dijkstra-Algorithmus
Bei der Abstandsmessung wird der kürzeste Weg zwischen zwei Messpunkten mit dem Dijkstra-Algorithmus berechnet:
Startpunkt, Endpunkt und Abstand werden in der Statuszeile angezeigt – siehe Erste Schritte → Die Statuszeile.
Weitere Infos: Dijkstra-Algorithmus (Wikipedia)
Kartenkacheln
Bei OpenTopoMap wird die Weltkarte in rund 23 Milliarden Bitmaps zu je 256 × 256 Pixeln auf 18 Ebenen bereitgestellt – einer sogenannten MIP-Map:
Quelle: MIP Mapping (Wikipedia)
Aus der Größe des darzustellenden Bereiches wird die Zoom-Ebene (z) ermittelt:
Aus Länge und Breite des Bereichsmittelpunkts wird die Nummer der zentralen Kartenkachel (x, y) berechnet. Die Nummern der benachbarten Kacheln können durch Addition bestimmt werden:
Siehe Visualisierung → Kartenansichten.
Meridiankonvergenz
Die Meridiankonvergenz gibt den Winkel zwischen geografisch Nord und dem UTM-Gitter an:
Grafik aus „Wissen wo – Orientierung im Gelände mit Karte und GPS", Springer-Verlag
Karten im UTM-Gitter sind an den Hauptmeridianen ausgerichtet (… 15°W, 9°W, 3°W, 3°E, 9°E, 15°E …). Die Meridiankonvergenz kann aus Länge und Breite des Höhleneingangs berechnet werden:
Um eine Höhle, die nach geografisch Nord vermessen wurde, im UTM-Gitter anzuzeigen, muss jeder Messpunkt um die Meridiankonvergenz gedreht werden:
CaveRenderPro erledigt das über Berechnen → Nord → UTM-Gitter, wobei die Konvergenz für jeden Eingang einzeln berechnet wird.
Der berechnete Wert steht im Höhlendaten-Dialog im Feld Meridian. Für höhlenübergreifende Zeichnungen muss die Nordausrichtung auf UTM-Gitter stehen.