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

���迎关注更多精彩

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

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

相关背景和理论

点击前往

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

平拟合输入和输出要求

输入

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

输出

1. 平面上一点X0，用三个坐标表示。
2. 法向A。
3. 平面度F，所有点到平面距离最大的2倍。

精度要求

1. X0点平面距离不能超过0.0001mm。
2. 法向A与标准法向夹角不能超过0.0000001rad。
3. F与标准平面度误差不能超过0.00001mm。

平面优化标函数

根据认证要求，平面拟合转化成数学表示如下：

平面参数化表示

1. 平面上1点X0 = (x0, y0, z0)。
2. 方向单位向量A=(a,b,c)。

点到平面距离

第i个点 pi(xi, yi, zi)。

根据点乘得到距离

d i = ∥ ( p i − X 0 ) ⋅ A ∥ ∥ A ∥ d_i = \frac { \left \| (p_i-X_0)\cdot A \right \|}{\left \| A \right \|} di​=∥A∥∥(pi​−X0​)⋅A∥​

展开一下：

d i = a ( x i − x 0 ) + b ( y i − y 0 ) + c ( z i − z 0 ) a 2 + b 2 + c 2 d_i = \frac {a(x_i-x_0) + b(y_i-y_0) + c(z_i-z_0)} {\sqrt{a^2+b^2+c^2}} di​=a2+b2+c2 ​a(xi​−x0​)+b(yi​−y0​)+c(zi​−z0​)​

优化能量方程

能量方程 H = f ( X 0 , A ) = max ⁡ 1 n ∣ d i ∣ H=f(X0, A)=\displaystyle \max_1^n {|d_i|} H=f(X0,A)=1maxn​∣di​∣

X0, A是未知量，拟合平面的过程也可以理解为优化X0, A使得方程H最小。

如何3个参数表示平面

如果直接拿6个参数去做迭代，1是比较麻烦，会出现比较难解的方向，2是平面上的点有很多个，结果不唯一。

当平面法向与Z轴偏差比较小的时候可以使用3个参数来表示。

如上图，绿线为Z轴，橙色线为XOY平面。

由于法向与Z轴比较相近，可以设法向为(a, b, 1), a,b 是比较小的量。

现在表示 平面还需要一个点，规定点必须在以(a,b,1)为法向过0点的直线上。

就有直线公式 x0/a=y0/b=z0/c

那么只要知道z0就可知 x0=az0, y0=bz0.

综上，可以使用a, b, z0 表示一个法向与Z轴相近的 平面。

转化为线性规划（法向与Z轴接近）

设 a = ( z 0 , A a , A b ) , d i = F ( x i ;   a ) , 引入 Γ ＝ M A X i = 1 n    ∣ d i ∣ 设a=(z_0, A_a, A_b), d_i=F(x_i;\ a), 引入\Gamma＝\overset n{\underset {i=1}{MAX}}\;|d_i| 设a=(z0​,Aa​,Ab​),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 )