Xref: utzoo comp.graphics:1797 comp.sys.ibm.pc:12412
Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!lll-tis!ames!ll-xn!husc6!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: <21223@bbn.COM>
Date: 25 Feb 88 19:15:58 GMT
References: <971@ut-emx.UUCP> <210@geza.SW.MCC.COM>
Sender: news@bbn.COM
Reply-To: cosell@BBN.COM (Bernie Cosell)
Organization: Bolt Beranek and Newman Inc., Cambridge MA
Lines: 29

In article <210@geza.SW.MCC.COM> begeman@geza.SW.MCC.COM (Michael Begeman) writes:
>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..
>
>This is a simple variation of the "convex hull" problem.  The C-H problem
>involves finding, for a set of points, that subset which when connected
>by line segments encloses the remaining points (you can think of this as
>playing connect-the-dot around the outer edge).

  Sorry, no cigar I think.  What if the line segments give you a non-convex
  shape?  For convex shapes the problem is pretty easy (the only interesting
  part is figuring out tricks to make it be quickly-calculable).  One thing
  that comes to mind quickly for arbitrary (!!) regions is to find a point
  *known* to be outside the region and then take the line segment from the
  point-being-tested to the known-outside-point.  Now check how many
  region-boundary segments this line segment intersects.  If the number is
  odd, then the point is inside the region, if even it is outside the region.
  (if you handle "intesection" properly, you can just pick an endpoint of one
  of the region-boundary lines as the known-outside point).  also note that
  this trick (the parity of the number of intersections) works pretty much no
  matter WHAT the boundary of the region is (e.g., if you had the boundary
  built up of splines, this'd STILL work, although the did-it-intersect
  question would probably be harder to figure out)
   __
  /  )                              Bernie Cosell
 /--<  _  __  __   o _              BBN Labs, Cambridge, MA 02238
/___/_(<_/ (_/) )_(_(<_             cosell@bbn.com