Ear Clipping Triangulierung
Inhaltsverzeichnis
Allgemeines
Bei dem "Ear Clipping"-Algorithmus, handelt es sich um ein einfaches Verfahren, nach der beliebige, sich nicht überschneidende Polygone in Dreiecke unterteilt (trianguliert) werden können. Dies wird Notwendig, da moderne Grafikkarten auf das Darstellen von Dreiecken optimiert sind und vor allem mit konkaven Polygonen nicht zurecht kommen.
Theorie
Grundidee
Nimmt aus einem Polygon die beiden benachbarten Punkte eines Punktes, so erhält man ein Dreieck. Ein Polygon beinhaltet immer ein solches Dreieck, in dem keine anderen Punkte des Polygons liegen. Dieses Dreieck wird "Ohr" genannt. Schneidet man dieses Dreieck ab, so erhält man ein neues Polygon, für das die Regel wieder angewandt werden kann. Die Nachfolgende Grafik veranschaulicht das Prinzip:
Der Algorithmus lässt sich noch verbessern, indem man bestimmt, ob der aktuell ausgewählte Punkt an einer konvexen oder konkaven Ecke des Polygons liegt. Handelt es sich um eine konvexe Ecke, so kann man direkt zum nächsten Punkt springen und dort seine Überprüfungen anstellen.
Vor- und Nachteile, Alternativen
Der wahre Vorteil dieses Algorithmus ist, dass er einfach zu Implementieren und nachvollziehen ist. Jedoch hat er bei guter Implementierung eine quadratische Laufzeit. Das bedeutet, dass er gerade bei größeren Datenmengen in zeitkritischen Anwendungen nicht zu gebrauchen ist. Zudem können gerade bei Polygonen mit unregelmäßiger Punktverteilung Dreiecke von sehr unterschiedlicher Größe entstehen. Hierbei ist es besonders problematisch, dass immer wieder sehr kleine Dreiecke entstehen (siehe letztes Dreieck im Beispiel oben). Auf manchen Grafikkarten kann dies zu Bildfehlern bei der Füllung/Texturierung führen.
Beim zuletzt genannten Problem schneiden andere Algorithmen deutlich besser ab. Jedoch sind diese um einiges komplizierter. Die Delaunay-Triangulation und das Voronoi-Diagramm sind hier als Alternativen hervorzuheben.
Die Earclipping Triangulierung lässt sich zwar von Natur aus bei konvexen Polygonzügen anwenden, hat jedoch Probleme mit Überschneidungen oder so genannten "Inseln" im Polygon. Dieses Problem lässt sich dadurch lösen, dass das Polygon zuvor in mehrere Polygone ohne Überschneidungen und Inseln unterteilt wird.
Beispielimplementierung
Im Nachfolgenden findet sich eine einfach Beispielimplementierung des Ear Clipping Algorithmus. Bitte beachtet, dass die Punkte des Polygon im Uhrzeigersinn angeordnet sein müssen und das Polygon keine Überschneidungen haben darf.
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 konkav 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;
Weblinks
http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
http://www.iti.fh-flensburg.de/lang/algorithmen/geo/polygon.htm
http://nuttybar.drama.uga.edu/pipermail/dirgames-l/2003-December/027342.html