Diskussion:Delaunay-Triangulierung

---

Habe nur ich den Eindruck, dass der Artikel für den nicht-Fachmann arg unverständlich ist?

---

Ich kann mich nur anschliessen! Nachdem ich den Artikel von der Hauptseite aus aufgerufen habe, musste ich enttäuscht feststellen, dass hier Mathematiker am Werk waren. Hinweise zur Anwendung des Verfahrens und zum Praxisbezug wären wünschenswert, da das Thema an sich interessant ist. Wie kommt ein solcher Artikel überhaupt auf die Hauptseite - Tobias, Hannover 09.04.06

Du täuschst dich: Hier waren Informatiker am Werk. Mathematiker hätten den Artikel zusätzlich noch mit Formeln überflutet. :-) --Nü 20:07, 9. Apr 2006 (CEST)

---

Die Kreise in dem Bild zum Flip-Algorithmus sind doch falsch oder? Die Kreise müssen doch durch alle drei Ecken des Dreiecks verlaufen und nicht nur durch die zwei der Geraden! Wenn das noch jemand bestätigt, änder ich das mal... --mswiege 23:23, 11. Apr 2006 (CEST)

Ja, die Bilder sind nicht korrekt. Zwar garantiert die im Bild gezeigte Thales-Kreis-Bedingung die Einhaltung der Umkreis-Bedingung, aber sie ist schärfer als die ursprüngliche Umkreis-Bedingung und nicht unbedingt notwendig. Du darfst meine Grafik verändern oder ersetzen. --Nü 17:12, 12. Apr 2006 (CEST)

Die Bilder haben schon ihren Sinn :) Alternativ zu der Dreiecks-Umkreis-Bedingung kann man nämlich auch fordern, daß jede Kante einen von anderen Punkten freien Umkreis hat. Als Umkreis zählt dabei jeder Kreis, der die Kante genau an ihren Endpunkten schneidet. Auf dem Bild sieht es so aus, als müsse dieser Kreis genau mittig auf der Kante sitzen - das ist natürlich missverständlich. --84.63.112.168 17:38, 14. Apr. 2007 (CEST)

Wäre beim Flip-Algorithmus nicht auch folgende Bedingung ausreichend: - Um die gemeinsame Kante einen mittigen Kreis ziehen. - Beinhaltet dieser Kreis höchstens einen der anderen beiden Punkte (der beiden sich berührenden Dreiecke), dann bildet die gemeinsame Kante mit diesem einzigen im Kreis liegenden Punkt, bzw. mit dem dem Kreis am nächsten liegenden Punkt ein (ich nenne es mal so) Delaunay-Dreieck. Meiner Meinung nach erfüllt diese Konstruktionsbeschreibung die Delaunay-Bedingung. -- Ithaqua 23:58, 30. Mai 2007 (CEST)

