点到指定Bezier曲线的最短距离

 
Bezier曲线本质上是一个多项式。
 
三次曲线Q：
$\begin{aligned} Q(u) &= (1-u)^3P_0+3(1-u)^2uP_1+3(1-u)u^2P_2+u^3P_3\\ &=nu^3+ru^2+su+v \end{aligned}$Q(u)​=(1−u)3P0​+3(1−u)2uP1​+3(1−u)u2P2​+u3P3​=nu3+ru2+su+v​

 
点P到曲线Q的距离D(u)：
$D(u)=|Q(u)-P|^2=(Q_x-P_x)^2+(Q_y-P_y)^2+(Q_z-P_z)^2 \quad (1)$D(u)=∣Q(u)−P∣2=(Qx​−Px​)2+(Qy​−Py​)2+(Qz​−Pz​)2(1)
 
求最短距离，即最小值优化问题：
$D^2(u)_{min}=min{ {\sum^1_{u=0}D^2(u)} } \quad (2)$D2(u)min​=minu=0∑1​D2(u)(2)

 

二分区间法求解

 

算法流程：

 

1.分别计算点P到数据点Pi (i=0,1,2,3)的距离，取最小距离对应点位Pj

2.取Pj对应的节点ui为初始节点

3.选取合适的区间值 interval

4.根据式(1),计算节点 ui+interval,ui-interval,ui处的距离 d1,d2,d0

5.如果d1或者d2小于d0，将ui的值更改为ui+interval或ui-interval

6.如果d1、d2都大于d0，将区间interval减半为interval/2

7.重复以上步骤，直到d1 d2 d0之间的差值满足设置的精度

 

Python仿真结果

图中，

黑色点位为给定的点位P；

红色点位为曲线Q（u）上距离P最近的点Pmin；

黑色线为P到曲线Q的距离D(u)；

红色线为拟合的Bezier曲线Q（u）；

黑色点的y坐标不变，横坐标不断向右移动。由动图可见，计算得到的Pmin始终跟随D(u)的最小距离位置，

最短距离点计算成功！

 

牛顿迭代法求解

 
由数学知识可知，为求解式(2)，即求解式(1)在区间[0,1]的极小值，此问题即转化为求极值问题。
 
是(1)的极值即出现在其导数值为0的点，其导数为：
$D^{'}(u)=2(Q_x-P_x)Q^{'}_x+2(Q_y-P_y)Q^{'}_y+2(Q_z-P_z)Q^{'}_z=0 \quad (3)\\ f(u) = (Q_x-P_x)Q^{'}_x+(Q_y-P_y)Q^{'}_y+(Q_z-P_z)Q^{'}_z\\ f^{'}(u)=Q_x^{'2}+(Q_x-P_x)Q^{''}_x+Q_y^{'2}+(Q_y-P_y)Q^{''}_y+Q_z^{'2}+(Q_z-P_z)Q^{''}_z$D′(u)=2(Qx​−Px​)Qx′​+2(Qy​−Py​)Qy′​+2(Qz​−Pz​)Qz′​=0(3)f(u)=(Qx​−Px​)Qx′​+(Qy​−Py​)Qy′​+(Qz​−Pz​)Qz′​f′(u)=Qx′2​+(Qx​−Px​)Qx′′​+Qy′2​+(Qy​−Py​)Qy′′​+Qz′2​+(Qz​−Pz​)Qz′′​
 
求解式子（3）,可以使用牛顿迭代公式求解：
$u_{k+1}=u_k-\frac{f(u)}{f^{'}(u)} \quad (4)$uk+1​=uk​−f′(u)f(u)​(4)

 
牛顿迭代公式求解速度很快，但是对初值的选取比较敏感，如果初值选取的不好，有可能出现无解的情况。

 
二分区间法求解求解比较稳定，但是其速度比较慢。有一种思路是将二分区间法和牛顿迭代法结合，先计算一个粗略的初始值，再用

值的选取比较敏感，如果初值选取的不好，有可能出现无解的情况。

 
二分区间法求解求解比较稳定，但是其速度比较慢。有一种思路是将二分区间法和牛顿迭代法结合，先计算一个粗略的初始值，再用牛顿迭代法求解，以加快算法速度。