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

 
Bezier曲线本质上是一个多项式
 
三次曲线Q:

点P到曲线Q的距离D(u):

 
求最短距离,即最小值优化问题:

二分区间法求解

 

算法流程:

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的点,其导数为:

 
求解式子(3),可以使用牛顿迭代公式求解:

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

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