Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
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
add comment

1 Answer

up vote 0 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.