# Smallest enclosing cylinder for an irregular body

I have an $3$-dimensional irregular body composed of 162 points $(x,y,z)$. I need to find the smallest enclosing cylinder for this body. Is there a standard algorithm for achieving this?

-
Do you care whether the cylinder is circular? Do you care whether its base is parallel to the $xy$ plane? Do you care whether its sides are all perpendicular to the $xy$ plane? to its base? – msh210 Nov 27 '11 at 19:07
Yes, the cylinder should be circular. The base need not be parallel to the xy plane. Sides need not be perpendicular to the plane. But the sides need be perpendicular to the base. Basically, a right circular cylinder that may/may not be parallel to the xy plane – Lelouch Lamperouge Nov 27 '11 at 19:32
Do you have an application in mind, and are you working in a particular language? – user_123abc Nov 28 '11 at 16:38
Just ran across this an thought I'd leave it here for future reference: geometrictools.com/Documentation/CylinderFitting.pdf – user_123abc Feb 10 '12 at 5:02

I'll assume it's to be a right circular cylinder, and "smallest" is in terms of volume. Consider a cylinder of radius $r$ and height $h$, with one of the ends centred at point $P$, and axis in the direction of unit vector $U$. Then a point $X = (x,y,z)$ is in the cylinder if $0 \le (X - P)\cdot U \le h$ and $\|X - P - ((X -P)\cdot U) U \|^2 \le r^2$. Thus you want to minimize $r^2 h$ subject to constraints $r \ge 0$, $h \ge 0$, $\|U\|^2 = 1$, and for all $X$, $(X - P) \cdot U \ge 0$, $(X - P)\cdot U \le h$, $\|X - P - ((X -P)\cdot U) U \|^2 \le r^2$. You only need to consider those $X$ that are extreme points of their convex hull. You can also require, say, $U_1 \ge 0$ because you have your choice of which end of the cylinder $P$ is on. This is a (non-convex) nonlinear constrained optimization problem. I might try Maple's Global Optimization Toolbox.