Wo wird die Delaunay-Methode angewendet? Leere-Ball-Methode nach Delaunay. Konstruktion im Allgemeinen. Es gibt auch Abschnitte, die die Algorithmen zum Erstellen von Triangulationen im Detail beschreiben, ihre vergleichenden Eigenschaften und die Komplexität der Algorithmen angeben.

Räumliche Delaunay-Triangulation

Das Problem des Aufbaus eines Netzwerks nicht überlappender Dreiecke ist eines der grundlegenden in der Computergeometrie und wird in Computergrafik- und Geoinformationssystemen häufig zur Oberflächenmodellierung und Lösung räumlicher Probleme verwendet.

Das Problem der Konstruktion eines Netzes nicht überlappender Dreiecke wurde erstmals 1934 in Arbeiten des sowjetischen Mathematikers B. N. Delone gestellt, der auch die entsprechenden Bedingungen formulierte.

In der Mathematik wird das Problem der Konstruktion einer Triangulation durch gegebene Punkte das Problem ihrer paarweisen Verbindung durch sich nicht schneidende Segmente genannt, so dass ein Netzwerk von Dreiecken entsteht. Seine Hauptelemente sind (Abbildung 5.3): Knoten (Dreiecksecken), Kanten (Seiten) und Flächen (eigentliche Dreiecke). Die konstruierte Triangulation kann konvex sein (wenn dies das minimale Polygon ist, das den Simulationsbereich abdeckt), nicht-konvex (wenn die Triangulation nicht konvex ist) und optimal (wenn die Summe der Längen aller Kanten minimal ist).

Ein Netzwerk aus solchen Dreiecken wird als Delaunay-Triangulation bezeichnet, wenn es bestimmte Bedingungen erfüllt:

Keiner der Startpunkte liegt innerhalb des beschriebenen Kreises um ein beliebiges Dreieck (Abb. 5.3);

Die Triangulation ist konvex und erfüllt die oben formulierte Delaunay-Bedingung;

Die Summe der minimalen Winkel aller Dreiecke ist das Maximum aller möglichen Triangulationen;

Die Summe der Radien der um die Dreiecke umschriebenen Kreise ist die kleinste aller möglichen Dreiecke.

Das erste der obigen Kriterien zum Konstruieren einer Delaunay-Triangulation, Kreisform genannt, ist eines der Hauptkriterien und wird für jedes Paar von Dreiecken mit gemeinsamen Flächen überprüft. Die mathematische Interpretation des Kriteriums folgt aus Abb. 5.3:

(5.2)

Es gibt viele Möglichkeiten, die Delaunay-Triangulation zu konstruieren, die in letzter Zeit eine der beliebtesten Methoden zum Konstruieren eines Triangulationsnetzes ist. Es wird in vielen GIS-Systemen zum Erstellen von Geländemodellen verwendet.

Übertragen auf den zweidimensionalen Raum wird es wie folgt formuliert: Ein System miteinander verbundener, nicht überlappender Dreiecke hat den kleinsten Umfang, wenn keine der Ecken in einen der beschriebenen Kreise um die gebildeten Dreiecke fällt (Abb. 5.4).

Reis. 5.4. Delaunay-Triangulation

Dies bedeutet, dass die gebildeten Dreiecke in einer solchen Triangulation möglichst gleichseitig sind und jede der Seiten der gebildeten Dreiecke von der gegenüberliegenden Spitze aus unter dem maximalen Winkel von allen möglichen Punkten der entsprechenden Halbebene sichtbar ist. Dies ist genau die optimale Triangulation, an deren Rändern normalerweise linear interpoliert wird, um Isolinien zu konstruieren.

Viele Algorithmen zum Konstruieren einer Delaunay-Triangulation verwenden den folgenden Satz.

Satz 1. Die Delaunay-Triangulation kann aus jeder anderen Triangulation auf demselben Punktsystem erhalten werden, indem Paare benachbarter Dreiecke ABC und BCD, die die Delaunay-Bedingung nicht erfüllen, nacheinander in Dreieckspaare ABD und ACD umgebaut werden (Abb. 5.5).

Reis. 5.5 Wiederaufbau von Dreiecken, die die Delaunay-Bedingung nicht erfüllen

Dieser Wiederherstellungsvorgang wird oft als Flip bezeichnet. Dieser Satz erlaubt es, eine Delaunay-Triangulation sequentiell zu konstruieren, indem man zunächst eine Triangulation konstruiert und diese dann sukzessive im Sinne der Delaunay-Bedingung verbessert. Beim Prüfen der Delaunay-Bedingung für Paare benachbarter Dreiecke kann man die Definition direkt verwenden, aber manchmal werden andere Methoden basierend auf den oben aufgeführten Bedingungen verwendet.

Unter diesen Bedingungen erscheint die Gesamtcharakteristik der gesamten Triangulation (die Summe der minimalen Winkel oder die Summe der Radien), durch deren Optimierung man die Delaunay-Triangulation erhalten kann.

Wie oben erwähnt, ist eine der wichtigsten Operationen, die beim Konstruieren einer Triangulation durchgeführt wird, die Überprüfung der Delaunay-Bedingung für gegebene Dreieckspaare. Basierend auf der Definition der Delaunay-Triangulation und den entsprechenden Bedingungen werden in der Praxis üblicherweise mehrere Nachweisverfahren verwendet:

- Überprüfung durch die Gleichung des umschriebenen Kreises;

– Prüfung mit einem vorberechneten Umkreis;

– Prüfung der Summe gegenüberliegender Winkel;

ist eine modifizierte Überprüfung der Summe entgegengesetzter Winkel.

