最小围筒
对于三维点云，是否有一种寻找半径最小的圆柱体的算法？我知道用最小的包围圈的2D情况是解决的(例如这个线程Python中最小的封闭圈，代码中的错误)，但是对于3D有什么工作方法吗？
EDIT1：OBB.下面是一个弧形圆点云的例子.该工具https://www.nayuki.io/page/smallest-enclosing-circle求出了最小的包围圆。
圆是由三个点定义的，其中两个点几乎位于一个直径上，因此很容易估计出中心轴的位置。“拳击”的圆点将产生一个中心的盒子，显然很大程度上偏离了真正的中心。
我的结论是，OBB的方法并不是一般的。
EDIT2：PCA.下面是一个分析紧密点云与带异常点云的PCA分析的例子。对于紧点云，PCA能较好地预测圆柱体方向。但是，如果有少量的离群点，与主云相比，PCA基本上会忽略它们，产生的向量离包围圆柱的真正轴非常远。在下面的例子中，圆柱体的真实几何轴用黑色表示。
我得出的结论是，PCA方法并不普遍。
EDIT3：OBB与PCA和OLS。一个主要的区别- OBB只依赖于一个几何形状，而PCA和OLS取决于总点数，包括在集合的中间，这不影响形状。为了使它们更有效，可以包括一个数据准备步骤。首先，找出凸包。第二，排除所有内部要点。然后，沿船体的点可能分布不均匀。我建议全部删除，只留下多边形船体，并覆盖它的网格，其中的节点将是新的点。将PCA或OLS应用于这一新的点云，可以更准确地估计圆柱轴。
所有这些都是不必要的，如果OBB提供一个轴，尽可能平行于包围圆柱轴。
EDIT4：发布了“方法”。@meowgoesthedog: Michel Petitjean的论文(关于最小的圆柱体问题的代数解决方案)可能会有帮助，但我没有足够的资格将它转化为一个工作程序。作者自己做的(模块CYL在这里http://petitjeanmichel.free.fr/itoweb.petitjean.freeware.html)。但在论文的结论中，他说：“而目前的软件，名为CYL，可在http://petitjeanmichel.free.fr/itoweb.petitjean.freeware.html免费下载，既没有声称能提供这些方法的最佳实现，也没有声称比其他柱面计算软件工作得更好。”论文中的其他词组也给人一种印象，认为这是一种实验方法，但没有得到充分的验证。不管怎样，我会试着用它的。
@Ripi2:这篇由TimothyM.Chan撰写的论文对我来说也有点复杂。我不是那种程度的数学专家，我不能转换成工具。
@Helium_1s2:也许，这是一个很好的建议，但是，与上面的两篇论文相比，它的细节要少得多。还有，没有验证。
EDIT5：回复user1717828。两个相对于圆柱轴的最远点。反例-8点在一个立方体的形状，适合在一个圆柱体。两点之间最大的距离-绿色对角线。显然与圆柱轴不平行。
“中间点”方法( by Ripi2)：它只在2D中工作。在三维情况下，圆柱轴不可能在任何两点之间相交一段。
回答 5
Stack Overflow用户
发布于 2018-07-20 06:45:31
- 计算OBB 所以要么使用PCA，要么使用这个
- [How to Compute OBB of Multiple Curves?](https://stackoverflow.com/a/42997918/2521214)获得三维OBB。链接中的代码必须移植到3D，但原理是相同的。在这里，我更多地使用了对先进的三维OBB逼近的递归搜索(这里的代码和方法不如它)。
- 初始猜测 所以OBB会给你定向的包围盒。它最大的一面将平行于你的汽缸的旋转轴。所以让我们从这个OBB的滚筒开始。因此，中轴将是OBB的中心，并与其最大的一面平行。(如果你没有最大的一面，那么你需要检查所有三个组合)。其馀边的直径将越大。
- 配合气缸 现在，只要尝试“所有”的偏移量和半径(可能也是高度)的组合，把你的所有点包围在初始猜测附近，记住最好的(根据你想要的规格)。您可以对此使用任何优化方法，但我最喜欢的是：
- [How approximation search works](https://stackoverflow.com/a/36163847/2521214)结果的有效性取决于拟合过程。但不要过于疯狂的嵌套拟合，因为复杂性也是疯狂的。
Edit1 3D OBB在C++中的应用
我很好奇，今天有一些时间，所以我编码了3D OBB，类似于上面链接的2D示例。看起来起作用了。这是预览：
我用两个簇来验证方向..。在这里，代码(以简单C++类的形式)：
//---------------------------------------------------------------------------
class OBB3D
{
public:
double p0[3],u[3],v[3],w[3]; // origin,3 axises sorted by size asc
double V,l[3]; // volume, and { |u|,|v|,|w| }
double p[8*3]; // corners
OBB3D() {}
OBB3D(OBB3D& a) { *this=a; }
~OBB3D() {}
OBB3D* operator = (const OBB3D *a) { *this=*a; return this; }
//OBB3D* operator = (const OBB3D &a) { ...copy... return this; }
void compute(double *pnt,int num) // pnt[num] holds num/3 points
{
OBB3D o; // temp OBB values
int i,j;
double a,_a,a0,a1,da,ca,sa; int ea; // search angles
double b,_b,b0,b1,db,cb,sb; int eb;
double c,_c,c0,c1,dc,cc,sc; int ec;
double u0[3],v0[3],pmin[3],pmax[3],q,*qq;
const double deg=M_PI/180.0;
p0[0]=0.0; u[0]=1.0; v[0]=0.0; w[0]=0.0; l[0]=0.0; V=-1.0;
p0[1]=0.0; u[1]=0.0; v[1]=1.0; w[1]=0.0; l[1]=0.0;
p0[2]=0.0; u[2]=0.0; v[2]=0.0; w[2]=1.0; l[2]=0.0;
if (num<3) { V=0.0; return; }
a0=0; a1=360.0*deg; da=10.0*deg; _a=a0;
b0=0; b1= 90.0*deg; db=10.0*deg; _b=b0;
c0=0; c1= 90.0*deg; dc=10.0*deg; _c=c0;
// recursively increase precision
for (j=0;j<5;j++)
{
// try all 3D directions with some step da,db
for (ea=1,a=a0;ea;a+=da){ if (a>=a1) { a=a1; ea=0; } ca=cos(a); sa=sin(a);
for (eb=1,b=b0;eb;b+=db){ if (b>=b1) { b=b1; eb=0; } cb=cos(b); sb=sin(b);
// spherical to cartesian direction
o.w[0]=cb*ca;
o.w[1]=cb*sa;
o.w[2]=sb;
// init u,v from cross product
vector_ld(u0,1.0,0.0,0.0);
if (fabs(vector_mul(u0,o.w))>0.75) // |dot(u,w)>0.75| measn near (anti)parallel
vector_ld(u0,0.0,1.0,0.0);
vector_mul(v0,o.w,u0); // v0 = cross(w,u0)
vector_mul(u0,v0,o.w); // u0 = cross(v0,w)
vector_one(u0,u0); // u0/=|u0|
vector_one(v0,v0); // v0/=|v0|
// try all rotations within u0,v0 plane
for (ec=1,c=c0;ec;c+=dc){ if (c>=c1) { c=c1; ec=0; } cc=cos(c); sc=sin(c);
for (i=0;i<3;i++)
{
o.u[i]=(u0[i]*cc)-(v0[i]*sc);
o.v[i]=(u0[i]*sc)+(v0[i]*cc);
}
// now u,v,w holds potential obb axises socompute min,max
pmin[0]=pmax[0]=vector_mul(pnt,o.u); // dot(pnt,u);
pmin[1]=pmax[1]=vector_mul(pnt,o.v); // dot(pnt,v);
pmin[2]=pmax[2]=vector_mul(pnt,o.w); // dot(pnt,w);
for (i=0;i<num;i+=3)
{
q=vector_mul(pnt+i,o.u); if (pmin[0]>q) pmin[0]=q; if (pmax[0]<q) pmax[0]=q;
q=vector_mul(pnt+i,o.v); if (pmin[1]>q) pmin[1]=q; if (pmax[1]<q) pmax[1]=q;
q=vector_mul(pnt+i,o.w); if (pmin[2]>q) pmin[2]=q; if (pmax[2]<q) pmax[2]=q;
}
// compute V,l from min,max
for (o.V=1.0,i=0;i<3;i++) { o.l[i]=pmax[i]-pmin[i]; o.V*=o.l[i]; }
// remember best solution u,v,w,V,l and compute p0
if ((V<0.0)||(V>o.V))
{
*this=o; _a=a; _b=b; _c=c;
for (i=0;i<3;i++) p0[i]=(pmin[0]*u[i])+(pmin[1]*v[i])+(pmin[2]*w[i]);
}
}
}}
a0=(_a-0.5*da); a1=a0+da; da*=0.1;
b0=(_b-0.5*db); b1=b0+db; db*=0.1;
c0=(_c-0.5*dc); c1=c0+dc; dc*=0.1;
}
// sort axises
{ i=0; qq=u; } // w is max
if (l[1]>l[i]){ i=1; qq=v; }
if (l[2]>l[i]){ i=2; qq=w; }
for (j=0;j<3;j++) { q=w[j]; w[j]=qq[j]; qq[j]=q; } q=l[2]; l[2]=l[i]; l[i]=q;
{ i=0; qq=u; } // v is 2nd max
if (l[1]>l[i]){ i=1; qq=v; }
for (j=0;j<3;j++) { q=v[j]; v[j]=qq[j]; qq[j]=q; } q=l[1]; l[1]=l[i]; l[i]=q;
// compute corners from p0,u,v,w,l
for (i=0;i<3;i++)
{
j=i;
p[j]=p0[i] ; j+=3;
p[j]=p0[i]+(l[0]*u[i]) ; j+=3;
p[j]=p0[i]+(l[0]*u[i])+(l[1]*v[i]) ; j+=3;
p[j]=p0[i] +(l[1]*v[i]) ; j+=3;
p[j]=p0[i] +(l[2]*w[i]); j+=3;
p[j]=p0[i]+(l[0]*u[i]) +(l[2]*w[i]); j+=3;
p[j]=p0[i]+(l[0]*u[i])+(l[1]*v[i])+(l[2]*w[i]); j+=3;
p[j]=p0[i] +(l[1]*v[i])+(l[2]*w[i]); j+=3;
}
}
void gl_draw()
{
glBegin(GL_LINES);
glVertex3dv(p+ 0); glVertex3dv(p+ 3);
glVertex3dv(p+ 3); glVertex3dv(p+ 6);
glVertex3dv(p+ 6); glVertex3dv(p+ 9);
glVertex3dv(p+ 9); glVertex3dv(p+ 0);
glVertex3dv(p+12); glVertex3dv(p+15);
glVertex3dv(p+15); glVertex3dv(p+18);
glVertex3dv(p+18); glVertex3dv(p+21);
glVertex3dv(p+21); glVertex3dv(p+12);
glVertex3dv(p+ 0); glVertex3dv(p+12);
glVertex3dv(p+ 3); glVertex3dv(p+15);
glVertex3dv(p+ 6); glVertex3dv(p+18);
glVertex3dv(p+ 9); glVertex3dv(p+21);
glEnd();
}
} obb;
//---------------------------------------------------------------------------您只需调用带有点云数据的计算，其中num为3x的点数。结果存储为单位基向量u,v,w和原点p0以及每个轴的l[]大小，或存储为OBB p的8个角点。
这些东西只需尝试“所有”球面位置，在w轴上做一些步骤，然后尝试所有垂直于每一个的u,v极坐标，w记住最小体积的OBB。然后递归搜索附近的位置，用较小的步骤找到最优解，以提高精度。
我认为这应该是一个很好的起点。如果您实现最小圆而不是u,v旋转(循环for (ec=1,c=c0;ec;c+=dc))，那么您可以直接从这个搜索中获得你的圆柱。
代码还没有优化(比如w轴检查)可以移动到嵌套循环的较低层。但我想尽量保持简单易懂。
Edit2 3D OBC在C++中的应用
我设法修改了我的3D OBB，用最小的包围圈代替了U,V搜索(希望我实现得对，但它看起来像.)这就找到了UV平面上投影的所有点的最小包围二维圆，这使得它成为一个与W平行的定向包围圆柱。我使用了来自pdf来自您的链接的第一种方法(使用平分线)。这里的结果是：
蓝色是3D OBB，棕色/橙色是已发现的3D OBC。在这里，代码：
class OBC3D // 3D Oriented Bounding Cylinder
{
public:
double p0[3],u[3],v[3],w[3]; // basecenter,3 axises
double V,r,h; // volume, radius height
double p1[3]; // other base center
OBC3D() {}
OBC3D(OBC3D& a) { *this=a; }
~OBC3D() {}
OBC3D* operator = (const OBC3D *a) { *this=*a; return this; }
//OBC3D* operator = (const OBC3D &a) { ...copy... return this; }
void compute(double *pnt,int num) // pnt[num] holds num/3 points
{
OBC3D o; // temp OBB values
int i,j,k,kk,n;
double a,_a,a0,a1,da,ca,sa; int ea; // search angles
double b,_b,b0,b1,db,cb,sb; int eb;
double pmin[3],pmax[3],q,qq,*pnt2,p[3],c0,c1,u0,v0,du,dv,dr;
const double deg=M_PI/180.0;
p0[0]=0.0; u[0]=1.0; v[0]=0.0; w[0]=0.0; V=-1.0;
p0[1]=0.0; u[1]=0.0; v[1]=1.0; w[1]=0.0; r=0.0;
p0[2]=0.0; u[2]=0.0; v[2]=0.0; w[2]=1.0; h=0.0;
if (num<3) { V=0.0; return; }
// prepare buffer for projected points
pnt2=new double[num];
a0=0; a1=360.0*deg; da=10.0*deg; _a=a0;
b0=0; b1= 90.0*deg; db=10.0*deg; _b=b0;
// recursively increase precision
for (k=0;k<5;k++)
{
// try all 3D directions with some step da,db
for (ea=1,a=a0;ea;a+=da){ if (a>=a1) { a=a1; ea=0; } ca=cos(a); sa=sin(a);
for (eb=1,b=b0;eb;b+=db){ if (b>=b1) { b=b1; eb=0; } cb=cos(b); sb=sin(b);
// spherical to cartesian direction
o.w[0]=cb*ca;
o.w[1]=cb*sa;
o.w[2]=sb;
// init u,v from cross product
vector_ld(o.u,1.0,0.0,0.0);
if (fabs(vector_mul(o.u,o.w))>0.75) // |dot(u,w)>0.75| measn near (anti)parallel
vector_ld(o.u,0.0,1.0,0.0);
vector_mul(o.v,o.w,o.u); // v0 = cross(w,u0)
vector_mul(o.u,o.v,o.w); // u0 = cross(v0,w)
vector_one(o.u,o.u); // u0/=|u0|
vector_one(o.v,o.v); // v0/=|v0|
// now u,v,w holds potential obb axises so compute min,max and convert to local coordinates
pmin[0]=pmax[0]=vector_mul(pnt,o.u); // dot(pnt,u);
pmin[1]=pmax[1]=vector_mul(pnt,o.v); // dot(pnt,v);
pmin[2]=pmax[2]=vector_mul(pnt,o.w); // dot(pnt,w);
for (i=0;i<num;i+=3)
{
q=vector_mul(pnt+i,o.u); if (pmin[0]>q) pmin[0]=q; if (pmax[0]<q) pmax[0]=q; pnt2[i+0]=q;
q=vector_mul(pnt+i,o.v); if (pmin[1]>q) pmin[1]=q; if (pmax[1]<q) pmax[1]=q; pnt2[i+1]=q;
q=vector_mul(pnt+i,o.w); if (pmin[2]>q) pmin[2]=q; if (pmax[2]<q) pmax[2]=q; pnt2[i+2]=q;
}
// [compute min enclosing circle]
n=0;
// center (u0,v0) = avg( pnt2 )
for (u0=0.0,v0=0.0,i=0;i<num;i+=3)
{
u0+=pnt2[i+0];
v0+=pnt2[i+1];
} q=3.0/double(num); u0*=q; v0*=q;
// r = max(|pnt2 - (u0,v0)|)
for (o.r=0.0,i=0;i<num;i+=3)
{
c0=pnt2[i+0]-u0;
c1=pnt2[i+1]-v0;
q=(c0*c0)+(c1*c1);
if (o.r<q) o.r=q;
} o.r=sqrt(o.r);
for (kk=0;kk<4;kk++)
{
// update edgepoints count n
qq=o.r*o.r;
for (i=n;i<num;i+=3)
{
c0=pnt2[i+0]-u0;
c1=pnt2[i+1]-v0;
q=fabs((c0*c0)+(c1*c1)-qq);
if (q<1e-10)
{
pnt2[n+0]=pnt2[i+0];
pnt2[n+1]=pnt2[i+1];
pnt2[n+2]=pnt2[i+2]; n+=3;
}
}
// compute bisector (du,dv)
for (du=0.0,dv=0.0,i=0;i<n;i+=3)
{
du+=pnt2[i+0]-u0;
dv+=pnt2[i+1]-v0;
} q=1.0/sqrt((du*du)+(dv*dv)); du*=q; dv*=q;
// try to move center towards edge points as much as possible
for (dr=0.1*o.r,j=0;j<5;)
{
u0+=dr*du;
v0+=dr*dv;
// q = max(|pnt2 - (u0,v0)|)
for (qq=0.0,i=0;i<num;i+=3)
{
c0=pnt2[i+0]-u0;
c1=pnt2[i+1]-v0;
q=(c0*c0)+(c1*c1);
if (qq<q) qq=q;
} qq=sqrt(qq);
// recursively increase precision
if (qq>o.r)
{
u0-=dr*du;
v0-=dr*dv;
dr*=0.1;
j++;
}
else o.r=qq;
}
}
// compute h,V
o.h=pmax[2]-pmin[2];
o.V=M_PI*o.r*o.r*o.h;
// remember best solution u,v,w,V,l and compute p0
if ((V<0.0)||(V>o.V))
{
*this=o; _a=a; _b=b;
for (i=0;i<3;i++) p0[i]=(u0*u[i])+(v0*v[i])+(pmin[2]*w[i]);
}
}}
a0=(_a-0.5*da); a1=a0+da; da*=0.1;
b0=(_b-0.5*db); b1=b0+db; db*=0.1;
}
// compute corners from p0,u,v,w,l
for (i=0;i<3;i++) p1[i]=p0[i]+(h*w[i]);
delete[] pnt2;
}
void gl_draw()
{
int i,j,n=36;
double a,da=2.0*M_PI/double(n),p[3],uu,vv;
glBegin(GL_LINES);
glVertex3dv(p0); glVertex3dv(p1);
glEnd();
glBegin(GL_LINE_LOOP);
for (a=0.0,i=0;i<n;i++,a+=da)
{
uu=r*cos(a);
vv=r*sin(a);
for (j=0;j<3;j++) p[j]=p0[j]+(u[j]*uu)+(v[j]*vv);
glVertex3dv(p);
}
glEnd();
glBegin(GL_LINE_LOOP);
for (a=0.0,i=0;i<n;i++,a+=da)
{
uu=r*cos(a);
vv=r*sin(a);
for (j=0;j<3;j++) p[j]=p1[j]+(u[j]*uu)+(v[j]*vv);
glVertex3dv(p);
}
glEnd();
}
};
//---------------------------------------------------------------------------用法是一样的。我用这个测试过：
OBB3D obb;
OBC3D obc;
void compute()
{
int i,n=500;
// random pnt cloud
Randomize();
RandSeed=98123456789;
pnt.allocate(3*n); pnt.num=0;
// random U,V,W basis vectors
double u[3],v[3],w[3],x,y,z,a;
for (i=0;i<3;i++) w[i]=Random()-0.5; // random direction
vector_one(w,w); // w/=|w|
vector_ld(u,1.0,0.0,0.0);
if (fabs(vector_mul(u,w))>0.75) // |dot(u,w)>0.75| measn near (anti)parallel
vector_ld(u,0.0,1.0,0.0);
vector_mul(v,w,u); // v = cross(w,u)
vector_mul(u,v,w); // u = cross(v,w)
vector_one(u,u); // u/=|u|
vector_one(v,v); // v/=|v|
// random cylinder point cloud
for (i=0;i<n;i++)
{
a=2.0*M_PI*Random();
x= 0.5+(0.75*(Random()-0.5))*cos(a);
y=-0.3+(0.50*(Random()-0.5))*sin(a);
z= 0.4+(0.90*(Random()-0.5));
pnt.add((x*u[0])+(y*v[0])+(z*w[0]));
pnt.add((x*u[1])+(y*v[1])+(z*w[1]));
pnt.add((x*u[2])+(y*v[2])+(z*w[2]));
}
obb.compute(pnt.dat,pnt.num);
obc.compute(pnt.dat,pnt.num);
}其中List<double> pnt是我的动态数组模板double pnt[]。这在这里并不重要。
请注意，如果您选择了太大的初始步骤(**da,db**)进行 W 方向搜索，您可能会在本地最小值内捕获自己，从而错过正确的解决方案。
Stack Overflow用户
发布于 2018-07-20 17:17:35
概念性答案
- 找出两者之间最大距离的两点。它们位于气缸的表面上，连接它们的线将平行于气缸的轴线。
- 投影垂直于该轴的平面上的所有点。
- 在那架飞机上找出它们之间最大距离的两个点。它们定义了直径d等于圆柱体直径d的圆。
- 包含所有点的最小体积的圆柱体
。
*这假设只有一对点，它们之间的最大距离确定了圆柱的轴。如果有机会两对点共享最大的价值，重复步骤2-4对每对，并选择最小直径的圆柱。
Python回答
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
%matplotlib notebook
from numpy.linalg import norm
from scipy.spatial.distance import pdist, squareform如果您还没有生成点，则生成它们：
np.random.seed(0)
N = 30
M = np.random.randint(-3,3,(N,3))
print(M)
[[ 1 2 -3]
[ 0 0 0]
[-2 0 2]
[-1 1 -3]
[-3 1 -1]
...
[ 1 -3 1]
[ 0 -1 2]]计算每一对可能的点之间的距离，并选择最大距离的对。
max_dist_pair = list(pd.DataFrame(squareform(pdist(M))).stack().idxmax())
p1 = M[max_dist_pair[0]]
p2 = M[max_dist_pair[1]]
print(f"Points defining cylinder faces: {p1}, {p2}")
print(f"Length of cylinder: {norm(p1-p2)}")
Points defining cylinder faces: [-1 -3 -3], [1 2 2]
Length of cylinder: 7.3484692283495345用蓝色表示所有点的点，用红色表示最大间距的点。
fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
ax.scatter(*M.T, c = ['red' if i in max_dist_pair else 'blue' for i in range(N)])
ax.set_xlabel("X")
ax.set_ylabel("Y")
ax.set_zlabel("Z")
plt.show()
这是一个旋转的图，所以我们沿着两个红点之间的轴看。
上面的观点与垂直于圆柱轴的平面上的点是一样的。找出这个平面上包含点的最小圆。我们通过找出每个点到轴的位移，然后找出两点之间的最大距离来实现这一点。
perp_disp = (np.cross(p2-p1, M-p1))/norm(p2-p1) # Get perpendicular displacement vectors.
print(perp_disp)
[[-3.40206909 1.36082763 0. ]
[ 0. -0.13608276 0.13608276]
[ 1.36082763 -2.04124145 1.4969104 ]
[-2.72165527 0. 1.08866211]
[-1.36082763 -1.90515869 2.44948974]
[ 0.68041382 -0.95257934 0.68041382]
[ 2.72165527 0.68041382 -1.76907593]
...
[ 0. 0.27216553 -0.27216553]
[ 0. -0.40824829 0.40824829]
[ 2.72165527 0.27216553 -1.36082763]
[ 2.04124145 -0.68041382 -0.13608276]]最大的距离是通过做相同的pdist使用的技巧以上。
max_perp_disp_pair = list(pd.DataFrame(squareform(pdist(perp_disp))).stack().idxmax())
perp_p1 = M[max_perp_disp_pair[0]]
perp_p2 = M[max_perp_disp_pair[1]]
print(perp_p1, perp_p2)
[ 1 2 -3] [-3 -2 1]最后，我们得到了圆柱的直径。
print(norm(perp_p1 - perp_p2))
6.92820323028可以包含这些点的圆柱体的最小体积是
备注
- 利用Numpy的成对距离函数
pdist求出点间的最大距离。然后用squareform对其进行格式化，将其放入PandasDataFrame，以便使用idxmax很容易地找到这两个点的索引。在没有潘达斯的情况下，可能有更好的方法来做到这一点。 - 如果
np.cross部分让您挠头，这只是为了找到点和线之间的最小距离。如果您感兴趣的话，我可以进一步了解更多的细节，但是如果您画了两条线的交叉积，就会得到一个平行四边形，其中两个非平行的边是由直线给出的。这个平行四边形的面积与长方形相同，长度等于一条直线，宽度等于从点到直线的距离。
Stack Overflow用户
发布于 2018-07-20 03:59:01
首先，查找点云的定向边界框(OBB)。这方面有几种算法。这个可能是最优的：
https://pdfs.semanticscholar.org/a76f/7da5f8bae7b1fb4e85a65bd3812920c6d142.pdf
现在，通过绕着OBB长轴旋转OBB，可以很容易地找到一个非优化的定向圆柱体包围OBB。同样，被OBB包围的圆柱体与另一个圆柱体具有相同的轴，但半径是OBB面与轴正向的最短边的一半。
我的结论是，最优的圆柱体半径在这两个圆柱体之间。
如果计算所有点到外圆柱的最小距离，并调整它的半径使之等于零，那么就可以很容易地找到最佳的圆柱体。
这种方法可能有效，但在计算上不是最优的，因为您必须计算从所有点到圆柱的距离。也许内筒可能被用来裁剪它里面的所有点。我没有详细阐述这个想法。
更新：
这个问题似乎不清楚什么是“最小的”，实际上是要求“最小”以外的东西，而且它没有很好地提出。包围一个点云的“最小”圆柱体被认为是将圆柱体内部的空空间最小化(至少我理解为最小)。但是OP也施加了一个约束，那就是最小的圆柱应该符合输入数据的形状。这意味着，如果输入的数据是一个圆柱体的一半(被它最孤独的一面切割)，答案应该是最适合这一半形状的圆柱体。不管那个圆柱体是否有更多的空空间，比其他封装数据的圆柱都要多。
这两项要求是矛盾的。由于最小的圆柱体可能不适合数据的弯曲形状，而圆柱体最适合于数据的弯曲形状，所以数据的曲线形状不可能是最小的圆柱。
我基于OBB的答案(和其他答案)确实回答了关于“最小”圆柱体的问题，该圆柱体将数据的空隙最小化。
另一种情况是将圆柱体拟合成数据的形状，也可以用优化方法来回答。但没有一个普遍的答案。“最佳”柱体取决于应用程序的需求，并且必须根据数据使用至少两种不同的策略进行计算。
https://stackoverflow.com/questions/51430816
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号