20. August 2012 um 22:41 Uhr

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

• Bildverarbeitung ,
• Programmierung

Ich verrate Ihnen ein Geheimnis, wie Sie die Delaunay-Bedingung für zwei Dreiecke schnell überprüfen können.
Eigentlich wird die Optimierung selbst etwas weiter unten beschrieben (siehe „Optimierung des Algorithmus zur Überprüfung der Delaunay-Bedingung durch die Umkreisgleichung“), aber ich erzähle Ihnen alles der Reihe nach.

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 Phasen unterteilt: Anpassen, Grenzen erkennen, Grenzen umgehen, Konturen ausstreichen. Dies ist im allgemeinsten Sinne. Ich würde, glaube ich, gerne bei der schwierigsten Phase aufhören: dem Fegen des Flugzeugs.

Am Eingang

Nachdem ich die Grenzen erkannt und überschritten hatte, erhielt ich am Ausgang viele äußere Schleifen. Jede berührende Kontur hat verschiedene Farben. Jeder dieser Schaltkreise enthält auch eine bekannte Anzahl interner Schaltkreise.
Unter dem Gesichtspunkt des „Überstreichens der Ebene“ haben wir also, wenn wir die Außenkonturen separat betrachten, eine Menge von Punkten, von denen jeder rechts und links einen Nachbarn hat. Diese. Alle Punkte sind in einer Kette geschlossen, es gibt keinen einzigen „hängenden“ Punkt und jede Kette enthält mindestens 3 Punkte (Abbildung 1).

Bild 1

Was muss getan werden?

Sie müssen die Figur mit Dreiecken bedecken.

Suchen

Nachdem ich das Buch gelesen hatte, fand ich keine einzige (zumindest eine) Methode zur Konstruktion einer Delaunay-Triangulation, die für meinen Fall zumindest einigermaßen geeignet wäre. Ich habe nicht nach anderen Büchern gesucht. Und das reichte, es brachte die Gedanken in meinem Kopf in Ordnung. Daraufhin erfand er sein eigenes „Fahrrad“.

Algorithmus

1) Nehmen wir zunächst einmal an, dass es in der betrachteten Abbildung nur eine Sequenz gibt. Dann kommt es darauf an, nacheinander Dreiecke zu nehmen. Wir nehmen einen beliebigen Punkt und versuchen, mit benachbarten Punkten ein Dreieck zu konstruieren. Wenn es nicht möglich war, ein Dreieck zu bilden (die Linie, die diese beiden Punkte verbindet, schneidet die bereits erstellten oder die Linie verläuft in der Sperrzone (Abbildung 2), bewegen wir uns zum nächsten Punkt, beispielsweise nach rechts. Wenn das nächste Dreieck entsteht Wenn es gefunden wird, fügen wir es der Liste hinzu (Abbildung 3) und entfernen den Punkt, von dem aus es erstellt wurde (Abbildung 4).

Figur 2

Figur 3

Figur 4

Noch etwas: Beim Speichern des nächsten Dreiecks ist es notwendig, die Eckpunkte im Uhrzeigersinn (im rechten Koordinatensystem) aufzuzeichnen. Dies wird in Zukunft nützlich sein, um Rechenressourcen zu reduzieren.

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

3) Bei mehreren Sequenzen, d.h. eine, und darin befinden sich eine oder mehrere Innenkonturen (Abbildung 1). Hier ist es notwendig, jede Sequenz einzeln zu betrachten. Nehmen wir eine weitere Innenkontur. Aus einem externen und einem internen erstellen wir zwei einzelne Schaltkreise. Dazu müssen Sie zwei „Ports“ von einem Stromkreis zum anderen finden. Bedingung für „Anschlüsse“: Sie sollten sich nicht überschneiden (auch ihre Enden sollten sich nicht berühren) und sollten sich nicht mit Konturlinien überschneiden (Abbildung 5).

Abbildung 5

Abbildung 6
4) Als nächstes sollten Sie nacheinander alle internen Sequenzen getrennt voneinander in die bereits gebildeten Sequenzen eintragen (Punkt 3). Sie müssen es mit dem zusammenführen, das das neue enthält. Per Definition berührt oder überschneidet sich keine interne Sequenz mit anderen (sowohl einer externen als auch allen möglichen internen), sodass alles reibungslos verläuft.
Nachdem die Ports gefunden wurden (Abbildung 6), ist es einfach, neue Sequenzen zu erstellen und diese mithilfe der Punkte 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). Es ist, als wäre die Aufgabe bereits erledigt, aber es bleibt nur noch, das Bild schön zu machen: Überprüfen Sie, ob die Delaunay-Bedingung erfüllt ist (Abbildung 9).

Abbildung 8

Abbildung 9

6) Mit Blick auf die Zukunft erzähle ich Ihnen den sechsten Punkt. Es besteht darin, die Liste der erhaltenen Dreiecke nacheinander mit Schritt Nr. 5 durchzugehen. 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 die Nachbarn und das aktuelle Dreieck neu auf und markieren sie als „schmutzig“. Wenn die Bedingung erfüllt ist, markieren wir es als sauber. In meiner Implementierung des Algorithmus hat jedes Dreieck eine Verbindung zu seinen Nachbarn. In diesem Fall funktioniert Punkt 6 am schnellsten.

Mehr zur fünften Etappe

Soweit ich weiß, sind es zwei mögliche Wege Bestimmen Sie, 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 den Abstand 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 multiplizieren/dividieren und 13 addieren/subtrahieren.
Rechenleistung Nr. 2: 29 Multiplikations-/Divisionsoperationen und 24 Additions-/Subtraktionsoperationen.

Aus Sicht der Rechenleistung, die beispielsweise im Buch berechnet wird, ist Option Nr. 1 rentabler. Ich hätte es umgesetzt, wenn nicht... (Abbildung 10). Wie sich nach der Produktion herausstellte diese Methode Auf das „Förderband“ kam es zu Unsicherheit. Dies ist eine Option, wenn Winkel A selbst mehr als 180 Grad beträgt. Sie wird im Buch als eine der individuellen Privatmethoden betrachtet. Und damit verschwindet all seine Eleganz, Transparenz und Leistung. Und es stellte sich später auch heraus, dass Methode Nr. 2 sehr deutlich optimiert werden kann.

Abbildung 10

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

Als nächstes kommt die reine Mathematik.

Also haben wir:
Die Überprüfung der Bedingung für den Punkt M(X, Y) anhand der 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) ⋅ Vorzeichen a ≥ 0

