Ein inkrementeller Algorithmus zur Konstruktion einer Delaunay-Triangulation. In einigen Fällen kann der Nachteil dieses Einfügealgorithmus darin bestehen, dass eine große Anzahl zusätzlicher Triangulationsknoten und -kanten erzeugt werden. Gleichzeitig überwiegt dieser Nachteil in anderen Fällen.

Das Senden Ihrer guten Arbeit an die Wissensdatenbank ist ganz einfach. Nutzen Sie das untenstehende Formular

Studierende, Doktoranden und junge Wissenschaftler, die die Wissensbasis in ihrem Studium und ihrer Arbeit nutzen, werden Ihnen sehr dankbar sein.

Gehostet unter http://www.allbest.ru/

KURSPROJEKT

KONSTRUKTIONTriangulationDelaunay

Von Disziplin "StrukturenUndAlgorithmenwird bearbeitetDaten"

Inhalt

Einführung
2.1 Greedy-Algorithmus
2.4 Algorithmus mit Indizierung von Dreieckszentrenk- D- Baum
3.4 Lüfteralgorithmus
4. Softwareteil
Abschluss

Einführung

Heute, zu Beginn des 21. Jahrhunderts, tritt die Menschheit in eine neue Zivilisation ein – eine Zivilisation, die mit dem Eindringen von Computern in alle Bereiche des menschlichen Lebens verbunden ist. Diese Zivilisation heißt Information, virtuell, Computer.

theoretischInformatik- eine mathematische Disziplin, die die Methoden der Mathematik nutzt, um Modelle zur Verarbeitung, Übertragung und Nutzung von Informationen zu erstellen und zu studieren. Es basiert auf mathematischer Logik und umfasst Abschnitte wie die Theorie von Algorithmen und Automaten, Informationstheorie und Codierungstheorie, die Theorie formaler Sprachen und Grammatiken, Operations Research und andere.

Einer der Bereiche der theoretischen Informatik ist die Computergeometrie , das Methoden zur Lösung geometrischer Probleme am Computer mithilfe von Algorithmen und Programmen entwickelt.

ComputerGeometrie ist ein Zweig der Informatik, der Algorithmen zur Lösung geometrischer Probleme untersucht. Solche Aufgaben finden sich in der Computergrafik, dem Entwurf integrierter Schaltkreise, technische Geräte und andere. Die Ausgangsdaten solcher Probleme können eine Menge von Punkten auf einer Ebene, eine Menge von Segmenten, ein Polygon usw. sein. Geometrische Probleme in der Informatik sind sie weit verbreitet, da ein Computer ein sehr bequemes und schnelles Werkzeug zu ihrer Lösung ist, da manuelles Zählen hier absolut nicht anwendbar ist.

ZielarbeitenUndAufgaben: Untersuchung eines der iterativen Algorithmen zur Konstruktion der Delaunay-Triangulation.

1) Studieren Sie die grundlegenden Definitionen und Theoreme des Delaunay-Triangulationsproblems;

2) Betrachten Sie die wichtigsten Arten iterativer Algorithmen zur Konstruktion der Triangulation;

3) Implementieren Sie den „Delete and Build“-Algorithmus zur Konstruktion der Delaunay-Triangulation.

1. allgemeine Beschreibung Delaunay-Triangulation

Die Aufgabe, eine Triangulation zu konstruieren.

Delaunay ist einer der Grundlagenforscher in der Computergeometrie. Viele andere Aufgaben werden darauf reduziert, es wird häufig in Computergrafiken und Geoinformationssystemen zur Modellierung von Oberflächen und zur Lösung räumlicher Probleme eingesetzt. Das Problem der Konstruktion einer Delaunay-Triangulation wurde erstmals 1934 in dem Werk gestellt Sowjetischer Mathematiker Boris Nikolajewitsch Delaunay.

TriangulationDelaunay Für eine Menge von Punkten S in der Ebene heißt eine Triangulation DT (S), so dass kein Punkt A aus S in einem Kreis enthalten ist, der um ein beliebiges Dreieck aus DT (S) so umschrieben ist, dass keiner seiner Eckpunkte ein Punkt A ist.

1.1 Analyse der Literatur zum Thema

SkvortsovA.IN.TriangulationDelaunayUndihrAnwendung. /SkvortsovA.IN. -Tomsk: VerlagVolumen. un-ta,2002 . - 128s. Gegeben Lernprogramm ist die Grundlage für dieses Kursprojekt. Es beschreibt im Detail theoretische Informationen Im Zusammenhang mit der Delaunay-Triangulation werden verschiedene Definitionen und Theoreme angegeben.

Es gibt auch Abschnitte, in denen Algorithmen zur Konstruktion von Triangulationen ausführlich beschrieben werden Vergleichsmerkmale und die Komplexität der Algorithmen.

Was geliehen: Grundlagenmaterial, theoretische Informationen, Definitionen, Zeichnungen.

PopowMIT.A.ComputerMethodenUndProgrammierung. /PopovMIT.A. -Moskau: VerlagMoskauer Staatsuniversität2008, - 24s. Dieses Handbuch ist eine ergänzende Literaturquelle. Einige Algorithmen werden aus mathematischer Sicht beschrieben, Formeln zur Konstruktion berechnet und auch die Triangulation im euklidischen Raum wird beschrieben

Was geliehen: mathematische Beschreibung Delaunay-Triangulationen, Konstruktion im euklidischen Raum

MedwedewH.N.MethodeVoronoi - DelaunayVForschungStrukturennicht kristallinSysteme/ RAS,Nowosibirskrsk: VerlagSORAS,2000, - 214 Mit. Ein Buch, das der Beschreibung der Voronoi- und Delaunay-Methoden in nichtkristallinen Systemen gewidmet ist.

Was geliehen: Eigenschaften von Delaunay-Triangulationen, Definition von Delaunay-Triangulationen.

1.2 Grundlegende Definitionen und Eigenschaften

Triangulation ist ein planarer Graph, dessen innere Bereiche alle Dreiecke sind.

Eigenschaften:

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

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

· Die Delaunay-Triangulation maximiert den minimalen Winkel aller Winkel aller konstruierten Dreiecke und vermeidet so „dünne“ Dreiecke.

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

· Die Delaunay-Triangulation minimiert die diskrete Dirichlet-Funktion.

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

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

Abb. 1. Triangulation.

konvex Triangulation Eine Triangulation heißt so, dass das kleinste Polygon, das alle Dreiecke umschließt, konvex ist. Eine Triangulation, die nicht konvex ist, heißt nicht konvex.

Aufgabe Gebäude Triangulation Von gegeben Satz zweidimensional Punkte nennt man das Problem, gegebene Punkte durch sich nicht schneidende Segmente so zu verbinden, dass eine Triangulation entsteht.

Triangulation soll befriedigend sein Zustand Delaunay , wenn keiner der angegebenen Triangulationspunkte innerhalb des Kreises liegt, der um ein konstruiertes Dreieck beschrieben wird.

**TriangulationgenanntTriangulation *Delaunay*** , wenn es konvex ist und die Delaunay-Bedingung erfüllt.

Abb. 2. Delaunay-Triangulation.

1.3 Delaunays Leerball-Methode. Konstruktion im allgemeinen Fall

Nehmen wir eine leere Kugel, die wir bewegen und dabei ihre Größe ändern, sodass sie die Punkte des Systems (A) berühren kann, aber immer leer bleibt.

Platzieren wir also eine leere Delaunay-Kugel im 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 belassen. Irgendwann trifft die Oberfläche des Balls auf einen Punkt i des Systems (A). Dies wird auf jeden Fall passieren, da es in unserem System keine unendlich großen Hohlräume gibt. Wir werden den Radius der leeren Kugel weiter vergrößern, sodass der Punkt i auf ihrer Oberfläche verbleibt. Dazu müssen Sie den Mittelpunkt des Balls von Punkt i aus verschieben. Früher oder später wird der Ball mit seiner Oberfläche einen anderen Punkt des Systems (A) erreichen.

Abb.3 – Delaunay-Partition eines zweidimensionalen Punktesystems

Delaunays Einfachheiten füllen den Raum ohne Lücken und Überschneidungen.

Die beschriebene Kugel 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 dabei beide Punkte auf seiner Oberfläche belassen. Mit zunehmender Geschwindigkeit erreicht der Ball 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 innerhalb seines umschriebenen Systems keine anderen Punkte des Systems (A) gibt Kreis. In drei Dimensionen wird eine Kugel nicht durch drei Punkte definiert. Vergrößern wir seinen Radius weiter und behalten alle drei gefundenen Punkte auf seiner Oberfläche. Dies ist möglich, bis die Oberfläche des Balls 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 sich innerhalb seiner umschriebenen Kugel keine anderen Punkte des Systems (A) befinden. Ein solches Tetraeder wird Delaunay-Simplex genannt.

Ein Simplex wird in der Mathematik 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. Allerdings handelt es sich nur dann um einen Delaunay-Simplex, wenn seine umschriebene Kugel leer ist. Mit anderen Worten: Delaunay-Simplices werden durch eine spezielle Wahl von Punkttripeln (Vierlingen) im System (A) bestimmt.

Wir haben einen Delaunay-Simplex konstruiert, aber indem wir den leeren Ball an verschiedenen Orten platzieren und den gleichen Vorgang wiederholen, können andere definiert werden. Es wird angegeben, dass die Menge aller Delaunay-Simplices des Systems (A) den Raum ohne Überlappungen und Lücken ausfüllt, d. h. implementiert die Aufteilung des Raums, diesmal jedoch in Tetraeder. Diese Aufteilung heißt SpaltungDelaunay(Abb. 3).

1.4 Anwendung der Delaunay-Triangulation

Im euklidischen Raum werden häufig Delaunay-Triangulationen angewendet. Der minimale euklidische Spannbaum liegt garantiert auf einer Delaunay-Triangulation, daher verwenden einige Algorithmen die Triangulation. Außerdem wird durch die Delaunay-Triangulation das Problem des euklidischen Handlungsreisenden annähernd gelöst.

Bei der 2D-Interpolation teilt die Delaunay-Triangulation die Ebene in möglichst dicke Dreiecke auf und vermeidet so zu spitze oder zu stumpfe Winkel. Diese Dreiecke können beispielsweise zum Aufbau einer bilinearen Interpolation verwendet werden.

