How can I test if a point lies within a 3d shape with its surface defined by a point cloud?

I have a collection of points which describe the surface of a shape that should be roughly spherical, and I need a method with which to determine if any other given point lies within this shape. I've previously been approximating the shape as an exact sphere, but this has proven too inaccurate and I need a more accurate method. Simplicity and speed is favourabl开发者_开发百科e over complete accuracy, a good approximation will suffice.

I've come across techniques for converting a point cloud to a 3d mesh, but most things I have found have been very complicated, and I am looking for something as simple as possible.

Any ideas?

What if you computed the centroid of the cloud, and converted its coordinates to a polar system whose origin is that centroid.

Then, convert the point you want to examine to the same coordinate system.

Assuming the surface is representable by a Delaunay triangulation, determine the three points with the smallest difference in angle from the point you're examining.

Project the point you're examining onto the triangle determined by those three points, and see if the distance of the projected point from the centroid is larger than the distance of the actual point.

Essentially, you're constructing a triangular mesh of the convex hull, but as-needed one triangle at a time. If execution speed really matters, you might cache the resulting triangles as you go.

Steven Sudit has also suggested a useful optimization that I'd recommend if you go down this path.

I think Bill Carey's method is on the right track, but I do want to suggest a possible optimization.

Since the shape is roughly spherical, you can pre-calculate the radius of the sphere bound by it and of the sphere that bounds it. This way, if the distance of the point is within the smaller sphere, it's a definite hit and if it's outside the outer sphere, it's a definite miss.

This ought to let you resolve the easy cases very quickly. For the harder ones, Carey's method takes over.

Use a kd-tree.

http://en.wikipedia.org/wiki/Kd-tree

The article provides a good explanation.

I can clear up any further misunderstandings.