Xref: utzoo comp.graphics:1811 comp.sys.ibm.pc:12467
Path: utzoo!mnetor!uunet!seismo!sundc!pitstop!sun!decwrl!labrea!aurora!amelia!ames!hao!gatech!purdue!i.cc.purdue.edu!j.cc.purdue.edu!pur-ee!beatyr
From: beatyr@pur-ee.UUCP (Robert Beaty)
Newsgroups: comp.graphics,comp.sys.ibm.pc
Subject: Re: COMPLICATED PROBLEM; ONLY INTELLIGENT PEOPLE SHOULD READ
Message-ID: <7626@pur-ee.UUCP>
Date: 26 Feb 88 12:00:01 GMT
References: <971@ut-emx.UUCP> <20533@amdcad.AMD.COM>
Reply-To: beatyr@pur-ee.UUCP (Robert Beaty)
Organization: Purdue University Engineering Computer Network
Lines: 67
Keywords: READ THIS ONLY IF YOUR IQ >>125

In article <20533@amdcad.AMD.COM> msprick@amdcad.UUCP (Rick Dorris) writes:
>In article <971@ut-emx.UUCP> jezebel@ut-emx.UUCP (Jim @ MAC@/) writes:
>>Have a nice one here:
>>Have a boundary defined on the screen. Boundary is composed of points
>>joined by lines... Now some random points are generated and I want to check
>>if a given point is within or outside the existing boundary.. Any algorithm for
>>this ? Is it at all possible ????
>>Jim
>
>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

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.

Let's define the points that define the boundary lines segments
as Si, 1 <= i <= N. Also, the unknown point is P. All of these are in
rectangular coordinates. Assign some reference origin to the system
and then compute the angle theta, between the horizontal axis and the
line segment between P and Si. You will now have N values of theta.
Add these up. If the point is inside the boundary region this sum
will be very close to 360 degrees - the only reason it will be off is
due to numerical inaccuracies in the trig functions.
If the point, P, is outside the region the sum will be zero (or very close).
Use a simple threashold of 180 degrees - >180 inside, <180 outside.

>Running with GKS....under Fortran...
>Mind-boggling for you ? If not, you are the guy/gal who has the
>solution to my problem.....
>Please respond.....
>Jim

In a formula:

	   N
	\----|                        /
	 \       -1 ( Si(y) - P(y) )  |  > 180  then INSIDE
	  \   tan   ----------------  {
	  /         ( Si(x) - P(x) )  |  < 180  then OUTSIDE
	 /                            \
	/----|
	  i=1

where:

	Si = ( Si(x), Si(y) )
	P = ( P(x), P(y) )

No problem ( I have used it before in a program ) I think it is a pretty
neat solution - And it doesn't use much time.

If you have any other questions about this method I am sure I can whip
up some FORTRAN code to do it in about 5 min., so let me know.

			Bob
----------
   ... ihnp4!pur-ee!beatyr      <- usenet
  ... beatyr@ee.ecn.purdue.edu  <- arpa-net
   ... beatyr@pur-ee.UUCP       <- UUCP
----------