Ein weiteres Problem, das in der Geoinformatik häufig auftritt, ist die Konstruktion von Hangaufschlüssen. Hier ist es erforderlich, die dominanten Richtungen der Hänge anhand der Himmelsrichtungen zu bestimmen und die Oberfläche in Bereiche zu unterteilen, in denen eine bestimmte Richtung dominiert. Da die Definition der Exposition für horizontale Flächenabschnitte nicht sinnvoll ist, werden beispielsweise Bereiche, die horizontal liegen oder ein leichtes Gefälle aufweisen, einem eigenen Bereich zugeordnet.<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.

Abb.4. Ein Beispiel für die Berechnung von Hangexpositionen mithilfe eines Reliefmodells

Die Berechnung von Hangbelichtungen wird üblicherweise zur Analyse der Beleuchtung der Erde verwendet. In diesem Zusammenhang besteht häufig die Notwendigkeit, zusätzlich den aktuellen 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 Regionsauswahlalgorithmus aufrufen.

2. Beschreibung der Konstruktionsalgorithmen

Im Allgemeinen basieren alle Algorithmen auf einer sehr einfachen Idee, Punkte sequentiell zu einer teilweise konstruierten Delaunay-Triangulation hinzuzufügen. Formal sieht es so aus.

Gegeben ein Haufen aus N Punkte.

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

2. Führen Sie im Zyklus für n für alle anderen Punkte die Schritte 3–5 aus.

3. Der nächste n-te Punkt wird wie folgt zur bereits erstellten Triangulationsstruktur hinzugefügt. Zunächst wird der Punkt lokalisiert, d.h. Es gibt ein Dreieck (zuvor konstruiert), in das der nächste Punkt fällt. Wenn der Punkt nicht innerhalb der Triangulation liegt, befindet sich am Rand der Triangulation ein Dreieck, das dem nächsten Punkt am nächsten liegt.

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

5. Lokale Überprüfungen der neu gewonnenen Dreiecke auf Einhaltung der Delaunay-Bedingung werden durchgeführt und die notwendigen Umordnungen vorgenommen.

Ende Algorithmus.

Unter gegeben ist detailliert Beschreibung mehrere Algorithmen.

2.1 Greedy-Algorithmus

Einer der ersten schlug den folgenden Algorithmus zur Konstruktion der Triangulation vor.

GierigMethode Dies ist eine Methode, die niemals das rückgängig macht, was bereits zuvor getan wurde. Die folgenden Schritte werden im Algorithmus nacheinander ausgeführt.

1. Die Enden aller Struktursegmente werden in der Menge der Anfangspunkte platziert.

2. Segmente, die alle Punktpaare verbinden, werden generiert, die Segmente werden nach Länge sortiert.

3. Alle Bruchkantensegmente werden in die Triangulation eingefügt.

4. Segmente werden nacheinander für die Triangulation aus einem Satz von Segmenten ausgewählt, die nach Länge sortiert sind (von kürzer nach länger). Wenn sich das Segment mit einem der bereits eingefügten Segmente schneidet, wird es verworfen, andernfalls wird es in die Triangulation eingefügt.

Schritt 4 wird wiederholt, bis die Segmente aufgebraucht sind.

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

Triangulation heißt gierig wenn es von einem gierigen Algorithmus erstellt wird.

2.2 Algorithmus „Löschen und erstellen“

" löschen Und System " Es werden keine Neuerstellungen durchgeführt. Stattdessen werden mit jedem Einfügen eines neuen Knotens (a) sofort alle Dreiecke gelöscht, in denen ein neuer Knoten (b) in die beschriebenen Kreise fällt. In diesem Fall bilden alle entfernten Dreiecke implizit ein bestimmtes Polygon. Anschließend wird anstelle der gelöschten Dreiecke eine Fülltriangulation erstellt, indem ein neuer Knoten mit diesem Polygon verbunden wird (Abb. c).

Reis. 4. Algorithmus „Löschen und erstellen“

Dieser Algorithmus erstellt alle erforderlichen Dreiecke auf einmal, im Gegensatz zum üblichen iterativen Algorithmus, bei dem beim Einfügen eines Knotens mehrere Neuerstellungen desselben Dreiecks möglich sind. Allerdings steht hier das Verfahren zum Extrahieren der Kontur eines entfernten Polygons im Vordergrund, die Gesamtgeschwindigkeit des Algorithmus hängt von seiner Effizienz ab. Abhängig von der verwendeten Datenstruktur kann dieser Algorithmus im Allgemeinen weniger Zeit in Anspruch nehmen als der Algorithmus mit Neuerstellungen und umgekehrt.

2.3 Algorithmus „Build by Breaking“

Der Algorithmus zum Einfügen von Struktursegmenten „Build by Breaking“ ist am einfachsten in der Implementierung und stabil im Betrieb.

Darin ist es notwendig, nacheinander Dreiecke entlang des eingefügten Segments zu durchlaufen, um die Schnittpunkte mit den Triangulationskanten zu finden. An diesen Schnittpunkten müssen Sie neue Triangulationsknoten platzieren und die vorhandenen Kanten und Dreiecke in Teile zerlegen. Danach müssen alle neu konstruierten Dreiecke auf den Delaunay-Zustand überprüft und ggf. neu aufgebaut werden, ohne die festen Kanten zu beeinträchtigen.

Reis. 5. Algorithmus „Build by Breaking“

In einigen Fällen kann der Nachteil dieses Einfügungsalgorithmus in der Erstellung liegen eine große Anzahl zusätzliche Knoten und Kanten der Triangulation. Gleichzeitig wird dieser Nachteil in anderen Fällen zum Vorteil, da er die Bildung langer schmaler Dreiecke verhindert, was besonders bei der Geländemodellierung geschätzt wird.

Ein weiterer Vorteil dieses Einfügealgorithmus im Vergleich zu den nachfolgenden zeigt sich, wenn versucht wird, ein Struktursegment in eine Triangulation einzufügen, bei der es feste Kanten zwischen den Kanten gibt, die es schneidet. Solche Kanten werden, wie alle anderen auch, einfach in zwei Teile geteilt.

2.4 Algorithmus mit k-D-Baum-Indizierung der Mittelpunkte von Dreiecken

IN Algorithmus Triangulation Mit Indizierung Zentren Dreiecke k-D- Baum nur die Mittelpunkte von Dreiecken werden im k-D-Baum platziert (für k = 2). Beim Löschen alter Dreiecke ist es notwendig, deren Mittelpunkte aus dem k-D-Baum zu entfernen, beim Aufbau neuer Dreiecke müssen diese eingetragen werden.

Um nach einem Dreieck zu suchen, das den aktuell in die Triangulation eingefügten Punkt enthält, muss eine nicht standardmäßige Punktabfrage an den k-D-Baum ausgeführt werden. Die Suche in einem Baum muss an der Wurzel beginnen und bis zu den Blättern reichen. Wenn die Nachkommen des aktuellen Knotens des k-D-Baums (das Rechteck, das die Nachkommen umschließt) den aktuellen Punkt nicht abdecken, muss für den weiteren Abstieg entlang des Baums der Nachkomme ausgewählt werden, der dem Suchpunkt am nächsten liegt.

Als Ergebnis wird ein Dreieck gefunden, dessen Mittelpunkt nahe am angegebenen Punkt liegt. Wenn der gegebene Punkt nicht in das gefundene Dreieck fällt, ist es außerdem notwendig, den üblichen Dreiecksuchalgorithmus von einem einfachen iterativen Algorithmus zur Konstruktion der Delaunay-Triangulation zu verwenden.

3. Bewertung der Effizienz von Algorithmen

Die Rechenkomplexität eines Algorithmus ist eine Funktion, die die Abhängigkeit des von einem Algorithmus geleisteten Arbeitsaufwands von der Größe der Eingabedaten bestimmt. Der Arbeitsaufwand wird üblicherweise in abstrakten Zeit- und Raumbegriffen gemessen, die als Rechenressourcen bezeichnet werden. Die Zeit wird durch die Anzahl der Elementarschritte bestimmt, die zur Lösung eines Problems erforderlich sind, während der Speicherplatz durch die Größe des Speichers oder des Speicherplatzes auf dem Speichermedium bestimmt wird.

3.1 Einfacher iterativer Algorithmus

In einem einfachen iterativen Algorithmus wird die Suche nach dem nächsten Dreieck wie folgt implementiert. Jedes Dreieck, das bereits zur Triangulation gehört, wird genommen (z. B. zufällig ausgewählt), und das gewünschte Dreieck wird durch aufeinanderfolgende Übergänge entlang der verbundenen Dreiecke gesucht.

In diesem Fall müssen im schlimmsten Fall alle Triangulationsdreiecke gekreuzt werden, sodass die Komplexität einer solchen Suche O (N) beträgt. Im Durchschnitt müssen jedoch nur O()-Sprungoperationen durchgeführt werden, um das Quadrat gleichmäßig zu verteilen. Somit ist die Komplexität des einfachsten iterativen Algorithmus im schlimmsten Fall und im Durchschnitt -

3.2 Iterativer Algorithmus mit Dreiecksindizierung

Die Komplexität, ein Dreieck in einem R-Baum zu finden, beträgt im schlimmsten Fall O(N) und im Durchschnitt O(log N). In diesem Fall können 1 bis N Dreiecke gefunden werden, die dann überprüft werden müssen. Darüber hinaus entsteht bei jedem Aufbau und Abbau von Dreiecken ein zusätzlicher Zeitaufwand für die Aufrechterhaltung der Baumstruktur - O (log N). Daraus erhalten wir, dass die Komplexität des Triangulationsalgorithmus mit der Indizierung von Dreiecken im schlimmsten Fall und im Durchschnitt O (N log N) beträgt.

3.3 Iterativer Algorithmus mit K-D-Baumindizierung von Dreieckszentren

Die Komplexität, einen Punkt in einem k-D-Baum zu finden, beträgt im schlimmsten Fall O(N) und im Durchschnittsfall O(logN). Darüber hinaus kann die Prozedur des Übergangs durch Dreiecke beteiligt sein, die im schlimmsten Fall von O N () mühsam sein kann. Außerdem entstehen bei jedem Aufbau und Abbau von Dreiecken zusätzliche Zeitkosten für die Aufrechterhaltung der Baumstruktur - O N (Stamm).

