Punkte in ein Polygon überführen

[Bjoerk]

So. Jetzt. Ja. Hab bei Bourke auf der Hompage mal gesucht. Und siehe da, dort steht völlig klar und eindeutig, wie er vorgeht.

Delphi-Quellcode:

procedure TPBDelaunyTriangulation.Triangulate;
var
  Triangle, Node, I: integer;
  Left, Right: TPBIntegers; // Edges;
begin
  // input : vertex list;
  // output : triangle list;
  //    initialize the triangle list;
  //    determine the supertriangle;
  //    add supertriangle vertices to the end of the vertex list;
  //    add the supertriangle to the triangle list;
  //    for each sample point in the vertex list;
  //       initialize the edge buffer;
  //       for each triangle currently in the triangle list;
  //          calculate the triangle circumcircle center and radius;
  //          if the point lies in the triangle circumcircle then;
  //             add the three triangle edges to the edge buffer;
  //             remove the triangle from the triangle list;
  //          endif;
  //       endfor;
  //       delete all doubly specified edges from the edge buffer;
  //          this leaves the edges of the enclosing polygon only;
  //       add to the triangle list all triangles formed between the point;
  //          and the edges of the enclosing polygon;
  //    endfor;
  //    remove any triangles from the triangle list that use the supertriangle vertices;
  //    remove the supertriangle vertices from the vertex list;
  // end;
  Left := TPBIntegers.Create;
  Right := TPBIntegers.Create;
  try
    AddSuperTriangle;
    for Node := 1 to NodesCount - 3 do
    begin
      Left.Clear;
      Right.Clear;
      for Triangle := TrianglesCount downto 1 do
      begin
        if InCircle(Node, Triangle) then
        begin
          Left.Add(A[Triangle]);
          Right.Add(B[Triangle]);
          Left.Add(B[Triangle]);
          Right.Add(C[Triangle]);
          Left.Add(C[Triangle]);
          Right.Add(A[Triangle]);
          FA.Delete(Triangle);
          FB.Delete(Triangle);
          FC.Delete(Triangle);
        end;
      end;
      DeleteInvalidEdges(Left, Right);
      for I := 1 to Left.Count do
      begin
        FA.Add(Left[I]);
        FB.Add(Right[I]);
        FC.Add(Node);
      end;
    end;
    DeleteSuperTriangle;
  finally
    Left.Free;
    Right.Free;
  end;
end;

Was mich an dem Code doch sehr störte, war diese katastrophale Triangulate, so daß man kein Items.Add ect. verwenden konnte, obwohl der Algo sozusagen ein Paradebeispiel für Listen ist. Das 1 basierte hab ich aber gelassen, stört mich nicht weiter (hab ja extra Listen dazu geschrieben). Werd die unit auch noch der Bourke Gemeinde rüberschicken. Hab noch eine kleine grafische Klasse ergänzt. Bitte den oben geposteten Code nicht mehr verwenden, sondern ggf. diesen. Schöne Pfingsten. LG Thomas