根据贝塞尔曲线上的点反算t值

更新日期: 2019-09-07阅读: 2.1k标签: 运算

这是一个项目中遇到的实际需求。 场景是一个智能仓库管理系统,场景里面有直线和曲线构成的环穿轨道。环穿轨道上面会有小车运动,后台推动小车的两个点位A和B,其中A和B都会在轨道上面,前端需要根据这两个推送点,自动播放小车从A点沿轨道到B点的动画。下面是项目截图:


项目中使用的是二次贝塞尔曲线,所以本文也主要以二次贝塞尔曲线为讲解重点。 要实现上述动画,需要首先确定A点和B点在曲线上面的比例值t<sub>a</sub>和t<sub>b</sub>

最终的需求变成:“根据贝塞尔曲线上的点反算t值”。 大概有以下几种方法。现假设贝塞尔曲线上的点为点P(后续会用到该点)。


分片迭代

分片迭代是一种近似的方法。我们知道,二次贝塞尔曲线的公式如下: B(t) = (1-t)2 * P0 + 2t(1-t) * P1 + t2 * P2 其中: $t \in $[0,1],P0为二次贝塞尔曲线的起始点,P1为控制点,P2为终止点。

从以上公式,我们可以得到,对于任意给定的比例值t,可以求出对应该比例值的点B(t)。分片迭代思路是:现在加设把范围[0,1]平均分成N(比如100)等份,形成一系列的比例值t,对于每一个t值,求取对应的点B(t) ,然后让点B(t)和已知在贝塞尔曲线上的点P进行比较,如果点B(t)和点P之间的直线距离在一定的误差范围之内,则认为B(t)等于P,而此时的t值,就是我们要求的t值。 以下是主要代码

function computeT(p0,p1,p2,p) {
  var t = 0;
  for(var i = 0;i < 1000;i ++){
      var point = getPointOnQuadraticCurve(p0,p1,p2,t);//根据二次贝塞尔曲线公式求B(t),其中point = B(t)
      if(distance(point,p) < 0.01){ // 判断point和p点的距离是否在特定误差之内
        return t;
      }
      t+= 0.001;
  }
  return null;
}

上述分片迭代的方法,思路最简单,最直观。在精度要求不高的情况下是可以满足的。而在精度要求高的时候,即代码中的“特定误差”值要很小,可能会出现函数返回值为null的情况,在精度要求高的时候要能够计算出值,就要增加迭代次数,此时会极大增加性能消耗。比如上面代码的迭代次数可能会变成10000甚至10000。

迭代方法同样适用于三次贝塞尔曲线和更加高阶的贝塞尔曲线。


分片迭代优化版本

上面提到在精度要求高的情况下,要得到正确结果,要极大的增加迭代次数,造成性能的极大消耗。 有没有办法既提高精度,又不大量增加迭代次数呢? 经过笔者的思考,发现是可以的。想想假设要求的t值在0.5附近,那么我们只需要在0.5附近加大分片的数量,而不需要在其他地方(0.1~0.4,0.6~1.0)增加分片的数量。 应此升级版本的思路就是,先用比较粗的分片初步确定t值的一个大致范围,再在该范围之类,比较细的分片确定t值。注意这是个递归的过程,如果在第二次比较细的分片情况下,仍然不能确定t值,那么就确定一个t值的更小分范围;重复上面过程,直到找到t值为止。 大致步骤如下:

  • 首先,通过一个小的迭代次数进行分片迭代;
  • 在迭代的过程中如果找到了符合的比例值t,直接返回;
  • 在迭代的过程中同时记录离目标点P最近的t值,如果上一步未找到符合的t值,则进行下一步操作。
  • 上一步找到了离目标点P最近的t值,在t值的附近(t - step,t + step)(其中step为上一次分片的步进值)进行分片迭代查找,在迭代的过程中如果找到了符合的比例值t,直接返回。
  • 如果没找到,重复上面的不断缩小范围并加大分片精度的过程。 直到找到t值为止。