Daraus erhalten wir, dass die Komplexität des Triangulationsalgorithmus mit Indizierung der Mittelpunkte von Dreiecken im schlimmsten Fall im Durchschnitt O (N log N) beträgt.

3.4 Lüfteralgorithmus

Beim Fächertriangulationsalgorithmus (Algorithmus zum radialen Überstreichen der Ebene) wird zunächst aus den Anfangspunkten derjenige ausgewählt, der möglichst nahe am Massenschwerpunkt aller Punkte liegt. Darüber hinaus wird für die verbleibenden Punkte der Polarwinkel relativ zum ausgewählten Mittelpunkt berechnet und alle Punkte werden nach diesem Winkel sortiert. Dann werden alle Punkte durch Kanten mit dem Mittelpunkt und benachbarten Punkten in der sortierten Liste verbunden. Dann wird die Triangulation zu einer konvexen vervollständigt. Abschließend wird die Triangulation vollständig neu aufgebaut, um die Delaunay-Bedingung zu erfüllen.

Die Komplexität eines solchen Algorithmus beträgt im Durchschnitt O N (). Der Algorithmus arbeitet ungefähr mit der gleichen Geschwindigkeit wie der vorherige Algorithmus.

4. Softwareteil

Das Programm wurde in der Entwicklungsumgebung Microsoft Visual Studio 2012 entwickelt. Die Anwendung ist ein Fenster, in dem der Benutzer beliebig Punkte hinzufügen kann, die sofort mit der Delaunay-Triangulation verbunden sind. Die Koordinatenliste aller hinzugefügten Punkte wird rechts angezeigt.

hauptsächlich. cpp – Fensterfunktionen, Benutzeroberflächenfunktionen

delone. cpp – Algorithmus und Funktionen, die für die Arbeit damit notwendig sind

Beschreibung der Programmfunktionen:

void DrawPoint (int x, int y) – Funktion zum Zeichnen eines Punktes im Anwendungsfenster

void Triangulation() – Funktion zur Durchführung einer Triangulation

void TriangulationIn () – eine Funktion zum Ausführen von Aktionen mit Punkten, die innerhalb eines Dreiecks liegen

void TriangulationOut() – eine Funktion zum Ausführen von Aktionen mit Punkten, die außerhalb des Dreiecks liegen.

Um mit der Anwendung zu arbeiten, muss der Benutzer in den gewünschten Bereich klicken, woraufhin die Konstruktion der Delaunay-Triangulation durchgeführt wird.

Algorithmus der Delaunay-Triangulationssoftware

Reis. 6. Programmschnittstelle

Abschluss

In dieser Arbeit wurde ein Programm entwickelt, auf dessen Grundlage die Konstruktion der Delaunay-Triangulation durchgeführt wird.

Außerdem wurden alle Ziele und Vorgaben erfüllt, nämlich einer der iterativen Algorithmen zur Konstruktion der Delaunay-Triangulation wurde untersucht; grundlegende Definitionen und Theoreme des Delaunay-Triangulationsproblems werden untersucht; die wichtigsten Arten iterativer Algorithmen zur Konstruktion der Triangulation werden betrachtet; Ein Algorithmus zur Konstruktion der Delaunay-Triangulation wurde implementiert.

Liste der verwendeten Literatur

1. Skvortsov A.V. Delaunay-Triangulation und ihre Anwendung. / Skvortsov A.V. - Tomsk: Verlag Bd. Univ., 2012. - 128s.

2. Popov S.A. Computermethoden und Programmierung. /Popov S.A. - Moskau: Verlag der Moskauer Staatlichen Universität, 2008, - 24 S.

3. Medwedew N.N. Die Voronoi-Delaunay-Methode bei der Untersuchung der Struktur nichtkristalliner Systeme / RAS, Nowosibirsk: Verlag der Sibirischen Zweigstelle der Russischen Akademie der Wissenschaften, 2009, - 214 S.

Gehostet auf Allbest.ru

Gieriger Algorithmus

Einer der ersten schlug den folgenden Algorithmus zur Konstruktion der Triangulation vor.

Gierige Methode Dies ist eine Methode, die niemals das rückgängig macht, was bereits zuvor getan wurde. Die folgenden Schritte werden im Algorithmus nacheinander ausgeführt.

1. Die Enden aller Struktursegmente werden in der Menge der Anfangspunkte platziert.

2. Segmente, die alle Punktpaare verbinden, werden generiert, die Segmente werden nach Länge sortiert.

3. Alle Bruchkantensegmente werden in die Triangulation eingefügt.

4. Segmente werden nacheinander für die Triangulation aus einem Satz von Segmenten ausgewählt, die nach Länge sortiert sind (von kürzer nach länger). Wenn sich das Segment mit einem der bereits eingefügten Segmente schneidet, wird es verworfen, andernfalls wird es in die Triangulation eingefügt.

Schritt 4 wird wiederholt, bis die Segmente aufgebraucht sind.

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

Eine Triangulation wird als Greedy bezeichnet, wenn sie durch einen Greedy-Algorithmus erstellt wird.

Algorithmus „Löschen und erstellen“

„Delete and Build“ führt keine Neuerstellungen durch. Stattdessen werden mit jedem Einfügen eines neuen Knotens (a) sofort alle Dreiecke gelöscht, in denen ein neuer Knoten (b) in die beschriebenen Kreise fällt. In diesem Fall bilden alle entfernten Dreiecke implizit ein bestimmtes Polygon. Anschließend wird anstelle der gelöschten Dreiecke eine Fülltriangulation erstellt, indem ein neuer Knoten mit diesem Polygon verbunden wird (Abb. c).

Reis. 4. Algorithmus „Löschen und erstellen“

Algorithmus „Build by Breaking“

Der Algorithmus zum Einfügen von Struktursegmenten „Build by Breaking“ ist am einfachsten in der Implementierung und stabil im Betrieb.

Reis. 5. Algorithmus „Build by Breaking“

In einigen Fällen kann der Nachteil dieses Einfügealgorithmus darin bestehen, dass eine große Anzahl zusätzlicher Triangulationsknoten und -kanten erzeugt werden. Gleichzeitig wird dieser Nachteil in anderen Fällen zum Vorteil, da er die Bildung langer schmaler Dreiecke verhindert, was besonders bei der Geländemodellierung geschätzt wird.

Ein weiterer Vorteil dieses Einfügealgorithmus im Vergleich zu den nachfolgenden zeigt sich, wenn versucht wird, ein Struktursegment in eine Triangulation einzufügen, bei der es feste Kanten zwischen den Kanten gibt, die es schneidet. Solche Kanten werden, wie alle anderen auch, einfach in zwei Teile geteilt.

Algorithmus mit Indizierung der k-D-Dreieckszentren – Baum

Im Triangulationsalgorithmus mit k-D-Baum-Indizierung von Dreieckszentren werden nur Dreieckszentren im k-D-Baum platziert (für k = 2). Beim Löschen alter Dreiecke ist es notwendig, deren Mittelpunkte aus dem k-D-Baum zu entfernen, beim Aufbau neuer Dreiecke müssen diese eingetragen werden.

Als Ergebnis wird ein Dreieck gefunden, dessen Mittelpunkt nahe am angegebenen Punkt liegt. Wenn der gegebene Punkt nicht in das gefundene Dreieck fällt, ist es außerdem notwendig, den üblichen Dreiecksuchalgorithmus von einem einfachen iterativen Algorithmus zur Konstruktion der Delaunay-Triangulation zu verwenden.

Vorlesungsstruktur Definitionen Definitionen Anwendungen Anwendungen Delaunay-Triangulationseigenschaften Delaunay-Triangulationseigenschaften Konstruktionsmethoden der Delaunay-Triangulation Konstruktionsmethoden der Delaunay-Triangulation Schritteingabemethoden Schritteingabemethoden Schrittstichprobenmethoden Schrittstichprobenmethoden Zerlegungsmethoden Zerlegungsmethoden Scan-Methoden Scan-Methoden Zwei-Durchlauf-Methoden Zwei-Durchlauf-Methoden

Triangulation Triangulation ist ein planarer Graph, dessen innere Bereiche allesamt Dreiecke sind. Eine Triangulation ist ein planarer Graph, dessen innere Bereiche allesamt Dreiecke sind. Der Begriff „Triangulation“ ist der Begriff „Triangulation“ ist ein Graph; Graph; Graphenerstellungsprozess. Graphenerstellungsprozess. Die Aufgabe, eine Menge von Punkten S zu triangulieren, besteht darin, alle Punkte der Menge S mit sich nicht schneidenden Segmenten zu verbinden, um einen Triangulationsgraphen zu erhalten. Die Aufgabe, eine Menge von Punkten S zu triangulieren, besteht darin, alle Punkte der Menge S mit sich nicht schneidenden Segmenten zu verbinden, um einen Triangulationsgraphen zu erhalten. Definition der Triangulation Punktmenge S

Eine optimale Triangulation ist eine Triangulation mit der minimalen Summe der Längen aller Graphkanten. Eine optimale Triangulation ist eine Triangulation mit der minimalen Summe der Längen aller Graphkanten. ! Anspruchsvolle, aber sehr zeitaufwändige Aufgabe O(2 n) ! In der Praxis werden Näherungen (Annäherungen an) optimale Triangulation verwendet: „Greedy“-Triangulation O(N 2 *logN) „Greedy“-Triangulation O(N 2 *logN) Delaunay-Triangulation O(N*logN) Delaunay-Triangulation O(N*logN ) Definition optimale Triangulation

Die Delaunay-Triangulation (DT(S)) ist eine konvexe Triangulation, die die Delaunay-Bedingung erfüllt: Die Delaunay-Triangulation (DT(S)) ist eine konvexe Triangulation, die die Delaunay-Bedingung erfüllt: Keiner der Scheitelpunkte des Graphen sollte innerhalb eines umschriebenen Kreises liegen eines seiner Dreiecke. Keiner der Eckpunkte des Diagramms sollte innerhalb eines Kreises liegen, der um eines seiner Dreiecke verläuft. Definition der Delaunay-Triangulation Delaunay-Bedingung ist erfüllt Delaunay-Bedingung ist nicht erfüllt B.N. Delaunay ()

