       Re: testing if a point is inside a polygon

• To: mathgroup at smc.vnet.net
• Subject: [mg96259] Re: testing if a point is inside a polygon
• From: dh <dh at metrohm.com>
• Date: Tue, 10 Feb 2009 05:52:54 -0500 (EST)
• References: <gmp0mt\$btn\$1@smc.vnet.net>

Hi Mitch,

To write a routines that checks if a point is inside a polygon you must

realize that if you walk around the polygon you see a inner point

always on the same side. This is false for a outside point. Therefore,

the test is to check if the point in question: p0 is always on the same

side of the polygon sides.

Assume {p1,p1,..} are the polygon points, arrange in a definite order

(clockwise or anti-clockwise). How can we check on which side of  {pi+1,

pi}  p0 is? We may get a vector perpendicular to the side by rotating by

Pi/2: {{0,1},{-1,0}}.(pi+1 - pi). If we take the dot product with (p0

-pi) the sign will tell us the side. Here is an example:

pts = {{0, 0}, {1, 0}, {1, 1}, {0, 1}};

p0 = {0.5, 0.5};

sides= Subtract @@ # & /@ Partition[Append[pts, pts[]], 2, 1];

perp= {{0,1},{-1,0}}.#& /@ sides;

Equal @@ Sign @ MapThread[Dot, {p0 - # & /@ pts, perp}]

The third lines calculates (pi+1 - pi), note that we added to first

point to the end of the list to close the polygon. The fourth turns each

vector by Pi/2. The fifth calculates p0-pi = {p0 - # & /@ pts and takes

the Dot product of corresponding vectors. Finally it takes the sign and

checks if all signs are the same.

hope this helps, Daniel

Mitch Murphy wrote:

> is there a way to test whether a point is inside a polygon? ie.

>

> 	PointInsidePolygonQ[point_,polygon_] -> True or False

>

> i'm trying to do something like ...

>

>

> to create what would be called a "clipping mask" in photoshop.

>

> cheers,

> Mitch

>

• Prev by Date: Re: FindFit & NIntegrate
• Next by Date: Re: newbie: explicit function works, "function object" doesn't
• Previous by thread: Re: testing if a point is inside a polygon
• Next by thread: Re: testing if a point is inside a polygon