Determine if a point is in a polygon

[Andrew Coulton]

Is there a function that will take a set of points defining the vertices
of a polygon, and another point, and return a value indicating if the
point is inside or outside the polygon? Or do I have to write one?

Cheers,

Andrew Coulton

[Bjørge Sæther]

<<Andrew:

Is there a function that will take a set of points defining the vertices
of a polygon, and another point, and return a value indicating if the
point is inside or outside the polygon? Or do I have to write one?>>

Hi !

Check out the following WinAPI calls:

CreatePolygonRgn
PtInRgn

--

Bjoerge

[Jim Hargis]

The "builtin" point in polygon is in Win32 "PointinRegion", assuming your
poly is converted to a region.

something like this should work.

var Rgn1:hRgn;//handles to the regions
var Points:Array[0..100]of POINTS;
begin
...
Rgn1:=CREATEPOLYGONRGN(Points,npts,ALTERNATE);
RESULT:=PTINREGION( rgn1,p.x,p.y);
...
end;

Of course, you wouldn't want to do this with a lot of polygons, but you can
with a lot of points, because CREATEPOLYGONRGN is slow.

Point in Polygon with Delphi is faster. See attached.

{===================================================}
{Point in simple CONVEX polygon}
function PointInPoly (const p0: PointType; const apoly: PolygonType):
BOOLEAN;
{Collected Algorithsm from ACM, Algo. 112, corrected and optimized}
{use half-plane test optimized for convex polygon and standard data
structures}
{given points x[i],y[i], i=1..n are the vertices of a simple closed
polygon }
{and x0,y0 is a point not on any side of the polygon, }
{then determine whether x0,y0 lies in the interior of the polygon}

{ Timings:
7/7/99 2.27 microseconds per test for 4-point polygon on a P166.}
var
i: INTEGER;
p1, p2: pointtype;
{given points x[i],y[i], i=1..n are the vertices of a simple closed
polygon }
{and x0,y0 is a point not on any side of the polygon, }
{then determine whether x0,y0 lies in the interior of the polygon}
begin
RESULT:=false;// nint := 0;
with apoly do {7/3/96}
begin {points[0..npoints-1]}
p2 := points[npoints-1]; {start at last point and avoid recalc of
subscript}
for i := 0 to npoints-1 do {2/6/99}
begin { each side}
p1 := p2; {get next side; p1==p[i-1], p2==p[i]}
p2:=points[i+1];{8/8/98}
{IF ident(y0 <= y[i], y0 > y[i + 1]) THEN y0 is overlapped by y[i],y[i+1]
where boolean operator IDENT(a,b) = true if and only if a,b are both true
or both false.
Thus, IDENT(a,b)== NOT(a XOR b)==(NOT a)XOR(NOT b),
so, IDENT((y0 <= y[i], y0 > y[i + 1])==(y0 > y[i])XOR(y0 <= y[i + 1]),
so...}
if ((p0.x >= p1.x)XOR( p0.x < p2.x)) then{check if intersection is
with y axis}
begin //split y
{check if + or - axis}
if ((p1.y-p0.y)*1.0*(p2.x-p1.x))>((p1.x-p0.x)*1.0*(p2.y-p1.y)) then
begin {+y}
RESULT:=NOT RESULT;{if CONVEXpolygon, can have only 2
intersects}
IF RESULT then continue else exit {DROP THIS LINE IF NOT CONVEX}
end {intersect axis}
else ;{-y}
end {split axis}
else ;{miss axis}
end;{for each side}
end;{with}
end;

Andrew Coulton wrote in message <3787647F...@proscenia.clara.net>...

>Is there a function that will take a set of points defining the vertices
>of a polygon, and another point, and return a value indicating if the
>point is inside or outside the polygon? Or do I have to write one?
>

>Cheers,
>
>Andrew Coulton
>
>

[AlanGLLoyd]

In article <I5Th3.1948$pF3.2...@news.uswest.net>, "Jim Hargis"
<jha...@uswest.net> writes:

>{Point in simple CONVEX polygon}
>function PointInPoly (const p0: PointType; const apoly: PolygonType):
>BOOLEAN;
>{Collected Algorithsm from ACM, Algo. 112, corrected and optimized}
>{use half-plane test optimized for convex polygon and standard data
>structures}
>{given points x[i],y[i], i=1..n are the vertices of a simple closed
>polygon }
>{and x0,y0 is a point not on any side of the polygon, }
>{then determine whether x0,y0 lies in the interior of the polygon}
>

<snip a lot of clever code>

> end;{with}
>end;
>

Is this an implementation of the "Alternative to PtInRegion()" which is in
Win32.hlp as :-
"based on an algorithm presented in "Algorithms" by Robert Sedgewick,
Addison-Wesley, 1988, 2nd ed. ISBN 0201066734. The algorithm is on p.354, in
the section "Inclusion in a Polygon" in the chapter "Elementary Geometric
Methods." It is also discussed in "Computer Graphics" by Foley, van Dam, Feiner
and Hughes, Addison-Wesley, 1990, 2nd ed. ISBN 0201121107, chapter 2, section
1, p.34."

The algorithm determines :-
" the number of times an imaginary line drawn from the point you want to test
crosses edges of your polygon. If the line crosses edges an even number of
times, the point is outside the polygon. If it crosses an odd number of times
it is inside. The line is drawn horizontally from the point to the right."

Alan Lloyd
alang...@aol.com