Delaunay-Triangulation

[Bjoerk]

So. Jetzt wirds langsam. Flippen geht aber Hatch ist nicht so prickelnd.

Jens, weißt du noch nach welchem Verfahren du deine Polygone "vorgedreieckt" hast?

[Jens01]

Zitat:

"vorgedreieckt"

Äh, was meinst Du genau?

[Dejan Vu]

Zitat von Bjoerk:

Ok. Ich versuch mal bissl näher zu erläutern...

Hat das dann noch etwas mit der Delaunay-Triangulation zu tun?

[Bjoerk]

Zitat von Jens01:

Zitat:

"vorgedreieckt"

Äh, was meinst Du genau?

Damit könnte man Polygone wunderbar Delaunay like vorbereiten und dann easy weiter verfeinern.
(Siehe TDelaunayTriangulation.Triangulate in #18)

[Bjoerk]

Kaum vergeht ein Jahr, schon bekommt man eine Idee wie man's umsetzen könnte.

Delphi-Quellcode:

function TPolygonTriangulation.AdvancingFrontTriangulate(const RefineCount: integer): boolean;
var
  A, B, C, I: integer; // Dreieck ABC (B = Current)
  D: TFloatPoint;
  Beta: double;
  Triangle: TPolygonTriangle;
  AdvancingFront: TFloatPoints;
begin
  Result := true;
  AdvancingFront := TFloatPoints.Create;
  try
    AdvancingFront.Assign(FPoints);
    AdvancingFront.RefinePolygon(RefineCount);
    FTriangles.Clear;
    B := 0;
    while Result and (AdvancingFront.Count > 3) do
    begin
      A := AdvancingFront.Prev(B);
      C := AdvancingFront.Next(B);
      Triangle.A := AdvancingFront[A];
      Triangle.B := AdvancingFront[B];
      Triangle.C := AdvancingFront[C];
      Beta := Triangle.Beta;
      if CompareFloat(Beta, 0.5 * Pi) < 0 then // Konvex;
      begin
        AdvancingFront.Delete(B);
        FTriangles.Add(Triangle);
      end
      else
        if (CompareFloat(Beta, 0.5 * Pi) >= 0) and (CompareFloat(Beta, Pi) <= 0) then // Konvex;
        begin
          D.X := 0.5 * (Triangle.A.X + Triangle.C.X) + 0.2 * (Triangle.A.Y - Triangle.C.Y);
          D.Y := 0.5 * (Triangle.A.Y + Triangle.C.Y) + 0.2 * (Triangle.C.X - Triangle.A.X);
          I := FTriangles.IndexOfPtIn(D);
          if I < 0 then
          begin
            AdvancingFront[B] := D;
            FTriangles.AddTriangle(Triangle.A, Triangle.B, D);
            FTriangles.AddTriangle(Triangle.B, Triangle.C, D);
          end
          else
          begin
           // ???
           // Result := false;
          end;
        end
        else
        begin
          Result := false; // Konkav; to do ..
          FTriangles.Clear;
        end;
      if Assigned(FOnTriangulate) then
        FOnTriangulate(50, 100);
      B := AdvancingFront.Next(B);
    end;
    if Result then
    begin
      FTriangles.AddTriangle(AdvancingFront[0], AdvancingFront[1], AdvancingFront[2]);
      FTriangles.CircumcircleFlip;
    end;
  finally
    AdvancingFront.Free;
  end;
end;

Hab mal bissl weitergemacht. Macht einen echt fertig.. Ich kriegs jetzt bis soweit hin, bis ein neuer Punkt innerhalb eines bereits bestehenden Dreiecks zu liegen kommt. Aber, wie geht es dann weiter? Jemand eine Idee dazu?

Anlage

[Jens01]

Ich habe mal bei H.Herrmann gelesen, dass das das richtige Konzept für FEM-Netze ist.

[Bjoerk]

Danke für den Link. Der Nelson sucht sich den neuen Punkt nach gewissen Kriterien. Damit hat man aber noch nicht die eigentlich Triangulation (wenn ich's richtig gelesen hab). Hab für dieses Jahr auch schon wieder die Schnauze voll von diesem Thema. Ist wohl nur was für Männer ohne Nerven.. Rufe ggf. mal den Autor dieser Diss an (wohnt grad um die Ecke). LG Thomas

[Jens01]

Also die reine Triangulation ist doch einfach
Ich habe mir vor einiger Zeit einen fertig gemacht. Unterm Strich ist die finale Lösung ganz einfach und ein überschaubarer Code.
u.a. gibt es hier auch einen Triangulator. Den habe ich aber nicht probiert.

[Bjoerk]

Jens, den Delauny kann ich dir auch schicken..

Stell dir aber eine Geschoßdecke vor. Da gibt es verschiedene Polygone (Zimmer) die aneinander stoßen. Die Übergänge müssen geglättet werden. Dann gibt es i.d.R. ein Treppenloch. Dann kann es vorgegebene Achsen geben (Unterzüge). Dann gibt es ggf. Einzellasten aus Dachpfosten auf der Decke. Dann gibt es evtl. Stützen. Das heiß, die Lage all dieser Knoten ist fest und das Raster muß diese in etwa treffen und das Treppenloch muß ausgespart werden. Usw. usw..

Ich hab das bis jetzt ja auch in meiner Software, nur daß der User ein Raster angeben muß. Es sind nur Koordinaten zulässig, die einen Rasterpunkt darstellen. Und Schrägen werden abgetreppt (da Rechteckselemente). Ich wollte halt zusätzlich eine neues FEM Programm entwickeln (Dreiecke).

Apropos Dreiecke, hast du einen Tipp für eine GUTE Steifigkeitsmatrix für Dreieckselemente?

[Jens01]

Okay, dann habe ich Dich falsch verstanden.