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
>