 Mirror

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

 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;

<< Back to main page