Viele Systeme testen mit einem vorberechneten Umkreis. Die Hauptidee des Algorithmus zum Überprüfen vorberechneter Kreise besteht darin, für jedes konstruierte Dreieck den Mittelpunkt und den Radius des umschriebenen Kreises vorab zu berechnen, wonach die Überprüfung der Delaunay-Bedingung auf die Berechnung der Entfernung reduziert wird zum Mittelpunkt dieses Kreises und vergleiche das Ergebnis mit dem Radius. Der Mittelpunkt und der Radius r eines Kreises, der herum beschrieben wird, kann gefunden werden als , , , r 2 = (b 2 + c 2 - 4ad)/4a 2 , wobei die Werte A B C D definiert durch Formeln (5.3)

(5.3)

Eine andere Möglichkeit, die Gleichung für diesen Kreis zu schreiben, ist:

(5.5.)

(5.6)

Dann ist die Delaunay-Bedingung für nur dann erfüllt, wenn für jeden anderen Triangulationspunkt gilt:

(x 0 – x C) 2 + (y 0 – y C) 2 ≥ r 2 . (5.7)

Gegenwärtig gibt es viele Algorithmen zum Konstruieren der Delaunay-Triangulation. Viele der bekannten Algorithmen verwenden die Definition der Delaunay-Triangulation als sekundäres Merkmal der Triangulation. Daher haben solche Algorithmen folgende Schwächen:

- Algorithmen verwenden ständig berechnete trigonometrische Funktionen, was den Prozess drastisch verlangsamt;

- Beim Studium der Beziehung zwischen Punkten und dem Basissegment treten sehr kleine Winkel auf, und bei der Verwendung trigonometrischer Funktionen besteht aufgrund der begrenzten Genauigkeit der Datendarstellung in einem Computer die ständige Gefahr des Verschwindens der Ordnung und der Division durch 0. diese Situation erfordert eine ständige zusätzliche Verarbeitung.

Die bekanntesten Softwareprodukte bauen die Delaunay-Triangulation unter Verwendung des Satzes leerer Kugeln als Hauptprinzip zum Konstruieren von Dreiecken auf. Der Algorithmus sieht folgendermaßen aus:

– die ganze Punktmenge wird in Dreiecke geteilt, d.h. Kombinationen aus drei Punkten werden erstellt;

– für jede Kombination werden der umschriebene Kreis und die Koordinaten seines Mittelpunkts gefunden;

- wenn sich kein einziger Punkt von den verbleibenden innerhalb des Kreises der aktuellen Kombination befindet, dann ist diese Kombination ein Dreieck - Teil der Delaunay-Triangulation.

Zu den Vorteilen dieses Algorithmus gehören:

– keine Verwendung trigonometrischer Funktionen, was den Bauprozess nicht verlangsamt;

– direkte Konstruktion der Delaunay-Triangulation, ohne Vorkonstruktionen;

– Einfachheit aller Berechnungen und Transformationen;

- Infolgedessen wird das Triangulationsnetz durch viele Dreiecke dargestellt, nicht durch einzelne Linien.

Die so konstruierte Triangulation ist die geometrische Grundlage für die Konstruktion von Isolinien.

Algorithmen zur Konstruktion der Delaunay-Triangulation können in eine Reihe von Gruppen eingeteilt werden, die sich in der Struktur der verwendeten Eingabedaten, der Anzahl der Rechenoperationen, den Anfangsannahmen usw. unterscheiden. Betrachten wir einige davon.

Zusammenführungsalgorithmen beinhalten das Aufteilen einer Menge von Anfangspunkten in Teilmengen, das Erstellen einer Triangulation auf jedem von ihnen und das Kombinieren dieser Punkte zu einem einzigen Netzwerk. Die Essenz eines dieser Algorithmen ist wie folgt.

Der Satz von Anfangspunkten wird durch vertikale Linien in zwei oder mehr Teile geteilt, wonach jeder von ihnen durch horizontale und vertikale Linien in ungefähr gleiche Teile geteilt wird. Als Ergebnis wird der gesamte Bereich der Anfangspunkte in Grundelemente von drei oder vier Punkten unterteilt (Abb. 2.4), auf denen ein oder zwei Dreiecke aufgebaut sind.

Das Zusammenführen dieser Dreiecke zu einem einzigen Netzwerk erfolgt durch Konstruieren von zwei Basislinien (P 0 P 1 und P 2 P 3, Reis. 5.7.a), Zeichnen von Kreisen mit variablem Radius, die auf der Mittellinie senkrecht zur Grundlinie zentriert sind (Abb. 5.7, b), Suchen nach einem Knoten, der auf den Kreis fällt (Punkt EIN, Reis. 5.7. c) und die Konstruktion eines neuen Dreiecks (P 0 P 1 A). In diesem Fall kann es erforderlich sein, ein bereits vorhandenes Dreieck zu löschen (z. P0AB).

Iterative Algorithmen basieren auf der Idee der sequentiellen Hinzufügung von Punkten zu einer teilweise konstruierten Triangulation mit gleichzeitiger Verbesserung und Neuaufbau gemäß den Delaunay-Kriterien. Im Allgemeinen umfassen sie mehrere Schritte und laufen darauf hinaus, ein Dreieck auf den ersten drei Startpunkten zu bauen und mehrere Optionen zum Platzieren des nächsten Punkts zu erkunden. Insbesondere werden Optionen in Betracht gezogen, um es über die Grenze des Modellierungsbereichs hinaus, auf einen vorhandenen Knoten oder eine Kante, in ein konstruiertes Dreieck usw. zu bringen. Jede dieser Optionen beinhaltet die Durchführung einer bestimmten Operation: Teilen einer Kante in zwei, einer Fläche in drei usw.; Danach werden die resultierenden Dreiecke auf Einhaltung der Delaunay-Bedingung und der erforderlichen Umordnungen überprüft.

