切比雪夫(最小区域法)球拟合算法
欢迎关注更多精彩
关注我,学习常用算法与数据结构,一题多解,降维打击。
本期话题:切比雪夫(最小区域法)球拟合算法
相关背景和理论
点击前往
主要介绍了应用背景和如何转化成线性规划问题
球拟合输入和输出要求
输入
- 10到631个点,全部采样自球附近上。
- 每个点3个坐标,坐标精确到小数点后面20位。
- 坐标单位是mm, 范围[-500mm, 500mm]。
输出
- 1点X0表示 球心,用三个坐标表示。
- 球半径r。
- 球度F,所有点到球面距离最大的2倍。
精度要求
- C点到标准球心距离不能超过0.0001mm。
- r与标准半径的差不能超过0.0001mm。
- F与标准球度误差不能超过0.00001mm。
球优化标函数
根据论文,球拟合转化成数学表示如下:
球参数化表示
- 球心为1点X0 = (x0, y0, z0)。
- 半径r。
球方程 ( x − x 0 ) 2 + ( y − y 0 ) 2 + ( z − z 0 ) 2 = r 2 球方程 (x-x_0)^2+(y-y_0)^2+(z-z_0)^2=r^2 球方程(x−x0)2+(y−y0)2+(z−z0)2=r2
点到球距离
第i个点 pi(xi, yi, zi)。
根据点乘得到距离
d i = ∥ ( p i − X 0 ) ∥ − r d_i =\left \| (p_i-X_0) \right \|-r di=∥(pi−X0)∥−r
展开一下:
d i = r i − r d_i = r_i -r di=ri−r
r i = ( x i − x 0 ) 2 + ( y i − y 0 ) 2 + ( z i − z 0 ) 2 r_i = \sqrt{(x_i-x_0)^2 + (y_i-y_0)^2+(z_i-z_0)^2} ri=(xi−x0)2+(yi−y0)2+(zi−z0)2
优化能量方程
能量方程 H = f ( X 0 , r ) = max 1 n ∣ d i ∣ H=f(X0, r)=\displaystyle \max_1^n {|d_i|} H=f(X0,r)=1maxn∣di∣
上式是一个4函数,X0, r是未知量,拟合球的过程也可以理解为优化X0, r使得方程H最小。
转化为线性规划
设 a = ( x 0 , y 0 , z 0 , r ) , d i = F ( x i ; a ) , 引入 Γ = M A X i = 1 n ∣ d i ∣ 设a=(x_0, y_0, z_0, r), d_i=F(x_i;\ a), 引入\Gamma=\overset n{\underset {i=1}{MAX}}\;|d_i| 设a=(x0,y0,z0,r),di=F(xi; a),引入Γ=i=1MAXn∣di∣
根据上述定义,可以将原来的最值问题转化为下述条件
对于所有点应该满足
F ( x i ; a ) ≤ Γ , ( F ( x i ; a ) > 0 ) F(x_i;\ a)\le \Gamma, (F(x_i;\ a)>0) F(xi; a)≤Γ,(F(xi; a)>0)
− F ( x i ; a ) ≤ Γ , ( F ( x i ; a )
还没有评论,来说两句吧...