Anwendung der Delaunay-Triangulation Bei anderen VG-Problemen Bei anderen VG-Problemen Mindestspanne einer Punktmenge Mindestspanne einer Punktmenge Erstellen von Pufferzonen Erstellen von Pufferzonen Erstellen eines Voronoi-Diagramms (Nähezonen) Erstellen eines Voronoi-Diagramms (Nähezonen) Finden der maximaler leerer Kreis Finden des maximalen leeren Kreises usw. usw. In Anwendungen in CG, GIS, GM in CAD In Anwendungen in CG, GIS, GM in CAD Polygonale Oberflächenmodelle Polygonale Oberflächenmodelle Reliefs in GIS, Skulpturen, Industriemodelle, Modelle in Spiele, Reliefs in GIS, Skulpturen, Industriemodelle, Modelle in Spielen, Numerische Analyse von Modellen Numerische Analyse von Modellen Isolinien, Isoklinen, FEM. Isolinien, Isoklinen, FEM.

Eigenschaften einer beliebigen konvexen Triangulation 1. Für eine Menge von n Punkten, von denen m intern sind. Anzahl der Triangulationsdreiecke = n + m – 2 Anzahl der Triangulationsdreiecke = n + m – 2 Anzahl der Triangulationskanten 3n – 6 Anzahl der Triangulationskanten 3n – 6 Beispiel: Punkte (n) – 13 Punkte (n) – 13 Innen (m) – 4 Innen (m) – 4 Dreiecke – 15 = Dreiecke – 15 = Kanten – 26 3*13-6 = 33 Kanten – 26 3 *13-6 = 33

Eigenschaften der Delaunay-Triangulation 2. Die Delaunay-Triangulation hat die maximale Summe der minimalen Winkel aller Dreiecke unter allen möglichen Triangulationen. 3. Die Delaunay-Triangulation hat unter allen möglichen Triangulationen die minimale Summe der Radien von Kreisen, die um Dreiecke umschrieben sind. Delaunay-Triangulation, NICHT Delaunay-Triangulation

Konstruktionsmethoden der Delaunay-Triangulation Schritt-für-Schritt-Eingabemethoden Schritt-für-Schritt-Eingabemethoden Iterative Algorithmen () Iterative Algorithmen () Schritt-für-Schritt-Stichprobenmethoden Schritt-für-Schritt-Stichprobenmethoden Direkte (schrittweise) Konstruktionsalgorithmen (3) Direkte (schrittweise) Konstruktionsalgorithmen (3) Zerlegungsmethoden Zerlegungsmethoden Zusammenführungsalgorithmen (2) ) Zusammenführungsalgorithmen (2) Scanning-Methoden Scanning-Methoden Iterative Algorithmen mit geänderter Reihenfolge der Addition von Punkten (1.4) Iterative Algorithmen mit eine geänderte Reihenfolge beim Hinzufügen von Punkten (1.4) Two-Pass-Algorithmen (4) Two-Pass-Algorithmen (4)

Schrittweise Eingabemethoden Iterative Algorithmen () Allgemeines Schema iterativer Algorithmen zur Konstruktion der Delaunay-Triangulation 1. Konstruieren Sie an den ersten drei Punkten ein Dreieck. 2. Schleife über alle verbleibenden Punkte p i der Menge S. 3. Finden Sie das Dreieck t j der aktuelle Triangulation, die dem Punkt p i am nächsten liegt. 4. Wenn der Punkt p i außerhalb des Dreiecks t j liegt, konstruieren Sie Dreiecke zur nächstgelegenen Kante. 5. Wenn der Punkt p i innerhalb des Dreiecks t j liegt, teilen Sie das Dreieck in drei Teile. 6. Wenn der Punkt p i auf einer Kante liegt, teilen Sie die angrenzenden Dreiecke in Paare. 7. Wenn die Delaunay-Bedingung für Nachbarn verletzt wird, dann bauen Sie die benachbarten Dreiecke neu auf. Optionen zur Beschleunigung der Dreieckssuche: Dreiecksindizierung (Bäume) – O(log n) Dreiecksindizierung (Bäume) – O(log n) Dreiecks-Caching (Netz) – O(s) Dreiecks-Caching (Gitter) – O(s)

Methoden der schrittweisen Stichprobenziehung Algorithmen der direkten (schrittweisen) Konstruktion (3) Bauen Sie die erforderlichen Dreiecke auf einmal auf, ohne das, was bereits erstellt wurde, neu anzuordnen. Allgemeines Schema von Algorithmen zur direkten Konstruktion der Delaunay-Triangulation. Es ist praktisch, einen Stapel von Kanten zu verwenden, die noch nicht verarbeitet wurden. 1. Finden Sie eine beliebige Kante q der konvexen Hülle der Punktmenge S. 2. Schieben Sie die Kante q auf den Stapel roher Kanten. 3. Machen Sie eine Schleife, bis der Stapel roher Kanten leer ist. 4. Nehmen Sie die Kante v vom Stapel. 5. Suchen Sie für die Kante v einen Punkt p, der die Delaunay-Bedingung erfüllt (den Delaunay-Nachbarn). 6. Wenn der Delaunay-Nachbarn p gefunden wird, dann 7. Konstruieren Sie ein Dreieck von der Kante v zum Punkt p. 8. Schieben Sie die neuen Kanten des neuen Dreiecks auf den Rohkantenstapel. Optionen zur Beschleunigung der Suche nach einem Delaunay-Nachbarn: Punktindizierung durch k-D-Baum - O(log n) Punktindizierung durch k-D-Baum - O(log n) Zellularpunktindizierung - O(c) Zellularpunktindizierung - O(c )

Der Arbeitsablauf des gierigen Delaunay-Triangulationsalgorithmus

Zerlegungsmethoden Zusammenführungsalgorithmen (2) Aufteilung in Teilmengen, unabhängige Verarbeitung, Ergebnisse zusammenführen. Das allgemeine Schema der Zusammenführungsalgorithmen 0. Wenn die Menge S nicht mehr als 3 Punkte enthält, konstruieren Sie direkt, andernfalls 1. Teilen Sie die Menge der Punkte S in ungefähr gleiche Teilmengen auf. 1. Teilen Sie die Punktmenge S in ungefähr gleiche Teilmengen auf. 2. Konstruktion der Triangulation für Teilmengen. 2. Konstruktion der Triangulation für Teilmengen. 3. Zusammenführen der resultierenden Triangulationen zu einer. 3. Zusammenführen der resultierenden Triangulationen zu einer. Methoden zur Unterteilung in Teilmengen Orthogonale Linien Orthogonale Linien Durch den Durchmesser der konvexen Hülle Durch den Durchmesser der konvexen Hülle Streifen Streifen

Zusammenführungsalgorithmen (2) Methoden zum Zusammenführen von Triangulationen „Löschen und bauen“ (Prüfung vor dem Bau) „Löschen und bauen“ (Prüfung vor dem Bau) „Bauen und Neuaufbau“ (Prüfung nach dem Bau) „Bauen und Umbau“ (Prüfung nach dem Bau) „ „Build Build by Rebuilding“ (zur Build-Zeit prüfen) „Build by Rebuild“ (zur Build-Zeit prüfen)

Das allgemeine Schema iterativer Methoden mit einer geänderten Reihenfolge beim Hinzufügen von Punkten 1. Punkte ordnen (eine Liste von Ereignispunkten erstellen) 2. Zyklus über alle Ereignispunkte scannen 3. Für jeden Punkt p bilde ich Dreiecke zum vorherigen Dreieck. 4. Wenn die Delaunay-Bedingung für Nachbarn verletzt wird, dann bauen Sie die benachbarten Dreiecke neu auf. Scanverfahren Iterative Algorithmen mit geänderter Reihenfolge der Punktzugabe (1.4)

Scanmethoden Methoden zum Ordnen von Ereignispunkten Geradlinig Geradlinig Polar (kreisförmig, fächerförmig) Polar (kreisförmig, fächerförmig) Streifen Streifen Quadrat Quadrat Hilbert-Kurve Hilbert-Kurve Z-Code Z-Code Ziele: Sofort so viele gute Dreiecke bauen. Sofort bauen wie viele gute Dreiecke Minimieren Sie die Anzahl der Neuaufbauten. Minimieren Sie die Anzahl der Neuaufbauten

Zusammenfassende Merkmale der Delaunay-Triangulationsmethoden Triangulationsmethode Durchschnittliche Zeit Schlechteste Zeit Zeit Sek. / t Einfache Implementierung Inkrementelle Eingabemethoden Inkrementelle Eingabemethoden Iterative Algorithmen () Iterative Algorithmen ()O(n)- O(n 3/2) O(n 2) 1,5-9,2 2-5 Inkrementelle Stichprobenmethoden Inkrementelle Stichprobenmethoden Direkte Konstruktionsmethode (3) Direkt Konstruktionsmethode (3) O(n)- O(n 2) O(n 2) -2 Zerlegungsmethoden Zerlegungsmethoden Zusammenführungsmethoden (2) Zusammenführungsmethoden (2) O(n)- O(nlogn) O (nlogn)- O(n 2) 2.5-4.52-3 Scan-Methoden Scan-Methoden Iterativ mit der geänderten Reihenfolge der Punktzugabe (1.4) Iterativ mit der geänderten Reihenfolge der Punktzugabe (1.4)O(n) O(n 2) 1 ,9-5 ,34-5 Zwei-Durchgangs-Methoden (4) Zwei-Durchgangs-Methoden (4) O(n)- O(n 2) O(nlogn)- O(n 2) 2,2-15,41-5 Skvortsov empfiehlt: iterativer Algorithmus mit dynamischem Caching

Wie wäre es mit heute? Über Delaunay-Triangulation! Definition Definition Anwendungen Anwendungen Eigenschaften der Delaunay-Triangulation Eigenschaften der Delaunay-Triangulation Konstruktionsmethoden der Delaunay-Triangulation Konstruktionsmethoden der Delaunay-Triangulation Inkrementelle Eingabemethoden Inkrementelle Eingabemethoden Inkrementelle Stichprobenmethoden Inkrementelle Stichprobenmethoden Zerlegungsmethoden Zerlegungsmethoden Scan-Methoden Scan-Methoden Zwei-Pass-Methoden Zwei-Pass-Methoden

GRID-Modelle sind Modelle regulärer Zellen.

Lassen Sie das Koordinatensystem
Und Und
. Benutzersätze
und Probenahmeschritte
.

- physikalische Koordinaten des Punktes.

Berechnung
Und
,
- Bitraster.