下面是示例代码:

function computeT(p0, p1, p2, p,startT = 0,endT = 1) {
  var t = startT;
  var minDistance = Infinity,
      minDistanceT = null;
  var step = (endT - startT) / 100;
  for (var i = 0; i < 100; i++) {
    var point = getPointOnQuadraticCurve(p0, p1, p2, t);
    var dst = distance(point,p);
    if (dst < minDistance) {
      minDistance = dst;
      minDistanceT = t;
    }
    if (dst < 0.0001) {
      return t;
    }
    t += step;
  }
  return computeT(p0, p1, p2, p, minDistanceT - step,minDistanceT + step);
}

以上过程虽然增加了一定的迭代次数,但是是常量级别的增加,而非数量级别的增加,所以会极大提高性能。 比如目标t值在0.5附近,第一次通过100次迭代可以确定t值的范围在0.4 ~ 0.6之间;然后进行第二次迭代,第二次迭代此次数仍然为100次,假设确定t值的范围在0.51 ~ 0.53之间;然后进行第三次迭代,第三次迭代此次数仍然为100次,此时可以获取t值为0.516,可以看出最多值迭代了300次。 假设总共经过第N次迭代,每次迭代次数为M,才找到t值,那么总共的迭代次数是N * M。

该迭代方法同样适用于三次贝塞尔曲线和更加高阶的贝塞尔曲线。而且相对于未优化的版本,该方法的性能好了很多。是适合所有贝塞尔曲线的比较好的反算t值的方法。


二分法

二分法的思路是:

  • 首先确定一个起始t值和结束t值t<sub>0</sub>和t<sub>1</sub>,初始值t<sub>0</sub> = 0,t<sub>1</sub> = 1。
  • 取t<sub>0</sub>和t<sub>1</sub>的中间值t<sub>m</sub> = (t<sub>0</sub>+t<sub>1</sub>)/2
  • 通过t<sub>m</sub>计算出点P<sub>m</sub>,如果P<sub>m</sub>和目标点P之间的距离在误差值范围之内,则t<sub>m</sub>为需要计算的目标t值。
  • 如果上一步P<sub>m</sub>和目标点P之间的距离不在误差值范围之内,则判断P<sub>m</sub>和目标点P的前后顺序,如果P<sub>m</sub>在目标点P的前面,则把t<sub>m</sub>赋值给t<sub>1</sub>;否则把t<sub>m</sub>赋值给t<sub>0</sub>。
  • 重复以上步骤直到找到合适的t<sub>m</sub>值。

上述步骤有一个难点: 如何判断P<sub>m</sub>和目标点P的前后顺序? 对于二次贝塞尔曲线,如下图所示:

 

其中,P0为起始点,P2为终止点,P1为控制点。 二次贝塞尔曲线有如下特点: 线段(P1,P0)、(P1,P2)和曲线相切,这也就意味着曲线一定在三角形(P0,P1,P2)之内,而且二次贝塞尔曲线本身不会自身相交,所有我们可以有如下结论,

对于曲线上面的点A,直线(P1,A)和线段(P0,P1)相交于点a;对于曲线上面的点B,直线(P1,B)和线段(P0,P1)相交于点b。点A和点B的先后顺序与点a和点b的先后顺序是一致的,而直线上面的点(a和b)的前后顺序是容易判断的。 也就是说如果点a在点b的前面,则点A也在点B的前面,反之亦然。如下图所示:

 

有了以上的结论,我们就找到了判断P<sub>m</sub>和目标点P的前后顺序的方法。

有了这个方法,加上前面描述的二分查找的步骤,可以得出示例代码如下:

