Punkte in ein Polygon überführen

[Jens01]

Mein Programm ist eine reine Triangulation. Dazu benötigt man mehr als 3 Punkte, sonst ist es ja schon ein Dreieck. Alles andere muss vor der Nutzung berücksichtigt werden.

Ich war mir bei Deiner verlinkten Software nicht so sicher, ob das die beste Lösung für eine Triangulation ist.

[Bjoerk]

Das nette an dem Link oben ist daß dieser Algo konvexe und Konkave Polygone trianguliert..

Deinen Ansatz über Delauny mit dem nachträglichen rauslöschen finde ich aber auch nicht schlecht. Solange es nur Flächen sind. Genial.

Delphi-Quellcode:

procedure TDelaunyTriangulationForm.AssignButtonClick(Sender: TObject);
var
  I, A, B, C: integer;
  P1, P2, P3: TFloatPoint;
  Points: TFloatPoints;
begin
  Points := TFloatPoints.Create;
  try
    Points.Add(FloatPoint(0, 0));
    Points.Add(FloatPoint(3, 0));
    Points.Add(FloatPoint(5, 2));
    Points.Add(FloatPoint(5, 0));
    Points.Add(FloatPoint(8.5, 0));
    Points.Add(FloatPoint(8.5, 4));
    Points.Add(FloatPoint(10, 4));
    Points.Add(FloatPoint(10, 1));
    Points.Add(FloatPoint(12.5, 3.5));
    Points.Add(FloatPoint(11, 6));
    Points.Add(FloatPoint(8.5, 6));
    Points.Add(FloatPoint(5, 8));
    Points.Add(FloatPoint(3, 6));
    Points.Add(FloatPoint(5, 6));
    Points.Add(FloatPoint(4, 4));
    Points.Add(FloatPoint(1.5, 3.5));
    Points.Add(FloatPoint(0, 8));
    Points.Add(FloatPoint(0, 3));
    Points.Add(FloatPoint(1.5, 1.5));
    FMesh.Assign(Points);
    FMesh.Mesh;
    for I := FMesh.TrianglesCount downto 1 do
    begin
      A := FMesh.A[I];
      B := FMesh.B[I];
      C := FMesh.C[I];
      P1 := FloatPoint(FMesh.X[A], FMesh.Y[A]);
      P2 := FloatPoint(FMesh.X[B], FMesh.Y[B]);
      P3 := FloatPoint(FMesh.X[C], FMesh.Y[C]);
      if not Points.PtIn(TriangleIncircleCenter(P1, P2, P3), true) then
        FMesh.DeleteTriangle(I);
    end;
    PaintBox.Invalidate;
  finally
    Points.Free;
  end;
end;

[Bjoerk]

Jens, du hast völlig recht. Das geht mit dem Delauny auch für meine Zwecke.

Delphi-Quellcode:

procedure TPBDelaunyTriangulation.PolygonsMesh(Value: TAreas; const dX, dY: double); // PB = Paul Bourke;
var
  Line, Horz, Vert: TFloatLine;
  I, J, Row, Col: integer;
  P: TFloatPoint;
  MaxX, MinX, MaxY, MinY: double;
  AxisHorz, AxisVert: TFloats;
  Nodes: TFloatPoints;
