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[[1]]], 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 ... > > ListContourPlot[table,RegionFunction->CountryData["Canada","Polygon"]] > > to create what would be called a "clipping mask" in photoshop. > > cheers, > Mitch >