Einzelheiten finden Sie im hervorragenden Buch. (Nein, ich bin nicht der Autor)
Das Zeichen a ist also das Richtungszeichen der Durchquerung. Ich habe die Dreiecke von Anfang an im Uhrzeigersinn erstellt, sodass es weggelassen werden kann (es ist gleich eins).

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

D>=0

Abbildung 11

Einfach, nicht wahr?

Dem Buch zufolge wiederum

(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 Tom. Universität, 2002. – 128 S. ISBN 5-7511-1501-5

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

Das topologische Kriterium basiert auf den nächsten Nachbarn eines Punktes aus einer Menge. Im Idealfall hat ein Punkt 6 Nachbarn für eine zweidimensionale Region und 12 Nachbarn für eine dreidimensionale Region. Wir erhalten eine topologische Schätzung mithilfe der Formel (1), wobei die Gesamtzahl der Punkte in der Fläche der Grad oder die Anzahl benachbarter Punkte ist, die mit einem internen Punkt verknüpft sind.

Das geometrische Kriterium basiert auf der Differenz zwischen den eingeschriebenen und umschriebenen Kreisen um das dreieckige Designelement. Wir erhalten eine geometrische Schätzung mit Formel (2), wobei die Anzahl der Dreiecke, der Radius des eingeschriebenen Kreises und der Radius des umschriebenen Kreises sind.

Algorithmen zur Konstruktion der Triangulation

Es gibt eine große Anzahl von Algorithmen zur Konstruktion einer Triangulation. Sie unterscheiden sich in der Arbeitsintensität, der Komplexität der Implementierung am Computer und den Konstruktionsansätzen. Weitere Informationen zu Algorithmen finden Sie im Buch von A.V. Skvortsova. Schauen wir uns einige Algorithmen an.

Einer der ersten, der vorgeschlagen wurde Gieriger Algorithmus Konstruktion der Triangulation. Eine Delaunay-Triangulation wird als Greedy-Triangulation bezeichnet, wenn sie mithilfe eines Greedy-Algorithmus erstellt wird. Die Komplexität des Greedy-Algorithmus mit einigen seiner Verbesserungen beträgt . Aufgrund der hohen Arbeitsintensität wird es in der Praxis fast nie eingesetzt. Schauen wir uns den Algorithmus Schritt für Schritt an:

Schritt 1. Eine Liste aller möglichen Segmente, die Quellpunktpaare verbinden, wird generiert und nach Segmentlängen sortiert.

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

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

Iterativer Algorithmus basieren auf einer sehr einfachen Idee, Punkte nacheinander zu einer teilweise konstruierten Delaunay-Triangulation hinzuzufügen. Die Komplexität dieses Algorithmus besteht aus der Komplexität der Suche nach einem Dreieck, zu dem im nächsten Schritt ein Punkt hinzugefügt wird, der Komplexität der Konstruktion neuer Dreiecke sowie der Komplexität entsprechender Rekonstruktionen der Triangulationsstruktur als Ergebnis unbefriedigender Ergebnisse Überprüfung von Paaren benachbarter Dreiecke der resultierenden Triangulation auf Erfüllung der Delaunay-Bedingung. Schauen wir uns den Algorithmus Schritt für Schritt an:

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

Schritt 2. Im Zyklus für alle anderen Punkte führen wir die Schritte 3-5 durch.

Schritt 3. Der nächste i-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.

Schritt 4. Fällt ein Punkt auf einen zuvor eingefügten Triangulationsknoten, so wird ein solcher Punkt in der Regel verworfen, andernfalls wird der Punkt als neuer Knoten in die Triangulation eingefügt. Wenn der Punkt außerdem auf eine Kante fällt, 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 konstruiert.

Schritt 5. Es werden lokale Kontrollen der neu gewonnenen Dreiecke auf Einhaltung der Delaunay-Bedingung durchgeführt und die notwendigen Rekonstruktionen durchgeführt.

Beim Konstruieren neuer Dreiecke sind zwei Situationen möglich: Der hinzugefügte Punkt liegt entweder innerhalb der Triangulation oder außerhalb. Im ersten Fall werden neue Dreiecke konstruiert und die Anzahl der vom Algorithmus durchgeführten Aktionen festgelegt. Im zweiten Fall ist es notwendig, zusätzliche Dreiecke außerhalb der aktuellen Triangulation zu konstruieren, und ihre Anzahl kann im schlimmsten Fall gleich sein? 3. Während aller Schritte des Algorithmus werden jedoch keine weiteren Dreiecke hinzugefügt, wobei - Gesamtzahl Ausgangspunkte. Daher beträgt die Gesamtzeit, die für die Konstruktion von Dreiecken aufgewendet wird, in beiden Fällen.

Kettenalgorithmus Einer der ersten effektiven Algorithmen zur Konstruktion einer Triangulation basiert auf dem Verfahren der Regularisierung eines planaren Graphen und der Triangulation monotoner Polygone. Die Komplexität dieses Algorithmus liegt in der Anzahl der Anfangssegmente. Schauen wir uns den Algorithmus Schritt für Schritt an:

Schritt 1. Aus der Menge der anfänglichen Struktursegmente bilden wir einen verbundenen planaren Graphen (Abbildung 4, a).

Schritt 2. Der Graph ist reguliert, d.h. Es werden neue Kanten hinzugefügt, die andere nicht schneiden, sodass jeder Scheitelpunkt des Diagramms an mindestens einen Scheitelpunkt darüber und einen darunter angrenzt. Die Regularisierung erfolgt in zwei Durchgängen mittels vertikalem Flat Sweeping. Im ersten Durchgang von unten nach oben werden nacheinander alle Eckpunkte gefunden, aus denen keine nach oben führenden Kanten hervorgehen. In (Abbildung 4,b) ist dies beispielsweise der Scheitelpunkt B. Indem wir eine horizontale Linie zeichnen, finden wir die nächstgelegenen Kanten des Graphen AD und EF, die er links und rechts schneidet. Dann finden wir im Viereck DEHG den niedrigsten Scheitelpunkt und zeichnen eine Kante von B hinein. Der zweite Durchgang von oben nach unten wird ähnlich 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 zur nichtkonvexen Verschmelzung zweier Triangulationen verwenden (Abbildung 4, d).

Abbildung 4. Funktionsschema des Kettentriangulationsalgorithmus: a) - Anfangssegmente; b – Bottom-Up-Durchgang der Graph-Regularisierung; c) - Durchgang von oben nach unten; d) - Triangulation monotoner Polygone

Um einen verketteten Algorithmus zu implementieren, verwenden Sie am besten Datenstrukturen, in denen Kanten explizit dargestellt werden, wie zum Beispiel „Doppelte Kanten“ oder „Knoten, Kanten und Dreiecke“.

