Xref: utzoo comp.graphics:1814 comp.sys.ibm.pc:12471
Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!lll-tis!ames!ll-xn!mit-eddie!bbn!bbn.com!cosell
From: cosell@bbn.com (Bernie Cosell)
Newsgroups: comp.graphics,comp.sys.ibm.pc
Subject: Re: COMPLICATED PROBLEM; ONLY INTELLIGENT PEOPLE SHOULD READ
Message-ID: <21274@bbn.COM>
Date: 26 Feb 88 19:37:38 GMT
References: <971@ut-emx.UUCP> <20533@amdcad.AMD.COM> <7626@pur-ee.UUCP>
Sender: news@bbn.COM
Reply-To: cosell@cosell.bbn.com.BBN.COM (Bernie Cosell)
Organization: Bolt Beranek and Newman Inc., Cambridge MA
Lines: 41
Keywords: READ THIS ONLY IF YOUR IQ >>125

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.
>
>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.
...
>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.

"superior" is clearly in the eye of the beholder.  Doing line intersections
is a trivial and VERY quick affair that can be done easily in fixed point.
Just _thinking_ about calling a trig function, much less calculating any
significant number of them is SURELY going to eat up beau coup CPU time, AND
require that you be working in floating point (another invitation for many
machines to go into snail-mode).

I had worked on a sort-of similar line of reasoning but abandoned it because
I couldn't figure out how to make it fast enough to be practically
calculable.  Also -- I think you got the algorithm wrong (or else I misread
it).  Let the point-in-question, P, be at the original, and let the X-axis be
the reference axis.  Now assume that the region-in-question is a simple
square, ABCD.  Assume that the square is a long distance off up the
Y axis.  The P-A, P-B ... angles wrt to the X axis will all be very close
to 90 degress, and so the sum of the angles will be close to 360.  What WILL
work (but is even HARDER to calculate) is to compute the angle subtended by
each segment of the boundary (with the angle being negative if the angle is
subtended "the other way").  *THEN* you get 360 or 0. (in your original
terminology, instead of measuring Si-P-xaxis, you measure Si-P-Si+1).  Still
MUCH too hard to calculate, I think.
   __
  /  )                              Bernie Cosell
 /--<  _  __  __   o _              BBN Labs, Cambridge, MA 02238
/___/_(<_/ (_/) )_(_(<_             cosell@bbn.com