DruckenMister WongFacebook

Prüfen, ob ein Punkt in einem Polygon liegt
Autor Henning Brackmann
System Win9x, WinNT, Win2000, WinXP, Vista, Win7
Ab Delphi-Version Delphi 1
Letzte Änderung 30.04.2011

Bei diesem Algorithmus geht man von dem Punkt nach rechts und zählt die überquerten Kanten. Bei einer ungeraden Anzahl überquerter Kanten liegt der Punkt im Polygon.

Dabei sind folgen Fälle zu unterscheiden:

  1. Punkt auf einem Polygon-Punkt
  2. Punkt liegt auf gleicher Höhe mit einem Polygon-Punkt
    Hier gibt es zwei Möglichkeiten:
    Wird gezählt:

    Wird nicht gezählt:
  3. Punkt.y liegt zwischen zwei Polygon-Punkten und die beiden Punkte liegen rechts vom Punkt3.
  4. Punkt.y liegt zwischen zwei Polygon Punkten und der Punkt liegt zwischen den beiden Punkten

    Hier muss noch zusätzlich geprüft werden auf welcher Seite der Punkt liegt
function PointInPolygon(const APolygon: TPointArray; const TestPoint: TPoint): Boolean;

function getNextPoint(const APolygon: TPointArray; const index: integer): TPoint;
begin
  if index=High(APolygon) then
    result := APolygon[0]
  else
    result := APolygon[index+1];
end;

function getPreviousPoint(const APolygon: TPointArray; const index: integer): TPoint;
begin
  if index=0 then
    result := APolygon[High(APolygon)]
  else
    result := APolygon[index-1];
end;

var
  i: integer;
  currentPolygonPoint: TPoint;
  nextPolygonPoint: TPoint;
  previousPolygonPoint: TPoint;
  crossLines: integer;
begin
  crossLines:=0;
  result := false;
  for i := 0 to High(APolygon) do               // check polygon vertices
  begin
    currentPolygonPoint := APolygon[i];
    nextPolygonPoint := getNextPoint(APolygon,i);


    if (TestPoint.y=currentPolygonPoint.y) and (TestPoint.x=currentPolygonPoint.x) or
       //Horizontale Linie:
       ((TestPoint.y=currentPolygonPoint.y) and (TestPoint.y=nextPolygonPoint.y) and
        (TestPoint.x<currentPolygonPoint.x) and (TestPoint.x>nextPolygonPoint.x)) or
       //vertikale Linie:
       ((TestPoint.x=currentPolygonPoint.x) and (TestPoint.x=nextPolygonPoint.x)and
        (TestPoint.y>currentPolygonPoint.y) and (TestPoint.y<nextPolygonPoint.y)) then
    begin  //Fall 1  oder Punkt auf seknkrehcter oder horiuontaler Linie
      crossLines := 1;
      break;
    end
    else
    begin
      if (TestPoint.y=currentPolygonPoint.y) and (TestPoint.x<currentPolygonPoint.x) then
      begin //Fall 21
        previousPolygonPoint := getPreviousPoint(APolygon,i);
        if ((previousPolygonPoint.y>TestPoint.y) and (nextPolygonPoint.y<TestPoint.y)) or
           ((previousPolygonPoint.y<TestPoint.y) and (nextPolygonPoint.y>TestPoint.y)) then
        begin
          inc(crossLines);
        end;
      end
      else
      begin
        if ((TestPoint.y > currentPolygonPoint.y) and (TestPoint.y < nextPolygonPoint.y)) or
           ((TestPoint.y > nextPolygonPoint.y) and (TestPoint.y < currentPolygonPoint.y)) then
        begin

          if (TestPoint.x<currentPolygonPoint.x) and (TestPoint.x<nextPolygonPoint.x)then
          begin //Fall 3
            inc(crossLines);
          end;

          if ((TestPoint.x >= nextPolygonPoint.x) and (TestPoint.x < currentPolygonPoint.x)) or
             ((TestPoint.x >= currentPolygonPoint.x) and (TestPoint.x < nextPolygonPoint.x)) then
          begin //Fall 4
            if currentPolygonPoint.y < nextPolygonPoint.y then
            begin // Punkt1 ist oben links}
              if (nextPolygonPoint.x-currentPolygonPoint.x)/(nextPolygonPoint.y-currentPolygonPoint.y) >=
                 (TestPoint.x-currentPolygonPoint.x)/(TestPoint.y-currentPolygonPoint.y) then
                inc(crossLines);
            end;

            if currentPolygonPoint.y > nextPolygonPoint.y then
            begin // Punkt1 ist unten links
              if (nextPolygonPoint.x-currentPolygonPoint.x)/(nextPolygonPoint.y-currentPolygonPoint.y) <=
                 (TestPoint.x-currentPolygonPoint.x)/(TestPoint.y-currentPolygonPoint.y) then
                inc(crossLines);
            end;
          end;
        end;

      end;
    end;

  end;
  if (crossLines mod 2) <> 0 then result := true;

end;