Delauny Triangulation

[Thomas D.II]

Hallo,
wüsche erstma schönen Tag!
Ich versuche gerad einen Logarhytmus für eine triangulation für sehr viele Punkte im 3D zu programmieren!
Scheitere allerdings kläglich!
Habe die Punkte bisher in ein Vektorarray gespeichert!Kann mir hier jemand helfen?wäre echt klasse!
Mfg,Thomas

 

[Lim_Dul]

Kennst du den die Algorithmen für eine Delauny Triangulation?

Ohne die kommst du nicht weit.

Hier läuft ein Applet, dass das berechnet: http://web.informatik.uni-bonn.de/I/GeomLab/VoroGlide/

 

[Thomas D.II]

Ja kenne den!Versteh ihn allerdings nicht vollständig!
Ich bräuchte einen der bei über 2000Punkten noch in einer halbwegs akzeptablen Zeit rechnet!(Der dortige benötigt ca.60min!)
Wäre nett wen jemand einen mit verständlicher beschreibung hätte!Danke

 

[Thomas D.II]

Sorry meinte Algorhytmus!!!

 

[Lim_Dul]

Schneller als O(n log n) kann es nicht gehen, da das Problem mindestens so schwierig ist.
Das Verfahren im Applet nutzt, soweit ich weiß, die inkrementelle Konstruktion, die O(n²) benötigt.

Es gibt allerdings Verfahren die eine Laufzeit von O(n log n) haben, allerdings wage ich jetzt aus dem Bauch heraus zu bezweifeln, dass du dafür fertige Java Algorithmen im Netz findest. Du wirst vermutlich nicht drum rum kommen, dir selber den Algorithmus in Java umzusetzen. Ich würde mir einen Algorithmus aussuchen, von dem du ausgehst, dass du ihn sauber in Java umgesetzt bekommst.
In der Literatur, die ich jetzt gerade zur Hand habe (Algorithmische Geometrie, Rolf Klein, 1996) stehen zwei Verfahren drin, die diese Laufzeit Schranke einhalten.

Einmal ein Sweep Verfahren und einmal ein Divide & Conquer Verfahren. Beide sind aber meines Erachtens nicht ohne in der Programmierung und nicht mal eben runterzuschreiben.

 

[Thomas D.II]

Wäre froh wenn jemand einen zur Hand hätte der ca. ne minute braucht!das wäre schon echt super!!!Und dann noch erklärt wäre Perfekt!!!!!!!!