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?
Smallest enclosing cylinder for an irregular body
-
0Do 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? – 2011-11-27
-
1Yes, 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 – 2011-11-27
-
0Do you have an application in mind, and are you working in a particular language? – 2011-11-28
-
0Just ran across this an thought I'd leave it here for future reference: http://www.geometrictools.com/Documentation/CylinderFitting.pdf – 2012-02-10
1 Answers
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.