Delaunay-Triangulation

[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..

[Jens01]

Ich hab sowas mal vor kurzem gemacht.
Wenn ich mich richtig entsinne, hatte der Code von Bourke das Problem, dass als Ergebnis keine ganzen Dreiecke kamen. Es wurden nur nacheinander Linien gezeichnet. Das brachte mich auf jeden Fall nicht richtig weiter. Also habe ich es mal selbst probiert. Hatte zum Schluß zwar kein schönen Code, aber dann irgendwann ein gutes Ergebnis.

Bei OpenGL gibt es in der GLU-Lib einen 3d-Triangulator. MrMath hat neben seiner guten Matrix-Lib noch diesen Triangulator. Ich habe den aber nie getestet. Der Autor sagte mir mal, dass der Code funktioniert und er den Triangulator für eine Gesichtserkennung nutzt.

[Bjoerk]

Hi Bud,

außerdem ist der Code ja mal so richtig kacke..

Delphi-Quellcode:

  dVertex = record
    x: Double;
    y: Double;
  end;

..

  public
    HowMany: Integer;
    tPoints: Integer
    TargetForm: TForm;
    destructor Destroy;

Gruß
Thomas

[Jens01]

Also noch mal zur Triangulation.
So einfach wie Dejan Vu das meint, war es nicht. Man muß auch irgendwie den Rand/Umriss festlegen. Ebenso die Umrisse der Löcher. Das kann ganz schön verwirrend sein. War es jedenfalls bei mir.
Ich konnte zum Schluß aber Flächenmomente von beliebigen Querschnitten ausrechnen.

Dies Konzept "Fortscheitende Front" von jfheins würde mich auch interessieren. Hatte ich noch nicht gehört. -zumal es sich wie eine rus Militärtaktik anhört-

Wofür brauchst Du das jetzt genau? Finite Elemente?

[Bjoerk]

Ja, FE. Hab zur Zeit nur eine Lösung für Rechtecke. Wie hats du denn die gemeinsamen Lagerpunkte hingekriegt?

[Jens01]

Zitat:

Wie hats du denn die gemeinsamen Lagerpunkte hingekriegt?

Nein, mache kein FE! Brauche das ganze um Löcher in Flächen von Körpern zu schneiden. Z.B. für ein Zapfenloch in einem Pfosten bei der grafischen OpenGL-Darstellung.
Das mit den Flächenmomenten habe ich einfach nur so aus Spaß dazuprogrmmiert, als ich mit dem Programmteil fertig war. War auch kaum noch Arbeit. Ich glaube aber, dass sich Flächenmomente anders einfacher rechnen lassen als mit Triangulationen.

[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