20. August 2012 um 22:41 Uhr

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

• Bildverarbeitung ,
• Programmierung

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

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

Am Eingang

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

Bild 1

Was tun müssen

Es ist notwendig, die Figur mit Dreiecken zu fegen.

Suche

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

Algorithmus

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

Figur 2

Figur 3

Figur 4

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

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

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

Abbildung 5

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

Abbildung 7

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

Abbildung 8

Abbildung 9

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

Mehr zur fünften Etappe

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

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

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

Abbildung 10

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

Was folgt, ist reine Mathematik.

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

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

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

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

D >= 0

Abbildung 11

Ist es nicht?

Laut dem Buch noch einmal

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

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

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

Literaturverzeichnis

1. Skvortsov A.V. Delaunay-Triangulation und ihre Anwendung. - Tomsk: Verlag Bd. un-ta, 2002. - 128 p. ISBN 5-7511-1501-5 20. August 2012 um 22:41 Uhr

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

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

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

Am Eingang

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

Bild 1

Was tun müssen

Es ist notwendig, die Figur mit Dreiecken zu fegen.

Suche

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

Algorithmus

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

Figur 2

Figur 3

Figur 4

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

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

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

Abbildung 5

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

Abbildung 7

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

Abbildung 8

Abbildung 9

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

Mehr zur fünften Etappe

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

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

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

Abbildung 10

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

Was folgt, ist reine Mathematik.

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

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

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

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

D >= 0

Abbildung 11

Ist es nicht?

Laut dem Buch noch einmal

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

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

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

Literaturverzeichnis

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

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

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

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

Algorithmen zur Konstruktion von Triangulation

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

GRID-Modelle sind Modelle regulärer Zellen.

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

,

- Physikalische Koordinaten des Punktes.

Berechnung
und
,
- Bitraster.

- quantisierte Werte. Echt:

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

- Entfernungsgrad (1 oder 2).

Normalisierungsfaktor:

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

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

Vorteil– Einfachheit

Mangel:

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

1) Triangulation (Zinn).

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

Triangulation– Interpolation innerhalb des konvexen Bereichs.

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

Wir brauchen einen Algorithmus, um eine optimale Triangulation aufzubauen.

Eine Ebene, die durch 3 Punkte geht.

1) Finden Sie ein Dreieck, das
;

2)
- Wir bauen die Gleichung der Ebene auf.

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

Struktur ansehen:

Jede Triangulation enthält die gleiche Anzahl von Dreiecken.

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

Gierige Triangulation.

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

Delaunay-Triangulation.

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

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

Delaunay-Zustand.

Kreisgleichung durch drei Punkte:

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

ist die Delaunay-Bedingung.

Der Algorithmus zur Konstruktion der Delaunay-Triangulation:

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

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

Theoretische Komplexität

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

Wir bewegen uns vom ersten Punkt zum nächsten.

(Development and Implementation of Algorithms for Constrained Volume Triangulations: Iterative Algorithms
Vordruck, Inst. Appl. Math., Russische Akademie der Wissenschaften)

Galanin M.P., Shcheglov I.A.
(M. P. Galanin, I. A. Sheglov)

IPM sie. M. V. Keldysh RAS

Moskau, 2006
Diese Arbeit wurde von der Russischen Stiftung für Grundlagenforschung (Projekt Nr. 06-01-00421) unterstützt.

Anmerkung

Es werden iterative Verfahren zur dreidimensionalen Diskretisierung räumlicher Bereiche (Konstruktion von Tetraedernetzen) betrachtet: Randkorrekturverfahren, Verfahren basierend auf dem Delaunay-Kriterium und Erschöpfungsverfahren. Varianten von Algorithmen für jedes dieser Verfahren sind angegeben. Die Merkmale der Konstruktion von Gittern in komplexen Domänen werden diskutiert.

Abstrakt

