Robert Sedgewick: Algorithmen

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


24. Elementare geometrische Methoden



Enthaltensein in einem Polygon

Das nächste Problem, das wir betrachten wollen, ist von natürlicher Art: Gegeben seien ein Punkt und ein Polygon, das als Feld von Punkten dargestellt ist; es ist zu bestimmen, ob der Punkt innerhalb oder außerhalb des Polygons liegt. Eine einfache Lösung für dieses Problem bietet sich sofort an: Man zeichne eine in diesem Punkt beginnende, eine beliebige Richtung besitzende Strecke (die so lang ist, daß ihr anderer Endpunkt garantiert außerhalb des Polygons liegt) und zähle die zum Polygon gehörenden Linien, die sie schneidet. Falls die Anzahl ungerade ist, muß der Punkt innerhalb des Polygons liegen; wenn sie gerade ist, liegt er außerhalb. Dies läßt sich leicht einsehen, wenn man überlegt, was passiert, wenn wir von dem außerhalb des Polygons gelegenen Endpunkt zurückkommen: Nach der ersten Linie befinden wir uns innerhalb des Polygons, nach der zweiten außerhalb usw. Wenn wir dies eine gerade Anzahl Male wiederholen, muß sich der Punkt, zu dem wir am Ende gelangen (der ursprünglich gegebene Punkt), außerhalb des Polygons befinden.

Die Situation ist jedoch nicht ganz so einfach, da manche Schnitte unmittelbar an den Ecken des gegebenen Polygons erfolgen könnten. Abbildung 24.5 zeigt einige der Situationen, die behandelt werden müssen. Die erste ist ein einfacher Fall vom Typ »außerhalb«, die zweite ein einfacher Fall vom Typ »innerhalb«; in der dritten Situation verläßt die Testlinie das Polygon an einer Ecke (nachdem sie zwei andere Ecken berührt hat), und in der vierten fällt sie mit einer Seite des Polygons zusammen, bevor sie dieses verläßt. In manchen Fällen, in denen die Testlinie eine Ecke schneidet, sollte dies als ein Schnitt mit dem Polygon zählen, in anderen Fällen sollte es als kein Schnitt (oder zwei Schnitte) zählen. Der Leser könnte versuchen, vor dem Weiterlesen einen einfachen Test zur Unterscheidung dieser Fälle zu finden.

Abbildung 24.5
Abbildung 24.5 Fälle, die durch einen Algorithmus »Punkt im Polygon« behandelt werden müssen.

Die Notwendigkeitzur Behandlung der Fälle, in denen Ecken des Polygons auf der Testlinie liegen, zwingt uns, mehr zu tun, als nur die Strecken im Polygon zu zählen, die die Testlinie schneiden. Im wesentlichen wollen wir das Polygon umfahren und einen Zähler jedesmal dann inkrementieren, wenn wir von einer Seite der Teststrecke auf die andere gelangen. Eine Möglichkeit, dies zu implementieren, besteht darin, wie im folgenden Programm auf der Testlinie liegende Punkte einfach zu ignorieren;

    function inside(t: point): boolean;
      var count,i,j: integer;
          lt,lp: line;
      begin
      count:=0; j:=0;
      p[0]:=p[N]; p[N+1]:=p[1];
      lt.p1:=t; lt.p2:=t; lt.p2.x:=maxint;
      for i:=1 to N do
        begin
        lp.p1:=p[i]; lp.p2:=p[i];
        if not intersect(lp,lt) then
          begin
          lp.p2:=p[j]; j:=i;
          if intersect(lp,lt) then count:=count+1;
          end;
        end;
      inside:=((count mod 2)=1);
      end;

Dieses Programm verwendet zur Vereinfachung der Berechnung eine waagerechte Testlinie (man stelle sich die Diagramme in Abbildung 24.5 um 45 Grad gedreht vor). Die Variable j wird für den Index des letzten Punktes des Polygons verwendet, von dem bekannt ist, daß er nicht auf der Testlinie liegt. Das Programm nimmt an, daß p[1] der Punkt mit der kleinsten x-Koordinate unter allen Punkten mit der kleinsten y-Koordinate ist, so daß, wenn p[1] auf der Testlinie liegt, dies bei p[0] nicht der Fall sein kann. Das gleiche Polygon kann mittels N verschiedener Felder p dargestellt werden, doch wie durch dieses Programm veranschaulicht wird, ist es manchmal zweckmäßig, gewisse Regeln für p[1] festzulegen. (Zum Beispiel ist die gleiche Regel für p[1] als »Anker« für die oben vorgeschlagene Prozedur zur Berechnung eines einfachen geschlossenen Polygons von Nutzen.) Falls sich der nächste Punkt im Polygon, der nicht auf der Testlinie liegt, auf der gleichen Seite der Testlinie befindet wie der j-te Punkt, so brauchen wir den Zähler der Schnitte (count) nicht zu inkrementieren; andernfalls liegt ein Schnitt vor. Der Leser mag sich davon überzeugen, daß dieser Algorithmus für die in Abbildung 24.5 dargestellten Fälle korrekt abläuft.

Falls das Polygon nur drei oder vier Seiten hat, wie es in vielen Anwendungen der Fall ist, ist ein derart komplexes Programm nicht erforderlich; in solchen Fällen ist eine einfachere Prozedur angebracht, die auf Aufrufen von ccw beruht. Ein anderer wichtiger Spezialfall ist das konvexe Polygon, das im folgenden Kapitel untersucht wird; es besitzt die Eigenschaft, daß keine Testlinie mehr als zwei Schnitte mit dem Polygon haben kann. In diesem Fall kann eine Prozedur von der Art der binären Suche benutzt werden, um in O(log N) Schritten zu bestimmen, ob ein Punkt sich innerhalb des Polygons befindet oder nicht.


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