Jump to content
• ### What is your GameDev Story?

• Advertisement

# point in polyhedron

This topic is 4887 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

## Recommended Posts

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

#### Share this post

##### Share on other sites
Advertisement
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]

#### Share this post

##### Share on other sites
Out of curiosity, what would you do if the polyhedron wasn't convex?

#### Share this post

##### Share on other sites
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.

#### Share this post

##### Share on other sites
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.

#### Share this post

##### Share on other sites
wow !! thanks to all .
But AP what is that Dobkin-Kirkpatrick hierarchy.

#### Share this post

##### Share on other sites
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...

#### Share this post

##### Share on other sites
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.

#### Share this post

##### Share on other sites

• Advertisement
• Advertisement
• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

(You must login to your GameDev.net account.)

• ### Popular Now

• 14
• 14
• 45
• 22
• 27
• Advertisement
• ### Forum Statistics

• Total Topics
634044
• Total Posts
3015211
×

## Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!