The question was: how to tell if a point is inside a polygon. The first
suggestion may be informative, but it's wrong -- read the followup. A
right answer appears later.
==============================================================================
From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Need Algorithm - Is point (x,y) inside the polygon?
Date: 29 Jul 1995 04:17:24 GMT
In article <3vau44$bdb@service1.uky.edu>,
Harold G Peach Jr wrote:
>I am looking for an algorithm to test whether a point (defined by
>two integers -- x and y) is inside a polygon, given the points that
>makeup the polygon's vertices. Practically, the algorithm would
>need to work with polygons having up to 30 or so vertices.
A point P lies inside the polygon P0 P1 P2 ... Pn P0 iff the
area of the polygon is the sum of the areas of the two polygons
Pn P0 P Pn (a triangle) and P P0 P1 P2 ... Pn P.
Now you just need to know that area can be computed from the vertices's
coordinates Pi = ( x[i], y[i] ):
Area = | Sum (x[i] y[i+1] - x[i+1] y[i]) |/2
(Actually it's the absolute values which make the game interesting --
without them you'd always have Sum1 = Sum2 + Sum3. So if you really
need to process minimal information, I guess all you need to do is
compare the _signs_ of the two interior 'areas'; the area of the whole
polygon need not be considered.)
dave
==============================================================================
From: rusin@washington.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Need Algorithm - Is point (x,y) inside the polygon?
Date: 2 Aug 1995 05:10:22 GMT
I goofed.
Harold G Peach Jr wrote in asking for an algorithm to
determine whether a given point lay inside a given polygon. I suggested one
which began:
>A point P lies inside the polygon P0 P1 P2 ... Pn P0 iff the
>area of the polygon is the sum of the areas of the two polygons
>Pn P0 P Pn (a triangle) and P P0 P1 P2 ... Pn P.
to which David Ullrich responded
> Are you sure about that? (Does "polygon" mean "convex polygon"?)
I have to say I missed something here: the second figure I said to
trace need not be a polygon! (Try points (0,0), (2,0), (2,2), and (0,2), with
P=(3,1).) _If_ the second region is a polygon, that is, if the line segments
P P0 and Pn P don't intersect the original polygon, then the argument is
OK, and does not require convexity.
Indeed, the argument I used isn't really about areas at all. Oh, sure, I
mentioned area but I interpreted this to mean the integral of 1 dx dy over
the interior of the polygon, and then I used Green's theorem to express
this as the integral of the one-form x dy over the boundary of the
polygon (traversed counterclockwise, i.e., with the interior on the
left of the curve). If (x(t), y(t)) is a parameterization of the
curve, this is just the integral of x(t)*y'(t) dt. For a polygon one
may use piecewise linear parameterizations, which leads to the
determinant-looking formula I posted. The presence of the absolute
value signs was just so I needn't worry about the direction of the
parameterization.
(By the way, I used this Green's Theorem approach to compute the area in the
separate "Baseball" thread, too.)
It's clear that the line integrals over the two paths I indicated add
to the line integral over the original polygon -- two pairs of paths
connecting to P will cancel out. So here's why the method I posted works.
If P is outside the polygon, then when we travese, say, the edge P P0
we will keep the interiors of _both_ new sets on the same side of us,
meaning that both line integrals are computing the (positive) area, or
both are computing its negative. If instead P is inside the polgon, as
we traverse this edge we will have the two net sets on opposite sides
of the edge; thus one line integral is computing an area and the other is
computing the negative of the area. So we just compare signs of the two
line integrals, and make the right conclusion.
I now have to concede a difficulty: that the last curve I said to create
need not be simple. When it does self-intersect, the concept of
"interior" is no longer well defined. Sure, the line integral may be
thought of as computing some kind of signed area, but then it's not clear
how to interpret the result of taking the absolute value of this; that is,
there is no way to use the sign of the line integral as an indicator to
be used in a decision algorithm.
Incidentally, even if all the pieces _do_ turn out to be polygons, the
method I proposed is a little unstable numerically. You see, the
result of the line integral calculation may also be viewed as taking
the sum of signed areas of oriented rectangles (those joining the
origin to consecutive sides of the polygon). The sign of the sum is
what is of interest, but of course it is difficult to judge accurately
the sign of a sum of large terms of both signs. This condition can be
ameliorated by translating the polygons so that the origin is in or
near the polygon (for example, by subtracting the average of the
vertices). If someone still wishes to pursue this method, I can
clarify the details of this improvement.
For my penance I propose the standard topologist's test for inside and
outside. Choose any ray based at P and count the number of
polygon edge segments the ray crosses. If the number is odd, P is inside;
if even, P is outside. (It is possible to check for a crossing by checking
the signs of a few low-degree poynomials in the coefficients of the vertices).
Of course one must be careful if the ray crosses at a vertex.
Again, my apologies for my oversight.
dave
==============================================================================
From: rochel@bre.co.uk ()
Newsgroups: sci.math
Subject: Re: Need Algorithm - Is point (x,y) inside the polygon?
Date: 3 Aug 1995 10:25:00 GMT
...
Here's a simple algorithm based on the concept of winding number.
Think of the polygon and the point as being in the complex plane.
w.l.o.g. assume the point is at the origin (subtract it from all of the vertices
of the polygon).
List the arguments of all of the points of the polygon: a(0),...a(n).
Add up the angles subtended by each of the sides of the polygon: a(0)-a(1),
.. a(n)-a(0) (mod 2*pi) with these angles being taken in the range (-pi, pi).
If the answer is non-zero, the point is inside the polygon.
Liam Roche