function computeT2(p0,p1,p2,p,startT = 0,endT = 1) {
   var halfT  = (startT + endT) / 2;
   var halfPoint = getPointOnQuadraticCurve(p0,p1,p2,halfT);
    if(distance(halfPoint,p) < 0.0001){
      return halfT;
   }
   //求交点:
   var inter1 = segmentsIntr(p0,p2,p1,p);
   var inter2 = segmentsIntr(p0,p2,p1,halfPoint);
  
   var r1 = interpolationRate(p0,inter1,p2),
       r2 = interpolationRate(p0,inter2,p2);
   
   if(r1 > r2){
       startT = halfT;  
   }else {
     endT = halfT;
   }
   return computeT2(p0,p1,p2,p,startT,endT);
}

解方程

前面说过,贝塞尔曲线的公式如下: B(t) = (1-t)2 * P0 + 2t(1-t) * P1 + t2 * P2 其中: $t \in $[0,1],P0为二次贝塞尔曲线的起始点,P1为控制点,P2为终止点。 分别表示成x和y的方程,则可以表示如下:

  • x<sub>P</sub> = (1-t)<sup>2</sup> * x<sub>P0</sub> + 2t(1-t) * x<sub>P1</sub> + t<sup>2</sup> * x<sub>P2</sub>
  • y<sub>P</sub> = (1-t)<sup>2</sup> * y<sub>P0</sub> + 2t(1-t) * y<sub>P1</sub> + t<sup>2</sup> * y<sub>P2</sub>

实际上就是两个变量t的二次元方程,取上面任意一个方程,带入相关的值解方程,方程的解即为我们要求的目标t值。

整理方程: x<sub>P</sub> = (1-t)<sup>2</sup> * x<sub>P0</sub> + 2t(1-t) * x<sub>P1</sub> + t<sup>2</sup> * x<sub>P2</sub>,可以得出二次方程如下: (x<sub>P2</sub> + x<sub>P0</sub> - 2 * x<sub>P1</sub> ) * t<sup>2</sup> + 2*(x<sub>P1</sub> - x<sub>P0</sub>) * t + (x<sub>P0</sub> - x<sub>P</sub>) = 0。 我们已知二次方程的: a*t<sup>2</sup> + b * t + c = 0的解为:

  • 如果a = 0,则解为 -c/b
  • 如果a != 0,解如下图所示:
  •  

应此令:

  • a = (x<sub>P2</sub> + x<sub>P0</sub> - 2 * x<sub>P1</sub> )
  • b = 2*(x<sub>P1</sub> - x<sub>P0</sub>)
  • c = (x<sub>P0</sub> - x<sub>P</sub>) 可以方便求出方程的解。

需要注意的是,二次方程的解可能会有两个。如果求出的解有两个怎么办呢。 首先我们知道贝塞尔曲线的t值的范围是$t \in $[0,1],所以如果有两个解:

  • 其中一个不再[0,1]的范围之内,则另外一个解就是目标t值。(注意不可能两个都不在[0,1]范围之内,因为我们知道,目标点P在贝塞尔曲线上面)。
  • 如果两个解都在[0,1]范围之内,那就把两个解再带入贝塞尔曲线的公式,分别求出两个B(t)点,那个离目标点P近,就取那个解。

下面是示例代码,其中函数equation2用于解曲线的方程:

function computeT(p0,p1,p2,p) {
    let interpolationx =  (p1.x - p0.x) / (p2.x - p0.x);
    let tt;
    if(interpolationx >= 0 && interpolationx <= 1){
      let ty = equation2(p0.y,p1.y,p2.y,p.y);
      return ty;
    }else{
      tt = equation2(p0.x,p1.x,p2.x,p.x);
      if(tt.tt1){
        var pointTest = getPointOnQuadraticCurve(p0,p1,p2,tt.tt1);
        if(distance(pointTest,p) < 0.01){
          return tt.tt1;
        }else{
          return tt.tt2;
        }
      }else{
        return tt;
      }
    }
}

