UD138985@NDSUVM1.BITNET (01/11/88)
Hello there...
I would like to know if anyone out there has a fool proof method
(algorithm) for determining whether or not a point is inside of a polygon.
Every time I think I've got a way to do it, I think up a polygon that screws
it up. Could someone send me either a method for doing so, or a some
references on how to do it?
Thanks in advance for any replies.
Bob
Bitnet: UD138985 at NDSUVM1bsmith@lands.ced.berkeley.edu (Brian Smith) (01/13/88)
I had a hell-of-a-time finding it, but the algorithm for testing if a point is in a polygon can be found in Robert Sedgewick, "Algorithms", Addison-Wesley, 1984, pp 315-317. The basic idea is to draw a line from the point to infinity and count how many intersections it makes with the polygon. If it crosses an odd number of times, then it's inside, otherwise it's outside. Usually a horizontal line is chosen for efficiency, and intersections of the line with vertices have to be handled specially. Brian Smith
saponara@batcomputer.tn.cornell.edu (John Saponara) (01/13/88)
In article <22564@ucbvax.BERKELEY.EDU> bsmith@postgres.berkeley.edu (Brian Smith) writes: >I had a hell-of-a-time finding it, but the algorithm for testing >if a point is in a polygon can be found in > >Robert Sedgewick, "Algorithms", Addison-Wesley, 1984, pp 315-317. > >The basic idea is to draw a line from the point to infinity and >count how many intersections it makes with the polygon. If it >crosses an odd number of times, then it's inside, otherwise it's >outside. Usually a horizontal line is chosen for efficiency, and >intersections of the line with vertices have to be handled >specially. > > Brian Smith Thanks, I've been wanting a source to cite for this procedure. Since people already in the know may not have plowed through my longwinded explanation of basically the same algorithm, which I posted yesterday, I thought I'd point out the nice addition to Sedgewick's explanation which makes all the "vertex on the testing ray" special cases go away. We used the basic algorithm outlined by Sedgewick for years at Cornell and then at 3D/Eye. About two years ago I found yet another bug in this darn routine, one of those "if the first vertex starts on the ray and a second vertex touches the ray when..." type obscure cases that come up once in a million polygons. (Berlin talks about similar problems in "Efficiency Considerations in Image Synthesis" SIGGRAPH Course Notes, Vol. 11, 1985. By the way, this article gives three methods for doing point/polygon comparisons. Avoid his method, though - it is slower. Sedgewick with the modification outlined below is the way to go). After some frustration with getting rid of all those special cases, I happened upon a simplification which is very useful. Anyway, the modification is that the ray traced along the horizontal axis should not be considered a set of points at all, but rather is simply a dividing line between zero and the negative numbers along the Y axis. This change leads to a wonderful simplification: there are now no vertices which are intersected by the ray, i.e. no special cases! Now all polygon vertices are either above or below this new sort of ray (which is really just a boundary instead of a true ray). This change made for faster, simpler, and correct code. Try it - it works! Eric Haines, 3D/Eye Inc (borrowing John Saponara's account)
dambrose@drivax.UUCP (David Ambrose) (01/14/88)
In article <506UD138985@NDSUVM1> UD138985@NDSUVM1.BITNET writes: > I would like to know if anyone out there has a fool proof method >(algorithm) for determining whether or not a point is inside of a polygon. You could use the tried and true "parity" algorithm. Draw a line from the point to "infinity". Find all the intersections of this line with the polygon's edges and count them. If the number is odd, the point is inside; even, it's outside. I don't have any referrences at hand but may be able to provide them if badgered. -- ______________________________________________________________________________ David L. Ambrose, -- Digital Research, Inc ...!amdahl!drivax!dambrose DISCLAIMER: Don't blame DRI. They wouldn't approve of this anyway. r}ix NO CARRIER
tompkins@ttidca.TTI.COM (Pete Tompkins) (01/21/88)
In article <2932@drivax.UUCP> dambrose@drivax.UUCP (David Ambrose) writes: >In article <506UD138985@NDSUVM1> UD138985@NDSUVM1.BITNET writes: >> I would like to know if anyone out there has a fool proof method >>(algorithm) for determining whether or not a point is inside of a polygon. > > You could use the tried and true "parity" algorithm. Draw a >line from the point to "infinity". Find all the intersections of this >line with the polygon's edges and count them. If the number is odd, >the point is inside; even, it's outside. If you hit a vertex, you need to consider the two adjacent vertices: if they are on the same side of your line, do not count this as a transition; if they are on opposite side, count it. This is most easily done with a horizontal (or vertical) line. You must compare the y-coordinates of the adjacent vertices with that of the line. Only if one vertex is greater than the line and the other is less than the line, should this count as a transition (of course, using x-coordinates for a vertical line). -- *Pete Tompkins *Citicorp/TTI *Santa Monica, CA *Path:{trwrb|philabs|csun|psivax}!ttidca!tompkins or tompkins@ttidca.tti.com *