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 dem Householder-Algorithmus gelöst. 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:
Modifizierte Tiefensuche
Sie ermittelt für den automatischen Messzug-Ausgleich diejenigen Messlinien, die Teil von Zyklen sind oder auf der Strecke zwischen Eingang und weiteren Referenzpunkten liegen:
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.