Algorithmen mit zwei Durchgängen liefern zunächst eine Konstruktion einer gewissen Triangulation, ignorieren die Delaunay-Bedingungen und bauen sie dann gemäß diesen Bedingungen neu auf. Ein Beispiel für die Anwendung des Algorithmus ist in Abb. 1 gezeigt. 5.8.

Um das erstellte Reliefmodell dem realen anzunähern, werden zusätzliche Elemente eingeführt, die die Berücksichtigung und Anzeige seiner linearen und flächenhaften Strukturelemente sicherstellen. Solche zusätzlichen Elemente sind die in der Topographie weit verbreiteten Strukturlinien, die das "Reliefskelett" definieren: Wassereinzugsgebiete, Talwege, Grate, Klippen, Felsvorsprünge, Seen, Schluchten, Küstenlinien, Grenzen künstlicher Strukturen usw., deren Gesamtheit z es war der Rahmen der Delaunay-Triangulation. Diese Bruchkanten werden als Kanten von Dreiecken in die Triangulation eingebracht, wodurch die Modellierung echter Reliefelemente vor dem Hintergrund der allgemeinen Rauhigkeit der Erdoberfläche erreicht wird. Solche Kanten werden als strukturell (fest, nicht rekonstruierbar) bezeichnet, schneiden die Kanten anderer Dreiecke nicht und ändern sich anschließend nicht.

Die Aufgabe, ein Oberflächenmodell unter Berücksichtigung von Bruchkanten zu konstruieren, wird als Delaunay-Triangulation mit Einschränkungen bezeichnet, wenn die Delaunay-Bedingungen für jedes Paar benachbarter Dreiecke erfüllt sind, die nicht durch Bruchkanten getrennt sind. Die Forscher glauben, dass eine solche Triangulation am effektivsten mit iterativen Algorithmen konstruiert wird.

Ein Fragment der Delaunay-Triangulation mit zusätzlichen darin enthaltenen Elementen ist in Abb. 5.9, wo Knoten, Kanten, Flächen und Bruchkanten auf der rechten Seite und Bruchkanten des Geländes (Küstenlinien, Schluchtenränder usw.) und Punkte mit bekannten Markierungen auf der linken Seite angezeigt werden.

Algorithmen zum Konstruieren der Delaunay-Triangulation werden mit einer reellen oder ganzzahligen Darstellung der Koordinaten der Knoten implementiert, was die Geschwindigkeit und Genauigkeit der Verarbeitung erheblich erhöhen kann, aber zu Problemen beim Auffinden und Eliminieren von passenden Knoten führt.

Das TIN-Modell lässt sich leicht bearbeiten, indem Knoten verschoben, neue eingefügt, vorhandene gelöscht, die Position einer oder mehrerer Kanten geändert, neue Bruchkanten eingefügt usw. werden. Solche Änderungen wirken sich immer auf eine kleine Gruppe benachbarter Dreiecke aus und müssen nicht vollständig neu erstellt werden Netzwerk und werden im Online-Modus ausgeführt, indem Sie mit dem Cursor auf das entsprechende Element zeigen .

Über Genauigkeit:

Beim Platzieren von Latten auf charakteristischen Reliefelementen (z. B. Wasserscheiden und Talwegen) ignorieren wir kleinere Elemente dazwischen. Beim Konstruieren von Höhenlinien1 entlang solcher Dreieckskanten tritt ein Fehler auf, der von der Größe der Unebenheit des Reliefs und dem Neigungswinkel des Geländes abhängt. Beispielsweise sollte der durchschnittliche Fehler der Reliefvermessung 1/3 des Reliefquerschnitts bei Oberflächenneigungswinkeln von 2 bis 10 Grad nicht überschreiten. Es lässt sich berechnen, dass bei einem Entlastungsquerschnitt von 0,5 m der Grenzwert der übersehenen Unebenheit (d. h. die Abweichung der Erdoberfläche von einer durch benachbarte Latten verlaufenden Geraden) nicht größer als (0,5/3)*cos10 sein sollte °=0,16 m.

Für die Genauigkeit der Bestimmung des Volumens des bewegten Bodens ist auch die Fläche wichtig, die das nicht berücksichtigte Reliefdetail einnimmt. Angenommen, in einem Quadrat von 20 x 20 m zwischen zwei Lattenpaaren befindet sich eine zylindrische Ausbuchtung mit einer maximalen Höhe von 0,15 m. Es ist leicht zu berechnen, dass ihre Vernachlässigung bei der Darstellung dieser Fläche mit nur zwei Dreiecken zu einem Fehler von ungefähr 40 führt m3. Nicht so sehr, aber für ein Grundstück von 1 ha, das sich auf einem Hügel oder im oberen (normalerweise konvexen) Teil des Hangs befindet, erhalten Sie bereits 40 * 25 = 1000 m3 überschüssige Erde. Wenn Pfähle doppelt so oft (dh alle 10 m) genommen werden, verringert sich der Fehler um das Vierfache und beträgt 250 m3 pro Hektar. Dieser Faktor kann im Vorfeld berücksichtigt werden, da die Positivformen des Flachreliefs meist konvex und die Negativformen konkav ausgebildet sind. Wenn das zu vermessende Gebiet ungefähre Daten zum Relief hat, können der Krümmungsradius der Oberfläche und die erforderliche Lattendichte leicht aus den Werten der Höhenlinien oder einzelnen Erhebungen berechnet werden.

20. August 2012 um 22:41 Uhr

Optimierung des Algorithmus zur Überprüfung der Delaunay-Bedingung durch die Umkreisgleichung und deren Anwendung

Ich verrate Ihnen das Geheimnis, wie Sie die Delaunay-Bedingung für zwei Dreiecke schnell überprüfen können.
Eigentlich ist die Optimierung selbst etwas weiter unten beschrieben (siehe "Optimierung des Algorithmus zur Überprüfung der Delaunay-Bedingung durch die Gleichung des umschriebenen Kreises"), aber ich werde Ihnen alles der Reihe nach erzählen.

