Xref: utzoo comp.graphics:1891 comp.sys.ibm.pc:12811
Path: utzoo!mnetor!uunet!wucs1!wucs2!posdamer
From: posdamer@wucs2.UUCP (Jeff Posdamer)
Newsgroups: comp.graphics,comp.sys.ibm.pc
Subject: Re: COMPLICATED PROBLEM; ONLY INTELLIGENT PEOPLE SHOULD READ
Message-ID: <794@wucs2.UUCP>
Date: 4 Mar 88 14:46:50 GMT
References: <971@ut-emx.UUCP> <867@bingvaxu.cc.binghamton.edu> <3634@cup.portal.com>
Organization: Washington University, St. Louis
Lines: 38
Summary: Re:point in polygon

In article <3634@cup.portal.com>, William_Charles_Thibault@cup.portal.com 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.. 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.
I hate to continue beating a dead and decaying horse BUT...

Preparata and Shanos, Computational Geometry:An Introduction, Springer-
		Verlag, 1985

Mehlhorn, Multi-dimensional Searching and Computational Geometry, Springer_
		Verlag, 1984

Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987

are three good places to start looking at problems like this. 
The work has been done on these algorithms!!
With preprocessing, point in polygon can be done O(log n).
If computer science ever amounts to anything, we better start learning our
own research results


		Jeff Posdamer

-- 
Jeff Posdamershington University, St. Louis, MO, (314) 889-6147
UUCP:		posdamer@wucs1.UUCP   or   ...!{ihnp4,seismo}!wucs1!posdamer
ARPANET:	wucs1!posdamer@seismo.CSS.GOV  (or .ARPA)
CSNET:		wucs1!posdamer%seismo.CSS.GOV@csnet-relay