MathGroup Archive 2009

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: testing if a point is inside a polygon

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

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


  • 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