How to detect if a point lies within a polygon (2)

Problem/Question/Abstract:

I have an array of polygons and I would like to check in what polygon my last mouse click occured. How can I do that?

Answer:

This routine checks for being on a line first. Polygon is set for an arbitrary 100 points. You change to your needs. MyPoint is mouse location. You do not need to move off the point with this routine, and thus it works for floats.

{ ... }
var
  Form1: TForm1;
  MyPolygon: array[1..100] of TPoint;
  MyPoint: TPoint;

implementation

{$R *.DFM}

function IsPointInPolygon: Boolean;
var
  i, j, k: Integer;
  LoY, HiY: Integer;
  LoX, HiX: Integer;
  IntersectY: Integer;
  Slope, Intercept: double;
  UseSegment, NotDone: Boolean;
  PointCount: Integer = 1;
  CrossingCount: Integer;
  Remainder: Integer;
begin
  Result := false;
  CrossingCount := 0;
  for i := 1 to PointCount - 1 do
  begin
    {Use only segments whose x values encompass point x}
    LoX := Min(MyPolygon[i].x, MyPolygon[i + 1].x);
    HiX := Max(MyPolygon[i].x, MyPolygon[i + 1].x);
    if ((MyPoint.x >= LoX) and (MyPoint.x <= HiX)) then
    begin
      {See if the x values line up with either endpoint
      a) see if we are on the endpoint exactly if yes inside the polygon and we
                                are done
      b) if lined up with lo indexed point see if line is vertical and if we are
                                on the line - then exit ignore line otherwise
      c) if lined up with hi indexed point see if line is vertical and if we are
                                on the line - then exit ignore line otherwise
         see if next segment creates a parity counting problem. If yes, skip
                                the segment}
      if (MyPoint.x = MyPolygon[i].x) then
      begin {matching lo index}
        if (MyPoint.y = MyPolygon[i].y) then
        begin {is it same as endpoint}
          Result := true;
          Exit;
        end
        else if (MyPolygon[i].x = MyPolygon[i + 1].x) then
        begin {vertical}
          LoY := Min(MyPolygon[i].y, MyPolygon[i + 1].y);
          HiY := Max(MyPolygon[i].y, MyPolygon[i + 1].y);
          {see if y coord is within the segment}
          if ((MyPoint.y >= LoY) and (MyPoint.y <= HiY)) then
          begin
            Result := true;
            Exit;
          end {if on line segment}
          else {vertical, not on line segment}
            UseSegment := false;
        end {if x's match}
        else // not a vertical line but endpoint matches drop it
          UseSegment := false;
      end {if point x matches lower index x}
      else if (MyPoint.x = MyPolygon[i + 1].x) then
      begin {matching hi index}
        {check same stuff as low point first}
        if (MyPoint.y = MyPolygon[i + 1].y) then
        begin {is it same as endpoint}
          Result := true;
          Exit;
        end
        else if (MyPolygon[i].x = MyPolygon[i + 1].x) then
        begin {vertical}
          LoY := Min(MyPolygon[i].y, MyPolygon[i + 1].y);
          HiY := Max(MyPolygon[i].y, MyPolygon[i + 1].y);
          {See if y coord is within the segment}
          if ((MyPoint.y >= LoY) and (MyPoint.y <= HiY)) then
          begin
            Result := true;
            Exit;
          end {if on line segment}
          else {vertical, not on line segment}
            UseSegment := false;
        end {if x's match}
        else
        begin {not a vertical line - but on endpoint}
          {Check the next non vertical segment to handle counting error}
          NotDone := true;
          j := i + 1;
          k := i + 2;
          if k > PointCount then
            k := 1;
          while NotDone do
          begin
            if (MyPolygon[j].x = MyPolygon[k].x) then
            begin {vertical}
              j := j + 1;
              if j > PointCount then
                j := 1;
              k := k + 1;
              if k > PointCount then
                k := 1;
            end
              {not vertical - see if we include it in the count}
            else
            begin
              NotDone := false;
              if (((MyPolygon[i].x < MyPolygon[j].x) and (MyPolygon[k].x >
                MyPolygon[j].x))
                or ((MyPolygon[i].x > MyPolygon[j].x) and (MyPolygon[k].x <
                  MyPolygon[j].x))) then
                UseSegment := true
              else
                UseSegment := false;
            end;
          end; {if not vertical}
        end; {while not done}
      end {if point x matches hi endpoint x}
      else {no endpoint matches - use the segment}
        UseSegment := true;
      if UseSegment then
      begin
        {compute the slope and intercept of non vertical segments that
                                pass the parity test}
        Slope := (MyPolygon[i].y - MyPolygon[i + 1].y) / (MyPolygon[i].x - MyPolygon[i
          + 1].x);
        Intercept := MyPolygon[i].y - (Slope * MyPolygon[i].x);
        {Compute the y value at the point of intersection of a line dropped
                                from MyPoint to the x axis and the segment}
        IntersectY := Trunc((Slope * MyPoint.x) + Intercept);
        {if the intersection is at or below count it}
        if IntersectY <= MyPoint.Y then
        begin
          {debug}
          Form1.Image1.Canvas.Pen.Color := clRed;
          CrossingCount := CrossingCount + 1;
        end;
      end; {if segment is a good candidate}
    end; {if segment x values qualify}
  end; {for all segments in the polygon}
  {last step - see if we crossed an odd number of times}
  Remainder := CrossingCount mod 2;
  if Remainder = 1 then
    Result := true; {odd crossings gets us in}
end;