How to detect if a point lies within a polygon (2) (Views: 27)
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; |