Xref: utzoo comp.graphics:11408 sci.math.num-analysis:807
Newsgroups: comp.graphics,sci.math.num-analysis
Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!usenet.ins.cwru.edu!eagle!news
From: jsh0447@DOMAIN_2.lerc.nasa.gov (Jeff Hojnicki)
Subject: Re: Needed: Methods/heuristics for deterining if a point is in a Polytope
Message-ID: <1990May9.230947.26572@eagle.lerc.nasa.gov>
Reply-To: jshoj@csd.lerc.nasa.gov (Jeff Hojnicki)
Organization: NASA/Lewis Research Center  
References: <35059@shemp.CS.UCLA.EDU>
Date: Wed, 9 May 90 23:09:47 GMT

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, 

Isn't this just an n-dimensional extension to the age-old problem:
Determine is a 2D point lies inside a closed 2D polygon?

A reliable method to solve that problem is to create an arbitrary vector
from the point in any direction.  Then determine the number of edges in the
polygon which the vector intersects.  Count the number of intersections.
If the number is odd, the point is inside the polygon; if it is even, the
point is outside.

I would think the problem would be identical in n dimensions, but
determining the intersections may be a bit more difficult.

Have I forgotton anything? 
--
 Jeff Hojnicki   |    jshoj@csd.lerc.nasa.gov         |   // //        // //
 NASA/LeRC       |    jhojnicki@nasamail.nasa.gov     |  =====FREEDOM======
 (216)-433-5393  | - - - - - - - - - - - - - - - - - -| // //  () () // //
 "My opinions are my own, don't blame NASA for them!" |