Path: utzoo!attcan!uunet!husc6!linus!bs
From: bs@linus.UUCP (Robert D. Silverman)
Newsgroups: comp.graphics
Subject: Re: Points inside Polyhedra
Message-ID: <32897@linus.UUCP>
Date: 26 May 88 00:13:43 GMT
References: <8805212313.AA26306@decwrl.dec.com> <13077@jumbo.dec.com>
Reply-To: bs@linus.UUCP (Robert D. Silverman)
Organization: The MITRE Corporation, Bedford MA
Lines: 21

In article <13077@jumbo.dec.com> stolfi@src.dec.com (Jorge Stolfi) writes:
:*++-+++-++-++--++++-+-+++-+----+-++----+--++--+-+-+-+--+++--+++-++--+-
:
:Mitch Norcross asks:
:
:    I'm trying to find if a point (x,y,z) lies inside or outside of
:    a closed polyhedron.
:
:You can use the three-dimensional equivalent of Jordan's theorem for
:plane curves. Informally, a point p is inside a closed orientable
 
etc.

A FAST way to do this numerically is to treat it as a linear programming
problem and simply determine whether the point is a feasible point for
the problem by reducing the constraint matrix to row-echelon form.
 
the constraint matrix is construced from the planes defining the polyhedron.


Bob Silverman