Hallo Community,
Ich bastle momentan immer noch an meiner Physik-Engiene(2d) rum und bin so langsam an den Punkt angelangt an dem ich auch Polygone als Objekte möglich machen will. Dazu muss ich aber Fläche, Mittelpunkt und Trägheitsmoment kennen. Um die zu bekommen ist meines Wissens nach das Polygon in Dreiecke zu zerteilen und dann Fläche, Gewicht usw. separat auszurechnen die einzige Möglichkeit. Dazu habe ich diesen Algorithmus gefunden:
Quelle: Ear Clipping Triangulierung ? DGL Wiki
Das Problem daran ist aber dass dieser nur funktioniert wenn dass Polygon im Uhrzeigersinn angeordnet ist!
(Moment mal? Was meinen die mit im Uhrzeigersinn? Darf mein Polygon also nur ein Oval dessen Punkte im Uhrzeigersinn angeordnet sind sein oder wie???)
Ich denke dass Problem daran liegt in dieser Zeile:
Wäre das Polygon gegen den Uhrzeigersinn angeordnet würde er wahrscheinlich denken dass die Ecke genau das Gegenteil vom korrekten Ergebnis ist.
Dass alles ist kein Problem da wenn ich wüsste wierum es um dass Polygon bestellt ist könnte ich ganz einfach bei einem gegen dem Uhrzeigersinn angeordneten Polygon vom Gegenteil ausgehen.
Ich weiß nur leider nicht (auch intensives Googeln half nichts) wie ich erkennen kann ob ein Polygon im oder gegen den Uhrzeigersinn ausgerichtet ist.
Gruß Spyboot
Ich bastle momentan immer noch an meiner Physik-Engiene(2d) rum und bin so langsam an den Punkt angelangt an dem ich auch Polygone als Objekte möglich machen will. Dazu muss ich aber Fläche, Mittelpunkt und Trägheitsmoment kennen. Um die zu bekommen ist meines Wissens nach das Polygon in Dreiecke zu zerteilen und dann Fläche, Gewicht usw. separat auszurechnen die einzige Möglichkeit. Dazu habe ich diesen Algorithmus gefunden:
Code:
uses
Classes, Types;
type
TPolygon = array of TPoint;
TTriangle = array[0..2] of TPoint;
TTriangles = array of TTriangle;
function Triangulate(APolygon: TPolygon; var ATriangles: TTriangles):boolean;
var
lst:TList;
i, j:integer;
p, p1, p2, pt: PPoint;
l:double;
intriangle : boolean;
lastear : integer;
//Berechnet aus einem Index, der auch die Listen-Grenzen über- oder unterschreiten
//kann einen validen Listenindex.
function GetItem(const ai, amax:integer):integer;
begin
result := ai mod amax;
if result < 0 then
result := amax + result;
end;
//Überprüft ob ein Punkt in einem Dreieck liegt
function PointInTriangle(const ap1, tp1, tp2, tp3 : TPoint): boolean;
var
b0, b1, b2, b3: Double;
begin
b0 := ((tp2.x - tp1.x) * (tp3.y - tp1.y) - (tp3.x - tp1.x) * (tp2.y - tp1.y));
if b0 <> 0 then
begin
b1 := (((tp2.x - ap1.x) * (tp3.y - ap1.y) - (tp3.x - ap1.x) * (tp2.y - ap1.y)) / b0);
b2 := (((tp3.x - ap1.x) * (tp1.y - ap1.y) - (tp1.x - ap1.x) * (tp3.y - ap1.y)) / b0);
b3 := 1 - b1 - b2;
result := (b1 > 0) and (b2 > 0) and (b3 > 0);
end else
result := false;
end;
begin
lst := TList.Create;
//Kopiere die Punkte des Polygons in eine TList (also eine Vektordatenstruktur)
for i := 0 to High(APolygon) do
begin
New(p);
p^.X := APolygon[i].X;
p^.Y := APolygon[i].Y;
lst.Add(p);
end;
i := 0;
lastear := -1;
repeat
lastear := lastear + 1;
//Suche drei benachbarte Punkte aus der Liste
p1 := lst.Items[GetItem(i - 1, lst.Count)];
p := lst.Items[GetItem(i, lst.Count)];
p2 := lst.Items[GetItem(i + 1, lst.Count)];
//Berechne, ob die Ecke konvex oder konkav ist
l := ((p1.X - p.X) * (p2.Y - p.Y) - (p1.Y - p.Y) * (p2.X - p.X));
//Nur weitermachen, wenn die Ecke konvex ist
if l < 0 then
begin
//Überprüfe ob irgendein anderer Punkt aus dem Polygon
//das ausgewählte Dreieck schneidet
intriangle := false;
for j := 2 to lst.Count - 2 do
begin
pt := lst.Items[GetItem(i + j, lst.Count)];
if PointInTriangle(pt^, p1^, p^, p2^) then
begin
intriangle := true;
break;
end;
end;
//Ist dies nicht der Fall, so entferne die ausgwewählte Ecke und bilde
//ein neues Dreieck
if not intriangle then
begin
SetLength(ATriangles, Length(ATriangles) + 1);
ATriangles[High(ATriangles)][0] := Point(p1^.X, p1^.Y);
ATriangles[High(ATriangles)][1] := Point(p^.X, p^.Y);
ATriangles[High(ATriangles)][2] := Point(p2^.X, p2^.Y);
lst.Delete(GetItem(i, lst.Count));
Dispose(p);
lastear := 0;
i := i-1;
end;
end;
i := i + 1;
if i > lst.Count - 1 then
i := 0;
//Abbrechen, wenn nach zwei ganzen Durchläufen keine Ecke gefunden wurde, oder nur noch
//drei Ecken übrig sind.
until (lastear > lst.Count*2) or (lst.Count = 3);
if lst.Count = 3 then
begin
p1 := lst.Items[GetItem(0, lst.Count)];
p := lst.Items[GetItem(1, lst.Count)];
p2 := lst.Items[GetItem(2, lst.Count)];
SetLength(ATriangles, Length(ATriangles) + 1);
ATriangles[High(ATriangles)][0] := Point(p1^.X, p1^.Y);
ATriangles[High(ATriangles)][1] := Point(p^.X, p^.Y);
ATriangles[High(ATriangles)][2] := Point(p2^.X, p2^.Y);
end;
result := lst.Count = 3;
for i := 0 to lst.Count - 1 do
begin
Dispose(PPoint(lst.Items[i]));
end;
lst.Clear;
lst.Free;
end;Quelle: Ear Clipping Triangulierung ? DGL Wiki
Das Problem daran ist aber dass dieser nur funktioniert wenn dass Polygon im Uhrzeigersinn angeordnet ist!
(Moment mal? Was meinen die mit im Uhrzeigersinn? Darf mein Polygon also nur ein Oval dessen Punkte im Uhrzeigersinn angeordnet sind sein oder wie???)
Ich denke dass Problem daran liegt in dieser Zeile:
Code:
//Berechne, ob die Ecke konvex oder konkav ist
l := ((p1.X - p.X) * (p2.Y - p.Y) - (p1.Y - p.Y) * (p2.X - p.X));Wäre das Polygon gegen den Uhrzeigersinn angeordnet würde er wahrscheinlich denken dass die Ecke genau das Gegenteil vom korrekten Ergebnis ist.
Dass alles ist kein Problem da wenn ich wüsste wierum es um dass Polygon bestellt ist könnte ich ganz einfach bei einem gegen dem Uhrzeigersinn angeordneten Polygon vom Gegenteil ausgehen.
Ich weiß nur leider nicht (auch intensives Googeln half nichts) wie ich erkennen kann ob ein Polygon im oder gegen den Uhrzeigersinn ausgerichtet ist.
Gruß Spyboot
.
