Path: utzoo!utgpu!water!watmath!clyde!rutgers!mit-eddie!husc6!linus!philabs!ttidca!tompkins
From: tompkins@ttidca.TTI.COM (Pete Tompkins)
Newsgroups: comp.graphics
Subject: Re: polygons and points
Message-ID: <1703@ttidca.TTI.COM>
Date: 20 Jan 88 16:04:37 GMT
References: <506UD138985@NDSUVM1> <2932@drivax.UUCP>
Organization: Citicorp/TTI, Santa Monica
Lines: 23
In-reply-to: dambrose@drivax.UUCP's message of 13 Jan 88 19:58:57 GMT
Posting-Front-End: GNU Emacs 18.47.10 of Sat Sep 12 1987 on ttidca (berkeley-unix)


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 *