- quantisierte Werte. Real:

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

- Abstandsgrad (1 oder 2).

Normalisierungsfaktor:

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

Dies ist die IDW-Methode - long, für jedes t müssen Nachbarn gefunden werden. Eine Reihe von Nachbarn kann effizient gefunden werden – die nächstgelegenen. Jeder der Punkte erzeugt einen „Pflock“ einer bestimmten Höhe. Viel hängt von der Unregelmäßigkeit der Punktsetzung ab, dafür nehmen sie
oder
diese. 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 aneinandergrenzenden Dreiecken darzustellen, ohne sich zu überlappen. Die Triangulation basiert auf mehreren Arten auf einer Reihe von Punkten.

Wir brauchen einen Algorithmus, um eine optimale Triangulation aufzubauen.

Eine Ebene, die durch 3 Punkte fliegt.

1) Finden Sie ein Dreieck, das
;

2)
- Wir bilden die Gleichung der Ebene.

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

Struktur anzeigen:

Jede Triangulation enthält die gleiche Anzahl an Dreiecken.

, Wo ist die Anzahl der internen Punkte,
- Anzahl der Punkte.

Gierige Triangulation.

Wir verbinden alle Punkte mit Kanten, wählen das Minimum aus und ergänzen die Triangulation. 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 ein Dreieck herum verläuft. Auf eine Art gebaut.

Ein Flip ist ein Flip von Kanten. Sie können von der herkömmlichen Triangulation zur Delaunay-Triangulation wechseln. Um zu überprüfen, ob ein Punkt zu einem Kreis gehört, ersetzen Sie if< R, то внутри.

Delaunay-Zustand.

Gleichung eines Kreises, der durch drei Punkte geht:

Wenn kleiner als Null, dann extern, andernfalls intern.

ist die Delaunay-Bedingung.

Der Algorithmus zur Konstruktion der Delaunay-Triangulation:

1) Es wird noch geprüft, ob Punkte hinzugefügt werden ist ein einfacher iterativer Algorithmus:

Es gibt ein Set
Zum Dreieck hinzufügen, die Konstruktion ist ausgeführt
Teilung eines Dreiecks
Wiederaufbau. Im Nullstadium fügen wir 3-4 fiktive Punkte hinzu, die offensichtlich unseren Umschlag abdecken, alle Punkte liegen darin. Nachdem wir einen Punkt geworfen haben, schauen wir uns an, welches Dreieck er getroffen hat, teilen es in drei Teile auf, für jedes Dreieck überprüfen wir die Delaunay-Bedingung und drehen die Kanten um. Die durchschnittliche Anzahl der Umbauten beträgt drei.

Theoretische Komplexität

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

Wir bewegen uns vom ersten Punkt zum anderen.

Bei der Triangulation handelt es sich um eine Annäherung an die Oberfläche des simulierten Objekts durch dreieckige Platten, die in einem Abstand voneinander angeordnet sind, der einen bestimmten festgelegten Wert 6 nicht überschreitet. Alle dreieckigen Platten müssen miteinander verbunden sein. Ihre Spitzen liegen an der Oberfläche. Mit einem Satz dreieckiger Platten lässt sich einfacher arbeiten als mit einer generischen Oberfläche. Dreieckige Platten werden Dreiecke genannt. Für ein Dreieck lässt sich schnell der Abstand zu einem gegebenen Punkt oder der Schnittpunkt mit einer gegebenen Geraden im Raum berechnen. Die Triangulation der Gesichter erfolgt zur visuellen Wahrnehmung des geometrischen Modells, daher werden die Seiten der Dreiecke so gewählt, dass das Auge die Brüche nicht wahrnehmen kann.

Bei der Darstellung geometrischer Objekte durch Dreiecke auf den parametrischen Ebenen von Oberflächen sollte eine räumliche Triangulation von Körperflächen erstellt werden, indem eine Reihe von Punkten im Raum und eine Reihe von Normalen zu den Körperflächen an diesen Punkten unter Verwendung einer Reihe von Zwei-Punkten berechnet werden. dimensionale Punkte Um Körper schnell darzustellen, werden ihre Flächen durch auf Punkten aufgebaute dreieckige Platten angenähert. Normalen sind erforderlich, um das Verhalten von Lichtstrahlen zu bestimmen, die mit Körperflächen interagieren. Die Tonmuster in den vorherigen Kapiteln und in diesem Kapitel werden mithilfe der Triangulation erstellt.

Als Ergebnis der Oberflächentriangulation möchten wir ein Array von zweidimensionalen Punkten auf der parametrischen Ebene und ein Array von Tripeln ganzer Zahlen haben, die die Anzahl der Punkte im erstgenannten Array darstellen. Somit wird jedes Dreieck durch seine drei Scheitelpunktnummern im Parameterarray dargestellt. Für jeden zweidimensionalen Punkt des parametrischen Bereichs kann ein Raumpunkt auf der Oberfläche und die darin befindliche Oberflächennormale berechnet werden. Räumliche Punkte und Normalen können in Arrays ähnlich einem 2D-Punktarray gespeichert werden.

Lassen Sie uns auf einige Methoden der Triangulation eingehen. Für ebene Flächen gibt es kostengünstige Triangulationsverfahren, bei denen an den Randpunkten der Fläche Dreiecke gebildet werden und es nicht notwendig ist, nach Punkten innerhalb des parametrischen Bereichs zu suchen.

Delaunay-Triangulation.

Betrachten Sie einen Bereich im Flugzeug. Eine Region heißt konvex, wenn man sich bei der Bewegung entlang ihrer Grenze nur in eine Richtung (nur nach links oder nur nach rechts) drehen muss. Sie können den Delaunay-Algorithmus verwenden, um konvexe planare Regionen zu triangulieren. Wir werden diesen Algorithmus nicht direkt auf die Triangulierung von Freiformflächen anwenden können, aber wir werden seine Methode zur Konstruktion von Dreiecken verwenden.

Reis. 9.7.1. Konvexer Bereich mit vorgegebenen Punkten im Inneren

Gegeben sei ein konvexer zweidimensionaler Bereich, der durch eine geschlossene gestrichelte Linie begrenzt ist, und eine Menge von Punkten innerhalb dieses Bereichs (Abb. 9.7.1).

Es ist erforderlich, die angegebene Fläche in Dreiecke zu unterteilen, deren Eckpunkte sind vergebene Punkte innerhalb der Region und dem Scheitelpunkt der sie begrenzenden Polylinie. Die Dreiecke dürfen sich nicht überlappen und ihre Seiten dürfen sich nur an den Eckpunkten schneiden.

Sie können mehrere verschiedene Dreieckssätze erstellen, die den angegebenen Bereich ausfüllen. In allen Fällen beträgt die Anzahl der Dreiecke, wobei K die Anzahl der Eckpunkte der begrenzenden Polylinie und I die Anzahl der gegebenen Punkte innerhalb der Fläche ist.

Reis. 9.7.2. Auswahl des dritten Punktes des Delaunay-Algorithmus

Eine Domänentriangulation ist eine Delaunay-Triangulation, wenn sich innerhalb des umschriebenen Kreises um jedes Dreieck keine Eckpunkte anderer Dreiecke befinden. Die Delaunay-Triangulation baut Dreiecke auf, die möglichst gleichwinklig sind (die Konstruktion unangemessen verlängerter Dreiecke ist nicht möglich).

Man kann es als ausgeglichen bezeichnen. Eine Delaunay-Triangulation ist eindeutig, wenn keine vier Eckpunkte auf demselben Kreis liegen.

Betrachten Sie die Delaunay-Triangulation. Die Scheitelpunkte der Polylinie, die die Region begrenzt, und die angegebenen Punkte innerhalb der Region werden als Triangulationsscheitelpunkte bezeichnet. Die Seiten von Dreiecken werden Kanten genannt. Unter den Kanten wählen wir die Segmente der begrenzenden Polylinie aus, die wir als Begrenzungskanten bezeichnen. Richten wir alle Grenzkanten so aus, dass der konvexe Bereich links von jeder Kante liegt. Es soll ein Dreieck konstruiert werden, dessen Seite die in Abb. gezeigte Grenzkante AB ist. 9.7.2.

Ein Kreis kann durch die Eckpunkte A, B und jeden Eckpunkt gezeichnet werden, der nicht mit ihnen auf derselben Linie liegt. Als dritten Scheitelpunkt des Dreiecks wählen wir den Scheitelpunkt V, entsprechend dem der Kreis keine anderen Scheitelpunkte auf derselben Seite in Bezug auf das Segment AB enthält, auf dem der Punkt V liegt. Im allgemeinen Fall ein solcher Scheitelpunkt kann für eine Grenzkante gefunden werden. Nennen wir es das nächstgelegene. Der Mittelpunkt des Kreises, der durch die Punkte A, B und V verläuft, liegt im Schnittpunkt der Senkrechten zu den Mittelpunkten der Strecken AB, BV und VA. Die Position des Kreismittelpunkts wird durch den Parameter t des Segments MN senkrecht zur Kante AB charakterisiert, das gleich lang ist und durch die Mitte der Kante AB verläuft.

Reis. 9.7.3. Delaunay-Triangulationsprozess

Für alle Scheitelpunkte links vom Segment AB hat der nächstgelegene Scheitelpunkt den kleinsten Parameter t. Der Kreis, der dem nächstgelegenen Scheitelpunkt entspricht, enthält keine weiteren Scheitelpunkte links vom Segment AB. Die Eckpunkte A, B und V seien jeweils durch zweidimensionale Radiusvektoren beschrieben. Die Radiusvektoren der Mittelpunkte der Segmente AB und BV sind gleich

Der Wert des Parameters t der Geraden, der der Position des Mittelpunkts des Kreises entspricht, der durch die Punkte A, B und V verläuft, ist gleich

Für den Scheitelpunkt, der dem Segment AB am nächsten liegt, hat der Parameter t einen minimalen Wert.

