Data Dependent Triangulation Project

Dipl.-Math. Stefan Rolf Paff / Paff InfoTec

Kontakt:
postmeister@ddtri.de

 

Data Dependent Triangulations


Problemstellung   Ergebnisse   Algorithmus 1   Algorithmus 2   Beispiele   Perspektiven   Nutzbarkeit   Modellierung   Zusammenfassung    

GLOBALE UND LOKALE OPTIMIERUNG

Will man eindeutige (eindimensionale) Werte in Abhängigkeit von einem zweidimensionalen Urbild darstellen, wie dieses z.B. bei Geländemodellen der Fall ist, so ist im mathematischen Sinne eine interpolierende Funktion f: R2 -> R zu finden.

Es bestehen verschiedene Möglichkeiten: Ein bewährtes Verfahren ist die exakte Interpolation der gegebenen Werte mittels kubischer Splines unter Ableitungsrandbedingungen über einer Triangulierung, d.h. einer vollständigen und kreuzungsfreien Verbindung der Knoten zu Dreiecken.
Kubische Splines gelten wegen ihrer hervorragenden numerischen und interpolatorischen Eigenschaften auf vielen Anwendungsgebieten als Mittel der Wahl. Die über jedem Dreieck entstehende Oberfläche ist stetig differenzierbar, also C1 und wird durch eine zusätzliche Interpolationsbedingung an den Wert im Dreiecksschwerpunkt eindeutig bestimmt.

Zur Triangulierung der Menge der Knoten wird im allgemeinen ein Standardverfahren verwendet, meistens die sogenannte Delaunay-Triangulierung, bei der in jedem Viereck aus zwei benachbarten Dreiecken der kleinste Winkel möglichst gewählt wird.