Drei Hauptfamilien von iterativen Algorithmen für freie und eingeschränkte simpliziale Volumentriangulation werden beschrieben: Grenzkorrektur (einschließlich "Octree"-Algorithmus), Delaunay-basierte Verfahren und fortschrittlicher Frontansatz. Für jeden Methodentyp wird ein Beispielalgorithmus angegeben.

1. Einführung 3

2. Grenzkorrekturmethoden4

2.1 Aufbau des Primärnetzes4

2.2 Korrektur des Primärrasters6

3. Methoden basierend auf dem Delaunay-Kriterium9

3.1 Erstellen einer Delaunay-Triangulation auf einer gegebenen Menge von Punkten 12

3.2. Delaunay-Triangulation mit Einschränkungen17

3.3 Merkmale der technischen Umsetzung von Algorithmen basierend auf
Delaunay-Kriterium 22

4. Erschöpfungsmethoden23

4.1 Beispiel eines Erschöpfungsalgorithmus26

Referenzen3 0

1. Einleitung

Unter den zwei Klassen von Triangulationsverfahren – direkt und iterativ – haben die letzteren eine ausreichende Universalität und können daher im Gegensatz zu den direkten verwendet werden, um Bereiche einer eher willkürlichen Form zu triangulieren. Diese Vielseitigkeit wird mit einem deutlich höheren Ressourcenverbrauch und einer arbeitsintensiveren Implementierung des Verfahrens in einen bestimmten Algorithmus erkauft.

Derzeit wurde eine große Anzahl von Softwarepaketen entwickelt, die auf der einen oder anderen iterativen Methode basieren, die die Konstruktion von Gittern (teilweise oder vollständig) im automatischen Modus implementiert. Grundsätzlich sind diese Pakete kommerziell, was angesichts des Aufwands für ihre Erstellung durchaus gerechtfertigt ist, da der dreidimensionale Raum eine Reihe unangenehmer Merkmale aufweist, die das Leben des Entwicklers erheblich erschweren.

Durch iterative Methoden konstruierte Netze sind normalerweise unstrukturiert und inhomogen. Die Unstrukturiertheit ist darauf zurückzuführen, dass die Topologie des Gitters im Konstruktionsprozess gebildet wird und daher selbst innerhalb derselben Teildomäne natürlich variieren kann. Aus dem gleichen Grund ist Homogenität, wenn sie entstehen kann, nur zufällig.

Da vor dem Bau des Netzes nichts über dessen künftigen Aufbau gesagt werden kann, kann auch dessen Qualität nicht garantiert werden. Oft kann das konstruierte Netz mit einer der vielen Optimierungstechniken erheblich verbessert werden. Diese Möglichkeit wird in der Regel nicht vernachlässigt, da der Zeitaufwand für die Optimierung in der Regel deutlich geringer ist als der Zeitaufwand für das Bauen.

Der Zweck dieser Arbeit ist es, die bestehenden Methoden zur Konstruktion von Tetraedernetzen in dreidimensionalen Domänen zu überprüfen und zu klassifizieren. Aufgrund der umfangreichen Informationen werden im Folgenden nur die sogenannten „iterativen Verfahren“ betrachtet. Direkte Methoden sind in beschrieben.

Diese Arbeit wurde teilweise von der Russischen Stiftung für Grundlagenforschung (Projekt Nr. 06-01-00421) unterstützt.

Reis. 11. Triangulation eines Gebiets, das die Vereinigung eines Dodekaeders und eines Ikosaeders darstellt (Delaunay-Triangulation mit Einschränkungen)

Die Qualität der mit diesem Verfahren konstruierten Netze liegt auf einem durchschnittlichen Niveau (Tetraeder in Randnähe können eine sehr schlechte Form haben), so dass meist zusätzlich auf eines der Optimierungsverfahren zurückgegriffen wird.

In den Arbeiten von B. Joe werden andere Varianten des Algorithmus vorgeschlagen, die keine zusätzlichen Punkte verwenden und vollständig auf lokalen Transformationen basieren, ähnlich wie "Handel".

4) Das Volumen des Tetraeders ist nicht größer als das maximal zulässige ().

