Board index » delphi » Detecting whether a point lies within a polygon

Detecting whether a point lies within a polygon

Hi,

Can anyone help be with detecting whether the screen coord that a user has
clicked on lies within a defined polygon
(I`ll know all the screen coords of the points defining the polygon).
An algorithm would be good, or any links to useful techy sites.

Thanks,

Mike

Re:Detecting whether a point lies within a polygon

Mike,
This works for me

function PointInPolygonTest( x,y: Integer ;aList: Array of TPoint): Boolean;

// The code below is from Wm. Randolph Franklin <w...@ecse.rpi.edu>
// with some minor modifications for speed.  It returns 1 for strictly
// interior points, 0 for strictly exterior, and 0 or 1 for points on
// the boundary.

var L, I, J : Integer;

Function xp(aVal:Integer):Integer;
Begin
Result:= PPoint(@aList[aVal]).X;
end;

Function yp(aVal:Integer):Integer;
Begin
Result:= PPoint(@aList[aVal]).Y;
end;

begin
Result:=False;
L:= Length(aList) ;
If L=0 then exit;
J:=L-1;
for I:=0 to L-1 do
begin
if ((((yp(I)<=y) and (y<yp(J))) OR
((yp(J)<=y) and (y<yp(I)))) and
(x < (xp(J)-xp(I))*(y-yp(I))/(yp(J)-yp(I))+xp(I)))
then Result:=not Result;
J:=I;
end;
end;

John

Quote
"Mike" <mikedown@*remove_this_bit*totalise.co.uk> wrote in message

news:3bcf3315_2@dnews...
Quote
> Hi,

> Can anyone help be with detecting whether the screen coord that a user has
> clicked on lies within a defined polygon
> (I`ll know all the screen coords of the points defining the polygon).
> An algorithm would be good, or any links to useful techy sites.

> Thanks,

> Mike

Re:Detecting whether a point lies within a polygon

Thanks for the quick reply John,
I`ll give it a go . . . !

Quote
"John Hutchings" <jo...@datavis.com.au> wrote in message

news:3bcf3982_1@dnews...
Quote
> Mike,
> This works for me

> function PointInPolygonTest( x,y: Integer ;aList: Array of TPoint):
Boolean;

> // The code below is from Wm. Randolph Franklin <w...@ecse.rpi.edu>
> // with some minor modifications for speed.  It returns 1 for strictly
> // interior points, 0 for strictly exterior, and 0 or 1 for points on
> // the boundary.

> var L, I, J : Integer;

>   Function xp(aVal:Integer):Integer;
>   Begin
>     Result:= PPoint(@aList[aVal]).X;
>   end;

>   Function yp(aVal:Integer):Integer;
>   Begin
>     Result:= PPoint(@aList[aVal]).Y;
>   end;

> begin
>   Result:=False;
>   L:= Length(aList) ;
>   If L=0 then exit;
>   J:=L-1;
>   for I:=0 to L-1 do
>   begin
>     if ((((yp(I)<=y) and (y<yp(J))) OR
>          ((yp(J)<=y) and (y<yp(I)))) and
>         (x < (xp(J)-xp(I))*(y-yp(I))/(yp(J)-yp(I))+xp(I)))
>     then Result:=not Result;
>     J:=I;
>   end;
> end;

> John
> "Mike" <mikedown@*remove_this_bit*totalise.co.uk> wrote in message
> news:3bcf3315_2@dnews...
> > Hi,

> > Can anyone help be with detecting whether the screen coord that a user
has
> > clicked on lies within a defined polygon
> > (I`ll know all the screen coords of the points defining the polygon).
> > An algorithm would be good, or any links to useful techy sites.

> > Thanks,

> > Mike