title: smallest enclosing cylinder
body: <p>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 <a href="https://stackoverflow.com/questions/27673463/smallest-enclosing-circle-in-python-error-in-the-code">Smallest enclosing circle in Python, error in the code</a>), but is there any working approach for 3D?</p>
  
  <hr>
  
  <p>EDIT1: <strong>OBB</strong>. Below is an example of an arc-shaped cloud of dots. The smallest enclosing circle was found by this tool <a href="https://www.nayuki.io/page/smallest-enclosing-circle" rel="noreferrer">https://www.nayuki.io/page/smallest-enclosing-circle</a></p>
  
  <p>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.</p>
  
  <p>I conclude, that <em>OBB approach is not general</em>.</p>
  
  <p><a href="https://i.stack.imgur.com/SfwiP.png" rel="noreferrer"><img src="https://i.stack.imgur.com/SfwiP.png" alt="Example of an arc-shaped data set"></a></p>
  
  <hr>
  
  <p>EDIT2: <strong>PCA</strong>. Below is an example of PCA analysis of a tight dot cloud <em>vs</em>. 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.</p>
  
  <p>I conclude that <em>PCA approach is not general</em>.</p>
  
  <p><a href="https://i.stack.imgur.com/xYHrV.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/xYHrV.jpg" alt="PCA with outliers"></a></p>
  
  <hr>
  
  <p>EDIT3: <strong>OBB vs. PCA and OLS</strong>. 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.</p>
  
  <p>All this can be unnecessary, if OBB provides an axis, as much parallel to the enclosing cylinder axis, as possible.</p>
  
  <hr>
  
  <p>EDIT4: <strong>published approaches</strong>.
  @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 <a href="http://petitjeanmichel.free.fr/itoweb.petitjean.freeware.html" rel="noreferrer">http://petitjeanmichel.free.fr/itoweb.petitjean.freeware.html</a>). But at the conclusions in the paper he says: "<em>and the present software, named CYL, downloadable for free at <a href="http://petitjeanmichel.free.fr/itoweb.petitjean.freeware.html" rel="noreferrer">http://petitjeanmichel.free.fr/itoweb.petitjean.freeware.html</a>, is neither claimed to offer the best possible implementations of the methods nor is claimed to work better than other cylinder computation softwares.</em>" 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.</p>
  
  <p>@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.</p>
  
  <p>@Helium_1s2: probably, it is a good suggestion, however, it is much less detailed compared to two papers above. Also, not validated.</p>
  
  <hr>
  
  <p>EDIT5: <strong>reply for user1717828</strong>. 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.</p>
  
  <p><a href="https://i.stack.imgur.com/lc41m.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/lc41m.jpg" alt="Cube in cylinder"></a></p>
  
  <p><strong>"Middle-points" approach</strong> by Ripi2: it works only in 2D. In a 3D case the cylinder axis may not intersect a single segment between any two points.</p>
  
  <p><a href="https://i.stack.imgur.com/YI1PO.jpg" rel="noreferrer"><img src="https://i.stack.imgur.com/YI1PO.jpg" alt="Triangular prism in cylinder"></a></p>