In meinem Fall wird die Triangulation bei der Bildverfolgung verwendet, um die Ebene in primitive Sektoren (Dreiecke) zu unterteilen. Wie Sie wissen, ist es auch in mehrere Schritte unterteilt: Anpassung, Erkennung von Grenzen, Umfahren von Grenzen, Ausfegen von Konturen. Dies ist im allgemeinsten Sinne. Ich möchte, glaube ich, bei der schwierigsten Phase aufhören: dem Fegen des Flugzeugs.

Am Eingang

Nachdem ich die Grenzen am Ausgang erkannt und umgangen hatte, bekam ich viele Außenkonturen. Jede sich berührende Kontur hat eine andere Farbe. Jede solche Kontur enthält auch eine bekannte Anzahl interner Konturen.
Unter dem Gesichtspunkt des „Sweeping the plane“ haben wir also, wenn wir die Außenkonturen getrennt betrachten, eine Menge von Punkten, die jeweils rechts und links einen Nachbarn haben. Jene. alle Punkte in der Kette sind geschlossen, es gibt keinen einzigen „hängenden“ Punkt, und jede der Ketten enthält mindestens 3 Punkte (Abbildung 1).

Bild 1

Was tun müssen

Es ist notwendig, die Figur mit Dreiecken zu fegen.

Suche

Nachdem ich das Buch gelesen hatte, fand ich keinen einzigen (mindestens einen) Weg, eine Delaunay-Triangulation zu konstruieren, die für meinen Fall zumindest einigermaßen geeignet wäre. Ich habe nicht nach anderen Büchern gesucht. Ja, und das war genug, sie brachte die Gedanken meines Kopfes in Ordnung. Als Ergebnis erfand er sein eigenes "Fahrrad".

Algorithmus

1) Nehmen wir für den Anfang an, dass es in der betrachteten Figur nur eine Sequenz gibt. Dann läuft alles auf die sequentielle Aufnahme von Dreiecken hinaus. Wir nehmen einen beliebigen Punkt und versuchen mit benachbarten Punkten ein Dreieck zu bauen. Wenn es nicht möglich war, ein Dreieck zu bauen (die Linie, die diese beiden Punkte verbindet, schneidet sich mit den bereits gebauten oder die Linie verläuft in der Sperrzone (Abbildung 2), bewegen wir uns zum benachbarten Punkt, sagen wir nach rechts. Wenn der nächste Dreieck gefunden wird, fügen wir es der Liste hinzu (Abbildung 3) und der Punkt, an dem es erstellt wurde, wird gelöscht (Abbildung 4).

Figur 2

Figur 3

Figur 4

Noch etwas: Beim Speichern des nächsten Dreiecks müssen die Eckpunkte im Uhrzeigersinn (im rechten Koordinatensystem) aufgezeichnet werden. Dies wird in Zukunft nützlich sein, um Rechenressourcen zu reduzieren.

2) Wiederholen Sie Schritt 1, bis wir das gesamte Flugzeug gefegt haben.

3) Bei mehreren Sequenzen, d.h. eine, und darin befinden sich eine oder mehrere Innenkonturen (Abbildung 1). Hier ist jede Sequenz einzeln zu betrachten. Nehmen wir eine andere innere Kontur. Aus einer äußeren und einer inneren machen wir zwei einzelne Konturen. Dazu müssen Sie zwei "Ports" von einem Stromkreis zum anderen finden. Die Bedingung für die "Ports": Sie sollten sich nicht schneiden (sie sollten nicht einmal die Enden berühren), sie sollten sich nicht mit den Konturlinien schneiden (Abbildung 5).

Abbildung 5

Abbildung 6
4) Als nächstes sollten Sie der Reihe nach alle internen Sequenzen in die bereits gebildeten, voneinander getrennten (Punkt 3) Sequenzen einfügen. Sie müssen mit derjenigen zusammenführen, die die neue enthält. Per Definition berührt oder überschneidet sich keine interne Sequenz mit anderen (entweder eine externe oder alle möglichen internen Sequenzen), sodass alles reibungslos ablaufen wird.
Nachdem die Ports gefunden wurden (Abbildung 6), ist es einfach, neue Sequenzen zu erstellen und sie mit den Punkten 1 und 2 des aktuellen Algorithmus zu umgehen (Abbildung 7).

Abbildung 7

5) Nach der 4. Stufe haben wir eine Liste von Dreiecken (Abbildung 8). Als hätten wir die Aufgabe schon bewältigt, aber es bleibt noch, das Bild schön zu machen: Überprüfen Sie die Erfüllung der Delaunay-Bedingung (Abbildung 9).

Abbildung 8

Abbildung 9

6) Mit Blick auf die Zukunft erzähle ich Ihnen vom sechsten Punkt. Es besteht aus einem sequentiellen Durchlaufen der Liste der empfangenen Dreiecke nach Punkt Nr. 5. Zuerst markieren wir alle Dreiecke als „schmutzig“. In jedem Zyklus überprüfen wir die Delaunay-Bedingung für jedes Dreieck. Wenn die Bedingung nicht erfüllt ist, bauen wir neu und markieren die Nachbarn und das aktuelle Dreieck als „dirty“. Wenn die Bedingung erfüllt ist, markieren Sie sie als sauber. In meiner Implementierung des Algorithmus hat jedes Dreieck eine Verbindung zu seinen Nachbarn. In diesem Fall arbeitet der 6. Punkt am schnellsten.

Mehr zur fünften Etappe

Nun, soweit ich weiß, gibt es zwei Möglichkeiten, um festzustellen, ob Dreiecke die Delaunay-Bedingung erfüllen oder nicht: 1) Überprüfen Sie die Summe der entgegengesetzten Winkel. Er muss kleiner als 180 sein. 2) Berechnen Sie den Mittelpunkt des umschriebenen Kreises und berechnen Sie die Entfernung zum 4. Punkt. Jeder weiß, dass die Delaunay-Bedingung erfüllt ist, wenn der Punkt außerhalb des umschriebenen Kreises liegt.

