切比雪夫（最小区域法）球拟合算法

���迎关注更多精彩

关注我，学习常用算法与数据结构，一题多解，降维打击。

本期话题：切比雪夫（最小区域法）球拟合算法

相关背景和理论

点击前往

主要介绍了应用背景和如何转化成线性规划问题

球拟合输入和输出要求

输入

1. 10到631个点，全部采样自球附近上。
2. 每个点3个坐标，坐标精确到小数点后面20位。
3. 坐标单位是mm, 范围[-500mm, 500mm]。

输出

1. 1点X0表示 球心，用三个坐标表示。
2. 球半径r。
3. 球度F，所有点到球面距离最大的2倍。

精度要求

1. C点到标准球心距离不能超过0.0001mm。
2. r与标准半径的差不能超过0.0001mm。
3. F与标准球度误差不能超过0.00001mm。

球优化标函数

根据论文，球拟合转化成数学表示如下：

球参数化表示

1. 球心为1点X0 = (x0, y0, z0)。
2. 半径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=1MAX​n​∣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 )