Richten Sie alle Grenzkanten so aus, dass der zu triangulierende Bereich jeweils links davon liegt. Wir beginnen mit der Konstruktion von Dreiecken von einer beliebigen Grenzkante aus. Finden Sie dafür den nächstgelegenen Scheitelpunkt, dessen entsprechender Kreis keine anderen Scheitelpunkte enthält. Für die Randkante AB soll der nächstgelegene Scheitelpunkt V gefunden werden. Dann konstruieren wir das Dreieck ABV und transformieren die Kante AB in die Kategorie der inaktiven. Wir nennen inaktive Kanten und Eckpunkte, die nicht am Triangulationsalgorithmus teilnehmen. Wenn unter den Grenzkanten keine Kante BV vorhanden ist, konstruieren wir eine neue Grenzkante auf dem Segment VB. Befindet sich unter den Randkanten eine Kante BV, so überführen wir diese und den Scheitelpunkt B in die Kategorie der inaktiven Kanten. Wenn unter den Grenzkanten keine Kante VA vorhanden ist, konstruieren wir eine neue Grenzkante auf dem Segment AV. Wenn sich unter den Grenzkanten eine Kante VA befindet, übertragen wir diese und den Scheitelpunkt A in die Kategorie der inaktiven Kanten. Der Triangulationsprozess ist in Abb. dargestellt. 9.7.3.

Reis. 9.7.4. Delaunay-Triangulation

Wir beenden die Triangulation, wenn alle Scheitelpunkte und Kanten inaktiv werden. Das Ergebnis der Triangulation des gegebenen Bereichs ist in Abb. dargestellt. 9.7.4.

Triangulation durch Korrekturmethode.

Betrachten wir die Triangulation einer Oberfläche mit einem rechteckigen Parameterdefinitionsbereich. Teilen wir den Definitionsbereich der Oberflächenparameter durch zweidimensionale Linien in rechteckige Zellen. Diese Linien bilden ein rechteckiges Gitter. Wir nehmen die parametrischen Abstände zwischen benachbarten Linien gemäß Formel (9.4.7) gleich an

Wir nehmen die parametrischen Abstände zwischen benachbarten Linien gemäß der Formel (9.4.8) gleich an

Durch die Konstruktion von Diagonalen in allen rechteckigen Zellen erhalten wir eine Triangulation der Oberfläche (wir erhalten eine Menge von Dreiecken, die die Anforderungen erfüllt). Auf Abb. Abb. 9.7.5 zeigt die Triangulierung der Rotationsfläche in der beschriebenen Weise.

Betrachten Sie die Triangulation einer Oberfläche mit einer beliebigen Grenze. Wir bauen die Triangulationsmethode auf der Korrektur der oben beschriebenen Oberflächentriangulation durch Randkonturen mit einem rechteckigen Parameterdefinitionsbereich auf.

Reis. 9.7.5. Triangulation einer Oberfläche mit rechteckigem Parameterbereich

Der Rand der Oberfläche im Parameterdefinitionsbereich sei durch mehrere sich nicht schneidende zweidimensionale Konturen (2.12.7) beschrieben. Eine der Konturen ist außen und enthält die restlichen Konturen. Als positive Richtung für jede Kontur nehmen wir die Richtung, in der sich der Flächendefinitionsbereich bei der Bewegung immer links von der Kontur befindet, wenn man auf die Flächennormale blickt. Lassen Sie uns Polygone in der positiven Richtung der Grenzkonturen des Oberflächendefinitionsbereichs erstellen. Um Grenzpolygone zu erstellen, ist es notwendig, mit einem variablen Schritt entlang der Grenzkonturen der Oberfläche zu fahren und eine Reihe zweidimensionaler Punkte zu füllen, deren Koordinaten die Oberflächenparameter sind. Das Polygon wird aus Punkten auf der parametrischen Ebene aufgebaut, die Stufe beim Übergang von einem Punkt zum anderen wird jedoch aus der räumlichen Geometrie bestimmt, nämlich aus der Bedingung, dass die Ablenkung des Kurvenbogens zwischen benachbarten Punkten nicht mehr erfolgt als ein vorgegebener Wert. Die parametrischen Schritte zum Konstruieren eines Polygons für die Kurve der Grenzkontur der Oberfläche werden nach der Formel (9.4.4) berechnet.

Jedes Polygon besteht aus einer geordneten Menge von 2D-Punkten. Jeder Abschnitt eines Polygons kann als zweidimensionales gerades Liniensegment betrachtet werden, das auf zwei benachbarten Punkten aufgebaut ist. Wir verwenden solche Abschnitte als Grenzkanten und die Punkte der Polygone, auf denen die Kanten basieren, als Triangulationseckpunkte. Da der Definitionsbereich der Oberflächenparameter links von den Grenzpolygonen liegt, sollte man beim Konstruieren von Dreiecken für jede Grenzkante der Triangulation nach dem dritten Scheitelpunkt des Dreiecks links von der Kante suchen.

Lassen Sie uns bestimmen, welche Knoten innerhalb der Grenzpolygone liegen und welche auf der Grenze oder außerhalb des Oberflächendefinitionsbereichs liegen. Anhand dieser Informationen sortieren wir die rechteckigen Gitterzellen in zwei Gruppen. Die erste Gruppe umfasst Zellen, die vollständig im Definitionsbereich der Oberflächenparameter liegen (die Zellen sollten die Grenzpolygone nicht berühren). Die zweite Gruppe umfasst den Rest der Zellen (die außerhalb des Definitionsbereichs der Oberfläche liegen oder von Grenzpolygonen geschnitten werden).

Reis. 9.7.6. Unvollendete Oberflächentriangulation

Innerhalb jeder Zelle der ersten Gruppe konstruieren wir mithilfe der Diagonale zwei Dreiecke. Somit erhalten wir eine unvollendete Triangulation. Ein Beispiel für die Konstruktion von Dreiecken in den Zellen der ersten Gruppe für eine durch Konturen begrenzte Rotationsfläche ist in Abb. dargestellt. 9.7.6.

Auf den nicht geschnittenen Seiten der Zellen der zweiten Gruppe konstruieren wir Grenzkanten und richten sie so aus, dass sich die entsprechende Zelle links von der Kante befindet. Wir konstruieren eine geschlossene Polylinie um die Zellen der ersten Gruppe (mehrere geschlossene Linien sind möglich), so dass bei der Bewegung entlang dieser der nicht in Dreiecke unterteilte Teil des Bereichs links liegt, wenn man auf die Flächennormale blickt. Die geraden Abschnitte dieser Polylinie werden auch als Begrenzungskanten verwendet. Wir betrachten alle Kanten als gleichberechtigt. Um die Triangulation abzuschließen, müssen wir Dreiecke zwischen den Grenzkanten konstruieren. Für jede Kante suchen wir einen Eckpunkt, der links davon liegt und aus dem ein Dreieck gebildet werden kann. Wir werden nur unter den Scheitelpunkten nach einem Scheitelpunkt suchen, die in derselben Zelle mit einer Kante liegen. Um einen Scheitelpunkt auszuwählen, verwenden wir die oben beschriebene und in Abb. dargestellte Delaunay-Methode. 9.7.2. Wenn ein solcher Scheitelpunkt gefunden wird, sollte man prüfen, ob sich zwei neue Kanten des Dreiecks mit einer beliebigen Grenzkante schneiden. Der nächstgelegene Scheitelpunkt V soll für die Grenzkante AB gefunden werden und es sollte überprüft werden, dass die Segmente BV und VA keine anderen Grenzkanten schneiden. Dann konstruieren wir ein Dreieck ABV und übertragen die Kante AB in die Kategorie der inaktiven. Wenn es unter den Grenzkanten keine Kante BV gibt, konstruieren wir eine neue Grenzkante auf dem Segment VВ, wenn es jedoch eine Kante BV unter den Grenzkanten gibt, übertragen wir sie und den Scheitelpunkt B in die Kategorie inaktiv . Wenn unter den Grenzkanten keine Kante VA vorhanden ist, konstruieren wir auf dem Segment AV eine neue Grenzkante. Wenn jedoch zwischen den Grenzkanten eine Kante VA vorhanden ist, übertragen wir diese und den Scheitelpunkt A in die Kategorie inaktiv.

Wenn das Segment oder die VA andere Grenzkanten schneidet, fahren wir mit der Suche nach dem nächstgelegenen Scheitelpunkt für eine andere Grenzkante fort. Die Triangulation wird abgeschlossen, nachdem alle Kanten und Scheitelpunkte in die inaktive Kategorie übertragen wurden.

Reis. 9.7.7. Triangulation durch Korrekturmethode

Auf Abb. In Abb. 9.7.7 zeigt die Triangulation der Oberfläche durch die Methode der Korrektur von Dreiecken in Zellen, die von Grenzkonturen gekreuzt werden. Auf Abb. 9.7.8 Mit Hilfe der erhaltenen Triangulation wird die Oberfläche selbst dargestellt.

Wenn die Grenzpolygone und die Oberfläche eine gewisse Symmetrie aufweisen, weist die Korrekturtriangulation eine ähnliche Symmetrie auf.

Triangulation durch Absorptionsmethode.

Betrachten Sie eine andere Triangulationsmethode. Hinsichtlich der Geschwindigkeit ist sie der Delaunay-Triangulation und ihren Modifikationen unterlegen. Um den Triangulationsvorgang zu starten, ist es notwendig, die Oberflächengrenze in Form geschlossener Polygone darzustellen. Bei der Triangulation müssen wir die Stufen auf den Oberflächenparametern bestimmen. Bei bekannter Bewegungsrichtung werden diese Schritte durch die Formeln (9.4.6) bestimmt. Ungefähre Schritte zu Oberflächenparametern können wie folgt ermittelt werden. Definieren wir eine Region auf der Parameterebene um einen bestimmten Punkt herum so, dass jedes Raumsegment von einem Punkt zu einem Punkt in dieser Region nicht weiter als einen gegebenen Wert S von der Oberfläche entfernt wäre.

Dazu berechnen wir die zulässigen Parameterinkremente entlang der Koordinatenlinien

Wo sind die Koeffizienten des ersten und zweiten? quadratische Formen Oberfläche an einem Punkt. Wir nehmen eine Ellipse mit Mittelpunkt in einem Punkt und Halbachsen als Grenze des gewünschten Bereichs. Diese Ellipse hat die Gleichung

Wenn es erforderlich ist, einen Punkt auf der Ebene neben dem Punkt in der durch den Winkel mit der Achse und gegebenen Richtung zu finden, dann sind seine Parameter