Es gibt ein sehr einfaches Kriterium um zu testen ob zwei benachbarte Dreiecke Delaunay sind: die der gemeinsamen Kante gegenueberliegenden Winkel muessen gemeinsam weniger als 90 Grad ergeben. Das folgt aus dem allgemeinen Satz des Thales. Ist der Winkel groesser muss man Flippen. -- [[Benutzer: unangemeldet] 17:11, 19.Februar 2010 (CEST) (ohne Benutzername signierter Beitrag von 130.149.13.154 (Diskussion | Beiträge) )

Die Definition des Begriffes ist nicht korrekt: Die Delaunay-Triangulation ist kein Verfahren zur Erstellung eines Dreiecksnetzes, sondern beschreibt lediglich eine spezielle Art der Triangulierung einer Menge von Punkten. Vorschlag: "Benannt nach dem russischen Mathematiker Boris Nikolaevich Delone bezeichnet die Delaunay-Triangulation die Unterteilung einer Punktemenge P in Dreiecke (Triangulation), so dass kein Punkt in P innerhalb des Umkreises eines Dreiecks der Triangulierung liegt." -- Picnicer 23:06, 22. Jan. 2011 (CET)

Zusammenhang mit Voronoi-Diagrammen

Hier sollte man noch folgendes beachten: Die Delaunay-Triangulierung (DT) entspricht nur genau dann dem dualen Graph zum Voronoi-Diagramm, wenn sich die Punkte der Punktemenge in allgemeiner Lage befinden. Ansonsten enthält der duale Graph u. U. auch n-Ecke mit n >= 3. Diese Flächen lassen sich dann aber sehr einfach triangulieren, da sie konvex sind. In dem Fall spricht man auch von einem "Delaunay-Graphen". -- quirkquark 11:45, 26. Januar 2009 (CEST)

Name

Ich glaube, der Name Delaunay geht auf einen anderen zurück, nicht auf Charles Eugene Delaunay. Boris Delaunay (Delone) wird in der englischen Wikipedia genannt, und ich meine das auch irgendwo anders gelesen zu haben.

Bestätigt: Boris Delaunay hat den Artikel Sur la sphère vide geschrieben. --Schleinkofer 14:00, 21. Apr. 2008 (CEST)

Aussprache

Könnte am Anfang noch ein Hinweis hinzugefügt werden, wie man den Namen ausspricht? Danke! --134.106.143.90 11:59, 10. Aug 2006 (CEST)

akaik wird der Herr "Deloni" ausgesprochen, kann das jemand verifizieren und korrekt (in dieser Laut-Schrift, wie auch immer sie heißt) einbauen? - Robert

Varianten auseinander halten

Soweit ich weiß, geht der reine Delaunay-Algorithmus von einer festen Punktmenge aus und baut daraus die Dreiecke auf. Ein Programm wie Triangle übernimmt diese Punkte, fügt allerdings auch neue Punkte hinzu, um Dreiecke von besserer Qualität erzeugen zu können (Steiner points). Schließlich gibt es noch Programme, die ein Gebiet mit kontinuierlicher Randkurve annehmen, und dann auf dieser Kurve Punkte verteilen (zb das WMG ganz unten).

Ich denke, man sollte diese Unterschiede in dem Artikel auch deutlich machen, und dann erklären, welcher Algorithmus sich für welche Variante des Problems eignet.

Algorithmen

Ein gute Zusammenfassung gibt Tomas Lehner in seiner Diplomarbeit. Dort finden sich auch Angaben zum Aufwand. Ich habe beides eingefügt, jedoch sollten die Sekundär-Zitate bei den Aufwandsangaben bei Gelegenheit nachgeprüft und durch die Erstquellen ersetzt werden. --Schleinkofer 14:00, 21. Apr. 2008 (CEST)

Mir ist nicht wirklich klar, wieso der Flip-Algorithmus einen Laufzeitaufwand von O(n^2) haben soll. Es wird zwar auch so im englischen Artikel angegeben, aber auch dort gibt es keine Hinweise. Naiv betrachtet müsste doch jede Kante nur einmal geflippt werden, d.h. die Laufzeit ist linear bzgl. der Kanten, also auch linear bezgl. der Eckpunkte. Wie auch immer, das sollte genauer beschrieben werden, finde ich. --84.167.214.74 17:13, 22. Mär. 2009 (CET) Simon Fuhrmann

Nach Klein, Rolf: Algorithmische Geometrie hat der letzte Algorithmus 'Berechnung über die konvexe Hülle in 3D' die optimale Zeitkomplexität O(n log n). Dies ist auch nicht überraschend, da man die konvexe Hülle in 3D in O(n log n) bestimmen kann und die Projektionen liegen in O(n). Die Schranke O(n^4) ist auf jeden Fall falsch. -- Kernstahl 22:28, 14. Apr. 2009 (CEST)

Fehler

Der Artikel ist teilweise leider sogar falsch, Die im Flip Algorithmus beschriebene Delaunay Bedingung ist falsch: "Dann wird für jeweils zwei Dreiecke, die eine Seite gemeinsam haben, überprüft, ob ein Kreis existiert, der durch die zwei Endpunkte dieser Kante geht und keine Knoten in seinem Innenraum enthält."

Richtigerweise muss der Kreis nicht durch die Endpunkte der gemeinsamen Kante gehen, sondern ist vielmehr der Umkreis um das entsprechende Dreieck. Auf der englischen Wikipedia ist dies ganz richtig beschrieben: "A circle circumscribing any Delaunay triangle does not contain any other input points in its interior." .. 192.35.17.26 14:08, 31. Mär. 2011 (CEST)

Ja, stimmt. Habs grad korrigiert. --Fjalnes 23:53, 31. Mär. 2011 (CEST)

Die Triangulierung im linken Bild scheint mir keine Delauney-Triangulierung zu sein.

Frage

"A circle circumscribing any Delaunay triangle does not contain any other input points in its interior." Das nennt man das Umkreiskriterim von Lawson. Allerdings ist dieses ohne Divide and Conquer Methode sehr ineffizient. In den 90 er Jahren habe ich daher ein Kriterium hergeleitet, das wie folgt funktioniert : Man ueberprueft alle Verbindungen zweier Punkte der Menge in der Form, ob diese aufgrund der Lage aller anderen Punkte eine Vornoikante aufweisen koennen. http://home.arcor.de/richardon/richy2001/mathe/delauny/index.htm Die Methode ist zumindestens schneller als das Umkreiskriterium. Auf einem 386 konnte man etwa 1000 Punkte triangulieren. Weiss jemand wo man die Methode einordnen koennte und wie man hier Teile und Herrsche anwenden kann ? MfG http://de.wikipedia.org/wiki/Benutzer:Richardon (17:26, 13. Jun. 2011 (CEST), Datum/Uhrzeit nachträglich eingefügt, siehe Hilfe:Signatur)

Triangulierung oder Triangulation

Ich kenne ehrlich gesagt eher die Verwendung des Begriffes Delaunay Triangulierung. Eine Triangulation ist für mich eher ein Verfahren aus der Geodäsie. Sieht das irgendwer ähnlich? --Andreschulz (Diskussion) 12:42, 26. Jun. 2013 (CEST)

Ja, "triangulation" ist der englische Begriff, im deutschen ist m.E. "Triangulierung" gebräuchlich. Ich schlage vor, die Seite zu verschieben.--Pugo (Diskussion) 03:55, 4. Feb. 2016 (CET)

verschoben --Pugo (Diskussion) 04:47, 5. Feb. 2016 (CET)

Θ(n) und O(n)

Ist es Absicht, dass $\Theta (n)$ und ${\mathcal {O}}(n)$ durcheinander genutzt werden? Wird damit was unterschiedliches gemeint?

Ja. Siehe Landau-Symbole. --RokerHRO (Diskussion) 23:22, 22. Okt. 2020 (CEST)

Rechenzeit und Speicherplatz - Symbole und Formeln an Beispielen erklären

Im Artikel sind u.a. in "Algorithmen" veschiedenen Methoden zur Triangulierung beschrieben. Die Bedeutung der dabei verwendeten Symbole ist nicht erklärt. Auch eine Prosa-Baschreibung der Formeln fehlt. Wenn ich richtig interpretiere, geht es um Speicherbedarf und Rechenzeit? Sowie um die Effizienz beim Hinzufügen zusätzlicher Punkte? Vielleicht kann das ja jemand anhand von Beispielen so erläutern, dass die Auswirkungen auf Rechenzeit und Speichergrösse numerisch deutlich werden? Wobei vermutlich noch zwischen RAM vs. ROM differenziert werden muss? Danke, --Markus (Diskussion) 09:26, 5. Jan. 2021 (CET)