begin
  // TAreas = Liste von Polygonen; Polygon[Index].Count = 1 .. N;
  // - Polygon[Index].Count = 1; -> Punkt;
  // - Polygon[Index].Count = 2; -> Linie;
  // - Polygon[Index].Count > 2 and Counterclockwise; -> pos. Fläche;
  // - Polygon[Index].Count > 2 and not Counterclockwise; -> neg. Fläche;
  AxisHorz := TFloats.Create;
  AxisVert := TFloats.Create;
  Nodes := TFloatPoints.Create;
  try
    // I von III: Nodes ermitteln;
    for I := 0 to Value.Count - 1 do // Alle Flächen, Punkte und Linien;
      for J := 0 to Value[I].Count - 1 do
      begin
        AxisHorz.Add(Value[I].Items[J].Y);
        AxisVert.Add(Value[I].Items[J].X);
      end;
    AxisHorz.RemoveSameValues; // Sortieren und Doppel rauslöschen;
    AxisVert.RemoveSameValues;
    AxisHorz.Refine(dX); // ggf. Zwischenwerte einfügen, so daß der Abstand..
    AxisVert.Refine(dY); // ..zwischen 2 Achsen <= dX bzw. dY wird;
    MinX := Value.MinX; // Unten/Links;
    MinY := Value.MinY;
    MaxX := Value.MaxX; // Oben/Rechts;
    MaxY := Value.MaxY;
    // Schnittpunkte ermitten;
    // *** Kriterium für TAreas.PtIn:
    // - Wenn in einer pos. Fläche und nicht in einer neg. Fläche;
    // - Polygonlinien können sich berühren:
    // - Value.PtIn führt für pos. Flächen Inflate(+1mm) und für neg. Flächen Inflate(-1mm) durch;
    // - Value.PtIn gibt den Index des Polygons zurück, in dem sich der Punkt befindet;
    // *** Kriterium für Line.Intersect;
    // - Gibt nur Schnittpunkte zurück, die sich innerhalb der Strecken A1A2 und B1B2 befinden;
    for Row := 0 to AxisVert.Count - 1 do
    begin
      Vert.P1 := FloatPoint(AxisVert[Row], MinY);
      Vert.P2 := FloatPoint(AxisVert[Row], MaxY);
      for I := 0 to Value.Count - 1 do
        for J := 0 to Value[I].Count - 1 do
        begin
          Line.P1 := Value[I].Items[J];
          Line.P2 := Value[I].NextItems[J];
          if Line.Intersect(Vert, false, P) then // 1 von 3: Schnittpunkte VertLines / PolygonLines;
            if Value.PtIn(P) > -1 then Nodes.Add(P);
      end;
      for Col := 0 to AxisHorz.Count - 1 do
      begin
        Horz.P1 := FloatPoint(MinX, AxisHorz[Col]);
        Horz.P2 := FloatPoint(MaxX, AxisHorz[Col]);
        for I := 0 to Value.Count - 1 do
          for J := 0 to Value[I].Count - 1 do
          begin
            Line.P1 := Value[I].Items[J];
            Line.P2 := Value[I].NextItems[J];
            if Line.Intersect(Horz, false, P) then // 2 von 3: Schnittpunkte HorzLines / PolygonLines;
              if Value.PtIn(P) > -1 then Nodes.Add(P);
          end;
        if Vert.Intersect(Horz, false, P) then // 3 von 3: Schnittpunkte HorzLines / VertLines;
          if Value.PtIn(P) > -1  then Nodes.Add(P);
      end;
    end;
    Nodes.RemoveSameValues; // Doppel rauslöschen;
    // II von III: Delauny;
    Clear;
    for I := 0 to Nodes.Count - 1 do
      Add(Nodes.X[I], Nodes.Y[I]);
    Mesh;
    // III von III: Nicht vorhandene Knoten und Elemente rauslöschen;
    for I := FTrianglesCount downto 1 do // Delauny ist 1-basiert;
      if Value.PtIn(IncircleCenter[I]) < 0 then
        DeleteTriangle(I);
    for I := FNodesCount downto 1 do // ..
      if not NeedNode[I] then
        DeleteNode(I);
    RefreshCapacity;
    Assert(CheckMesh, 'PolygonsMesh.CheckMesh');
    // Ggf. die Dreiecke in Tetragons überführen -> QuadMesh;
  finally
    AxisHorz.Free;
    AxisVert.Free;
    Nodes.Free;
  end;
end;

[Jens01]

Zitat:

Das nette an dem Link oben ist daß dieser Algo konvexe und Konkave Polygone trianguliert..

Das ist bei meinem Algo auch egal. Er benötigt aber die Außenkontur, damit nicht Punkte verbunden werden, die nicht zusammen gehören.
Bei dem Delaunay von Bourke und vielen anderen, hatte ich immer das Problem, dass da immer nur Linien produziert werden, was zum Zeichnen ausreichend ist, aber für die Weiterverarbeitung in einem Mesh nicht. Dazu braucht man dann richtige Dreiecke.
Ich habe mir den Algo deshalb noch mal neu entwickelt. In meinem Testprogramm sind eigentlich echte Dreiecke zu sehen.

[Jens01]

Sooo, eins noch.

Zitat:

Solange es nur Flächen sind. Genial.

Darüber habe ich noch mal nachgedacht. Mit dem Delaunay lassen sich aber auch Volumen zerlegen. Man sollte beliebige Volumen in Pyramiden aufteilen können.
Im 2d prüft man, ob ein Punkt im Kreis liegt. Im 3d müßte man prüfen, ob ein Punkt in einer aufgespannten Kugel liegt.

[Bjoerk]

Mit dem Bourke hab ich mich auch länger beschäftigt. Der Bourke produziert aber keine Linien sondern echte Dreiecke. Der veröffentlichte Delphi Code ist allerdings die totale Katastrophe. Man muß ihn komplett umschreiben. Bourke macht ja den Trick mit dem Supertriangle und löscht die Dreiecke zu dem am Schluß wieder raus, (genau wie wir mit den Dreiecken, die nicht im Polygon liegen). Anyway..

[Jens01]

Zitat:

Der Bourke produziert aber keine Linien sondern echte Dreiecke.

Hmm, hatte ich anders in Erinnerung. Wieso habe ich das denn noch mal neu gemacht? Wahrscheinlich, weil der Code so undurchsichtig war....