Xref: utzoo comp.graphics:1805 comp.sys.ibm.pc:12456
Path: utzoo!mnetor!uunet!seismo!sundc!pitstop!sun!decwrl!labrea!aurora!eos!ames!elroy!cit-vax!cit-vlsi!flaig
From: flaig@cit-vlsi.Caltech.Edu (Charles M. Flaig)
Newsgroups: comp.graphics,comp.sys.ibm.pc
Subject: Re: COMPLICATED PROBLEM; ONLY INTELLIGENT PEOPLE SHOULD READ
Message-ID: <5569@cit-vax.Caltech.Edu>
Date: 26 Feb 88 00:49:39 GMT
References: <971@ut-emx.UUCP>
Sender: news@cit-vax.Caltech.Edu
Reply-To: flaig@cit-vlsi.UUCP (Charles M. Flaig)
Organization: California Institute of Technology
Lines: 34
Keywords: READ THIS ONLY IF YOUR IQ >>125

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

Maybe I've missed something (and have to get my IQ rechecked :-), but can't
you just:

1) Extend a line segment from the point to infinity (or to any other point
   known to be outside the boundary).

2) Calculate intersections between this line segment and those making up the
   boundary.  It does not count as an intersection if it is a parallel line
   (overlaps). If the intersection is at a vertex, you count it as +1/2 
   intersection if the line from the vertex is to the "right" of your test
   line, and -1/2 if it is to the "left".

3) Total the number of intersections.  Odd total => inside, even => outside.
   Of course if your point is ON a segment, then it is ON the boundary.

Seems simple enough.  But I'll put on my handy helmet in case I'm wrong....
______________________________________________________________________________
  ___   ,               ,                                           ,;,;;;,
 /   Y /|              /|              Charles Flaig                ;/@-@\;
|      |/     __, ,__  |/              flaig@csvax.caltech.edu       | ^ |
|      /^\   /  | | |  /  /\  /\                                      \=/ 
 \____/|  \_/|_/\_/ \_/ \_\/_/_/_/     "What, you think they PAY me for this?"