Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


24. Elementare geometrische Methoden



Schnitt von Strecken

Als unser erstes elementares geometrisches Problem betrachten wir die Untersuchung, ob sich zwei gegebene Strecken schneiden oder nicht. Abbildung 24.3 veranschaulicht einige der Situationen, die eintreten können. Im ersten Fall schneiden sich die Strecken. Im zweiten Fall befindet sich der Endpunkt der einen Strecke auf der anderen Strecke; wir wollen das als Schnitt betrachten, indem wir die Strecken als »abgeschlossen« annehmen (die Endpunkte sind Bestandteil der Strecken); Strecken, die einen Endpunkt gemeinsam haben, schneiden sich demzufolge auch. In den beiden letzten Fällen in Abbildung 24.3 schneiden sich die Strecken nicht, doch die Fälle unterscheiden sich durch den Schnittpunkt der Geraden, die durch die Strecken definiert sind. Im vierten Fall befindet sich dieser Schnittpunkt auf einer der Strecken, im dritten Fall nicht. Weiterhin könnten die Geraden parallel sein (ein häufig auftretender Spezialfall ist, daß eine Strecke oder beide zu einem Punkt entarten).

Abbildung 24.3
Abbildung 24.3 Überprüfen, ob Strecken sich schneiden: vier Fälle.

Der direkte Weg zur Lösung dieses Problems besteht darin, den Schnittpunkt der Geraden zu ermitteln, die durch die Strecken definiert sind, und dann zu prüfen, ob dieser Schnittpunkt zwischen den Endpunkten beider Strecken liegt. Ein anderes einfaches Verfahren beruht auf einem Hilfsmittel, das uns später noch von Nutzen sein wird, weshalb wir es ausführlicher betrachten wollen: Für drei gegebene Punkte möchten wir wissen, ob wir uns, wenn wir vom ersten zum zweiten und dann zum dritten gehen, gegen den Uhrzeigersinn bewegen oder nicht (also im Uhrzeigersinn). Zum Beispiel lautet für die Punkte A, B und C in Abbildung 24.1 die Antwort »ja«, für die Punkte A, B und D lautet sie dagegen »nein«. Diese Funktion läßt sich aus den Geradengleichungen sehr leicht wie folgt berechnen:

    function ccw(p0,p1,p2: point): integer;
      var dx1,dx2,dy1,dy2: integer;
      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 ccw:=1;
      if dx1*dy2<dy1*dx2 then ccw:=-1;
      if dx1*dy2=dy1*dx2 then 
        begin
        if (dx1*dx2<0) or (dy1*dy2<0) then ccw:=-1 else
        if (dx1*dx1+dy1*dy1)>=(dx2*dx2+dy2*dy2) then ccw:=0 else ccw:=1;
        end;
      end;

Um zu verstehen, wie das Programm abläuft, nehmen wir zunächst an, daß die Größen dx1, dx2, dy1 und dy2 alle positiv sind. Dann bemerken wir, daß die Steigung der p0 und p1 verbindenden Geraden dy1/dx1 ist, und daß die Steigung der p0 und p2 verbindenden Geraden dy2/dx2 ist. Nun ist, falls die Steigung der zweiten Geraden größer ist als die Steigung der ersten, eine »linke« (gegen den Uhrzeigersinn erfolgende) Drehung erforderlich, um von p0 über p1 zu p2 zu gelangen; falls er kleiner ist, ist eine »rechte« (im Uhrzeigersinn erfolgende) Drehung notwendig. Der direkte Vergleich von Geradensteigungen im Programm ist etwas unbequem, da die Geraden vertikal sein könnten (dx1 oder dx2 könnte 0 sein); wir multiplizieren mit dx1 * dx2, um diese Schwierigkeit zu umgehen. Es erweist sich, daß die Steigungen nicht positiv sein müssen, damit dieser Test richtig funktioniert; wenn die Steigungen jedoch gleich sind (die drei Punkte sind kollinear), kann man mehrere Möglichkeiten ins Auge fassen, wie man ccw definieren könnte. Wir wählen die Funktion als dreiwertig: Anstelle von true und false benutzen wir 1 und -1, wobei wir den Wert 0 für den Fall reservieren, daß sich p2 auf der Strecke zwischen p0 und p1 befindet. Falls die Punkte kollinear sind und p0 zwischen p2 und p1 liegt, nehmen wir für ccw den Wert -1; falls p2 zwischen p0 und p1 liegt, nehmen wir für ccw den Wert 0; falls p1 zwischen p0 und p2 liegt, nehmen wir für ccw den Wert 1. Wir werden sehen, daß diese Vereinbarung in diesem und im folgenden Kapitel die Programmierung von Funktionen vereinfacht, die ccw benutzen.

Damit erhalten wir sofort eine Implementation der Funktion intersect (Schnitt). Falls die beiden Endpunkte jeder Strecke sich auf verschiedenen »Seiten« der anderen Strecke befinden (verschiedene ccw-Werte haben), müssen sich die Strecken schneiden:

    function intersect(l1,l2: line): boolean;
      begin
      intersect:=((ccw(l1.p1,l1.p2,l2.p1)*ccw(l1.p1,l1.p2,l2.p2))<=0)
             and C(ccw(l2.p1,l2.p2,l1.p1)*ccw(l2.p1,l2.p2,l1.p2))<=0);
      end;

Diese Lösung scheint für ein derart einfaches Problem einen erheblichen Rechenaufwand zu erfordern. Der Leser sollte versuchen, eine einfachere Lösung zu finden, dabei jedoch darauf achten, daß die Lösung wirklich für alle Fälle geeignet ist. Falls zum Beispiel alle vier Punkte kollinear sind, gibt es sechs verschiedene Fälle (Situationen, wo Punkte zusammenfallen, nicht mitgerechnet), von denen nur vier einem Schnitt entsprechen. Spezialfälle dieser Art sind ein generelles Problem geometrischer Algorithmen; sie lassen sich nicht vermeiden, doch wir können mit Grundelementen von der Art von ccw ihren Einfluß abschwächen.

Wenn viele Strecken betrachtet werden, wird die Situation wesentlich schwieriger. Im Kapitel 27 lernen wir einen komplizierten Algorithmus kennen, mit dessen Hilfe bestimmt werden kann, ob sich je zwei Strecken aus einer Menge von N Strecken schneiden.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]