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/>