Rechenleistung Nr. 1: 10 Multiplikations-/Divisionsoperationen und 13 Additions-/Subtraktionsoperationen.
Rechenleistung #2: 29 Multiplikationen/Divisionen und 24 Additionen/Subtraktionen.

Aus Sicht der Rechenleistung, die beispielsweise im Buch berechnet wird, ist Option Nummer 1 rentabler. Und er erkannte es, wenn nicht für ... (Abbildung 10). Wie sich herausstellte, gab es Unsicherheit, nachdem diese Methode auf das „Förderband“ gelegt worden war. Dies ist eine Option, wenn der Winkel A selbst größer als 180 Grad ist. Es wird in dem Buch als eine der separaten privaten Methoden behandelt. Und damit verschwinden all seine Eleganz, Transparenz und Leistungsfähigkeit. Und auch später stellte sich heraus, dass Methode Nr. 2 ganz erheblich optimiert werden kann.

Abbildung 10

Optimierung des Algorithmus zur Überprüfung der Delaunay-Bedingung durch die Kreisgleichung

Was folgt, ist reine Mathematik.

Also haben wir:
Die Überprüfung der Bedingung für den Punkt M(X, Y) durch die Gleichung eines Kreises, der durch die Punkte A(x1, y1), B(x2, y2), C(x3, y3) verläuft, kann wie folgt geschrieben werden:

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ Zeichen a ≥ 0

Details finden Sie in dem ausgezeichneten Buch. (Nein, ich bin nicht der Autor)
Zeichen a ist also das Zeichen der Durchlaufrichtung, ich habe von Anfang an Dreiecke im Uhrzeigersinn gebaut, damit es weggelassen werden kann (ist gleich eins).

A(x1 - X, y1 - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);

D >= 0

Abbildung 11

Ist es nicht?

Laut dem Buch noch einmal

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)* (y1*x2 - x1*y2)<= 0

Wir haben: 15 Multiplikations-/Divisionsoperationen und 14 Additions-/Subtraktionsoperationen.

Vielen Dank für Ihre Aufmerksamkeit. Ich warte auf Kritik.

Literaturverzeichnis

1. Skvortsov A.V. Delaunay-Triangulation und ihre Anwendung. - Tomsk: Verlag Bd. un-ta, 2002. - 128 p. ISBN 5-7511-1501-5

GRID-Modelle sind Modelle regulärer Zellen.

Lassen Sie das Koordinatensystem
und und
. Benutzersätze
und Abtastschritte
.

,

- Physikalische Koordinaten des Punktes.

Berechnung
und
,
- Bitraster.

- quantisierte Werte. Real:

- Algorithmusparameter - die Anzahl der Punkte, - Last. Je näher der Punkt, desto größer das Gewicht.

- Entfernungsgrad (1 oder 2).

Normalisierungsfaktor:

Wie näher an 1, desto mehr gewichtete Punkte werden berücksichtigt.

Dies ist die IDW-Methode - lang, für jedes t müssen Nachbarn gefunden werden. Eine Reihe von Nachbarn kann effizient gefunden werden – die nächsten. Jeder der Punkte erzeugt einen "Stift" einer bestimmten Höhe. Viel hängt von der Unregelmäßigkeit des Setzens des Punktes ab, dafür nehmen sie
oder
jene. in Sektoren aufteilen und in der Nähe des Punktes bauen.

Vorteil– Einfachheit

Mangel:

------Ticket 14. Blechmodell. Delaunay-Triangulationsalgorithmen ------

1) Triangulation (Zinn).

Triangulation– Konstruktion einer Funktion in Form einer Menge stückweise linearer Funktionen

Triangulation– Interpolation innerhalb des konvexen Bereichs.

Triangulation ist ein planarer Graph, dessen Innenkanten alle Dreiecke sind; eine Möglichkeit, den Raum in Form von Dreiecken darzustellen, die aneinandergrenzen, ohne sich zu überlappen. Die Triangulation basiert auf mehreren Wegen auf einer Reihe von Punkten.

Wir brauchen einen Algorithmus, um eine optimale Triangulation aufzubauen.

Eine Ebene, die durch 3 Punkte geht.

1) Finden Sie ein Dreieck, das
;

2)
- Wir bauen die Gleichung der Ebene auf.

Um zu überprüfen, ob sich die Punkte innerhalb des Dreiecks befinden oder nicht, müssen Sie den Wert in die Gleichung der Linien einsetzen - die Kanten des Dreiecks. Wenn alle 3 Gleichungen > 0, dann innen.

Struktur ansehen:

Jede Triangulation enthält die gleiche Anzahl von Dreiecken.

, wo ist die Anzahl der internen Punkte,
- Punktzahl.

Gierige Triangulation.

Wir verbinden alle Punkte mit Kanten, wählen das Minimum aus und fügen zur Triangulation hinzu. Als nächstes nehmen wir das nächste Minimum, das sich nicht mit den vorherigen schneidet, und so weiter. Das Ergebnis ist eine gierige Triangulation.

Delaunay-Triangulation.

Punkte anderer Dreiecke fallen nicht in einen Kreis, der um irgendein Dreieck herum umschrieben ist. Auf eine Weise gebaut.

Ein Flip ist ein Flip von Kanten. Sie können damit von herkömmlicher Triangulation auf Delaunay-Triangulation umschalten. Um zu prüfen, ob ein Punkt zu einem Kreis gehört: ersetzen Sie if< R, то внутри.

Delaunay-Zustand.

Kreisgleichung durch drei Punkte:

