Xref: utzoo comp.graphics:11382 sci.math.num-analysis:800
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!elroy.jpl.nasa.gov!ames!sgi!shinobu!odin!texas.esd.sgi.com!robert
From: robert@texas.esd.sgi.com (Robert Skinner)
Newsgroups: comp.graphics,sci.math.num-analysis
Subject: Re: Needed: Methods/heuristics for deterining if a point is in a Polytope
Message-ID: <7419@odin.corp.sgi.com>
Date: 8 May 90 17:20:04 GMT
References: <35059@shemp.CS.UCLA.EDU>
Sender: news@odin.corp.sgi.com
Reply-To: robert@sgi.com
Organization: Silicon Graphics Inc., Entry Systems Division
Lines: 40


In article <35059@shemp.CS.UCLA.EDU>, rosen@lanai.cs.ucla.edu (Bruce E
Rosen) writes:
|> I would appreciate it if anyone could send me methods and heuristics
|> to determine if a point is inside a general n dimensional polytope.  These
|> methods need not be efficient. More specifically, 
|> 	given an n dimensional polytope (convex or concave) consisting of
|> 	2^n verticies, each vertex being an n dimensional vector.
|> 	Determine if a point (n dim.) lies within the volume
|> 	of the polytope.
|> For example, one method that is easy to compute might be to determine
|> if the point lies within an inner bounding rectangular prism inside
|> of the polytope. If the point lies within the prism, it lies within
|> the polytope.  This method is easy to program and quick, yet if the
|> point lies outside the prism, it could still lie within the polytope.
|> In that case, a second more reliable (albeit less efficient) method
|> could be incorporated.  
|> 	Thanks
|> 	bruce

If your polytope is convex, you could use n-dimensional Cyrus-Beck clipping
(Procedural Elements of Computer Graphics, Rogers, p 135).  You have
to compute the inward facing normal of each plane of the polytope.  
Compute the dot product of the normal and a vector from any point on 
that plane to the point in question.  If the dot product is negative,
the point is outside the polytope.  If the dot product is positive for
all planes of the polytope, it is inside the polytope.

this doesn't work for concave polytopes.  I would suggest you look at
2D and 3D clipping algorithms for concave polygons/solids, they should
generalize to n dimensions.

Robert Skinner
robert@sgi.com

	"She complained that the dinosaurs weren't alive."

			-- Carmencita Cardoza, of the Dinosaurs Alive!
			   exhibit (San Jose), about a woman's reasoning 
			   for wanting her money back.