Xref: utzoo comp.graphics:1841 comp.sys.ibm.pc:12585
Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!ames!hao!gatech!udel!rochester!cornell!batcomputer!madden
From: madden@batcomputer.tn.cornell.edu (Pat Madden)
Newsgroups: comp.graphics,comp.sys.ibm.pc
Subject: Re: COMPLICATED PROBLEM; ONLY INTELLIGENT PEOPLE SHOULD READ
Message-ID: <3862@batcomputer.tn.cornell.edu>
Date: 25 Feb 88 22:11:04 GMT
References: <971@ut-emx.UUCP>
Reply-To: madden@tcgould.tn.cornell.edu (Pat Madden)
Organization: Cornell Theory Center, Cornell University, Ithaca NY
Lines: 40
Keywords: READ THIS ONLY IF YOUR IQ >>125

In article <971@ut-emx.UUCP> jezebel@ut-emx.UUCP (Jim @ MAC@/) writes:
>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 ????

Yes, and luckily enough, it's not too difficult to implement.  You do
need a reference point which you know to be either inside or outside
the closed region bounded by the points/lines (a point off the screen will
do nicely).  Call the reference point R.

Given a list E(1..n) of n edges, and the point P being tested, perform
the following:
  1. Count = 0
  2. For each i, 1 <= i <= n, DO
  3.   IF segment PR intersects edge E(i) THEN increment Count.
  4. END
  5. IF Count is even, then P is on the same side of boundary as R
     ELSE P is on other side of boundary.


Here's a short explanation/demonstration to justify this algorithm:

Draw an arbitrary boundary on paper.  Draw two points at any locations,
and slowly sketch a line from one point to the other.  Whenever you cross a
boundary, you must be either going into or leaving from the bounded
area, since you can not cross a boundary and still be on the same side.
So, if your start point was outside the boundary, the first crossing
would bring you inside, the next one out again, and so on, until you
get to the endpoint; hence the even/odd condition in step 5 above.

Note that this algorithm will work for any shaped region, not necessarily
convex.

I hope this helps.

--Pat
-- 
==========================================================================
Pat Madden
{cmcl2, shasta, uw-beaver, rochester}!cornell!batcomputer!madden
madden@batcomputer.tn.cornell.edu