Menu
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 favourable 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?
561
Draw a horizontal line to the right of each point and extend it to infinity. Count the number of times the line intersects with polygon edges. A point is inside the polygon if either count of intersections is odd or point lies on an edge of polygon.
Construct the direction vector from the cube center to the point in consideration and project it onto each local axis and check if the projection spans beyond the extent of the cube along that axis. If the projection lies inside the extent along each axis, then point is inside, otherwise it is outside of the cube.
In this post, we have discussed a new approach. Approach: If we observe carefully, It will be clear that for a point to be lie inside the rectangle, it should be lie inside the x-coordinate (x1, x2) of the rectangle as well as it should also lie inside the y-coordinate (y1, y2) of the rectangle.
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.
170
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