function equation2(z0,z1,z2,zp){ // z0、z1,z2代表P0、P1、P2的x坐标值或者y坐标值,zp代表目标点P的x坐标值或者y坐标值
    var a = z0 - z1 * 2 + z2,
      b = 2*(z1 - z0),
      c = z0 - zp;
  var tt = null;
  if(a == 0 && b != 0){
    tt = - c / b;
  } else {
    var sq = Math.sqrt( b * b - 4 * a * c );
    var tt1 = (sq - b)/ (2 * a),
        tt2 = (-sq - b) / (2 * a);
    // console.log("tt1,tt2:",tt1,tt2); 
    if((tt1 <= 1 && tt1>= 0) && (tt2 <= 1 && tt2>= 0)){
      return {tt1,tt2};
    }else if(tt1 <= 1 && tt1>= 0){
      tt = tt1;
    }else {
      tt = tt2;
    }
  }
  return tt;
}


几种方法的比较

从性能方面来说:

  • 解方程的方式是最快的
  • 二分法和分片迭代的优化版次之
  • 原始的分片迭代方法最差

从通用性来说,分片迭代的方式是适合任意阶的贝塞尔曲线。但是考虑到性能问题所以分片迭代的优化版是通用性最好的求解方法。

欢迎关注公众号“ITman彪叔”。彪叔,拥有10多年开发经验,现任公司系统架构师、技术总监、技术培训师、职业规划师。


链接: https://www.fly63.com/article/detial/5734

js除了Math.floor方法,还可以通过位运算|,>>实现向下取整

我们都知道通过Math.floor()方法可实现数值的向下取整,得到小于或等于该数字的最大整数。除了Math.floor方法,还可以使用位运算|,>>来实现向下取整哦

es6 扩展运算符 三个点(...)

扩展运算符( spread )是三个点(...)。它好比 rest 参数的逆运算,将一个数组转为用逗号分隔的参数序列。

巧用JS位运算

位运算的方法在其它语言也是一样的,不局限于JS,所以本文提到的位运算也适用于其它语言。位运算是低级的运算操作,所以速度往往也是最快的

js中使用位运算,让执行效率更高

平常的数值运算,其本质都是先转换成二进制再进行运算的,而位运算是直接进行二进制运算,所以原则上位运算的执行效率是比较高的,由于位运算的博大精深,下面通过一些在js中使用位运算的实例

js各种取整方式及方法_四舍五入、向上取整、向下取整

js实现:四舍五入、向上取整、向下取整等方法。parseInt、Math.ceil、Math.round、Math.floor、toFixed等的使用

JavaScript循环计数器

JS经常会遇到延迟执行的动作,并且失败后自动尝试,尝试N次之后就不再尝试的需求,今天刚好又遇到,于是写个闭包,以后不断完善继续复用。检查并计数第一个参数用来标记是尝试哪个动作的,第二个参数是最大尝试次数

js 位运算符_js按位运算符及其妙用

大多数语言都提供了按位运算符,恰当的使用按位运算符有时候会取得的很好的效果。在我看来按位运算符应该有7个:& 按位与、| 按位或、^ 按位异或、~ 按位非

PHP取整、四舍五入取整、向上取整、向下取整、小数截取

PHP取整数函数常用的四种方法:1.直接取整,舍弃小数,保留整数:intval(); 2.四舍五入取整:round(); 3.向上取整,有小数就加1:ceil(); 4.向下取整:floor()。

JavaScript 中的相等操作符 ( 详解 [] == []、[] == ![]、{} == !{} )

ECMAScript 中的相等操作符由两个等于号 ( == ) 表示,如果两个操作数相等,则返回 true。相等操作符会先转换操作数(通常称为强制转型),然后比较它们的相等性。

关于js开发中保留小数位计算函数(以向上取整或向下取整的方式保留小数)

前端工作中经常遇到数字计算保留小数问题,由于不是四舍五入的方式不能使用toFixed函数,本文采用正则表达式匹配字符串的方式,解决对数字的向上或向下保留小数问题:

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!