Can anyone suggest a good algo for finding whether a point is in a polyhedorn ?

a simple way would be for each polygon face, calculate the signed distance b/w the point and the plane defining the face. if every signed distance is negative, then it's in the shape.


to calcuate the signed distance between a point and a plane do this:

given:
P = a point on the plane
N = normal to plane
Point = point to test if inside

///////
V = Point - P
SignedDistance = N DOT V
if(signedDistance < 0)
not inside shape


note the normal vector doesn't even have to be normalized because we're just checking the sign of the result, we don't really need the true distnace, just the positive or negativeness of the result.

what it's basiclly doing is checking if the point is behind the face. if it's behind all the faces, then it's inside the shape(assuming outward pointing normals)

this algorithm follows directly form the definiion of convex


Tim

[Edited by - timw on August 29, 2005 7:55:36 AM]

Out of curiosity, what would you do if the polyhedron wasn't convex?

Quote:Out of curiosity, what would you do if the polyhedron wasn't convex?

There are some ways to test point-in-non-convex polygon or polyhedra. One method is based on the observation that a ray starting at the point in question will pass through the boundary of the object an odd number of times if the point is inside, and an even number of times if the point is outside. I can't say from experience, but it seems like it'd be difficult to implement this robustly.

Quote:Original post by jyk

Quote:Out of curiosity, what would you do if the polyhedron wasn't convex?

There are some ways to test point-in-non-convex polygon or polyhedra. One method is based on the observation that a ray starting at the point in question will pass through the boundary of the object an odd number of times if the point is inside, and an even number of times if the point is outside. I can't say from experience, but it seems like it'd be difficult to implement this robustly.

The robustness problems occur when the ray passes through a vertex or edge of the polyhedron or when a subsegment of the ray is contained within a face. Given such an implementation, you can cast a few rays from the point and take the majority "vote" on whether the point is inside or outside. The parity approach is O(N) for N faces.

If the point-in-polyhedron test is to be executed frequently, consider building a spatial data structure as a preprocessing step. For example, a BSP tree data structure may be used. The idea is to produce an O(log N) search at the expense of using some memory for the spatial data structure. For convex polyhedra with a large number of faces, this idea is useful to avoid the naive algorithm proposed by "timw". The Dobkin-Kirkpatrick hierarchy is one such data structure for accelerating the search. To motivate, think of a chevron polygon in 2D which has 4 vertices (in order V0, V1, V2, V3) but is not a convex polygon. If V0, V1, and V3 are the convex vertices and V2 is the reflex vertex, then timw's suggestion requires 4 point-inside-edge tests to find out a point is inside the polygon. Instead, you can test which side of the line through V0 and V2 the test point lines. If on the side containing V1, then you need only perform two more point-inside-edge tests. If on the other side, you still need only perform two point-inside-edge tests. In total, you do at most 3 tests instead of the 4 tests in timw's suggestion.

wow !! thanks to all .
But AP what is that Dobkin-Kirkpatrick hierarchy.

Quote:what is that Dobkin-Kirkpatrick hierarchy.

Briefly, the D-K hierarchy for a polytope is a series of nested polytopes, each contained within the one before. The original polytope is the first entry in the hierarchy; thereafter, each successive polytope is a simplification of the one before it, terminating in a simplex. The D-K hierarchy can be used to accelerate various queries, such as closest point, maximal vertex, etc.

clever...

Quote:Original post by _gl_coder_one_
wow !! thanks to all .
But AP what is that Dobkin-Kirkpatrick hierarchy.

jyk describes it briefly in his follow-up in this thread. A detailed description is presented in Joseph O'Rourke's book "Computational Geometry in C, Second Edition" (section 7.10 on Extremal Polytope Queries). Christer Ericson's book "Real-Time Collision Detection" discusses the use of the hierarchy in practical applications.