Der Nachteil des Kettenalgorithmus besteht darin, dass über die Form der resultierenden Triangulation nichts im Voraus gesagt werden kann. Dies ist keine optimale Triangulation, keine gierige 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 Sie alle Paare benachbarter Dreiecke, die nicht durch eine Strukturkante getrennt sind, auf die Delaunay-Bedingung überprüfen und gegebenenfalls Rekonstruktionen durchführen. Das Ergebnis wird eine Delaunay-Triangulation mit Einschränkungen sein.

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 sei eine Menge von N Punkten.

1. Wir bauen aus den ersten drei Startpunkten ein Dreieck.

2. Führen Sie in einer Schleife von 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. Fällt ein Punkt auf einen zuvor eingefügten Triangulationsknoten, 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 fällt, wird er in zwei neue geteilt, und beide an die Kante angrenzenden Dreiecke werden ebenfalls in zwei kleinere geteilt. Liegt ein Punkt genau innerhalb eines Dreiecks, wird er in drei neue aufgespalten. Liegt der Punkt außerhalb der Triangulation, werden ein oder mehrere Dreiecke konstruiert.

5. Lokale Überprüfungen der neu gewonnenen Dreiecke auf Einhaltung der Delaunay-Bedingung und die Durchführung der notwendigen Rekonstruktionen.

Ende des Algorithmus.

Nachfolgend finden Sie eine detaillierte Beschreibung mehrerer Algorithmen.

Gieriger Algorithmus

Einer der ersten, der den folgenden Algorithmus zur Konstruktion der Triangulation vorschlug.

Gierige Methode- Dies ist eine Methode, bei der das, was bereits zuvor getan wurde, niemals rückgängig gemacht wird. Der Algorithmus führt die folgenden Schritte nacheinander aus.

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 Segmente der Strukturlinien werden in die Triangulation eingefügt.

4. Für die Triangulation werden Segmente nacheinander aus einem Satz von Segmenten ausgewählt, die nach Länge sortiert sind (von kürzer nach länger). Wenn sich ein 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 Reihenfolge des Einfügens von Segmenten gleicher Länge ab.

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

Algorithmus „Löschen und Erstellen“

Remove and Build führt keine Neuerstellungen durch. Stattdessen werden bei jedem Einfügen eines neuen Knotens (a) alle Dreiecke, in denen der neue Knoten (b) in die umschriebenen Kreise fällt, sofort gelöscht. In diesem Fall bilden alle entfernten Dreiecke implizit ein Polygon. Anschließend wird anstelle der entfernten 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 Rekonstruktionen desselben Dreiecks möglich sind. Hier steht jedoch das Verfahren zum Extrahieren der Kontur eines entfernten Polygons im Vordergrund, von dessen Effizienz die Gesamtgeschwindigkeit des Algorithmus abhängt. Abhängig von der verwendeten Datenstruktur kann dieser Algorithmus im Allgemeinen weniger Zeit in Anspruch nehmen als ein Algorithmus mit Neuerstellungen und umgekehrt.

Algorithmus „Build by Breaking“

Der „Build by Breaking“-Algorithmus zum Einfügen von Struktursegmenten ist am einfachsten zu implementieren und im Betrieb am stabilsten.

Darin ist es notwendig, durch sequentielles Bewegen der Dreiecke entlang des eingefügten Segments die Schnittpunkte mit den Triangulationskanten zu finden. An diesen Schnittpunkten müssen Sie neue Triangulationsknoten platzieren und die vorhandenen Kanten und Dreiecke in Teile aufteilen. Danach müssen alle neu konstruierten Dreiecke auf die Delaunay-Bedingung überprüft und ggf. ohne Beeinträchtigung der festen Kanten rekonstruiert werden.

Reis. 5. Algorithmus „Build by Breaking“

In einigen Fällen kann ein Nachteil dieses Einfügungsalgorithmus in der Erstellung liegen große Zahl zusätzliche Knoten und Triangulationskanten. Gleichzeitig wird dieser Nachteil in anderen Fällen zum Vorteil, da er die Bildung langer schmaler Dreiecke verhindert, was besonders bei der Geländemodellierung von Nutzen ist.

Ein weiterer Vorteil dieses Einfügealgorithmus im Vergleich zu nachfolgenden Algorithmen 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 Rippen werden, wie alle anderen auch, einfach in zwei Teile gebrochen.

Algorithmus mit Indizierung der Dreieckszentren durch den k-D-Baum

Im Triangulationsalgorithmus mit Indizierung von Dreieckszentren durch einen k-D-Baum werden nur die Zentren von Dreiecken im k-D-Baum platziert (mit k = 2). Beim Löschen alter Dreiecke ist es notwendig, deren Mittelpunkte aus dem k-D-Baum zu entfernen und beim Aufbau neuer Dreiecke hinzuzufügen.