Aus allen Tetraedern () wird der Tetraeder mit der besten Qualität ausgewählt und zu Schritt 5 übergegangen; falls es keine Tetraeder gibt, die die angegebenen Bedingungen erfüllen, wird zu Schritt 4 übergegangen.

4. Es gibt einen solchen Punkt innerhalb der immer noch unerschöpflichen Region, der:

1) das Tetraeder () erfüllt alle Bedingungen des Absatzes 3;

2) in einer Kugel Es gibt keinen entfernten PunktF(Dies verhindert, dass Knoten platziert werdenp zu nahe an den Flächen und Ecken bestehender Tetraeder).

Eine Variante des Knotensuchalgorithmuspnachfolgend diskutiert.

5. Entfernen Sie alle EckpunkteF, die in (und auf die Grenzen) des gebildeten Tetraeders fallen. Dann wird die Front nach folgendem Schema aktualisiert: Jede Seite des gebildeten Tetraeders wird betrachtet und

1) wenn die Fläche eine Vorderseite ist, dann wird sie von der Vorderseite entfernt;

2) Wenn die Fläche KEINE Vorderseite ist, wird sie der Vorderseite hinzugefügt.

6. Wenn noch nicht gelöschte Punkte vorhanden sindFoder (was äquivalent ist) die Front nicht leer ist (dh der Bereich noch nicht vollständig erschöpft ist), wird der Übergang zu Schritt 1 durchgeführt, andernfalls ist der Vorgang beendet.

Also das ArrayFwird für mehrere Zwecke gleichzeitig verwendet: um den Wert des Raumwinkels zu schätzen, um die Korrektheit der Konstruktion zu kontrollieren und um die Platzierung neuer Knoten zu kontrollieren. Auch ein ArrayFnützlich, um den Fortschritt anzuzeigen. Das Verhältnis der Anzahl der Punkte, die während der Ausführung des Algorithmus entfernt wurdenFauf die anfängliche Anzahl vorhandener PunkteFzeigt tatsächlich, wie viel von der Fläche bereits erschöpft ist.

Kehren wir zu der Frage zurück, die Koordinaten eines neuen Knotens zum Konstruieren eines Tetraeders zu finden (Punkt 4 des beschriebenen Algorithmus). Lassen Sie drei Knoten - gegeben werden.

1. Im ersten Schritt finden wir - den Massenmittelpunkt des Dreiecks (als arithmetisches Mittel der Koordinaten seiner Knoten) und die Einheit senkrecht zur Ebene des Gesichts (durch das normalisierte Vektorprodukt).

2. Als nächstes wird die erste Näherung für die Entfernung von zum gewünschten Punkt bestimmtp (H), bezogen auf das maximale Volumen des Tetraeders: . Beachten Sie, dass der Bereich des GesichtsStatsächlich im vorherigen Schritt gefunden (das Ergebnis des Kreuzprodukts zweier Kanten ist gleich der doppelten Fläche des Gesichts), und die maximale Lautstärke wird durch den Wert der Steuerfunktion bestimmt.

3. Der Punkt wird geprüft. Wenn das Tetraeder () alle Anforderungen erfüllt, gehe zu Schritt 6, andernfalls gehe zu Schritt 4.

4. Der Punkt wird überprüft. Wenn das Tetraeder () alle Anforderungen erfüllt, gehe zu Schritt 6, andernfalls gehe zu Schritt 5.

5. Glauben und gehen Sie zu Schritt 3.

6. Der gewünschte Knoten wird gefunden.

Beachten Sie, dass sich der gewünschte Punkt in 99 % der Fälle bei 1 oder 2 Iterationen dieses Algorithmus befindet.

