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:

Berechnung des ersten Messpunkts

Alle weiteren Messpunkte ergeben sich aus den Daten der Messzüge: Länge, Azimut und Neigung, jeweils bezogen auf den Referenzpunkt:

Berechnung der weiteren Messpunkte

Die einzelnen Darstellungen (Grundriss, Längsschnitt, Profil, Perspektive) bedienen sich anschließend nur noch der so berechneten Werte:

Verwendung der berechneten Werte in den Darstellungen

Siehe Berechnung & Qualität → Messzug-Berechnung.

Perspektivische Darstellung

Mit Hilfe einer Reihe von Transformationen werden die Höhlen- in Bildschirmkoordinaten umgerechnet:

Transformationskette von Höhlen- zu Bildschirmkoordinaten

Jede Transformation wird in einer 4×4-Matrix definiert, die zu einer Transformations-Matrix multipliziert werden:

4x4-Transformationsmatrizen

Alle Messpunkt-Vektoren werden mit der Transformations-Matrix multipliziert. An dieser Stelle sind keine trigonometrischen Berechnungen mehr erforderlich:

Multiplikation der Messpunkt-Vektoren

Zum Schluss wird mit der Division durch w die Perspektive eingerechnet und die Punkte können am Bildschirm angezeigt werden:

Perspektivische Division durch w

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:

Kameraparameter als Stützstellen

Benachbarte Splines schneiden die gemeinsame Stützstelle und besitzen dort gleiche Steigung und Krümmung:

Bedingungen an den Stützstellen

Durch die Lösung eines linearen Gleichungssystems können die Koeffizienten der kubischen Gleichung ermittelt und alle Werte zwischen den Stützstellen berechnet werden:

Koeffizienten der kubischen Gleichung

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:

Konvexe Hülle nach Jarvis March

Quelle: Gift-Wrapping-Algorithmus (Wikipedia)

Die längste Verbindung zwischen den Eckpunkten der konvexen Hülle ergibt die Ausdehnung der Höhle:

Längste Verbindung zwischen den Eckpunkten

Siehe Berechnung & Qualität → Auswertung.

Kurven zeichnen

Per Maus oder Tablet gezeichnete Linien werden effizient als Polygone gespeichert und als wohlgeformte Kurven ausgegeben:

Gezeichnete Linie als Polygon

Die eingegebenen Linien werden mit dem Ramer-Douglas-Peucker-Algorithmus gefiltert und geglättet. Dadurch wird die zu speichernde Datenmenge minimiert:

Filterung nach Ramer-Douglas-Peucker

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:

Stütz- und Kontrollpunkte der Bézierkurven

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:

Schraffur als einzelne Linien

Dazu werden alle Schnittpunkte zwischen den Umrandungslinien (blau) und einer Schar von Linien (hellblau) berechnet:

Schnittpunkte zwischen Umrandung und Linienschar

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:

Muster aus einzelnen Symbolen

Durch den Punkt-in-Polygon-Test nach Jordan wird ermittelt, wie viele Schnittpunkte zwischen einem Strahl und den Umrandungslinien bestehen:

Strahl und Schnittpunkte mit der Umrandung

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:

Überbestimmtes lineares Gleichungssystem

Pro Referenzpunkt und Messlinie wird eine Gleichung aufgestellt (hier für die x-Koordinaten):

Gleichung je Referenzpunkt und Messlinie

Die Koeffizienten der Gleichungen werden in eine Matrix übernommen:

Koeffizientenmatrix

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:

Zyklen im Höhlennetz

Weitere Infos: Zyklus (Wikipedia)

Dijkstra-Algorithmus

Bei der Abstandsmessung wird der kürzeste Weg zwischen zwei Messpunkten mit dem Dijkstra-Algorithmus berechnet:

Kürzester Weg nach Dijkstra

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:

MIP-Map mit 18 Zoom-Ebenen

Quelle: MIP Mapping (Wikipedia)

Aus der Größe des darzustellenden Bereiches wird die Zoom-Ebene (z) ermittelt:

Berechnung der Zoom-Ebene

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:

Berechnung der Kachelnummern

Siehe Visualisierung → Kartenansichten.

Meridiankonvergenz

Die Meridiankonvergenz gibt den Winkel zwischen geografisch Nord und dem UTM-Gitter an:

Winkel zwischen geografisch Nord und UTM-Gitter

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:

Berechnung der Meridiankonvergenz

Um eine Höhle, die nach geografisch Nord vermessen wurde, im UTM-Gitter anzuzeigen, muss jeder Messpunkt um die Meridiankonvergenz gedreht werden:

Drehung der Messpunkte um die Meridiankonvergenz

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.

Siehe Berechnung & Qualität → Nordausrichtung.