Wenn kleiner als Null, dann extern, sonst - intern.

ist die Delaunay-Bedingung.

Der Algorithmus zur Konstruktion der Delaunay-Triangulation:

1) Hinzufügen von Punkten wird untersucht ist ein einfacher iterativer Algorithmus:

Es gibt einen Satz
zum Dreieck hinzufügen, wird die Konstruktion ausgeführt
Teilung eines Dreiecks
Wiederaufbau. In der Nullphase fügen wir 3-4 fiktive Punkte hinzu, die offensichtlich unseren Umschlag abdecken, alle Punkte sind drinnen. Nachdem wir einen Punkt geworfen haben, sehen Sie sich an, welches Dreieck er getroffen hat, teilen Sie es in 3, für jedes Dreieck überprüfen wir die Delaunay-Bedingung und kehren die Kanten um. Die durchschnittliche Anzahl der Rebuilds beträgt drei.

Theoretische Komplexität

2) Beschleunigungsmethoden. Basierend auf statistisch abhängigen Punkten. Das Startdreieck ist das Dreieck, in das der vorherige Punkt gefallen ist. Dann verbinden wir zwei Punkte - den vorherigen und den neuen.

Wir bewegen uns vom ersten Punkt zum nächsten.

Um die Qualität der konstruierten Triangulation zu quantifizieren, definieren wir zwei Arten von Kriterien, topologische und geometrische.

Das topologische Kriterium basiert auf den nächsten Nachbarn eines Punktes aus einer Menge. Idealerweise hat ein Punkt 6 Nachbarn für eine 2D-Region und 12 Nachbarn für eine 3D-Region. Wir erhalten eine topologische Schätzung unter Verwendung von Formel (1), wobei die Gesamtzahl der Punkte in der Region der Grad oder die Anzahl benachbarter Punkte ist, die mit einem internen Punkt verbunden sind.

Das geometrische Kriterium basiert auf der Differenz zwischen Innen- und Außenkreis um das berechnete Dreieckselement. Wir erhalten eine geometrische Schätzung unter Verwendung von Formel (2), wobei die Anzahl der Dreiecke ist, der Radius des einbeschriebenen Kreises ist, der Radius des umschriebenen Kreises ist.

Algorithmen zur Konstruktion von Triangulation

Es gibt eine große Anzahl von Algorithmen zum Konstruieren von Triangulation. Sie unterscheiden sich in Aufwand, Komplexität der Implementierung auf einem Computer und Konstruktionsansätzen. Mehr über Algorithmen erfahren Sie im Buch von A.V. Skwortsova. Betrachten wir einige Algorithmen.

Einer der ersten vorgeschlagenen Gieriger Algorithmus Aufbau einer Triangulation. Eine Delaunay-Triangulation heißt gierig, wenn sie mit einem gierigen Algorithmus erstellt wird. Die Komplexität des Greedy-Algorithmus mit einigen seiner Verbesserungen beträgt . Aufgrund der großen Komplexität in der Praxis wird es fast nie verwendet. Betrachten Sie den Algorithmus Schritt für Schritt:

Schritt 1. Eine Liste aller möglichen Liniensegmente, die Paare von Quellpunkten verbinden, wird erzeugt und nach der Länge der Segmente sortiert.

Schritt 2 Beginnend mit dem kürzesten werden Segmente sequentiell in die Triangulation eingefügt. Wenn sich das Segment nicht mit anderen zuvor eingefügten Segmenten schneidet, wird es eingefügt, andernfalls wird es verworfen.

Beachten Sie, dass, wenn alle möglichen Segmente unterschiedliche Längen haben, das Ergebnis dieses Algorithmus eindeutig ist, ansonsten hängt es von der Einfügereihenfolge von Segmenten gleicher Länge ab.

Iterativer Algorithmus basieren auf einer sehr einfachen Idee, Punkte sukzessive zu einer teilweise konstruierten Delaunay-Triangulation hinzuzufügen. Die Komplexität dieses Algorithmus besteht aus dem Aufwand ein Dreieck zu finden, dem im nächsten Schritt ein Punkt hinzugefügt wird, dem Aufwand neue Dreiecke zu konstruieren, sowie dem Aufwand des entsprechenden Neuaufbaus der Triangulationsstruktur als Ergebnis unbefriedigend Überprüfungen von Paaren benachbarter Dreiecke der resultierenden Triangulation für die Delaunay-Bedingung. Betrachten Sie den Algorithmus Schritt für Schritt:

Schritt 1. An den ersten drei Startpunkten bauen wir ein Dreieck.

Schritt 2 Führen Sie in der Schleife für alle anderen Punkte die Schritte 3-5 aus.

Schritt 3 Der nächste -te Punkt wird der bereits konstruierten Triangulationsstruktur wie folgt hinzugefügt. Zuerst wird der Punkt lokalisiert, d.h. es gibt ein Dreieck (früher konstruiert), in das der nächste Punkt fällt. Oder, wenn der Punkt nicht in die Triangulation fällt, gibt es ein Dreieck am Rand der Triangulation, das dem nächsten Punkt am nächsten liegt.

Schritt 4 Trifft ein Punkt auf einen zuvor eingefügten Triangulationsknoten, so wird ein solcher Punkt in der Regel verworfen, ansonsten wird der Punkt als neuer Knoten in die Triangulation eingefügt. Wenn der Punkt auf eine Kante trifft, wird er außerdem in zwei neue geteilt, und beide an die Kante angrenzenden Dreiecke werden ebenfalls in zwei kleinere geteilt. Wenn der Punkt strikt innerhalb eines Dreiecks liegt, wird er in drei neue geteilt. Wenn der Punkt außerhalb der Triangulation liegt, werden ein oder mehrere Dreiecke gebildet.

