Delaunay-Triangulation

[Bjoerk]

Ich hab leider gar keinen Plan von diesem Algo. Hat jemand mal was in der Richtung gemacht oder eine Idee wie man sowas angehen könnte?

http://de.wikipedia.org/wiki/Delaunay-Triangulation

[Dejan Vu]

Wo ist denn dein Problem? Ich habe es auch noch nicht gemacht, aber es sieht doch nicht so schwer aus.

Delphi-Quellcode:

Delaunay := TDelaunay.Create;
Delaunay.Initialize();
For P in Points do Delaunay.Add(P);

Initialize ist einfach und was das 'Add' macht, steht da doch auch.

Edit: Ok, ein wenig hochnäsig. Mach mal 'stepwise refinement' bzw. top down programming(*)
also

Delphi-Quellcode:

Procedure TDelaunay.Add (P : TPoint);
var
  i : Integer;
  tmp : TTriangle;

begin
  for i:=0 to Triangles.Length-1 do 
    if Triangles[i].Contains(P) then begin
      tmp := Triangles[i];
      Triangles.Remove(i);
      Triangles.Add(TTriangle.create(tmp.a,p,tmp.b));
      Triangles.Add(TTriangle.create(tmp.b,p,tmp.c));
      Triangles.Add(TTriangle.create(tmp.c,p,tmp.a));
      CheckBoundariesWithFlipAlgorithm;
      exit;
     end;

  raise exception.Create('Point not in triangle');
end;

Ok. Bleibt noch 'CheckBoundariesWithFlipAlgorithm'. Der geht einfach alle Dreiecke durch und prüft die Bedingungen mit diesem Umkreis. Oder nur für die drei Dreiecke, die dazugekommen sind, wäre vielleicht sinniger.

(*) Alles auskodieren, was einem klar ist und alles, was noch nicht klar ist, als Methode aufrufen. Danach die neuen Methoden nach dem gleichen Schema ausformulieren. Klappt meistens, ist gut lesbar und fast schon ein wenig 'clean code'.

[Medium]

Ich habe es zwar schon gemacht, aber so komplett ohne Ansatz und Ausgangslage ist sinnvolle Hilfe nicht möglich. Fang an, und bei konkreten Problemen sind wir sicher gerne dabei - ich zumindest, weil ich finde solche Themen spannend

[pelzig]

Zitat von Dejan Vu:

Wo ist denn dein Problem? Ich habe es auch noch nicht gemacht, aber es sieht doch nicht so schwer aus.

Delphi-Quellcode:

Delaunay := TDelaunay.Create;
Delaunay.Initialize();
For P in Points do Delaunay.Add(P);

Initialize ist einfach und was das 'Add' macht, steht da doch auch.

Ich habe zwar keinen Führerschein, aber:

- Auto kaufen
- Losfahren

sollte doch wohl kein Problem in einer Millionenstadt darstellen!

Meint wohl Dejan Vu?

MfG

[Dejan Vu]

Genau so. Wenn Du das nicht verstehst, dein Problem. Wie man fährt, habe ich oben ja schon gezeigt.
Der Algorithmus wird erklärt und man muss ihn nur in Delphi übersetzen. Wenn man die Sprache beherscht, geht das doch recht flott. Wie man sieht.

[pelzig]

Ganz genau so in #2:

Geändert von Dejan Vu (Heute um 17:37 Uhr)

Hinterher ist man immer schlauer und altklüger ...

MfG

[Bjoerk]

Ok. Ich versuch mal bissl näher zu erläutern. Und gleich vorab, so einfach wie sich das Dejan Vu in seinem judenglichen Leichtsinn vorstellt ist es natürlich nicht. Stellen wir uns eine beliebige Wohnung vor. Diese Wohnung hat Zimmer. Wir stehen in einem dieser Zimmer und schauen nach unten auf den Boden. Was wir dann sehen nennt sich der Grundriss dieses Zimmers. Wir bekommen vom Architekten einen Grundriss der gesamten Wohnung. Die Zimmer nennen wir Polygone und verlegen die gesamte Wohnung mit dreiecks- bzw. vierecksförmigen Parkett. Das Parkett nennen wir finite Elemente. Wir sollen das Parkett wie folgt verlegen: Es dürfen beliebige drei- und viereckige Teile verwendet werden, die Teile sollen jedoch in etwa gleich groß sein. Wir sollen nun in jedes Polygon ein Netz reinlegen ("ParkettFloodFill"), so daß jedes Polygonnetz die Randknoten der benachbarten Polygonnetze teilt. Dann gibt es ggf. Treppenlöcher. Die nennen wir Aussparungen. In diesen Aussparungen gibt es kein Netz. In etwa klar?

[jfheins]

Wenn es schon um FEM geht: Das Verfahren "Fortscheitende Front" führt meistens zu schöneren Netzen.
Morgen kann ich dir vielleicht etwas ausführlicher helfen.

[Bjoerk]

Gerade eben entdeckt. Das hat wohl ein netter Mensch nach Delphi übersetzt. Schau ich mir näher an.

[Bjoerk]

Wow jfheins, das sieht mega aus. So hätt ich's gern..