smallest enclosing cylinder

  • A+
Category:Languages

Is there an algorithm for finding of an enclosing cylinder with the smallest radius for a 3D cloud of dots? I know that 2D case with the smallest enclosing circle is solved (for example this thread Smallest enclosing circle in Python, error in the code), but is there any working approach for 3D?


EDIT1: OBB. Below is an example of an arc-shaped cloud of dots. The smallest enclosing circle was found by this tool https://www.nayuki.io/page/smallest-enclosing-circle

Circle is defined by three dots of which two are lying almost on a diameter, so it is easy to estimate where the central axis is. "Boxing" of dots will yield a center of the box obviously much shifted from the true center.

I conclude, that OBB approach is not general.

smallest enclosing cylinder


EDIT2: PCA. Below is an example of PCA analysis of a tight dot cloud vs. dot cloud with outliers. For the tight dot cloud PCA predicts the cylinder direction satisfactorily. But if there is a small number of outliers, compared to the main cloud, than PCA will basically ignore them, yielding vectors which are very far from the true axis of an enclosing cylinder. In the example below the true geometrical axis of an enclosing cylinder is shown in black.

I conclude that PCA approach is not general.

smallest enclosing cylinder


EDIT3: OBB vs. PCA and OLS. A major difference - OBB relies only on a geometrical shape, while PCA and OLS are dependent from the overall number of points, including those in the middle of the set, which do not affect the shape. In order to make them more efficient, a data preparation step can be included. First, find the convex hull. Second, exclude all internal points. Then, points along the hull can be distributed unevenly. I'd suggest to remove all of them, leaving only the polygonal hull body, and cover it with mesh, where nodes will be new points. Application of PCA or OLS to this new cloud of points should provide much more accurate estimation of the cylinder axis.

All this can be unnecessary, if OBB provides an axis, as much parallel to the enclosing cylinder axis, as possible.


EDIT4: published approaches. @meowgoesthedog: paper by Michel Petitjean ("About the Algebraic Solutions of Smallest Enclosing Cylinders Problems") could help, but I'm insufficiently qualified to convert it to a working program. Author himself did it (module CYL here http://petitjeanmichel.free.fr/itoweb.petitjean.freeware.html). But at the conclusions in the paper he says: "and the present software, named CYL, downloadable for free at http://petitjeanmichel.free.fr/itoweb.petitjean.freeware.html, is neither claimed to offer the best possible implementations of the methods nor is claimed to work better than other cylinder computation softwares." Other phrases from the paper also makes an impression, that it is an experimental approach, which was not thoroughly validated. I'll try to use it, anyway.

@Ripi2: this paper by Timothy M. Chan is also a bit too complicated for me. I'm not an expert of that level in mathematics, to be able to convert to a tool.

@Helium_1s2: probably, it is a good suggestion, however, it is much less detailed compared to two papers above. Also, not validated.


EDIT5: reply for user1717828. Two most distant points vs. cylinder axis. A counter example - 8 points in a shape of cube, fit in a cylinder. The biggest distance between two points - green diagonal. Obviously not parallel to cylinder axis.

smallest enclosing cylinder

"Middle-points" approach by Ripi2: it works only in 2D. In a 3D case the cylinder axis may not intersect a single segment between any two points.

smallest enclosing cylinder

 


Finding the exact solution seems a very difficult problem. By making hypotheses on the axis direction, and by rotating the cloud (of which you only keep the vertices of the convex hull) and projecting the points onto XY, you can indeed turn to a minimal enclosing circle problem.

But you have to make several hypothesis on the possible directions. For the exact solution, you should try all the directions such that the enclosing circle is defined by different pairs or triples of vertices. This defines complex regions in the space of the rotation angles, and for every region there is a point that achieves an optimimum. This involves a highly nonlinear minimization problem with nonlinear constraints, and seems barely tractable.

At this stage, all I can recommend is an approximate solution such that you try a fixed number of predefined directions and solve the corresponding circle fit. As the solution is approximate anyway, an approximate circle fit can do as well.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: