Delaunay-Triangulation

[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