Schritt 5 Es werden lokale Überprüfungen der neu erhaltenen Dreiecke auf Einhaltung der Delaunay-Bedingung durchgeführt und die notwendigen Umlagerungen durchgeführt.

Beim Konstruieren neuer Dreiecke sind zwei Situationen möglich, wenn der hinzugefügte Punkt entweder innerhalb oder außerhalb der Triangulation liegt. Im ersten Fall werden neue Dreiecke konstruiert und die Anzahl der vom Algorithmus ausgeführten Aktionen festgelegt. In der zweiten müssen außerhalb der aktuellen Triangulation zusätzliche Dreiecke gebaut werden, deren Anzahl im schlimmsten Fall gleich sein kann? 3. Es werden jedoch nicht mehr als Dreiecke für alle Schritte des Algorithmus hinzugefügt, wobei die Gesamtzahl der Anfangspunkte ist. Daher beträgt in beiden Fällen die Gesamtzeit, die für den Aufbau von Dreiecken aufgewendet wird.

Kettenalgorithmus Einer der ersten effizienten Triangbasiert auf einem Regularisierungsverfahren für planare Graphen und monotoner Polygontriangulation. Die Komplexität dieses Algorithmus besteht darin, wo die Anzahl der Anfangssegmente ist. Betrachten Sie den Algorithmus Schritt für Schritt:

Schritt 1. Aus dem Satz anfänglicher Struktursegmente bilden wir einen zusammenhängenden planaren Graphen (Abbildung 4, a).

Schritt 2 Der Graph ist regularisiert, d.h. neue Kanten werden hinzugefügt, die andere nicht schneiden, so dass jeder Scheitelpunkt des Graphen benachbart zu mindestens einem Scheitelpunkt darüber und einem darunter wird. Die Regularisierung erfolgt in zwei Durchgängen unter Verwendung eines vertikalen flachen Sweeps. Im ersten Durchlauf von unten nach oben finden wir sequentiell alle Knoten, von denen keine Kante nach oben führt. Auf (Abbildung 4, b) ist dies zum Beispiel Vertex B. Wenn wir eine horizontale Linie zeichnen, finden wir die nächstgelegenen Kanten der AD- und EF-Graphen, die von ihr auf der linken und rechten Seite gekreuzt werden. Dann finden wir den untersten Eckpunkt im DEHG-Viereck und ziehen eine Kante von B hinein.In ähnlicher Weise wird der zweite Durchgang von oben nach unten durchgeführt (Abbildung 4, c). Als Ergebnis dieses Schritts wird jeder Bereich des planaren Graphen zu einem monotonen Polygon.

Schritt 3 Jeder Bereich des Diagramms muss in Dreiecke unterteilt werden. Dazu können Sie den Algorithmus der nicht-konvexen Verschmelzung zweier Triangulationen verwenden (Abbildung 4, d).

Abbildung 4. Funktionsschema des Triangulationskettenalgorithmus: a) - Anfangssegmente; b - Übergang von unten nach oben der Graphregularisierung; c) - Durchgang von oben nach unten; d) - Triangulation von monotonen Polygonen

Um den Kettenalgorithmus zu implementieren, verwenden Sie am besten Datenstrukturen, in denen Kanten explizit dargestellt werden, wie z. B. „Doppelkanten“ oder „Knoten, Kanten und Dreiecke“.

Der Nachteil des Kettenalgorithmus ist, dass über die Form der resultierenden Triangulation im Voraus nichts gesagt werden kann. Dies ist keine optimale Triangulation, keine Greedy-Triangulation und keine eingeschränkte Delaunay-Triangulation. Der Kettenalgorithmus kann sehr lange längliche Dreiecke erzeugen.

Um die Qualität der resultierenden Triangulation zu verbessern, können alle Paare benachbarter Dreiecke, die nicht durch eine Strukturkante getrennt sind, auf die Erfüllung der Delaunay-Bedingung überprüft und ggf. neu aufgebaut werden. Als Ergebnis erhält man eine Delaunay-Triangulation mit Restriktionen.

Grundlegende Definitionen und Eigenschaften

Eine Triangulation ist ein planarer Graph, dessen Innenbereiche alle Dreiecke sind.

Eigenschaften:

· Die Delaunay-Triangulation entspricht eins zu eins dem Voronoi-Diagramm für dieselbe Punktmenge.

· Daraus folgt: Liegen keine vier Punkte auf demselben Kreis, ist die Delaunay-Triangulation eindeutig.

· Die Delaunay-Triangulation maximiert den minimalen Winkel unter allen Winkeln aller konstruierten Dreiecke, wodurch "dünne" Dreiecke vermieden werden.

· Die Delaunay-Triangulation maximiert die Summe der Radien der eingeschriebenen Kugeln.

· Delaunay-Triangulation minimiert das diskrete Dirichlet-Funktional.

· Die Delaunay-Triangulation minimiert den maximalen Radius der minimal umschließenden Kugel.

· Die Delaunay-Triangulation auf einer Ebene hat die minimale Summe der Radien von Kreisen, die um Dreiecke herum unter allen möglichen Triangulierungen umschrieben sind.

Abb. 1. Triangulation.

Eine konvexe Triangulation ist eine solche Triangulation, bei der das kleinste Polygon, das alle Dreiecke umschließt, konvex ist. Eine Triangulation, die nicht konvex ist, heißt nicht konvex.

Die Aufgabe, eine Triangulation aus einer gegebenen Menge zweidimensionaler Punkte zu konstruieren, ist das Problem, gegebene Punkte mit sich nicht schneidenden Segmenten so zu verbinden, dass eine Triangulation entsteht.

Eine Triangulation erfüllt die Delaunay-Bedingung, wenn keiner der gegebenen Triangulationspunkte in den Kreis fällt, der um ein konstruiertes Dreieck herum umschrieben ist.

Eine Triangulation heißt Delaunay-Triangulation, wenn sie konvex ist und die Delaunay-Bedingung erfüllt.