Um nach einem Dreieck zu suchen, das den aktuellen Punkt enthält, der in die Triangulation eingefügt wird, muss eine nicht standardmäßige Punktabfrage im k-D-Baum durchgeführt werden. Die Suche in einem Baum muss an der Wurzel beginnen und bis zu den Blättern reichen. Wenn die Nachkommen des aktuellen k-D-Baumknotens (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 das gefundene Dreieck nicht passt Sollwert, dann ist es dann notwendig, den üblichen Algorithmus zur Suche nach einem Dreieck aus einem einfachen iterativen Algorithmus zur Konstruktion der Delaunay-Triangulation zu verwenden.

Die Triangulation für eine endliche Menge von Punkten S ist das Problem der Triangulation der konvexen Hülle CH(S), die alle Punkte der Menge S umschließt. Gerade Segmente in der Triangulation können sich nicht schneiden – sie können sich nur an gemeinsamen Punkten treffen, die zur Menge S gehören. Da Gerade Segmente schließen Dreiecke, wir betrachten sie als Rippen. In Abb. Abbildung 1 zeigt zwei verschiedene Versionen der Triangulation für denselben Punktsatz (wir werden die in diesen Abbildungen gezeichneten Kreise vorübergehend ignorieren).

Reis. 1

Für eine gegebene Menge von Punkten S können wir sehen, dass alle Punkte aus der Menge S in Randpunkte – die Punkte, die auf der Grenze der konvexen Hülle CH(S) liegen – und innere Punkte – die innerhalb der konvexen Hülle liegen – unterteilt werden können Rumpf CH(S). Sie können die durch die Triangulation S erhaltenen Kanten auch klassifizieren als Muschelrippen Und innere Rippen. Zu den Hüllenkanten gehören die Kanten, die sich entlang der Grenze der konvexen Hülle CH(S) befinden, und zu den Innenkanten gehören alle anderen Kanten, die innerhalb der konvexen Hülle ein Netzwerk aus Dreiecken bilden. Beachten Sie, dass jede Schalenkante zwei benachbarte Grenzpunkte verbindet, während Innenkanten zwei Punkte beliebiger Art verbinden können. Insbesondere wenn eine Innenkante zwei Randpunkte verbindet, dann ist sie eine Sehne der konvexen Hülle CH(S). Beachten Sie auch, dass jede Kante der Triangulation die Grenze zweier Regionen ist: Jede Innenkante liegt zwischen zwei Dreiecken und jede Kante der Schale liegt zwischen einem Dreieck und einer unendlichen Ebene.

Mit Ausnahme einiger trivialer Fälle erlaubt jede Punktmenge mehr als eine Triangulationsmethode. Aber es gibt eine bemerkenswerte Eigenschaft: Jede Triangulationsmethode für eine gegebene Menge bestimmt die gleiche Anzahl von Dreiecken, was aus dem Satz folgt:

Ein Satz über die Triangulation einer Menge von Punkten. Angenommen, die Punktmenge S enthält n>3 Punkte und nicht alle davon sind kollinear. Darüber hinaus sind i Punkte von ihnen intern (d. h. liegen innerhalb der konvexen Hülle CH(S). Dann führt jede Methode der Triangulation der Menge S zu genau n + i - 2 Dreiecken.

Um den Satz zu beweisen, betrachten Sie zunächst n-i-Triangulation Grenzpunkte. Da sie alle Eckpunkte eines konvexen Polygons sind, führt eine solche Triangulation zu (n – i) – 2 Dreiecken. (Dies ist nicht schwer zu überprüfen und darüber hinaus kann gezeigt werden, dass jede Triangulation willkürlich Ein m-seitiges Polygon – konvex oder nicht konvex – enthält m – 2 Dreiecke). Schauen wir uns nun an, was mit der Triangulation passiert, wenn die verbleibenden i internen Punkte hinzugefügt werden, jeweils einer. Wir behaupten, dass das Hinzufügen jedes dieser Punkte die Anzahl der Dreiecke um zwei erhöht. Beim Hinzufügen eines internen Punktes können zwei Situationen auftreten, wie in Abb. 2. Erstens kann der Punkt innerhalb eines Dreiecks liegen und dann wird ein solches Dreieck durch drei neue Dreiecke ersetzt. Zweitens: Wenn ein Punkt mit einer der Triangulationskanten zusammenfällt, wird jedes der beiden an diese Kante angrenzenden Dreiecke durch zwei neue Dreiecke ersetzt. Daraus folgt, dass nach der Addition aller i Punkte die Gesamtzahl der Dreiecke (n – i – 2) + (2i) oder einfach n + i – 2 beträgt.

Reis. 2

In diesem Abschnitt stellen wir einen Algorithmus zum Erzeugen einer speziellen Art von Triangulation vor, die als Delaunay-Triangulation bekannt ist. Diese Triangulation ist in dem Sinne gut ausbalanciert, dass die gebildeten Dreiecke tendenziell gleichwinklig sind. Zum Beispiel die in Abb. 1a lässt sich dem Delaunay-Triangulationstyp zuordnen, und in Abb. Die 1b-Triangulation enthält mehrere stark verlängerte Dreiecke und kann nicht dem Delaunay-Typ zugeordnet werden. In Abb. Abbildung 3 zeigt ein Beispiel einer Delaunay-Triangulation für eine Menge von vielen Punkten.

Reis. 3

Um eine Delaunay-Triangulation zu bilden, benötigen wir mehrere neue Definitionen. Eine Punktmenge gilt als kreisförmig, wenn es einen Kreis gibt, auf dem alle Punkte der Menge liegen. Ein solcher Kreis wird für eine gegebene Menge von Punkten umschrieben. Der umschriebene Kreis eines Dreiecks verläuft durch alle drei seiner (nicht kollinearen) Eckpunkte. Man sagt, dass ein Kreis in Bezug auf eine gegebene Menge von Punkten S punktfrei ist, wenn sich innerhalb des Kreises keine Punkte aus der Menge S befinden. Es können jedoch Punkte aus der Menge S auf dem Kreis liegen am punktlosesten.

Eine Triangulation einer Menge von Punkten S ist eine Delaunay-Triangulation, wenn der Umkreis für jedes Dreieck punktfrei ist. Im Triangulationsdiagramm Abb. Abbildung 1a zeigt zwei Kreise, die offensichtlich keine anderen Punkte enthalten (Sie können Kreise für andere Dreiecke zeichnen, um sicherzustellen, dass sie auch frei von Punkten der Menge sind). Diese Regel wird im Diagramm in Abb. nicht beachtet. 16 - Ein Punkt eines anderen Dreiecks liegt innerhalb des gezeichneten Kreises, daher gehört diese Griangulation nicht zum Delaunay-Typ.

Über die Punkte in der Menge S können zwei Annahmen getroffen werden, um den Triangulationsalgorithmus zu vereinfachen. Damit es überhaupt eine Triangulation gibt, müssen wir zunächst annehmen, dass die Menge S mindestens drei Punkte enthält und diese nicht kollinear sind. Zweitens ist es für die Eindeutigkeit einer Delaunay-Triangulation notwendig, dass keine vier Punkte aus der Menge S auf demselben Umkreis liegen. Es ist leicht zu erkennen, dass die Delaunay-Triangulation ohne eine solche Annahme nicht eindeutig sein wird, da 4 Punkte auf einem umschriebenen Kreis es uns ermöglichen, zwei verschiedene Delaunay-Triangulationen zu realisieren.

Unser Algorithmus funktioniert, indem er die aktuelle Triangulation kontinuierlich um ein Dreieck nach dem anderen vergrößert. Die aktuelle Triangulation besteht zunächst aus einer einzelnen Kante der Schale; am Ende des Algorithmus wird die aktuelle Triangulation zu einer Delaunay-Triangulation. Bei jeder Iteration sucht der Algorithmus nach einem neuen Dreieck, das eine Verbindung herstellt Grenze aktuelle Triangulation.

Die Definition der Grenze hängt vom folgenden Klassifizierungsschema für die Kanten der Delaunay-Triangulation relativ zur aktuellen Triangulation ab. Jede Kante kann sein Schlafen, lebendig oder tot:

• Schlafrippen: Eine Kante einer Delaunay-Triangulation ist ruhend, wenn sie vom Algorithmus noch nicht erkannt wurde;
• lebende Rippen: Die Rippe ist lebendig, wenn sie gefunden wird, aber nur ein angrenzender Bereich bekannt ist;
• tote Rippen: Eine Kante gilt als tot, wenn sie gefunden wird und beide angrenzenden Bereiche bekannt sind.

Zunächst ist die einzige Kante, die zum konvexen i-Lappen gehört, lebendig – eine unbegrenzte Ebene grenzt daran an und alle anderen Kanten sind ruhend. Während der Algorithmus funktioniert, wechseln die Kanten von „schlafend“ zu „lebendig“ zu „tot“. Die Grenze in jeder Phase besteht aus einer Reihe lebender Kanten.

Bei jeder Iteration wird eine der Kanten der Grenze ausgewählt und einer Verarbeitung unterzogen, die darin besteht, nach einer unbekannten Region zu suchen, zu der die Kante e gehört. Wenn sich herausstellt, dass es sich bei dieser Region um ein Dreieck f handelt, das durch definiert ist Endpunkte der Kante e und ein dritter Scheitelpunkt v, dann wird die Kante e tot , da beide angrenzenden Flächen nun bekannt sind. Jede der beiden anderen Kanten des Dreiecks t wird in den folgenden Zustand überführt: vom Schlafen zum Lebendigen oder vom Lebenden zum Toten. Hier wird der Knoten v aufgerufen konjugieren mit Kante e. Andernfalls, wenn sich herausstellt, dass der unbekannte Bereich eine unendliche Ebene ist, stirbt Kante e einfach. In diesem Fall hat Kante e keinen konjugierten Scheitelpunkt.

In Abb. Abbildung 4 zeigt die Funktionsweise des Algorithmus, wobei die Aktion von oben nach unten und von oben nach rechts erfolgt. Der Rand jeder Stufe wird durch eine dicke Linie hervorgehoben.

Der Algorithmus ist im Programm delaunayTriangulate implementiert. Das Programm erhält ein Array s mit n Punkten und gibt eine Liste von Dreiecken zurück, die die Delaunay-Triangulation darstellen. Die Implementierung verwendet die Klasse „Circular List“ und Klassen aus dem Abschnitt „Geometrische Datenstruktur“. Die Dictionary-Klasse kann ein beliebiges Wörterbuch sein, das die erforderlichen Vorgänge unterstützt. Sie können beispielsweise #define Dictionary RandomizedSearchTree überschreiben.

Aufführen * (Punkt s, int n) ( Punkt p; Liste *Dreiecke = neue Liste ; Wörterbuch frontier(edgeCmp); Kante *e = hullEdge(s, n); frontier.insert(e); while (!frontier.isEmpty()) ( e = frontier.removeMin(); if (mate(*e, s, n, p)) ( updateFrontier(frontier, p, e->org); updateFrontier(frontier, e ->dest, p); Triangles->insert(triangle(e->org, e->dest, p)); ) delete e; ) return Triangles; )

Reis. 4

Dreiecke, die eine Triangulation bilden, werden in die Dreiecksliste geschrieben. Die Grenze wird durch ein Wörterbuch lebender Grenzkanten dargestellt. Jede Kante ist gerichtet, sodass der für sie unbekannte (zu bestimmende) Bereich rechts von der Kante liegt. Die EdgeCmp-Vergleichsfunktion wird zum Nachschlagen des Wörterbuchs verwendet. Es vergleicht die Startpunkte zweier Kanten; wenn sie gleich sind, werden ihre Endpunkte verglichen:

Int edgeCmp (Edge *a, Edge *b) ( if (a->org< b->org) return 1; if (a->org > b->org) return 1; if (a->dest< b->dest) return -1; if (a->dest > b->dest) return 1; 0 zurückgeben; )

Wie ändert sich der Rand von Schritt zu Schritt und wie ändert die updateFrontier-Funktion das Kantenwörterbuch des Randes, um diese Änderungen widerzuspiegeln? Wenn ein neues Dreieck t mit der Grenze verbunden wird, ändern sich die Zustände der drei Kanten des Dreiecks. Die an die Grenze angrenzende Dreieckskante t wechselt von lebend zu tot. Die Funktion „updateFrontier“ kann diese Kante ignorieren, da sie beim Aufruf der Funktion „removeMin“ bereits aus dem Wörterbuch entfernt sein sollte. Jede der beiden verbleibenden Kanten des Dreiecks t ändert ihren Zustand von „schlafend“ in „lebendig“, wenn sie zuvor nicht im Wörterbuch aufgezeichnet wurden, oder von „lebendig“ in „tot“, wenn die Kante bereits im Wörterbuch enthalten ist. In Abb. 5 zeigt beide Fälle. Gemäß der Abbildung verarbeiten wir die Live-Kante af und fügen, nachdem wir herausgefunden haben, dass Punkt b ihr Konjugat ist, das Dreieck afb zur aktuellen Triangulation hinzu. Dann suchen wir im Wörterbuch nach dem Edge-FB, und da er noch nicht vorhanden ist und zum ersten Mal entdeckt wird, ändert sich sein Zustand von „Schlafend“ in „Lebendig“. Um das Wörterbuch zu bearbeiten, drehen wir die Kante fb so, dass der unbekannte angrenzende Bereich rechts davon liegt, und schreiben diese Kante in das Wörterbuch. Dann finden wir die Kante ba im Wörterbuch – da sie darin enthalten ist, ist sie bereits lebendig (der bekannte Bereich daneben ist das Dreieck abc). Da der ihm unbekannte Bereich Dreieck afb gerade erst entdeckt wurde, wird diese Kante aus dem Wörterbuch entfernt.

Die Funktion updateFrontier bearbeitet das Frontier-Wörterbuch, in dem sich der Zustand der Kante von Punkt a zu Punkt b ändert:

Reis. 5

Void updateFrontier (Wörterbuch &frontier, Point &a, Point &b) ( Edge *e = new Edge (a, b); if (frontier.find (e)) frontier.remove(e); else ( e->flip(); frontier.insert( e); ) )

Die Funktion „hullEdge“ findet eine Hüllenkante unter n Punkten im Array s. Diese Funktion verwendet tatsächlich den Initialisierungsschritt und die erste Iteration der Geschenkverpackungsmethode:

Edge *hullEdge (Point s, int n) ( int m = 0; for (int i = 1; i< n; i++) if (s[i] < s[m]) m = i; swap(s, s[m]); for (m = 1, i = 2; i < n; i++) { int с = s[i].classify (s, s[m]); if ((c == LEFT) || (C == BETWEEN)) m = i; } return new Edge(s, s[m]); }

Die Dreiecksfunktion generiert einfach ein Polygon für die drei ihr als Parameter übergebenen Punkte und gibt es zurück:

Polygon *dreieck (Punkt &a, Punkt &b, Punkt &c) ( Polygon *t = neues Polygon; t->insert (a); t->insert (b); t->insert (c); return t; )

Unter Triangulation versteht man die Annäherung der Oberfläche eines modellierten Objekts durch dreieckige Platten, die in einem Abstand von höchstens einem bestimmten festgelegten Wert 6 davon entfernt sind. Alle dreieckigen Platten müssen miteinander verbunden werden. Ihre Spitzen liegen an der Oberfläche. Ein Satz dreieckiger Platten ist einfacher zu bearbeiten als eine allgemeine Oberfläche. Wir nennen dreieckige Platten Dreiecke. 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 dient der visuellen Wahrnehmung des geometrischen Modells. Dabei werden die Seiten der Dreiecke so ausgewählt, dass das Auge die Knicke nicht erkennen kann.

Bei der Darstellung geometrischer Objekte durch Dreiecke auf parametrischen Flächenebenen muss eine räumliche Triangulation der 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 berechnet werden zweidimensionale Punkte. Zur schnellen Darstellung von Körpern werden ihre Flächen durch auf ihnen aufgebaute dreieckige Platten angenähert. Normalpunkte werden benötigt, um das Verhalten von Lichtstrahlen zu bestimmen, die mit den Flächen eines Körpers interagieren. Die Tonzeichnungen in den vorherigen Kapiteln und in diesem Kapitel werden mittels Triangulation erstellt.

Als Ergebnis der Oberflächentriangulation möchten wir ein Array aus zweidimensionalen Punkten auf einer parametrischen Ebene und ein Array aus Tripletts ganzer Zahlen haben, die die Anzahl der Punkte im erstgenannten Array darstellen. Somit wird jedes Dreieck durch drei Nummern seiner Eckpunkte 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.

Schauen wir uns einige Methoden der Triangulation an. Für ebene Flächen gibt es kostengünstige Triangulationsverfahren, bei denen Dreiecke an den Randpunkten der Fläche konstruiert werden und keine Suche nach Punkten innerhalb des parametrischen Bereichs erforderlich ist.

Delaunay-Triangulation.

Betrachten wir einen Bereich im Flugzeug. Wir nennen eine Fläche konvex, wenn man sich beim Bewegen entlang ihrer Grenze nur in eine Richtung (nur nach links oder nur nach rechts) drehen muss. Der Delaunay-Algorithmus kann zur Triangulation konvexer planarer Regionen verwendet werden. Wir werden diesen Algorithmus nicht direkt auf die Triangulierung von Freiformflächen anwenden können, aber wir werden seine Methode zum Konstruieren 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 die angegebenen Punkte innerhalb der Fläche und die Eckpunkte der gestrichelten Linie sind, die sie begrenzt. Die Dreiecke dürfen einander nicht überlappen und ihre Seiten dürfen sich nur an den Eckpunkten schneiden.

Es können mehrere verschiedene Dreieckssätze konstruiert werden, um einen bestimmten Bereich auszufüllen. In allen Fällen ist die Anzahl der Dreiecke gleich, 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 Triangulation einer Region ist eine Delaunay-Triangulation, wenn sich innerhalb des um jedes Dreieck beschriebenen Kreises 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 ausgewogen bezeichnen. Eine Delaunay-Triangulation ist eindeutig, wenn keine vier Eckpunkte auf demselben Kreis liegen.

Betrachten wir die Delaunay-Triangulation. Wir nennen die Eckpunkte der Polylinie, die die Region begrenzt, und die angegebenen Punkte innerhalb der Region die Eckpunkte der Triangulation. Wir nennen die Seiten von Dreiecken Kanten. Unter den Kanten wählen wir Segmente der begrenzenden Polylinie aus, die wir Grenzkanten nennen. Richten wir alle Grenzkanten so aus, dass der konvexe Bereich links von jeder Kante liegt. Es sei notwendig, ein Dreieck zu konstruieren, dessen Seite die Grenzkante AB ist, wie in Abb. 9.7.2.

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

Reis. 9.7.3. Delaunay-Triangulationsprozess

Für alle Scheitelpunkte, die links vom Segment AB liegen, 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 Linie, 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 wir alle Grenzkanten so aus, dass der zu triangulierende Bereich links von jeder von ihnen liegt. Wir beginnen mit der Konstruktion von Dreiecken von einer beliebigen Grenzkante aus. Suchen wir den nächstgelegenen Scheitelpunkt dafür, dessen entsprechender Kreis keine anderen Scheitelpunkte enthält. Für die Grenzkante AB soll der nächstgelegene Scheitelpunkt V gefunden werden. Dann konstruieren wir ein Dreieck ABV und überführen die Kante AB in die Kategorie inaktiv. 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. Wenn es unter den Grenzkanten eine Kante BV gibt, übertragen wir diese und den Scheitelpunkt B in die Kategorie inaktiv. Wenn es unter den Grenzkanten keine Kante VA gibt, konstruieren wir eine neue Grenzkante auf dem Segment AV. Wenn es unter den Randkanten eine Kante VA gibt, übertragen wir diese und den Scheitelpunkt A in die Kategorie inaktiv. 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 eines bestimmten Bereichs ist in Abb. dargestellt. 9.7.4.

Triangulation durch Korrekturmethode.

Betrachten wir die Triangulation einer bestimmten Oberfläche mit einem rechteckigen Bereich zur Definition von Parametern. Teilen wir den Bereich zur Definition von Oberflächenparametern in rechteckige Zellen mit zweidimensionalen Linien. Diese Linien bilden ein rechteckiges Gitter. Nehmen wir an, dass die parametrischen Abstände zwischen benachbarten Linien gemäß Formel (9.4.7) gleich sind

Nehmen wir an, dass die parametrischen Abstände zwischen benachbarten Linien gemäß Formel (9.4.8) gleich sind

Durch die Konstruktion von Diagonalen in allen rechteckigen Zellen erhalten wir eine Triangulation der Oberfläche (wir erhalten eine Menge von Dreiecken, die den Anforderungen entspricht). In Abb. Abb. 9.7.5 zeigt die Triangulation der Rotationsfläche nach der beschriebenen Methode.

Betrachten wir die Triangulation einer Fläche mit einer beliebigen Grenze. Wir werden die Triangulationsmethode auf der Korrektur durch Randkonturen der oben beschriebenen Oberflächentriangulation mit einer rechteckigen Fläche zur Bestimmung der Parameter aufbauen.

Reis. 9.7.5. Triangulation einer Fläche mit rechteckigem Bereich zur Definition von Parametern

Die Oberflächengrenze im Parameterdefinitionsbereich sei durch mehrere sich nicht schneidende zweidimensionale Konturen (2.12.7) beschrieben. Eine der Konturen ist extern und enthält die übrigen Konturen. Als positive Richtung für jede Kontur nehmen wir die Richtung, in der sich der Oberflächendefinitionsbereich beim Verschieben immer links von der Kontur befindet, wenn man auf die Oberflächennormale blickt. Konstruieren wir Polygone in der positiven Richtung der Grenzkonturen des Oberflächendefinitionsbereichs. Um Grenzpolygone zu konstruieren, müssen Sie mit einem variablen Schritt entlang der Grenzkonturen der Oberfläche laufen und eine Reihe zweidimensionaler Punkte ausfüllen, deren Koordinaten die Oberflächenparameter sind. Wir werden ein Polygon aus Punkten auf einer parametrischen Ebene aufbauen, aber der Schritt beim Übergang von einem Punkt zum anderen wird aus der räumlichen Geometrie bestimmt, nämlich aus der Bedingung, dass die Auslenkung des Kurvenbogens zwischen benachbarten Punkten nicht mehr als ein gegebener Wert ist Wert. Wir berechnen die parametrischen Schritte zum Konstruieren eines Polygons für die Konturkurve der Oberflächengrenze mithilfe der Formel (9.4.4).

Jedes Polygon besteht aus einer geordneten Menge zweidimensionaler Punkte. Jeder Abschnitt eines Polygons kann als zweidimensionales gerades Liniensegment betrachtet werden, das aus zwei benachbarten Punkten besteht. Wir werden solche Flächen als Grenzkanten verwenden und die Punkte der Polygone, auf denen die Kanten basieren, werden als Triangulationsscheitelpunkte verwendet. Da der Bereich zur Bestimmung der Oberflächenparameter links von den Grenzpolygonen liegt, sollten Sie beim Konstruieren von Dreiecken für jede Grenztriangulationskante 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 innerhalb des Bereichs liegen, in dem die Oberflächenparameter bestimmt werden (die Zellen sollten die Grenzpolygone nicht berühren). Die zweite Gruppe umfasst die übrigen Zellen (die außerhalb des Oberflächendefinitionsbereichs liegen oder von Grenzpolygonen geschnitten werden).

Reis. 9.7.6. Unvollendete Oberflächentriangulation

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

Wir werden Grenzkanten auf den nicht geschnittenen Seiten der Zellen der zweiten Gruppe konstruieren und sie so ausrichten, dass die entsprechende Zelle links von der Kante liegt. Um die Zellen der ersten Gruppe herum werden wir eine geschlossene gestrichelte Linie (möglicherweise mehrere geschlossene Linien) konstruieren, so dass bei der Bewegung entlang dieser der Teil der Fläche, der nicht in Dreiecke unterteilt ist, links liegt, wenn man auf die Flächennormale blickt . Die geraden Abschnitte dieser gestrichelten Linie werden wir auch als Begrenzungskanten verwenden. Wir betrachten alle Kanten als gleich. Um die Triangulation abzuschließen, müssen wir Dreiecke zwischen den Grenzkanten konstruieren. Für jede Kante suchen wir einen Scheitelpunkt, der links davon liegt und zur Konstruktion eines Dreiecks verwendet werden kann. Wir werden nur unter den Scheitelpunkten nach einem Scheitelpunkt suchen, die in derselben Zelle wie die 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, sollten Sie prüfen, ob sich zwei neue Kanten des Dreiecks mit einer beliebigen Begrenzungskante schneiden. Finden Sie den nächstgelegenen Scheitelpunkt V für die Grenzkante AB und prüfen Sie, dass die Segmente BV und VA keine anderen Grenzkanten schneiden. Dann konstruieren wir das Dreieck ABV und übertragen die Kante AB in die inaktive Kategorie. Wenn unter den Grenzkanten keine Kante BV vorhanden ist, konstruieren wir eine neue Grenzkante auf dem Segment VB. Wenn jedoch unter den Grenzkanten eine Kante BV vorhanden ist, übertragen wir diese und den Scheitelpunkt B in die Kategorie inaktiv. Wenn unter den Grenzkanten keine Kante VA vorhanden ist, konstruieren wir eine neue Grenzkante auf dem Segment AV. Wenn jedoch zwischen den Grenzkanten eine Kante VA vorhanden ist, übertragen wir diese und den Scheitelpunkt A in die Kategorie inaktiv.

Wenn ein Segment oder eine VA andere Grenzkanten schneidet, fahren wir mit der Suche nach dem nächstgelegenen Scheitelpunkt für eine andere Grenzkante fort. Die Triangulation ist abgeschlossen, nachdem alle Kanten und Scheitelpunkte als inaktiv klassifiziert wurden.

Reis. 9.7.7. Triangulation durch Korrekturmethode

In Abb. In Abb. 9.7.7 zeigt die Oberflächentriangulation durch die Methode der Korrektur von Dreiecken in Zellen, die von Grenzkonturen geschnitten werden. In Abb. 9.7.8 wird anhand der resultierenden Triangulation die Oberfläche selbst dargestellt.

Wenn die Grenzpolygone und die Oberfläche eine gewisse Symmetrie aufweisen, weist die Triangulation mit der Korrekturmethode eine ähnliche Symmetrie auf.

Triangulation durch Absorptionsmethode.

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

Dazu berechnen wir die zulässigen Inkremente von Parametern entlang der Koordinatenlinien

Wo sind die Koeffizienten des ersten und zweiten? quadratische Formen Oberfläche am Punkt. Als Grenze der gewünschten Region nehmen wir eine Ellipse mit einem Mittelpunkt in einem Punkt und Halbachsen. Diese Ellipse hat die Gleichung

Wenn Sie einen Punkt auf der Ebene neben einem Punkt in der durch den Winkel mit der und-Achse vorgegebenen Richtung finden möchten, dann sind seine Parameter wie folgt

Betrachten wir zunächst einen einfacheren Fall, bei dem der Bereich der Oberflächenparameter auf eine Außenkontur beschränkt ist. Wir approximieren die Oberflächengrenze durch ein geschlossenes Polygon im parametrischen Bereich. Bei der Konstruktion der Triangulation verwenden wir das Arbeitspolygon, das wir in diesem Fall als Polygon der Außenkontur verwenden. Wir werden die Polygonpunkte zum resultierenden Array zweidimensionaler Punkte hinzufügen. Wir werden Dreiecke vom Rand des Arbeitsbereichs bilden und ihn verengen, bis nur noch drei Punkte im Arbeitsbereich übrig sind.

Suchen wir einen Scheitelpunkt im Arbeitspolygon, an dem es in die Region übergeht. Einen solchen Punkt gibt es immer und der Drehwinkel an ihm ist kleiner. Bezeichnen wir diesen Punkt mit O und seine Parameter mit In der Nähe dieses Punktes werden wir je nach Drehwinkel ein oder zwei Dreiecke konstruieren. Ist der Winkel kleiner, dann bilden wir aus diesen drei Punkten ein Dreieck (Abb. 9.7.9). Andernfalls konstruieren wir darauf zwei Dreiecke, zwei benachbarte und einen 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. Liegt der Scheitelpunkt des Parallelogramms innerhalb der Ellipse (Abb. 9.7.10), dann nehmen wir ihn als Punkt P Andernfalls 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 BC bestimmt

Der Winkel des Segments OP 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 wir ein Dreieck (merken uns die Nummern seiner Eckpunkte) und löschen den Punkt O im Arbeitsbereich. Im in Abb. 9.7.11 konstruieren wir zwei Dreiecke und ersetzen im Arbeitsbereich den Punkt O durch den Punkt P und platzieren diesen im resultierenden Punktefeld. In Abb. Abbildung 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 konstruiert werden können, wenn sich der Arbeitsbereich 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 die nicht angrenzenden Seiten des Arbeitsbereichs schneiden. Bevor wir ein neues Dreieck konstruieren, wie im Fall in Abb. 9.7.9 und im in Abb. 9.7.11 muss eine Prüfung durchgeführt werden, um sicherzustellen, dass 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 Arbeitsbereichs hat und nicht in die Nähe der die Punkte des Bereichs 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 es unmöglich ist, ein Dreieck (Dreiecke) in der Nähe von Punkt O zu konstruieren, sollten Sie stattdessen einen anderen Punkt finden, an dem sich das Polygon stärker als an anderen in die Kontur einfügt, und an diesem die beschriebenen Aktionen ausführen.

Als nächstes führen wir mit dem geänderten Arbeitsbereich 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. In dieser Ecke können keine Dreiecke gebaut werden.

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 bestehend aus drei Punkten. An diesen Punkten bauen wir das letzte Dreieck auf, eliminieren den Arbeitsbereich und schließen die Triangulation ab. Bei der beschriebenen Triangulationsmethode wird die durch den Arbeitsbereich begrenzte Fläche gewissermaßen 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 erfüllt sein. Die Ausrichtung der inneren Polygone muss entgegengesetzt zur Ausrichtung des äußeren Polygons sein. Beginnen wir mit der Konstruktion der Triangulation mit dem Außenkonturpolygon. Lassen Sie uns seine Punkte in das resultierende Array zweidimensionaler Punkte einfügen und das Polygon selbst zu einem funktionierenden Polygon machen.

Wir werden Dreiecke auf die gleiche Weise konstruieren wie im Fall einer einfach zusammenhängenden Region. Suchen wir den Punkt O im Arbeitsbereich, prüfen wir die Möglichkeit einer Verengung des Arbeitsbereichs dort und verengen den Bereich. Bei Innenkonturen wird es schwieriger, die Möglichkeit einer Einengung des Arbeitsbereichs an einer ausgewählten Stelle zu prüfen. Zusätzlich zu den beschriebenen Prüfungen des Schnittpunkts der Dreiecksseiten mit den Seiten des Arbeitsbereichs ist es notwendig, den Schnittpunkt der Dreiecksseiten mit den Seiten aller Innenpolygone zu prüfen.

Lassen Sie uns die Möglichkeit prüfen, am Punkt O zwei Dreiecke zu konstruieren (Abb. 9.7.11) und feststellen, dass der neue Punkt P nach seiner Konstruktion in eines der internen Polygone fällt oder sich in unzulässiger Nähe zu seinen Segmenten befindet. In diesem Fall konstruieren wir nicht den Punkt P, sondern beziehen dieses interne Polygon in das Arbeitspolygon ein, indem wir die beiden in Abb. gezeigten Dreiecke konstruieren. 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.

Lassen Sie uns Dreiecke an den Punkten OCF und CEF konstruieren und zwischen den Punkten O und C des Arbeitsbereichs Punkte des internen Polygons einfügen, beginnend mit Punkt F und endend mit Punkt E. Somit werden wir den Arbeitsbereich auf dem Segment OS unterbrechen, das aufteilen interne Polygone auf dem Segment EF und vereinen 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 müssen vor dem Zusammenführen der äußeren und inneren Polygone Überprüfungen durchgeführt werden, um sicherzustellen, dass dieser Vorgang korrekt ist.

Als nächstes verengen wir den Arbeitsbereich auf die beschriebene Weise weiter, bis wir uns in unmittelbarer Nähe eines anderen internen Bereichs befinden und diesen in den Arbeitsbereich einbeziehen. 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 zur Bestimmung von Oberflächenparametern mit Dreiecken bedeckt.

Reis. 9.7.16. In dieser Ecke können keine Dreiecke gebaut werden.

Es kann Situationen geben, in denen es unmöglich ist, aus den gegebenen Polygonen ein einzelnes Dreieck zu konstruieren. In Abb. Abbildung 9.7.16 zeigt eine Fläche, die durch zwei Polygone 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 im Weg ist. In diesem Fall finden wir zwei benachbarte Punkte B und C des Polygons, für die wir ein Dreieck HRV konstruieren können. 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. Eine andere Möglichkeit besteht darin, die äußeren und inneren Polygone zu einem Polygon zusammenzufassen, bevor mit der Triangulation begonnen wird. Sie können Punkte innerhalb des Parameterdefinitionsbereichs mit einem bestimmten Algorithmus „skizzieren“ und mit ihnen und den Punkten der Grenzkonturpolygone eine Delaunay-Triangulation durchführen. Es gibt Algorithmen, die zunächst große Dreiecke konstruieren und diese dann in überschaubare Größen aufteilen.

Körpertriangulation.

Die Triangulation eines Körpers ist 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 für benachbarte Flächen konsistent sein müssen (Abb. 9.7.17).

Reis. 9.7.17. Konsistenz des Körper-Gesichts-Grenzpolygons

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. In Abb. 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 Bereichs zur Bestimmung von Oberflächenparametern in Dreiecke kann in den Integralen (8.6.2), (8.6.3), (8.6.12), (8.7.17)-(8.7.22) bei der Berechnung der geometrischen Eigenschaften von Körpern verwendet werden . Bei der numerischen Integration sollte der parametrische Schritt für Kurven mit der Formel (8.11.5) berechnet werden, und für Flächen sollten die parametrischen Schritte mit den Formeln (8.11.1) und (8.11.2) berechnet werden.