rosen@lanai.cs.ucla.edu (Bruce E Rosen) (05/08/90)
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
bs@linus.UUCP (Robert D. Silverman) (05/08/90)
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
This is simply the feasibility problem for linear programming: does
a system of linear inequalities have a solution?
Karmarkar's algorithm solves this in polynomial time. Other techniques
[e.g. Khachian's, Simplex] work also.
--
Bob Silverman
#include <std.disclaimer>
Mitre Corporation, Bedford, MA 01730
"You can lead a horse's ass to knowledge, but you can't make him think"robert@texas.esd.sgi.com (Robert Skinner) (05/09/90)
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.
gordon@cs.tamu.edu (Dan Gordon) (05/09/90)
In article <108669@linus.UUCP} bs@gauss.UUCP (Robert D. Silverman) writes: }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 } }This is simply the feasibility problem for linear programming: does }a system of linear inequalities have a solution? } }Karmarkar's algorithm solves this in polynomial time. Other techniques }[e.g. Khachian's, Simplex] work also. It is not the feasibility problem for linear programming for 2 reasons: 1. The input is not a set of half-spaces (linear inequalities) but a set of points. 2. We are not asked if the convex hull is empty or non-empty (as in the feasibility problem). Instead, we are given an additional point and we are asked if the point is in the convex hull of the others. Note that the convex hull of a (non-empty) set of points is always non-empty, so the feasibility problem here is trivial.
jsh0447@DOMAIN_2.lerc.nasa.gov (Jeff Hojnicki) (05/10/90)
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!" |