Xref: utzoo comp.graphics:1878 comp.sys.ibm.pc:12725
Path: utzoo!mnetor!uunet!portal!cup.portal.com!William_Charles_Thibault
From: William_Charles_Thibault@cup.portal.com
Newsgroups: comp.graphics,comp.sys.ibm.pc
Subject: Re: COMPLICATED PROBLEM; ONLY INTELLIGENT PEOPLE SHOULD READ
Message-ID: <3634@cup.portal.com>
Date: 3 Mar 88 00:23:53 GMT
References: <971@ut-emx.UUCP> <867@bingvaxu.cc.binghamton.edu>
Organization: The Portal System (TM)
Lines: 13
XPortal-User-Id: 1.1001.3555


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

If a lot of "random points" are to be tested for inclusion in the region,
you might want to build a search structure for the boundary.  This requires
a preprocessing step, but can save time in the long run.  There are
good (optimal) techniques for convex polygons, but very little work
deals with concave ones.  One possibility is to use a 2D BSP tree
for the search structure. See the paper "Set Operations on Polyhedra
Using Binary Space Partitioning Trees,"  W. Thibault and B. Naylor,
Computer Graphics 21(4) (SIGGRAPH Proceedings), July 1987.