MathGroup Archive 2009

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

Search the Archive

Re: testing if a point is inside a polygon

  • To: mathgroup at smc.vnet.net
  • Subject: [mg96250] Re: [mg96189] testing if a point is inside a polygon
  • From: "David Park" <djmpark at comcast.net>
  • Date: Tue, 10 Feb 2009 05:51:14 -0500 (EST)
  • References: <23667197.1234176058052.JavaMail.root@m02>

Mitch,

Here is my attempt. The idea is to move around the polygon and add up the
angles made with the point. If the point is outside this will be zero. The
steps are basically:

1) Check if the point is one of the vertices of the polygon.
2) Add the first polygon point to the end of the list of points.
3) Subtract the test point from each of the polygon vertices.
4) Partition the points into pairs.
5) Rotate each pair so the first one lies along the x axis. (To prevent
crossing the branch line)
6) Find the ArcTan of the second point. This will have a sign.
7) Sum the angles and take the absolute value.
8) Test if this is zero or some multiple of 2\[Pi].

PointInsidePolygonQ::usage = 
  "PointInsidePolygonQ[point,polygon] will return True if the point \
is on the boundary or inside the polygon and False otherwise.";

PointInsidePolygonQ[point_, polygon_] :=
 Module[{work},
  work = If[Head[polygon] === Polygon, First[polygon], polygon];
  If[ \[Not] FreeQ[work, point], Return[True]];
  work = # - point & /@ Join[work, {First[work]}];
  work = Partition[work, 2, 1];
  work = RotationTransform[{First[#], {1, 0}}]@# & /@ work;
  work = Abs@Total[ArcTan @@ Last[#] & /@ work] // Chop // Rationalize;
  TrueQ[work != 0]
  ]

Here is a graphical test for a simple polygon:

testpoints = testpoints = RandomReal[{-9, 9}, {100, 2}];
polypoints = {{-1.856, 3.293}, {1.257, 
    2.635}, {2.395, -0.6587}, {-1.018, -2.455}, {-3.293, -0.05988}};
Graphics[
 {Lighter[Green, .8], Polygon[polypoints],
  AbsolutePointSize[4],
  {If[PointInsidePolygonQ[#, polypoints], Black, Red], Point[#]} & /@ 
   testpoints},
 PlotRange -> 10,
 Frame -> True]

Here is a test for a more complex polygon.

testpoints = testpoints = RandomReal[{-9, 9}, {100, 2}];
polypoints = {{-3.653, 5.329}, {0.2395, 6.168}, {-0.8982, 
    1.138}, {-0.6587, 1.138}, {5.569, 3.234}, {6.527, -2.036}, {1.677,
     0.479}, {-6.407, -1.976}, {-5.21, 2.635}, {1.856, -3.713}};
Graphics[
 {Lighter[Green, .8], Polygon[polypoints],
  AbsolutePointSize[4],
  {If[PointInsidePolygonQ[#, Polygon[polypoints]], Black, Red], 
     Point[#]} & /@ testpoints},
 PlotRange -> 10,
 Frame -> True]

There might be simpler methods.

David Park
djmpark at comcast.net
http://home.comcast.net/~djmpark/  


From: Mitch Murphy [mailto:mitch at lemma.ca] 


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: Problem importing HTML with Mathematica
  • 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