Ist ein Punkt in einem Polygon

[Gandalfus]

Zitat:

Teilweise wird für Punkte außerhalb des Polygons True zurückgegeben, teilweise für Punkte innerhalb des Polygons false.

Bis auf den Rand habe ich Fehler behoben.

Delphi-Quellcode:

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;