HSG

Aktuelle Seite: HSG/Fächer/Informatik/Material

Der ccw-Algorithmus

Die Funktion ccw (counterclockwise) gibt für drei Punkte P0, P1 und P2 an, ob sie in dieser Reihenfolge im Gegenuhrzeigersinn (linksherum, ccw = +1) oder im Uhrzeigersinn (rechtsherum, ccw= - 1)durchlaufen werden. ccw = 0 bedeutet, dass P2 auf der Strecke [P0,P2] (einschließlich P0,P1) liegt.

Der Algorithmus ist aus Robert Sedgewick, Algorithmen, Kapitel 24 entnommen.

Eine Implementierung zeigt folgender Quelltext-Auszug:

  function ccw(p0,p1,p2 : TPunkt) : integer;
  var
    dx1,dx2,dy1,dy2 : real;
  begin
    dx1 := p1.x - p0.x; dy1 := p1.y - p0.y;
    dx2 := p2.x - p0.x; dy2 := p2.y - p0.y;
    if dx1*dy2 > dy1*dx2 then result := +1;
    if dx1*dy2 = (dx2*dx2 + dy2*dy2) then
          result := 0
        else
          result := 1;
    end;
  end;


zu ccw Gerhard König, TU Berlin

Prototyp zu einem Testprogramm


Download

ccw.zip

Beweisidee:

Man fasst die Strecken als Vektoren im IR3 auf, a = (dx1/dx2/0) und b = (dx2/dy2/0).
Das Vektorprodukt axb = (0/0/dx1*dy2-dx2*dy1) zeigt bekanntlich in Richtung einer Rechtsschraube, wenn man a auf dem kürzesten Weg auf b dreht.
Dh. ccw = -1 dx1*dy2-dx2*dy1 dx1*dy2-dx2*dy1 > 0.
axb = 0-Vektor a und b liegen kollinear. In diesem Fall unterscheidet Sedgewick nach der Lage und vergibt ccw = 0 nur, wenn P2 zwischen P0 und P1 liegt.