Bei dem oben beschriebenen Erschöpfungsalgorithmus wird bei jedem Schritt ein Tetraeder aus dem Bereich entfernt. NASA-Mitarbeiter Sh. Pirzade ( Shahyar Pirzadeh ) schlug eine andere Version des Algorithmus vor, bei der eine ganze Schicht von Tetraedern auf einmal aus der Region entfernt wird (d. h. bei jeder Iteration werden Tetraeder sofort für alle Flächen der aktuellen Front aufgebaut). Diese Variante beschleunigt den Konstruktionsprozess wider Erwarten nicht wesentlich (weil alle neuen Tetraeder noch auf Korrektheit überprüft werden müssen), erspart aber die Suche nach der am besten geeigneten Fläche zum Konstruieren eines Tetraeders. Dies ist jedoch eher ein Minus als ein Plus, denn aufgrund dieser Eigenschaft ist die Pirzade-Variante weniger zuverlässig und kann in geometrisch komplexen Bereichen versagen. Gleichzeitig zeigt es in relativ einfachen Bereichen gute Ergebnisse.

Durch Ausschöpfungsverfahren konstruierte Netze weisen in der Regel eine gute Qualität auf, eine nachträgliche Optimierung der Lage der Knoten führt zu einer zusätzlichen Qualitätssteigerung. Zusammenfassend stellen wir fest, dass die Erschöpfungsmethoden am effektivsten sind, wenn zunächst eine Triangulation der Bereichsgrenze eingestellt wird. Dies ist ihr Hauptunterschied zu den Methoden, die auf dem Delaunay-Kriterium basieren, bei denen die Situation genau umgekehrt ist.

Referenzliste

1. Shaydurov V. V. Mehrgitter-Finite-Elemente-Methoden. - M., Nauka, 1989. - 288s.

2. Skvortsov A.V. Überblick über Algorithmen zur Konstruktion der Delaunay-Triangulation // , 2002, №3, c. 14-39.

3. Skvortsov A.V. Algorithmen zur Konstruktion einer Triangulation mit Restriktionen // Computermethoden und Programmierung, 2002, №3, c. 82-92.

4. I.Babushka, W.C. Rheinboldt. A-posteriori-Fehlerschätzungen für die Finite-Elemente-Methode // Int. J. Nummer. Meth. Eng., Vol. 12, S. 1597-1615, 1978.

5. T.J. Bäcker. Automatische Netzgenerierung für komplexe dreidimensionale Regionen mithilfe einer eingeschränkten Delaunay-Triangulation // Technik mit Computern, Springer-Verlag, Heft 5, S. 161-175, 1989.

6. M. Bern, D. Eppstein. Netzgenerierung und optimale Triangulation // Rechnen in der euklidischen Geometrie, World Scientific Publishing Co., S. p. 23-90, 1995.

7. D.K. Blandford, G. Blelloch, D. Cardoze, C. Kadow. Kompakte Darstellungen vereinfachter Netze in zwei und drei Dimensionen // Proceedings of 12th International Meshing Roundtable, Sandia National Laboratories, S. 135–146, Sept. 2003.

8. H. Borouchaki, S.H. Lo. Schnelle Delaunay-Triangulation in drei Dimensionen // Computermethoden in angewandter Mechanik und Technik, Elsevier, Bd. 128, S. 153-167, 1995.

9. E.K. Buratynski. Ein dreidimensionaler unstrukturierter Mesh-Generator für beliebige interne Grenzen // Numerische Gittererzeugung in der numerischen Strömungsmechanik, Pineridge Press, S. p. 621-631, 1988.

10. PR Cavalcanti, U.T. Mello. Dreidimensionale eingeschränkte Delaunay-Triangulation: ein minimalistischer Ansatz // Tagungsband des 8. International Meshing Roundtable, p.p. 119–129, 1999.

11. Dey, K. Tamal, K. Sugihara, C.L. Bajaj. Delaunay-Triangulationen in drei Dimensionen mit endlich genauer Arithmetik // Computergestütztes geometrisches Design, Nordholland, Nr. 9, p.p. 457-470, 1992.

12. H.N. Dschidjew. Kraftgesteuerte Methoden zum Glätten unstrukturierter dreieckiger und tetraedrischer Netze // Proceedings of 9th International Meshing Roundtable, Sandia National Laboratories, S. p. 395-406, Oktober 2000.