Betrachten wir zunächst einen einfacheren Fall, bei dem der Bereich der Oberflächenparameter durch eine Außenkontur begrenzt ist. Wir approximieren den Rand der Oberfläche durch ein geschlossenes Polygon im parametrischen Bereich. Beim Konstruieren einer Triangulation verwenden wir ein Arbeitspolygon, für das in dieser Fall Nehmen wir ein Polygon der Außenkontur. Die Punkte des Polygons werden in das resultierende Array zweidimensionaler Punkte eingegeben. Wir werden Dreiecke von der Kante des Arbeitspolygons bilden und diese verengen, bis nur noch drei Punkte im Arbeitspolygon übrig sind.

Suchen Sie im Arbeitspolygon den Scheitelpunkt, an dem es sich innerhalb der Fläche dreht. Ein solcher Punkt existiert immer und der Drehwinkel darin ist kleiner als . Bezeichnen wir diesen Punkt durch O und seine Parameter durch Um diesen Punkt herum konstruieren wir je nach Drehwinkel ein oder zwei Dreiecke. Wenn der Winkel kleiner ist, konstruieren wir aus diesen drei Punkten ein Dreieck (Abb. 9.7.9). Ansonsten konstruieren wir zwei Dreiecke auf dem gegebenen, zwei benachbarten und einem neuen Punkt (Abb. 9.7.11). Der neue Punkt wird mit P bezeichnet. Wir suchen den Punkt P auf der Diagonale des Parallelogramms B OS P. Wenn der Scheitelpunkt des Parallelogramms innerhalb der Ellipse liegt (Abb. 9.7.10), dann nehmen wir ihn als Punkt P. Ansonsten nehmen wir den Schnittpunkt der Ellipse und der Diagonale des Parallelogramms als Punkt P . Im letzteren Fall ist es überhaupt nicht notwendig, nach dem Schnittpunkt der Ellipse und des Segments zu suchen.

Die Koordinaten des Punktes P werden durch die Koordinaten der Punkte O VS bestimmt

Der Winkel des Segments OR mit der Horizontalen wird durch die Gleichheit bestimmt

(9.7.8)

Diese Daten ermöglichen es, die Position des Punktes P relativ zur Ellipse (9.7.5) zu bestimmen.

In dem in Abb. 9.7.9, konstruieren Sie ein Dreieck (merken Sie sich die Nummern seiner Eckpunkte) und löschen Sie den Punkt O im Arbeitspolygon. Im in Abb. 9.7.9 gezeigten Fall. 9.7.11, konstruieren Sie zwei Dreiecke und ersetzen Sie Punkt O im Arbeitspolygon durch Punkt P und platzieren Sie letzteren in der resultierenden Punktanordnung. Auf Abb. In Abb. 9.7.12 zeigt das Polygon, das nach der Konstruktion zweier Dreiecke und der Eliminierung von Punkt O erhalten wurde. In beiden Fällen wird Punkt O aus dem Arbeitspolygon entfernt und das Arbeitspolygon wird schmaler. Beachten Sie, dass Dreiecke nur dann erstellt werden können, wenn sich das Arbeitspolygon nach der Verengung nicht selbst schneidet.

Reis. 9.7.9. Konstruktion eines Dreiecks

Reis. 9.7.10. Ergebnispolygon

Reis. 9.7.11. Konstruktion aus zwei Dreiecken

Reis. 9.7.12. Ergebnispolygon

Solche Situationen sind in Abb. dargestellt. 9.7.13. Sie können auftreten, wenn die Seiten der konstruierten Dreiecke Seiten des Arbeitspolygons schneiden, die nicht an sie angrenzen. Bevor wir ein neues Dreieck konstruieren, wie im Fall in Abb. 9.7.9, und im in Abb. 9.7.9 gezeigten Fall. 9.7.11 muss überprüft werden, ob sich das resultierende Polygon nicht selbst schneidet.

Darüber hinaus ist es bei der Bestimmung der Position des Punktes P wichtig, dass dieser einen ausreichenden Abstand zu anderen Punkten des Arbeitspolygons hat und nicht in die Nähe der die Punkte des Polygons verbindenden Segmente kommt. Andernfalls kann es in Zukunft beim Aufbau von Dreiecken zu Schwierigkeiten kommen. Bevor Sie das Arbeitspolygon verengen, sollten Sie daher das resultierende Polygon auf Selbstüberschneidungen prüfen. Wenn in der Nähe von Punkt O kein Dreieck (Dreiecke) erstellt werden kann, sollten Sie stattdessen einen anderen Punkt finden, an dem sich das Polygon mehr als andere innerhalb der Kontur umschließt, und darin die beschriebenen Aktionen ausführen.

Als nächstes führen wir mit dem modifizierten Arbeitspolygon die gleichen Aktionen aus, die wir gerade beschrieben haben. Suchen wir einen Punkt im Arbeitspolygon, an dem es sich mehr als an anderen Punkten innerhalb der Fläche dreht, prüfen wir die Möglichkeit, das Polygon darin durch die Konstruktion von ein oder zwei Dreiecken zu verengen, und verengen das Polygon.

Reis. 9.7.13. Dreiecke sind in dieser Ecke nicht erlaubt.

Wenn wir diesen Prozess fortsetzen, werden wir die Anordnung der zweidimensionalen Punkte und die Anordnung der Dreiecke erweitern und gleichzeitig das Arbeitspolygon verengen, indem wir die von ihm abgedeckte Fläche und die Anzahl seiner Punkte verringern. Irgendwann im Verlauf dieser Aktionen erhalten wir ein Arbeitspolygon, das aus drei Punkten besteht. Lassen Sie uns das letzte Dreieck auf diesen Punkten aufbauen, das Arbeitspolygon entfernen und die Triangulation abschließen. Bei der beschriebenen Triangulationsmethode wird die durch das Arbeitspolygon begrenzte Fläche sozusagen eliminiert, indem Dreiecke daraus abgeschnitten werden.

Betrachten wir den allgemeinen Fall, wenn der Bereich der Oberflächenparameter durch eine Außenkontur und mehrere Innenkonturen begrenzt ist, die vollständig innerhalb der Außenkontur liegen. Wir approximieren die Oberflächengrenze durch geschlossene Polygone im parametrischen Bereich. Für jede Kontur erstellen wir unser eigenes Polygon. Ebenso wie bei Konturen muss auch bei darauf aufgebauten Polygonen die Regel ihrer gegenseitigen Ausrichtung eingehalten werden. Die Ausrichtung der inneren Polygone muss entgegengesetzt zur Ausrichtung des äußeren Polygons sein. Beginnen wir mit dem Aufbau einer Triangulation mit einem Polygon der Außenkontur. Fügen wir seine Punkte in das resultierende Array zweidimensionaler Punkte ein und sorgen dafür, dass das Polygon selbst funktioniert.

Wir konstruieren Dreiecke auf die gleiche Weise wie im Fall einer einfach zusammenhängenden Region. Suchen wir den Punkt O im Arbeitspolygon, prüfen wir, ob das Arbeitspolygon darin verengt werden kann, und verengen das Polygon. Bei Innenkonturen wird es schwieriger, die Möglichkeit einer Einengung des Arbeitspolygons am ausgewählten Punkt zu prüfen. Zusätzlich zu den beschriebenen Prüfungen des Schnittpunkts der Dreiecksseiten mit den Seiten des Arbeitspolygons müssen Sie den Schnittpunkt der Dreiecksseiten mit den Seiten aller internen Polygone prüfen.

Lassen Sie uns die Möglichkeit prüfen, zwei Dreiecke am Punkt O zu konstruieren (Abb. 9.7.11) und feststellen, dass der neu konstruierte Punkt P in eines der internen Polygone fällt oder sich in unannehmbar enger Nähe zu seinen Segmenten befindet . In diesem Fall erstellen wir keinen Punkt P, sondern beziehen dieses interne Polygon in das Arbeitspolygon ein, indem wir zwei Dreiecke konstruieren, wie in Abb. 9.7.14.

Um die Punkte eines der internen Polygone in das Arbeitspolygon einzubeziehen, suchen wir unter den Punkten des internen Polygons den Punkt, der dem Punkt C (neben Punkt O) des Arbeitspolygons am nächsten liegt.

Wir bauen Dreiecke auf den Punkten OCF und CEF und zwischen den Punkten O und C des Arbeitspolygons fügen wir die Punkte des internen Polygons ein, beginnend mit Punkt F und endend mit Punkt E. Somit brechen wir das Arbeitspolygon auf Segment OS, brechen Sie das interne Polygon auf dem Segment EF und vereinen Sie sie mit den Segmenten OF und EU.

Reis. 9.7.14. Konstruktion aus zwei Dreiecken

Reis. 9.7.15. Äußere und innere Polygone zusammenführen

Das Ergebnis der Fusion ist in Abb. dargestellt. 9.7.15. Natürlich muss vor dem Zusammenführen der äußeren und inneren Polygone die Richtigkeit dieser Operation überprüft werden.

Darüber hinaus werden wir das Arbeitspolygon auf die beschriebene Weise weiter verengen, bis wir uns in unmittelbarer Nähe eines anderen internen Polygons befinden und es in das Arbeitspolygon aufnehmen. Dadurch werden alle internen Polygone in das Arbeitspolygon einbezogen, das auf die letzten drei Punkte eingegrenzt werden sollte. Dadurch wird der gesamte mehrfach zusammenhängende Bereich der Oberflächenparameter mit Dreiecken bedeckt.

Reis. 9.7.16. Dreiecke sind in dieser Ecke nicht erlaubt.

Es gibt Situationen, in denen es unmöglich ist, aus den gegebenen Polygonen ein einzelnes Dreieck zu bilden. Auf Abb. 9.7.16 zeigt eine Fläche, die von zwei Polygonen begrenzt wird, die jeweils aus vier Segmenten bestehen. Für das äußere Polygon können wir die Triangulation nicht fortsetzen, da das innere Polygon interferiert. In diesem Fall finden wir zwei benachbarte Punkte B und C des Polygons, für die wir ein Dreieck VSR konstruieren können. Der Punkt P wird auf die Mitte der Seite BC projiziert und liegt in einem solchen Abstand davon, dass das neue Dreieck die Polygone nicht schneidet.

Andere Triangulationsmethoden.

