Re: Point inside a plygon?

*To*: mathgroup at smc.vnet.net*Subject*: [mg25299] Re: [mg25239] Point inside a plygon?*From*: Andrzej Kozlowski <andrzej at tuins.ac.jp>*Date*: Tue, 19 Sep 2000 03:45:21 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

on 9/17/00 5:47 PM, Adriano Moreira at adriano at dsi.uminho.pt wrote: > Hi, > > I need a routine to check if a point is inside or outside a polygon > (simple polygon non self-intersecting). > Any help appreciated. > > Adriano Moreira > > There is actually a very simple way (which should barring unexpected bugs in Mathematica). To demonstrate it let's look at two examples. Suppose we take the point (3,2) and the polygon Line[{{-1, -2}, {5, -2}, {5, 4}, {-5, 4}, {-1, -2}}]}]. The point is inside the polygon, as you can see by evaluating: Show[Graphics[{RGBColor[1, 0, 0], Point[{3, 2}], RGBColor[0, 0, 1], Line[{{-1, -2}, {5, -2}, {5, 4}, {-5, 4}, {-1, -2}}]}]] We shall think of all the points as points in the complex plane. Now define the complex function In[2]:= f[z_] := 1/(z - w) All we need to do is to compute the line integral of f along the polygon. If the point w is inside the polygon, as it is in this case, we shoudl get the answer 2Pi, otherwise the answer will be 0. You should use NIntegrate because Integrate is unreliable in such cases. There are some problems with NIntegrate, 8as we shall see) but they don't seem to be serious. Integrating around the polygon we get: In[3]:= Chop[NIntegrate[f[z], {z, -1 - 2I, 5 - 2I, 5 + 4I, -5 + 4I, -1 - 2I}]] Out[3]= 6.28319 I You need Chop, otherwise you will get a tiny real part (but it doesn't really matter anyway matter, since all we care is to determine if the answer is 0 or not). Now let us change the polygon so that the point lies outside. Let's take the polygon Line[{{-1, -2}, {2, -2}, {2, 4}, {-5, 4}, {-1, -2}}] You can see the polygon and the point by evaluating: In[4]:= Show[Graphics[{RGBColor[1, 0, 0], Point[{3, 2}], RGBColor[0, 0, 1], Line[{{-1, -2}, {2, -2}, {2, 4}, {-5, 4}, {-1, -2}}]}]] Okay, this time we again compute the contour integral: In[5]:= Chop[NIntegrate[f[z], {z, -1 - 2I, 2 - 2I, 2 + 4I, -5 + 4I, -1 - 2I}]] NIntegrate::ploss: Numerical integration stopping due to loss of precision. Achieved neither the requested PrecisionGoal nor AccuracyGoal; suspect one of the following: highly oscillatory integrand or the true value of the integral is 0. If your integrand is oscillatory try using the option Method->Oscillatory in NIntegrate. Out[5]= 0 You see that we got the answer 0, which confirms that the point lies inside (The warning message should not worry you, NIntegrate always produces it if the answer is 0.) -- Andrzej Kozlowski Toyama International University, JAPAN For Mathematica related links and resources try: <http://www.sstreams.com/Mathematica/>