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