13. L. Dürbeck. Verdunstung: Eine Technik zur Visualisierung der Netzqualität // Proceedings of 8th International Meshing Roundtable, South Lake Tahoe, CA, USA, p.p. 259-265, Oktober 1999.

14. DA Feld. Laplace-Glättung und Delaunay-Triangulationen // , Bd. 4, S. 709-712, 1988.

15. P.J. Frey, H. Borouchaki, P.-L. George. Delaunay-Tetraederisierung mit einem Advancing-Front-Ansatz // Proceedings of 5th International Meshing Roundtable, Sandia National Laboratories, S. p. 31-46, Oktober 1996.

16. LA Freitag, C. Oliver-Gooch. Ein Vergleich von Tetraedernetz-Verbesserungstechniken // Proceedings of 5th International Meshing Roundtable, Sandia National Laboratories, S. p. 87-106, Oktober 1996.

17. LA Freitag, C. Ollivier-Gooch Verbesserung tetraedrischer Netze durch Austauschen und Glätten // , Bd. 40, p.p. 3979-4002, 1995.

18. LA Freitag, C. Oliver-Gooch. Der Einfluss der Netzqualität auf die Lösungseffizienz // Proceedings of 6th International Meshing Roundtable, Sandia National Laboratories, S. 249, Oktober 1997.

19. P.L. George. TET MESHING: Konstruktion, Optimierung und Anpassung // Proceedings vom 8Internationaler Mesh-Roundtable, S. 133-141, 1999.

20. N / A. Golias, T. D. Tsiboukis. Ein Ansatz zur Verfeinerung dreidimensionaler Tetraedernetze basierend auf Delaunay-Transformationen // , John Wiley, Nr. 37, S. 793-812, 1994.

21. C. Hazlewood. Näherung eingeschränkter Tetraederisierungen // Computergestütztes geometrisches Design, Bd. 10, p.p. 67–87, 1993.

22. B. Joe. Delaunay-Dreiecksnetze in konvexen Polygonen, SIAM J Sci. Stat. Berechnung., Bd. 7, S. 514-539, 1986.

23. B. Joe. Konstruktion dreidimensionaler Delaunay-Triangulationen unter Verwendung lokaler Transformationen // Computergestütztes geometrisches Design, Bd. 8, S. 123-142, 1991.

24. B. Joe. Konstruktion dreidimensionaler Triangulationen mit verbesserter Qualität unter Verwendung lokaler Transformationen // Siam J. Sc. Berechnung., Bd. 16, S. 1292-1307, 1995.

25. R.W. Lewis, Yao Zheng, D.T. Gethin. Dreidimensionale unstrukturierte Netzgenerierung: Teil 3. Volumennetze // Computermethoden in angewandter Mechanik und Technik, Elsevier, Bd. 134, S. 285–310, 1996.

26. A. Liu, B. Joe. Über die Form von Tetraedern aus der Halbierung // Mathematik der Berechnung, Bd. 63, Nr. 207, 141–154, 1994.

27. SCH. Lo. Volumendiskretisierung in Tetraeder-I. Überprüfung und Orientierung von Grenzflächen // Computer und Strukturen, Pergamon Press, Bd. 39, Nr. 5, S. 493-500, 1991.

28. SCH. Lo. Volumendiskretisierung in Tetraeder - II. 3D-Triangulation durch fortschrittlichen Frontansatz // Computer und Strukturen, Pergamon, Bd. 39, Nr. 5, S. 501-511, 1991.

29. R. Lohner. Erzeugung dreidimensionaler unstrukturierter Gitter durch die Advancing-Front-Methode // Proceedings des 26. AIAA Aerospace Sciences Meeting, Reno, Nevada, 1988.

30. SJ Owen. Ein Überblick über die Technologie zur Erzeugung unstrukturierter Netze // Proceedings of 7th International Meshing Roundtable, p.p. 239-269, Dearborn, MI, 1998.

