1

For a point cloud do there exist algorithms to tell the bounding volume that bounds the points in the most compact way, or in a way that minimizes the empty spaces inside the bounding volume? Examples of the bounding volumes in question are bounding boxes, spheres, cylinders and capsules.

Lenny White
  • 406
  • 4
  • 8
  • Perhaps a variant of RanSaC? [RanSaC tutorial with the PCL library](https://pcl.readthedocs.io/projects/tutorials/en/latest/random_sample_consensus.html) – Stef Apr 21 '22 at 13:55
  • @Stef Would this algorithm help identify the closest shape that point cloud resembles like a sphere or a box from identifying "inliers"? – Lenny White Apr 21 '22 at 14:08
  • Yes, ransac can help you find the "best-fitting sphere" (or some other shape of your choice). That shape will not necessarily enclose all the points. The non-enclosed points will be called "outliers" and the enclosed points will be closed "inliers". If you want to enclose all the points then perhaps Ransac is not the right tool. – Stef Apr 21 '22 at 14:14
  • @Stef I don't necessarily need to enclose all points so this could work thank you! – Lenny White Apr 21 '22 at 14:49
  • Actually, Ransac was the first thing I thought of when I read your question, but after thinking a bit more I'm not completely convinced. Note that the library I linked uses the mathematical definition for "sphere". I.e., a sphere is just a surface, not a volume. So it won't try to "enclose some points inside the sphere" but rather "fit some points on the surface of the sphere"; points which are outside and points which are inside will both be considered outliers, and only points on the surface (or close to the surface) will be considered inliers. – Stef Apr 21 '22 at 15:02
  • Wikipedia lists some algorithms to find a minimum-volume [bounding sphere](https://en.wikipedia.org/wiki/Bounding_sphere), but these algorithms include all points, without leaving outliers. – Stef Apr 21 '22 at 15:05
  • @Stef The point clouds are actually generated from meshes which are shallow surfaces, so I think Ransac might still work... – Lenny White Apr 21 '22 at 16:54
  • Not enclosing all points and finding the minimum volume are conflicting goals. You need to specify more precisely. –  Apr 21 '22 at 18:49

1 Answers1

0

The problem is trivial for the axis-aligned boxes.

For arbitrary boxes, I guess that a generalization of rotating calipers is possible (compute the convex hull and try all orientations defined by a plane that contains a face and another plane containing an edge).

For spheres, use the Welzl algorithm.

For a cylindre or a capsule, mh, good luck...