Abb. 2. Delaunay-Triangulation.

Leere-Ball-Methode nach Delaunay. Konstruktion im Allgemeinen

Nehmen wir einen leeren Ball, den wir bewegen, indem wir seine Größe so ändern, dass er die Punkte des Systems (A) berühren kann, aber immer leer bleibt.

Legen wir also eine leere Delaunay-Kugel in das Punktesystem (A). Dies ist immer möglich, wenn der Ball klein genug gewählt wird. Beginnen wir damit, den Radius zu vergrößern und die Mitte des Balls an Ort und Stelle zu lassen. Irgendwann trifft die Oberfläche des Balls auf einen Punkt i des Systems (A). Das wird auf jeden Fall passieren, denn unendlich große Hohlräume gibt es in unserem System nicht. Wir werden den Radius der leeren Kugel weiter vergrößern, sodass der Punkt i auf ihrer Oberfläche verbleibt. Dazu müssen Sie die Mitte des Balls von Punkt i aus verschieben. Früher oder später wird die Kugel mit ihrer Oberfläche einen anderen Punkt des Systems (A) erreichen.

Abb. 3

Delaunay-Simplizes füllen den Raum ohne Lücken und Überschneidungen.

Die beschriebene Sphäre eines Simplex enthält keine anderen Punkte des Systems im Inneren.

Dies sei Punkt j. Lassen Sie uns den Radius unseres Balls weiter vergrößern und beide Punkte auf seiner Oberfläche halten. Der Ball steigt an und erreicht einen dritten Punkt des Systems, Punkt k. Im zweidimensionalen Fall wird unser "leerer Kreis" in diesem Moment fixiert, d.h. es wird unmöglich, seinen Radius weiter zu vergrößern, während der Kreis leer bleibt. Gleichzeitig offenbaren wir eine elementare zweidimensionale Konfiguration von drei Punkten (i, j, k), die ein bestimmtes Dreieck definiert, dessen Besonderheit darin besteht, dass es keine anderen Punkte des Systems (A) innerhalb seines umschriebenen gibt Kreis. In drei Dimensionen wird ein Ball nicht durch drei Punkte definiert. Lassen Sie uns seinen Radius weiter vergrößern und alle drei gefundenen Punkte auf seiner Oberfläche behalten. Dies ist möglich, bis die Kugeloberfläche den vierten Punkt l des Systems trifft. Danach wird die Bewegung und das Wachstum eines leeren Balls unmöglich. Die gefundenen vier Punkte (i, j, k, l) bestimmen die Eckpunkte des Tetraeders, der dadurch gekennzeichnet ist, dass es innerhalb seiner umschriebenen Sphäre keine weiteren Punkte des Systems (A) gibt. Ein solches Tetraeder wird als Delaunay-Simplex bezeichnet.

Ein Simplex in der Mathematik wird die einfachste Figur in einem Raum einer bestimmten Dimension genannt: ein Tetraeder - im dreidimensionalen Raum; Dreieck - in zwei Dimensionen. Ein beliebiges Tripel (Vierfach) von Systempunkten, die nicht in derselben Ebene liegen, definiert immer einen bestimmten Simplex. Es ist jedoch nur dann ein Delaunay-Simplex, wenn seine umschriebene Sphäre leer ist. Mit anderen Worten, Delaunay-Simplizes werden durch eine spezielle Wahl von Tripeln (Quadrupeln) von Punkten im System (A) bestimmt.

Wir haben einen Delaunay-Simplex konstruiert, aber indem wir die leere Kugel an verschiedenen Stellen platzieren und denselben Vorgang wiederholen, können andere definiert werden. Es wird festgestellt, dass die Menge aller Delaunay-Simplizes des Systems (A) den Raum ohne Überlappungen und Lücken füllt, d.h. implementiert die Aufteilung des Raums, diesmal jedoch in Tetraeder. Diese Aufteilung wird aufgerufen Delaunay-Partition(Abb. 3).

Anwendung der Delaunay-Triangulation

Oft werden Delaunay-Triangulationen im euklidischen Raum angewendet. Der minimale euklidische Spannbaum befindet sich garantiert auf einer Delaunay-Triangulation, daher verwenden einige Algorithmen Triangulation. Auch wird durch die Delaunay-Triangulation das euklidische Handlungsreisende-Problem näherungsweise gelöst.

Bei der 2D-Interpolation teilt die Delaunay-Triangulation die Ebene in möglichst dicke Dreiecke, wodurch zu scharfe oder zu stumpfe Winkel vermieden werden. Diese Dreiecke können zum Beispiel zum Aufbau einer bilinearen Interpolation verwendet werden.

Ein weiteres Problem, das in der Geoinformatik häufig auftritt, ist die Konstruktion von Hangaufnahmen. Hier ist es erforderlich, die dominierenden Richtungen der Hänge durch Kardinalpunkte zu bestimmen und die Oberfläche in Bereiche zu unterteilen, in denen eine bestimmte Richtung dominiert. Da bei horizontalen Flächenabschnitten die Expositionsdefinition nicht sinnvoll ist, werden z. B. horizontale oder leicht geneigte Flächen einem eigenen Bereich zugeordnet.<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.

Abb.4.

Die Aufgabe der Berechnung von Hangbelichtungen wird häufig verwendet, um die Beleuchtung der Erde zu analysieren. Dabei ist oft zusätzlich der aktuelle Sonnenstand zu berücksichtigen, d.h. Die Belichtung wird als Richtung zwischen der Normalen des Dreiecks und der Richtung der Sonne berechnet.

Somit kann jedes Triangulationsdreieck nach dem Prinzip der Zugehörigkeit zu einer bestimmten Region klassifiziert werden. Danach müssen Sie nur noch den Bereichsauswahlalgorithmus aufrufen.