Xref: utzoo comp.graphics:1835 comp.sys.ibm.pc:12546
Path: utzoo!mnetor!uunet!seismo!sundc!pitstop!sun!decwrl!decvax!mcnc!gatech!bloom-beacon!athena.mit.edu!tada
From: tada@athena.mit.edu (Michael Zehr)
Newsgroups: comp.graphics,comp.sys.ibm.pc
Subject: Re: COMPLICATED PROBLEM; ONLY INTELLIGENT PEOPLE SHOULD READ
Message-ID: <3320@bloom-beacon.MIT.EDU>
Date: 28 Feb 88 16:48:58 GMT
References: <971@ut-emx.UUCP> <20533@amdcad.AMD.COM> <7626@pur-ee.UUCP>
Sender: daemon@bloom-beacon.MIT.EDU
Reply-To: tada@athena.mit.edu (Michael Zehr)
Organization: Massachusetts Institute of Technology
Lines: 46
Keywords: READ THIS ONLY IF YOUR IQ >>125



In article <971@ut-emx.UUCP> jezebel@ut-emx.UUCP (Jim @ MAC@/) writes:
> [need algorithm to determine point-inside-polygon]

In article <20533@amdcad.AMD.COM> msprick@amdcad.UUCP (Rick Dorris) writes:
>Well not to say that I'm intelligent, but here's a solution.
>You can figure if the point is within the boundary by drawing
>a line from the point to the edge of the screen.  Count how many
>times this line crosses your boundary.  If odd, the point is inside
>the boundary, if even, it is not.  If I understood your problem 
>correctly, this should work.  How to actually program this--- well
>I told you that I wasn't that intelligent!
>
>Rick

In article <7626@pur-ee.UUCP> beatyr@pur-ee.UUCP (Robert Beaty) writes:
>I have seen this type of algorithm before and the one I thought up
>in an afternoon is FAR surperior and vastly simpler to code up.
>[describes ...]
>In a formula:
>
>	   N
>	\----|                        /
>	 \       -1 ( Si(y) - P(y) )  |  > 180  then INSIDE
>	  \   tan   ----------------  {
>	  /         ( Si(x) - P(x) )  |  < 180  then OUTSIDE
>	 /                            \
>	/----|
>	  i=1


"FAR superior" ? In what way? You want to do a divide and a tan-1 for each
edge or the polygon? And need to sum all of them before having an answer?

The method I use in some graphics programs requires a compare and an
xor for each edge of the polygon, and 2 multiplies (total, not for each
edge).  (And it works for concave as well, but might require more multiplies
in that case.)




-------
michael j zehr
"My opinions are my own ... as is my spelling."