Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!lll-tis!ames!ll-xn!husc6!bbn!rochester!PT.CS.CMU.EDU!andrew.cmu.edu!jv0l+
From: jv0l+@andrew.cmu.edu (Justin Chris Vallon)
Newsgroups: comp.graphics
Subject: Re: COMPLICATED PROBLEM; ONLY INTELLIGENT PEOPLE SHOULD READ
Message-ID: <IW97NWy00WIAQ6c0Bc@andrew.cmu.edu>
Date: 25 Feb 88 19:15:46 GMT
Organization: Carnegie Mellon University
Lines: 41
In-Reply-To: <971@ut-emx.UUCP>



In <971@ut-emx.UUCP>, Jim asks:
>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 ????

If the boundaries form a rectangle, the solution is trivial.  Given point P 
and rectangle R, the point is in the rectangle if:
(P.horiz >= R.left) and (P.horiz < R.right) and (P.vert >= R.top) and (P.vert 
< R.bottom)
But you probably aren't asking that.

If your boundary is a polygon, you need a point-in-a-polygon algorithm.  One 
solution is: count the number of lines in your boundary which pass directly 
above the given point.  If this count is odd, the point is in the polygon.  A 
point P is "under" the line L (with endpoints P1 and P2, including P1, but not 
including the point P2), if:

(P1.horiz <= P.horiz) and (P.horiz < P2.horiz) and (P.vert >= P1.vert + 
(P2.vert - P1.vert)/(P2.horiz - P1.horiz)*(P.horiz - P1.horiz))

The second inequality test is, and should be, "<", not "<=", since I stated 
that P2 is an open boundary.

There is a special case for vertical lines (where P2.horiz - P1.horiz = 0).  
You can ignore all vertical lines in your calculations.  Why?  Because it 
works.  Mathematically, there does exist some y for which (P.horiz, y) is in 
the line L, which should imply that the point P is "under" the line L, but an 
algorithm using this fact doesn't work.  Maybe somebody out in net-land could 
give some more insight.

Note also that the polygon method works for rectangles as well.

I am using a purely mathematical sense of the word line.  Ie: A line which is 
drawn from (0,0) to (5,0) contains 5 pixels, not 6; the rectangle (0, 0), (10, 
10) encloses the points (0..9, 0..9) but not any (10, y) or (x, 10).

Hope this helps and doesn't confuse matters more...

-Justin