Punkte in ein Polygon überführen

[Bjoerk]

Ich müßte für eine Triangulation Punkte in ein Polygon überführen. Der Algorithmus trianguliert jeweils die Punkte in einer Grid.Cell (Siehe Anlage). Der Algo benötigt die Punkte jeweils als rechtsdrehendes xor linksdrehendes Polygon. Konvex oder Konkav ist (hier) egal. Deshalb wollte ich Sortieren. Es sind in der Regel nur so 3 bis 6 Punkte je Cell. Das klappt aber nicht (immer). Überlegt hatte ich mir das. Klappt aber irgendwie nicht (immer). Jemand eine Idee? Wäre klasse.

Delphi-Quellcode:

function TFloatPoints.Counterclockwise(const Index: integer): boolean;
var
  A, B, C: TFloatPoint;
  x21, x31, y21, y31: double;
begin
  A := PrevItems[Index];
  B := Items[Index];
  C := NextItems[Index];
  x21 := B.X - A.X;
  x31 := C.X - A.X;
  y21 := B.Y - A.Y;
  y31 := C.Y - A.Y;
  Result := x21 * y31 - x31 * y21 > 0;
end;

procedure TFloatPoints.SortCounterclockwise;
var
  I, J: integer;
begin
  for I := 0 to Count - 2 do
    for J := I + 1 to Count - 1 do
      if not Counterclockwise(J) then
        Exchange(J, Next(J));
  for I := 0 to Count - 1 do
    if not Counterclockwise(I) then
      ShowMessage('not Counterclockwise');
end;

[Jens01]

Bist Du sicher, ob in Counterclockwise die Berechnung richtig ist?
PaulBourke hat das auf dieser Seite gemacht. Ich weiss nicht, ob Du die Formel optimiert hast, jedenfalls multipliziert er dort erst und subt dann.

Clockwise = Summe(Xi*Yi+1 - Xi+1*Yi) < 0

Edit:
Die Formel drüber könnte Deine sein. Die ist aber auch etwas anders, oder?

[Bjoerk]

Hi Bud, Summe Det kann man hier nicht anwenden. Hatten wir das nicht schonmal?

[Jens01]

Zitat:

cross product = ((xi - xi-1),(yi - yi-1)) x ((xi+1 - xi),(yi+1 - yi)
= (xi - xi-1) * (yi+1 - yi) - (yi - yi-1) * (xi+1 - xi)
A positive cross product means we have a counterclockwise polygon.

Ist das jetzt nicht Dein Ansatz?

[Bjoerk]

Ja, das wird wohl das gleiche sein. Jedenfalls immer drei aufeinander folgende Punkte und nicht die Summe aller Punkte. Man muß auf >= 0 prüfen (CompareValue(.., 0) >= 0) und statt J mit Next(J) natürlich I und J tauschen. War wohl gestern Abend schon ziemlich fertig. Dieser Mesh Kram macht einen sowieso völlig fertig. Ich denke mal, ich habs jetzt aber. Die Triangulation einer Grid.Cell mache ich übrigens damit. Den Code muß man allerdings komplett umschreiben. Soll ich's mal anhängen? Wollte mich bei dir übrigens auch noch bedanken, der Interessent vom Statikerforum letztens hat vor einer Woche gekauft (ist ein Bauamt).

[Jens01]

Hier ist mein Testprogramm

Moment, geht nicht..

[Jens01]

Ich lade das Programm gleich noch hoch, es gibt da kleine Probleme bei mir.

Die verlinkte Triangulation ist aber keine Delaunay-Triangulation, oder? Da könnte das Problem auch liegen.

[Jens01]

Hier jetzt mein Test für eine Delaunay-Triangulation.

Das Ding ist nur ein Test, den ich zur Entwicklung genutzt habe.
Man benötigt die Aussenkontur des Polygons und wirft Punkte rein. Die Punkte werden dann zu Dreiecken trianguliert. Wenn Löcher im Polygon sind, werden die entsprechenden Dreiecke einfach rausgelöscht.

[Bjoerk]

Fein. Sieht gut aus. Ich hab hier jedoch i.d.R. mehrere Polygone übereinder und/oder die Polygone können sich überlappen. Außerdem kann ein Polygon rechts- oder linksdrehend sein und aus nur einem oder 2 Punkten bestehen (Pfosten auf Decke, Wand auf Decke, Punktlager, Unterzug ect..). Diese Punkte, Linien und Ränder müssen sich im FE Raster wiederfinden. Und der User gibt eine max. Elementgröße vor. Deshalb der Aufwand mit dem Raster.

Beispiel:

Delphi-Quellcode:

var
  Areas: TAreas;
begin
  Areas := TAreas.Create;
  try
    Areas.Count := 2;

    Areas[0].Add(FloatPoint(0, 0));
    Areas[0].Add(FloatPoint(3, 0));
    Areas[0].Add(FloatPoint(5, 2));
    Areas[0].Add(FloatPoint(5, 0));
    Areas[0].Add(FloatPoint(8.5, 0));
    Areas[0].Add(FloatPoint(8.5, 4));
    Areas[0].Add(FloatPoint(10, 4));
    Areas[0].Add(FloatPoint(10, 1));
    Areas[0].Add(FloatPoint(12.5, 3.5));
    Areas[0].Add(FloatPoint(11, 6));
    Areas[0].Add(FloatPoint(8.5, 6));
    Areas[0].Add(FloatPoint(5, 8));
    Areas[0].Add(FloatPoint(3, 6));
    Areas[0].Add(FloatPoint(5, 6));
    Areas[0].Add(FloatPoint(4, 4));
    Areas[0].Add(FloatPoint(1.5, 3.5));
    Areas[0].Add(FloatPoint(0, 8));
    Areas[0].Add(FloatPoint(0, 3));
    Areas[0].Add(FloatPoint(1.5, 1.5));

    Areas[1].Add(FloatPoint(6, 3));
    Areas[1].Add(FloatPoint(7, 4.5));
    Areas[1].Add(FloatPoint(8, 3));

    FPolygonMesh.TriangleMesh(Areas, 1, 1);

    PaintBox.Invalidate;
  finally
    Areas.Free;
  end;

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