Ear Clipping Triangulierung

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.

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

Siehe auch

Triangulation