MathGroup Archive 2000

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

Search the Archive

Re: Point inside a plygon?

on 9/17/00 5:47 PM, Adriano Moreira at adriano at 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

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:

Chop[NIntegrate[f[z], {z, -1 - 2I, 5 - 2I, 5 + 4I, -5 + 4I, -1 - 2I}]]
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

Line[{{-1, -2}, {2, -2}, {2, 4}, {-5, 4}, {-1, -2}}]

You can see the polygon and the point by evaluating:

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:

Chop[NIntegrate[f[z], {z, -1 - 2I, 2 - 2I, 2 + 4I, -5 + 4I, -1 - 2I}]]
   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.

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:

  • Prev by Date: Re: Random spherical troubles
  • Next by Date: good intro book
  • Previous by thread: RE: Point inside a plygon?
  • Next by thread: Re: Point inside a plygon?