Der auf der konvexen Hülle einer definierten Knotenmenge interpolierende Spline enthält mit der Triangulierung dieser Knotenmenge noch einen im allgemeinen ungenutzten Freiheitsgrad, dessen Ausnutzung die Glattheit der Oberfläche insbesondere bei geringerer Feinheit der Knotenverteilung maßsgeblich beeinflussen kann. Unter Glattheit wird nicht eine bestimmte Differenzierbarkeitsordnung (z.B. C 1 oder C °° verstanden, da diese nicht sicherstellt, was man anschaulich unter glatt versteht, wie etwa das Beispiel der Funktion sin(1/x) zeigt, die für x = 0 unendlich-oft das Vorzeichen wechselt, sondern ein mathematisches Glattheitsmaß.

Für einige Anwendungen und Ausgangsdaten (Knoten und Werte) stellen Delaunay-Triangulierungen eine problemlose und ausreichende Basis für Interpolationen dar. Werden hingegen an die resultierenden Interpolationen höhere Glattheitsforderungen (etwa im Sinne von Differenzierbarkeitsordnungen oder Glattheitsfunktionalen) gestellt, oder sollen auf den Oberflächen andere Algorithmen aufsetzen (z.B. Isolinienverfahren), so ist eine Optimierung notwendig, die die Delaunay-Maxime aufgibt und die Triangulierung als Basis für die Interpolation den gegebenen Daten (also Knoten und Werten in denselben) anzupaßt. Man spricht in diesem Fall von datenabhängigen Triangulierungen.

Diese Optimierung kann theoretisch lokal oder global vorgenommen werden, also zu einem lokalen oder zu dem globalen Optimum führen. In der Praxis entfällt jedoch die Möglichkeit der globalen Optimierung, da deren Rechenaufwand mit der Anzahl der Knoten wie O(4n) wächst und für 100 Knoten bereits bis zu 1055 mögliche Triangulierungen durchgerechnet werden müßten. Die Bearbeitung eines Problems diese Größenordnung des Laufzeitverhaltens kann als fast unabhängig vom technologischen Stand unmöglich gelten. Auf einer problemspezifischen Rechenmaschine, die eine Triangulierung in einer Microinstruktion prüfen könnte, würde selbst bei 1040 Microinstruktionen pro Sekunde die Verarbeitung dann immer noch 108 Jahre dauern. Somit scheidet diese Betrachtungweise der Optimierung aus. Solange keine Möglichkeiten zur einschneidenden Effizienzverbesserungen der globalen Optimierung bekannt sind, bleibt also als zielführend nur der Weg der lokalen Optimierung .

Für die Optimierung der Triangulierung bezüglich der gegebenen Daten stehen zwei infinitesimale Glattheits-Kriterien zur Verfügung, ein

Aufgrund der Generierung von Gradienten spricht man auch von der Anwendung der lokalen oder globalen Gradientenmethode.

Für die Realisierung der lokalen Optimierung sind zwei verschiedene Algorithmen entwickelt worden, ein außerordentlich effizienter und äußerst leistungsfähiger Algorithmus (genannt: Verfahren 1), der in Testreihen in weit über 90% der Fälle Verbesserungen der Oberfläche brachte.

Ein weiterer, aufwendigerer Algorithmus (genannt: Verfahren 2), der auf den Ergebnissen des Verfahrens 1 aufsetzen kann, um auf weitere Verbesserungsmöglichkeiten zu untersuchen. Testreihen haben gezeigt, daß die Anwendung des Verfahrens 2 noch in über 15% der Fälle weitere Verbesserungen erbrachten.

Verfahren 1 und Verfahren 2 untersuchen lokale Strukturen unterschiedlichen Umfangs auf Verbesserbarkeit hinsichtlich des Glattheits-Kriteriums und sind in der Lage, pro Schritt je eine bzw. fünf Kanten der Triangulierung zu optimieren.

Zur Veranschaulichung erzielbarer Ergebnisse werden beispielhaft Graphiken gezeigt, die zum Teil durch die implementierten Programme erzeugt wurden.

   

ERZIELTE ERGEBNISSE

WAHL DER KNOTENMENGEN UND AUSGANGSFUNKTIONEN

Die Verfahren wurden mit beiden Gradientenmethoden, der lokalen und der globalen, getestet. Darüberhinaus wurden Vergleichsfunktionen konstruiert, und mit deren exakten Gradienten gerechnet. Weiter wurden Knotenfelder verschiedener Größe per Zufallsgenerator erstellt und andere konstruiert, darunter auch äquidistante. Die lokale Punkthäufigkeit der Knotenfelder wurde unterschiedlich gewählt. Weiter wurden Knotenfelder auf einzelne Vergleichs-Funktionen abgestimmt, in dem Sinne, daß um deren lokale Extrema herum in verschiedenen Mustern Punkte hinzugefügt wurden.

Bei den Vergleichs-Funktionen wurden neben verschiedenen einfacheren Funktionen vor allem solche Funktionen betrachtet, die lokale Extrema und Wendestellen bzw. -kurven oder Knickkanten enthalten. Es wurden Varianten von in einer oder beide Koordinatenrichtungen periodischen Funktionen durchgerechnet. Schließlich wurden Funktionen abschnittsweise definiert derart, daß deren stetige Zusammensetzung eine Knickkante entstehen läßt. In Fällen, in denen die Ableitung einer Funktion einen Pol besitzt, wurde mit dem Verhalten bei Umgehung des Pols durch entsprechende Wahl der Knoten wie auch mit Allokation der Pole unter Vorgabe einer großen endlichen Ableitung gerechnet. Ableitungen in durch abschnittsweise Definition erzeugten unstetigen Funktionen wurden als einseitiger Limes angegeben oder es wurden die Knoten so gewählt, daß die Unstetigkeitsstelle nicht alloziert wurde.

   

DER ALGORITHMUS Verfahren 1

Die Anwendung von Verfahren 1 auf eine Delaunay-Ausgangstriangulierung ist nahezu immer erfolgreich, unabhängig von der gewählten Gradientenmethode. Auch für "relativ glatte" Ausgangsfunktionen stellten sich fast immer Verbesserungen ein.
In vielen Fällen spiegelte der Graph der Interpolation über der mit Verfahren 1 behandelten Triangulierung die Verbesserung als Fehlen von Knickkanten wieder, welches in der graphischen Oberflächendarstellung gut erkennbar ist;

Die Abbildungen 1 und 2 zeigen je eine Graphik der zugehörigen Triangulierungen über dem identischen Knotenfeld.

Es ist gut zu erkennen, daß der Algorithmus Verfahren 1 deutliche Änderungen in der Struktur der Triangulierung vornimmt.

Unter den neuen Dreiecken ist in Abbildung 2, rechte Bildmitte, ist eines zu erkennen, welches besonders deutlich gegen die Delaunay-Maxime verstößt.

Die Abbildung 3, welche die Verbesserung durch Anwendung des Verfahrens 2 darstellt, zeigt großflächige Veränderungen mit einem deutlichen Trend. Die Kanten bewegen sich hier auf die Orthogonalität zum Gradienten hin. Die in dem hier gezeigten Fall erkennbare Eigenschaft ist jedoch kein allgemeines Entscheidungskriterium für Triangulierungsverbesserungen. In meinen Untersuchungen war es sogar weit von statistischer Signifikanz entfernt.

   

DER ALGORITHMUS Verfahren 2

In 300 ausgewählten Testfällen zeigten sich:

Es folgt eine Folge von Abbildungen zu den drei Verfahren für feste Gradientenmethode, Knotenfeld und Funktion.

Abb. 1 : DELAUNAY
Abb. 2 : Verfahren 1
Abb. 3 : Verfahren 2

Die Graphik Abb. 4 zeigt eine perspektivische Gitterdarstellung des Graphen der Interpolation über einer mit Verfahren 2 verbesserten Triangulierung eines nicht äquidistanten Knotenfeldes. Die roten Linien in der Graphik stellen den Graphen der Interpolation über der Triangulierung nach Verfahren 1 dar, dort wo er von der Interpolation über der mit Verfahren 2 verbesserten Triangulierung abweicht. Die Referenzfunktion bestand aus zwei aneinandergesetzten Ebenen. Hier läßt die graphische Darstellung der Interpolation mittels Verfahren 2 die aneinandergesetzten Ebenenstücke wesentlich besser erkennen als es die Interpolation gemäß Verfahren 1 erlaubt. die sich im Bereich mehrerer Dreiecke deutlich über der entsprechenden Ebene wölbt.

 

LAUFZEITVERHALTEN DER ALGORITHMEN

Die folgenden Angaben geben die Laufzeiten der Algorithmen Verfahren 1 und Verfahren 2 sowie eines Auswertungsteils einschließlich Fehleranalysemethoden für zwei unterschiedliche technologische Stände wieder:

CPU Verfahren 1 Verfahren 2 Auswertung
286-12/287-20 < 11 < 120 < 75
486-33 DX < 1,7 < 17 < 11
Pentium 60 < 0.6 < 6 < 4
Pentium 100 < 0.35 < 3.5 < 2.3

Größenordnungen der Laufzeiten in Sekunden für ein Testfeld mit 33 Knoten

Auf UNIX-Workstations, Power-PC, leistungsstarken Pentium-PC reduzieren sich die Laufzeiten entsprechend.

   

AUSGEWÄHLTE BEISPIELE

In diesem Kapitel wird anhand verschiedener Graphiken ein Eindruck vermittelt, wie Verbesserungen nach Verfahren 1 und Verfahren 2 die Oberflächen optimieren. In Abb. 3 ist eine Gegenüberstellung der Ausgangstriangulierung und der beiden Verbesserungen wiedergegeben.

Die darauffolgenden Abbildungen zeigen die graphischen Darstellungen verschiedener Interpolationen, jeweils als Vergleich der Verbesserung nach Verfahren 1 mit der Ausgangsoberfläche (1. Vergleich) bzw. als Vergleich der Verbesserung nach Verfahren 2 mit der Verbesserung nach Verfahren 1 (2. Vergleich). Die roten Linien zeigen die vorhergehende Interpolation, dort, wo sie von der Verbesserten abweicht.

Es werden fünf Beispiele gezeigt


Delaunay-Ausgangstriangulierung eines Knotenfeldes


QADJ-Verbesserung der obigen Ausgangstriangulierung


MADJ-Verbesserung der obigen Triangulierung


Hügel -
Delaunay / Verfahren 1


Hügel -
Verfahren 1 / Verfahren 2


Gpifel -
Delaunay / Verfahren 1


Beispiel 2: Gipfel -
Verfahren 1 / Verfahren 2


Beispiel 3: Muldenstruktur -
Delaunay / Verfahren 1


Beispiel 4: Äquidistant beprobter Bereich -
Delaunay / Verfahren 1


Beispiel 4: Äquidistant beprobter Bereich -
Verfahren 1 / Verfahren 2
Klar zu erkennen ist hier die Glättung an der linken Fußseite des Hügels.


Beispiel 5: Bruchkante -
Delaunay / Verfahren 1


Beispiel 5: Bruchkante -
Verfahren 1 / Verfahren 2

   

PERSPEKTIVEN FÜR WEITERE ARBEITEN

ÜBERTRAGBARKEIT

Die Algorithmen der Verfahren 1 und Verfahren 2 lassen sich beispielsweise auf das Problem der C0-Interpolation übertragen. Das Glattheitskriterium ist entsprechend der gegebenen Fragestellung abzuändern.

   

VORAUSSICHTLICHE NUTZBARKEIT DER TRIANGULIERUNGEN FšR ISOLINIEN-ALGORITHMEN

Oberflächen mit geschlossenen Darstellungen bilden grundsätzlich eine gute Basis für Isolinien-Algorithmen, da sie ein diskretes Vorgehen mit fast beliebiger Schrittweite genauso unterstützen wie Auswertung von Gradienten. Dabei muß davon ausgegangen werden, daß die Güte der Isolinien neben den zugrundeliegenden Knotenwerten stark von der Oberfläche abhängt, die erstere interpoliert. Es scheint evident, daß ein Isolinien-Algorithmus auf Oberflächen mit größerer Glattheit besser arbeitet als auf einer sehr un-'glatten' Oberfläche mit vermehrten und ausgeprägteren Wendepunkten und Extrema.

Es ist zu beobachten, daß lokale Extrema in der Interpolation, die nicht von den zu interpolierenden Knotenwerten vorgegeben waren, durch Verbesserung mit einem der Triangulierungs-Verbesserungsalgorithmus Verfahren 1 oder Verfahren 2 geringer ausfielen oder ganz entfielen, was für die Erstellung von Isolinien sicher von großem Wert ist.

Noch ungeprüft ist die Vermutung, daß Isolinien, die von einer C0-Oberfläche abgeleitet und dann mit einem Spline geglättet wurden, eine höhere Güte haben als Isolinien, die aus einer C1-Oberfläche erstellt wurden.

Voraussetzung ist in jedem Falle, daß die Triangulierung optimal gewählt wird, denn manche Fehlentscheidung eines Isolilien-Algorithmus, die durch ungünstige Kantenwahl entstand, ist mit geschlossenen algorithmischen Kriterien nicht mehr reversibel. Die Einführung einer guten Kostenfunktion (Analogon zum Glattheitsmaß der C1-Oberflächen) für C0-Oberflächen ist dabei von hoher Relevanz, da sie über die Kantenwahl und damit letztlich über die Eignung der Oberfläche als Basis für Isolinien-Algorithmen entscheidet.

Nach Einschätzung der Sachverhalte bietet eine C0-Oberfläche nach lokaler Optimierung mit einer Macro-Methode die optimale Basis für Isolinien.  

 

MODELLIERUNG VON GEGEBENEN KANTEN

An jeder Stelle der Anwendung der verschiedenen Triangulierungs-Verbesserungsalgorithmen kann ein Algorithmus zur Modellierung von naturgegebenen (z.B. Bachläufe) oder künstlichen (z.B. Straßen, Abbaukanten unter Tage) Kanten eingebaut werden, der die Triangulierung so verändert, daß eine vorgegebene Anzahl bestimmter Kanten realisiert wird. Die Triangulierungs-Verbesserungsalgorithmen können so modifiziert werden, daß sie diese Kanten entsprechend berücksichtigen.

 

 

ZUSAMMENFASSUNG

Die vorgestellten Algorithmen Verfahren 1 und Verfahren 2 erweisen sich als geeignet, Triangulierungen als Basis für Interpolationen auf endlichen zweidimensionalen Knotenmengen datenabhängig zu optimieren und erzielen, ihrem Rechenaufwand entsprechend, ausgezeichnete Ergebnisse. Sogar der Algorithmus Verfahren 2, welcher eine zusätzliche Verbesserungsmöglichkeiten auf der Basis des Verfahrens 1 darstellt, vermochte noch in vielen Fällen Verbesserungen von teilweise deutlich mehr als 30% vorzunehmen, in einzelnen Fällen erfolgte eine Verbesserung von bis zu 87 Prozent.

Aufgrund

  1. der gegebenen Verbesserungen im Sinne des mathematischen Glattheitskriteriums,
  2. der Minimierung nicht-datengegebener Extrema, sowohl nach Anzahl als auch nach deren Wert,
  3. der teils sehr deutlichen Reduzierung des nicht von den Daten gegebenen, Oszillationsverhaltens der Interpolation über der Delaunay-Triangulierung,
  4. der Reduzierung der Anzahl der Wendestellen und der Reduzierung des Ausmaßes des Krümmungswechsels und
  5. der größeren 'Natürlichkeit' der verbesserten Oberflächen

sind die schon mit recht geringem Aufwand durchführbare Verbesserung der Anpassung der Triangulierung an die gegebenen Daten in jedem Anwendungsfalle für angezeigt, handele es sich hierbei um Geländemodellierung oder Isolinienprobleme.

Es ergeben sich mehrere Möglichkeiten unterschiedlicher Effizienz und Effektivität. Aufgrund seines vergleichsweise geringen Aufwandes und seiner guten Effizienz empfiehlt sich der Algorithmus Verfahren 1 generell für eine Anpassung von Triangulierungen an gegebene Daten. Darüberhinaus stellt er eine gute Basis dar für die Anwendung komplexer und aufwendiger Verbesserungsalgorithmen wie z.B. Verfahren 2, da durch vorherige Anwendung von Verfahren 1 interne Schleifendurchläufe von Verfahren 2 eingespart werden können, wenn es gilt, eine energetisch möglichst gute datenabhängige Triangulierung zu finden.

Es bieten sich also die beiden Strategien der datenabhängigen Verbesserung von Triangulierungen an:

Für eine Anzahl von Anwendungen wird möglicherweise Variante 1 genügend gute Ergebnisse liefern.

Bei höheren Anforderungen gilt Variante 2 als Mittel der Wahl.

Das Konzept für eine Erweiterung des Algorithmus Verfahren 2 über die derzeitige Leistungsfähigkeit hinaus liegt bereits vor und kann im Bedarfsfall realisiert werden.

  1. [DLR] Dyn, Nira; Levin, David; Rippa, Samuel:
    Data dependent triangulations for piecewise linear interpolation; unveröffentlicht, Tel Aviv, December 1988
  2. [QS1] Quak, Ewald; Schumaker, Larry L.:
    Cubic Spline Fitting Using Data Dependend Triangulation, Preprint, 1989}
  3. [Far] Farin, G.:
    Bezier polynomials over triangles and the construction of piecewise $C^r$-polynomials, Report TR/91, Brunel University, Uxbridge, England, 1980}
  4. [QS2] Quak, Ewald; Schumaker, Larry L.:
    Calculation of the energy of a piecewise linear polynomial surface, in Algorithms for Approximation II, M.G. Cox and J.C.Mason, (eds.), Clarendon Press, 1989}
  5. [Ren] Renka, R.J.:
    Algorithm 624. Triangulation and interpolation at arbitraraly distributed points in the plane, ACM Trans. Math. Software 10 (1984)
  6. [Rip] Rippa, S.:
    Minimal roughness property of Delaunay triangulations, unveröffentlicht

  home


Paff InfoTec


Hier hin kommt der Text zu Belangen der Firma Paff InfoTec

  home


Data Dependent Triangulation Project


Hier hin kommt der Text zu Belangen des

  Private Homepage Dipl.-Math. Stefan Rolf Paff