Es gibt andere Möglichkeiten der Triangulation. Beispielsweise kann nach der Konstruktion der Polygone der Außen- und Innenkonturen des Oberflächendefinitionsbereichs eine andere Strategie zur Konstruktion von Dreiecken gewählt werden. Alternativ können Sie die äußeren und inneren Polygone zu einem Polygon zusammenführen, bevor Sie mit der Triangulation beginnen. Es ist möglich, Punkte innerhalb des Parameterdefinitionsbereichs nach einem bestimmten Algorithmus zu „zeichnen“ und mit ihnen und Punkten von Grenzkonturpolygonen eine Delaunay-Triangulation durchzuführen. Es gibt Algorithmen, die zunächst große Dreiecke erstellen und diese dann in akzeptable Größen aufteilen.

Triangulation des Körpers.

Bei der Triangulation eines Körpers handelt es sich um eine Menge von Dreiecken, die man durch Triangulation der Oberflächen seiner Flächen erhält. Die Triangulation einzelner Flächen unterscheidet sich von der Triangulation von Körperflächen dadurch, dass im letzteren Fall die Grenzpolygone benachbarter Flächen abgeglichen werden müssen (Abb. 9.7.17).

Reis. 9.7.17. Konsistenz der Grenzpolygone von Körperflächen

Abschnitte von Polygonen benachbarter Flächen, die entlang gemeinsamer Kanten verlaufen, sind konsistent, wenn ihre Punkte im Raum zusammenfallen.

Anwendung der Triangulation.

Die als Ergebnis der Triangulation konstruierten Dreiecke werden verwendet, um Tonbilder zu erhalten. Auf Abb. Die Abbildungen 9.7.18 und 9.7.19 zeigen Triangulationen der Oberfläche eines Blattkörpers, dessen Tonbild in Abb. dargestellt ist. 6.5.1.

Reis. 9.7.18. Triangulation eines Körpergesichts mit der Korrekturmethode

Die Aufteilung des Definitionsbereichs von Oberflächenparametern in Dreiecke kann in Integralen (8.6.2), (8.6.3), (8.6.12), (8.7.17)–(8.7.22) bei der Berechnung der geometrischen Eigenschaften von verwendet werden Körper. Für die numerische Integration sollte der parametrische Schritt für Kurven mit der Formel (8.11.5) berechnet werden, und für Flächen sollte der parametrische Schritt mit den Formeln (8.11.1) und (8.11.2) berechnet werden.

Das Senden Ihrer guten Arbeit an die Wissensdatenbank ist ganz einfach. Nutzen Sie das untenstehende Formular

Einführung

Heute, zu Beginn des 21. Jahrhunderts, tritt die Menschheit in eine neue Zivilisation ein – eine Zivilisation, die mit dem Eindringen von Computern in alle Bereiche des menschlichen Lebens verbunden ist. Diese Zivilisation heißt Information, virtuell, Computer.

Einer der Bereiche der theoretischen Informatik ist die Computergeometrie , das Methoden zur Lösung geometrischer Probleme am Computer mithilfe von Algorithmen und Programmen entwickelt.

ZielarbeitenUndAufgaben: Untersuchung eines der iterativen Algorithmen zur Konstruktion der Delaunay-Triangulation.

1) Studieren Sie die grundlegenden Definitionen und Theoreme des Delaunay-Triangulationsproblems;

2) Betrachten Sie die wichtigsten Arten iterativer Algorithmen zur Konstruktion der Triangulation;

3) Implementieren Sie den „Delete and Build“-Algorithmus zur Konstruktion der Delaunay-Triangulation.

1. allgemeine Beschreibung Delaunay-Triangulation

Die Aufgabe, eine Triangulation zu konstruieren.

TriangulationDelaunay Für eine Menge von Punkten S in der Ebene heißt eine Triangulation DT (S), so dass kein Punkt A aus S in einem Kreis enthalten ist, der um ein beliebiges Dreieck aus DT (S) so umschrieben ist, dass keiner seiner Eckpunkte ein Punkt A ist.

1.1 Analyse der Literatur zum Thema

Es gibt auch Abschnitte, in denen Algorithmen zur Konstruktion von Triangulationen ausführlich beschrieben werden Vergleichsmerkmale und die Komplexität der Algorithmen.

Was geliehen: Grundlagenmaterial, theoretische Informationen, Definitionen, Zeichnungen.

Was geliehen: mathematische Beschreibung Delaunay-Triangulationen, Konstruktion im euklidischen Raum

MedwedewH.N.MethodeVoronoi - DelaunayVForschungStrukturennicht kristallinSysteme/ RAS,Nowosibirskrsk: VerlagSORAS,2000, - 214 Mit. Ein Buch, das der Beschreibung der Voronoi- und Delaunay-Methoden in nichtkristallinen Systemen gewidmet ist.

Was geliehen: Eigenschaften von Delaunay-Triangulationen, Definition von Delaunay-Triangulationen.

1.2 Grundlegende Definitionen und Eigenschaften

Triangulation ist ein planarer Graph, dessen innere Bereiche alle Dreiecke sind.

Eigenschaften:

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

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

· Die Delaunay-Triangulation maximiert den minimalen Winkel aller Winkel aller konstruierten Dreiecke und vermeidet so „dünne“ Dreiecke.

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

· Die Delaunay-Triangulation minimiert die diskrete Dirichlet-Funktion.

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

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

Abb. 1. Triangulation.

konvex Triangulation Eine Triangulation heißt so, dass das kleinste Polygon, das alle Dreiecke umschließt, konvex ist. Eine Triangulation, die nicht konvex ist, heißt nicht konvex.

Aufgabe Gebäude Triangulation Von gegeben Satz zweidimensional Punkte nennt man das Problem, gegebene Punkte durch sich nicht schneidende Segmente so zu verbinden, dass eine Triangulation entsteht.

Triangulation soll befriedigend sein Zustand Delaunay , wenn keiner der angegebenen Triangulationspunkte innerhalb des Kreises liegt, der um ein konstruiertes Dreieck beschrieben wird.

TriangulationgenanntTriangulation Delaunay , wenn es konvex ist und die Delaunay-Bedingung erfüllt.

Abb. 2. Delaunay-Triangulation.

1.3 Delaunays Leerball-Methode. Konstruktion im allgemeinen Fall

Nehmen wir eine leere Kugel, die wir bewegen und dabei ihre Größe ändern, sodass sie die Punkte des Systems (A) berühren kann, aber immer leer bleibt.

Abb.3 – Delaunay-Partition eines zweidimensionalen Punktesystems

Delaunays Einfachheiten füllen den Raum ohne Lücken und Überschneidungen.

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

1.4 Anwendung der Delaunay-Triangulation

Bei der 2D-Interpolation teilt die Delaunay-Triangulation die Ebene in möglichst dicke Dreiecke auf und vermeidet so zu spitze oder zu stumpfe Winkel. Diese Dreiecke können beispielsweise zum Aufbau einer bilinearen Interpolation verwendet werden.

Abb.4. Ein Beispiel für die Berechnung von Hangexpositionen mithilfe eines Reliefmodells

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

2. Beschreibung der Konstruktionsalgorithmen

Im Allgemeinen basieren alle Algorithmen auf einer sehr einfachen Idee, Punkte sequentiell zu einer teilweise konstruierten Delaunay-Triangulation hinzuzufügen. Formal sieht es so aus.

Gegeben ein Haufen aus N Punkte.

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

2. Führen Sie im Zyklus für n für alle anderen Punkte die Schritte 3–5 aus.

5. Lokale Überprüfungen der neu gewonnenen Dreiecke auf Einhaltung der Delaunay-Bedingung werden durchgeführt und die notwendigen Umordnungen vorgenommen.

Ende Algorithmus.

Unter gegeben ist detailliert Beschreibung mehrere Algorithmen.

2.1 Greedy-Algorithmus

Einer der ersten schlug den folgenden Algorithmus zur Konstruktion der Triangulation vor.

GierigMethode Dies ist eine Methode, die niemals das rückgängig macht, was bereits zuvor getan wurde. Die folgenden Schritte werden im Algorithmus nacheinander ausgeführt.

1. Die Enden aller Struktursegmente werden in der Menge der Anfangspunkte platziert.

2. Segmente, die alle Punktpaare verbinden, werden generiert, die Segmente werden nach Länge sortiert.

3. Alle Bruchkantensegmente werden in die Triangulation eingefügt.

Schritt 4 wird wiederholt, bis die Segmente aufgebraucht sind.

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

Triangulation heißt gierig wenn es von einem gierigen Algorithmus erstellt wird.

2.2 Algorithmus „Löschen und erstellen“

Reis. 4. Algorithmus „Löschen und erstellen“

2.3 Algorithmus „Build by Breaking“

Der Algorithmus zum Einfügen von Struktursegmenten „Build by Breaking“ ist am einfachsten in der Implementierung und stabil im Betrieb.

Reis. 5. Algorithmus „Build by Breaking“

2.4 Algorithmus mit k-D-Baum-Indizierung der Mittelpunkte von Dreiecken

3. Bewertung der Effizienz von Algorithmen

3.1 Einfacher iterativer Algorithmus

3.2 Iterativer Algorithmus mit Dreiecksindizierung

3.3 Iterativer Algorithmus mit K-D-Baumindizierung von Dreieckszentren

Daraus erhalten wir, dass die Komplexität des Triangulationsalgorithmus mit Indizierung der Mittelpunkte von Dreiecken im schlimmsten Fall im Durchschnitt O (N log N) beträgt.

3.4 Lüfteralgorithmus

Die Komplexität eines solchen Algorithmus beträgt im Durchschnitt O N (). Der Algorithmus arbeitet ungefähr mit der gleichen Geschwindigkeit wie der vorherige Algorithmus.

4. Softwareteil

hauptsächlich. cpp – Fensterfunktionen, Benutzeroberflächenfunktionen

delone. cpp – Algorithmus und Funktionen, die für die Arbeit damit notwendig sind

Beschreibung der Programmfunktionen:

void DrawPoint (int x, int y) – Funktion zum Zeichnen eines Punktes im Anwendungsfenster

void Triangulation() – Funktion zur Durchführung einer Triangulation

void TriangulationIn () – eine Funktion zum Ausführen von Aktionen mit Punkten, die innerhalb eines Dreiecks liegen

void TriangulationOut() – eine Funktion zum Ausführen von Aktionen mit Punkten, die außerhalb des Dreiecks liegen.

**TriangulationgenanntTriangulation *Delaunay*** , wenn es konvex ist und die Delaunay-Bedingung erfüllt.