31. VN Parthasarathy, C.M. Graichen, A.F. Hathaway. Ein Vergleich von Tetraeder-Qualitätsmaßen // Finite Elemente in Analyse und Design, Elsevier, nein. 15, S. 255-261, 1993.

32. S. Pirzadeh. Unstrukturierte viskose Gittererzeugung durch Advancing-Layers-Methode // AIAA-93-3453-CP, AIAA, p.p. 420-434, 1993.

33. V.T. Rajan. Optimalität der Delaunay-Triangulation in // Proz. 7. ACM-Symp. Komp. Geometrie, p.p. 357-363, 1991.

34. A. Rassineux. Generierung und Optimierung von Tetraedergittern durch Advancing Front Technique // Internationale Zeitschrift für Numerische Methoden im Ingenieurwesen, Wiley, Bd. 41, S. 651-674, 1998.

35. S. Rebay. Effiziente Generierung unstrukturierter Netze mittels Delaunay-Triangulation und Bowyer-Watson-Algorithmus // Zeitschrift für Computerphysik, Bd. 106, S. 125-138, 1993.

36. M.-C. Rivara. Selektive Verfeinerungs-/Verfeinerungsalgorithmen für Sequenzen verschachtelter Triangulationen // Internationale Zeitschrift für Numerische Methoden im Ingenieurwesen, Nr. 28, S. 2889-2906, 1998.

37. M.-C. Rivara, C. Levin. Ein 3D-Verfeinerungsalgorithmus, der für adaptive und Mehrgittertechniken geeignet ist // Kommunikation in angewandten numerischen Methoden, Nr. 8, S. 281-290, 1998.

38. J.Ruppert. Ein Delaunay-Verfeinerungsalgorithmus für die Generierung hochwertiger zweidimensionaler Netze // Zeitschrift für Algorithmen, Nr. 18, S. 548-585, 1995.

39. FRAU. Schäfer, M. K. Georg. Dreidimensionale Netzgenerierung durch Finite-Octree-Technik // Internationale Zeitschrift für Numerische Methoden im Ingenieurwesen, Bd. 32, S. 709-749, 1991.

40. FRAU. Shephard, F. Guerinoni, J.E. Flaherty, R.A. Ludwig, P.L. Bähmann. Generierung endlicher Octree-Netze für die automatisierte adaptive 3D-Strömungsanalyse // Numerische Gittererzeugung in der numerischen Strömungsmechanik Miami, 1988

41. K. Shimada, DC Gossard. Blasennetz: Automatisierte Dreiecksvernetzung nicht-mannigfaltiger Geometrie durch Kugelpackung // Verfahren von 3. Symposium für Volumenmodellierung und Anwendungen , p.p. 409-419, 1995.

42. K. Shimada, A. Yamada, T. Itoh. Anisotrope Dreiecksvernetzung parametrischer Oberflächen durch enge Packung ellipsoidischer Blasen // Proceedings of 6th International Meshing Roundtable, p.p. 375-390, 1997.

43. D.F. Watson. Berechnung der Delaunay-Tessellation mit Anwendung auf Voronoi-Polytope // Das Computerjournal, Bd. 24(2), S. 167-172, 1981.

44. MA Yerry, M.S. Schäfer. Dreidimensionale Netzgenerierung durch modifizierte Octree-Technik // Internationale Zeitschrift für Numerische Methoden im Ingenieurwesen, Bd. 20, S. 1965-1990, 1984.

45. Galanin M.P., Shcheglov I.A. Entwicklung und Implementierung von Algorithmen zur dreidimensionalen Triangulation komplexer räumlicher Bereiche: Direkte Methoden. IPM-Vordruck im. MV Keldysh RAN, 2006, im Druck. Punkte, d.h. Steiner-Knoten - zusätzliche Knoten, die nicht im ursprünglichen Satz enthalten waren

Es mag den Anschein haben, dass Bedingung 2 aus Bedingung 3 folgt, aber in Wirklichkeit ist es das nicht. Beispielsweise kann ein bestehender Tetraeder vollständig sein Innerhalbgetesteter Tetraeder.