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
-
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.