這是一個(gè)項(xiàng)目中遇到的實(shí)際需求复旬。
場(chǎng)景是一個(gè)智能倉(cāng)庫(kù)管理系統(tǒng)诸蚕，場(chǎng)景里面有直線和曲線構(gòu)成的環(huán)穿軌道。環(huán)穿軌道上面會(huì)有小車運(yùn)動(dòng)自赔，后臺(tái)推動(dòng)小車的兩個(gè)點(diǎn)位A和B妈嘹，其中A和B都會(huì)在軌道上面，前端需要根據(jù)這兩個(gè)推送點(diǎn)绍妨，自動(dòng)播放小車從A點(diǎn)沿軌道到B點(diǎn)的動(dòng)畫(huà)润脸。下面是項(xiàng)目截圖：

項(xiàng)目截圖

項(xiàng)目中使用的是二次貝塞爾曲線，所以本文也主要以二次貝塞爾曲線為講解重點(diǎn)他去。
要實(shí)現(xiàn)上述動(dòng)畫(huà)津函，需要首先確定A點(diǎn)和B點(diǎn)在曲線上面的比例值t_a和t_b

最終的需求變成：“根據(jù)貝塞爾曲線上的點(diǎn)反算t值”。 大概有以下幾種方法」乱常現(xiàn)假設(shè)貝塞爾曲線上的點(diǎn)為點(diǎn)P（后續(xù)會(huì)用到該點(diǎn)）尔苦。

分片迭代

分片迭代是一種近似的方法。我們知道行施，二次貝塞爾曲線的公式如下：
B(t) = (1-t)2 * P0 + 2t(1-t) * P1 + t2 * P2
其中： [0,1]允坚，P0為二次貝塞爾曲線的起始點(diǎn)，P1為控制點(diǎn)蛾号，P2為終止點(diǎn)稠项。

如果你對(duì)于上面的知識(shí)點(diǎn)不是很熟悉，建議學(xué)習(xí)貝塞爾曲線相關(guān)知識(shí)鲜结。推薦學(xué)習(xí)本人的專欄Canvas高級(jí)進(jìn)階, 里面有專門的章節(jié)對(duì)貝塞爾曲線進(jìn)行了全面詳細(xì)的講解展运。本文也是從該專欄的文章中摘錄并適當(dāng)改編而成的活逆。

從以上公式，我們可以得到拗胜，對(duì)于任意給定的比例值t蔗候，可以求出對(duì)應(yīng)該比例值的點(diǎn)B(t)。分片迭代思路是：現(xiàn)在加設(shè)把范圍[0,1]平均分成N（比如100）等份埂软，形成一系列的比例值t锈遥，對(duì)于每一個(gè)t值，求取對(duì)應(yīng)的點(diǎn)B(t) 勘畔，然后讓點(diǎn)B(t)和已知在貝塞爾曲線上的點(diǎn)P進(jìn)行比較所灸，如果點(diǎn)B(t)和點(diǎn)P之間的直線距離在一定的誤差范圍之內(nèi)，則認(rèn)為B(t)等于P炫七，而此時(shí)的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);//根據(jù)二次貝塞爾曲線公式求B(t)万哪，其中point = B(t)
      if(distance(point,p) < 0.01){ // 判斷point和p點(diǎn)的距離是否在特定誤差之內(nèi)
        return t;
      }
      t+= 0.001;
  }
  return null;
}

上述分片迭代的方法懦尝，思路最簡(jiǎn)單，最直觀壤圃。在精度要求不高的情況下是可以滿足的陵霉。而在精度要求高的時(shí)候，即代碼中的“特定誤差”值要很小伍绳，可能會(huì)出現(xiàn)函數(shù)返回值為null的情況踊挠，在精度要求高的時(shí)候要能夠計(jì)算出值，就要增加迭代次數(shù)冲杀，此時(shí)會(huì)極大增加性能消耗效床。比如上面代碼的迭代次數(shù)可能會(huì)變成10000甚至10000。

迭代方法同樣適用于三次貝塞爾曲線和更加高階的貝塞爾曲線权谁。

分片迭代優(yōu)化版本

上面提到在精度要求高的情況下剩檀，要得到正確結(jié)果，要極大的增加迭代次數(shù)旺芽，造成性能的極大消耗沪猴。 有沒(méi)有辦法既提高精度，又不大量增加迭代次數(shù)呢采章？ 經(jīng)過(guò)筆者的思考运嗜，發(fā)現(xiàn)是可以的。想想假設(shè)要求的t值在0.5附近悯舟，那么我們只需要在0.5附近加大分片的數(shù)量担租，而不需要在其他地方（0.1_0.4，0.61.0）增加分片的數(shù)量抵怎。 應(yīng)此升級(jí)版本的思路就是奋救，先用比較粗的分片初步確定t值的一個(gè)大致范圍岭参，再在該范圍之類，比較細(xì)的分片確定t值尝艘。注意這是個(gè)遞歸的過(guò)程演侯，如果在第二次比較細(xì)的分片情況下，仍然不能確定t值利耍，那么就確定一個(gè)t值的更小分范圍；重復(fù)上面過(guò)程盔粹，直到找到t值為止隘梨。
大致步驟如下：

• 首先，通過(guò)一個(gè)小的迭代次數(shù)進(jìn)行分片迭代舷嗡；
• 在迭代的過(guò)程中如果找到了符合的比例值t轴猎，直接返回；
• 在迭代的過(guò)程中同時(shí)記錄離目標(biāo)點(diǎn)P最近的t值进萄，如果上一步未找到符合的t值捻脖，則進(jìn)行下一步操作。
• 上一步找到了離目標(biāo)點(diǎn)P最近的t值中鼠，在t值的附近(t - step,t + step)(其中step為上一次分片的步進(jìn)值)進(jìn)行分片迭代查找可婶，在迭代的過(guò)程中如果找到了符合的比例值t，直接返回援雇。
• 如果沒(méi)找到矛渴，重復(fù)上面的不斷縮小范圍并加大分片精度的過(guò)程。 直到找到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);
}

以上過(guò)程雖然增加了一定的迭代次數(shù)具温，但是是常量級(jí)別的增加，而非數(shù)量級(jí)別的增加筐赔，所以會(huì)極大提高性能。 比如目標(biāo)t值在0.5附近，第一次通過(guò)100次迭代可以確定t值的范圍在0.4 ~ 0.6之間膳音；然后進(jìn)行第二次迭代姐刁，第二次迭代此次數(shù)仍然為100次，假設(shè)確定t值的范圍在0.51 ~ 0.53之間贿肩；然后進(jìn)行第三次迭代鳞绕，第三次迭代此次數(shù)仍然為100次，此時(shí)可以獲取t值為0.516尸曼，可以看出最多值迭代了300次们何。 假設(shè)總共經(jīng)過(guò)第N次迭代，每次迭代次數(shù)為M控轿，才找到t值冤竹，那么總共的迭代次數(shù)是N * M拂封。

該迭代方法同樣適用于三次貝塞爾曲線和更加高階的貝塞爾曲線。而且相對(duì)于未優(yōu)化的版本鹦蠕，該方法的性能好了很多冒签。是適合所有貝塞爾曲線的比較好的反算t值的方法。

二分法

二分法的思路是：

• 首先確定一個(gè)起始t值和結(jié)束t值t₀和t₁钟病，初始值t₀ = 0萧恕，t₁ = 1。
• 取t₀和t₁的中間值t_m = (t₀+t₁)/2
• 通過(guò)t_m計(jì)算出點(diǎn)P_m肠阱，如果P_m和目標(biāo)點(diǎn)P之間的距離在誤差值范圍之內(nèi)票唆，則t_m為需要計(jì)算的目標(biāo)t值。
• 如果上一步P_m和目標(biāo)點(diǎn)P之間的距離不在誤差值范圍之內(nèi)屹徘，則判斷P_m和目標(biāo)點(diǎn)P的前后順序走趋，如果P_m在目標(biāo)點(diǎn)P的前面，則把t_m賦值給t₁噪伊；否則把t_m賦值給t₀簿煌。
• 重復(fù)以上步驟直到找到合適的t_m值。

上述步驟有一個(gè)難點(diǎn)： 如何判斷P_m和目標(biāo)點(diǎn)P的前后順序鉴吹？
對(duì)于二次貝塞爾曲線姨伟，如下圖所示：

二次貝塞爾曲線

對(duì)于曲線上面的點(diǎn)A造垛，直線(P1,A)和線段(P0,P1)相交于點(diǎn)a魔招；對(duì)于曲線上面的點(diǎn)B，直線(P1,B)和線段(P0,P1)相交于點(diǎn)b五辽。點(diǎn)A和點(diǎn)B的先后順序與點(diǎn)a和點(diǎn)b的先后順序是一致的办斑，而直線上面的點(diǎn)（a和b）的前后順序是容易判斷的。 也就是說(shuō)如果點(diǎn)a在點(diǎn)b的前面，則點(diǎn)A也在點(diǎn)B的前面乡翅，反之亦然鳞疲。如下圖所示：

判斷先后順序

如果你對(duì)上述結(jié)論不熟悉尚洽，建議學(xué)習(xí)貝塞爾曲線的相關(guān)知識(shí)，推薦學(xué)習(xí)本人的專欄Canvas高級(jí)進(jìn)階, 里面有專門的章節(jié)對(duì)貝塞爾曲線進(jìn)行了全面詳細(xì)的講解靶累。本文也是從該專欄的文章中摘錄并適當(dāng)改編而成的腺毫。

有了這個(gè)方法，加上前面描述的二分查找的步驟挣柬，可以得出示例代碼如下：

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;
   }
   //求交點(diǎn)：
   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);
}

解方程

前面說(shuō)過(guò)潮酒，貝塞爾曲線的公式如下：
B(t) = (1-t)2 * P0 + 2t(1-t) * P1 + t2 * P2
其中： [0,1]，P0為二次貝塞爾曲線的起始點(diǎn)凛忿，P1為控制點(diǎn)澈灼，P2為終止點(diǎn)竞川。
分別表示成x和y的方程店溢，則可以表示如下：

• x_P = (1-t)² * x_P0 + 2t(1-t) * x_P1 + t² * x_P2
• y_P = (1-t)² * y_P0 + 2t(1-t) * y_P1 + t² * y_P2

實(shí)際上就是兩個(gè)變量t的二次元方程，取上面任意一個(gè)方程委乌，帶入相關(guān)的值解方程床牧，方程的解即為我們要求的目標(biāo)t值。

整理方程: x_P = (1-t)² * x_P0 + 2t(1-t) * x_P1 + t² * x_P2遭贸，可以得出二次方程如下：
(x_P2 + x_P0 - 2 * x_P1 ) * t² + 2(x_P1 - x_P0) * t + (x_P0 - x_P) = 0戈咳。
我們已知二次方程的： at² + b * t + c = 0的解為：

• 如果a = 0，則解為 -c/b

• 如果a != 0壕吹，解如下圖所示：

  
  
  方程的解

應(yīng)此令：

• a = (x_P2 + x_P0 - 2 * x_P1 )
• b = 2*(x_P1 - x_P0)
• c = (x_P0 - x_P)
  可以方便求出方程的解著蛙。

需要注意的是，二次方程的解可能會(huì)有兩個(gè)耳贬。如果求出的解有兩個(gè)怎么辦呢踏堡。 首先我們知道貝塞爾曲線的t值的范圍是[0,1]，所以如果有兩個(gè)解：

• 其中一個(gè)不再[0,1]的范圍之內(nèi)咒劲，則另外一個(gè)解就是目標(biāo)t值顷蟆。（注意不可能兩個(gè)都不在[0,1]范圍之內(nèi)，因?yàn)槲覀冎栏辏繕?biāo)點(diǎn)P在貝塞爾曲線上面）帐偎。
• 如果兩個(gè)解都在[0,1]范圍之內(nèi)，那就把兩個(gè)解再帶入貝塞爾曲線的公式蛔屹，分別求出兩個(gè)B(t)點(diǎn)削樊，那個(gè)離目標(biāo)點(diǎn)P近，就取那個(gè)解兔毒。

下面是示例代碼,其中函數(shù)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坐標(biāo)值或者y坐標(biāo)值摇肌，zp代表目標(biāo)點(diǎn)P的x坐標(biāo)值或者y坐標(biāo)值
    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;
}

幾種方法的比較

從性能方面來(lái)說(shuō)：

• 解方程的方式是最快的
• 二分法和分片迭代的優(yōu)化版次之
• 原始的分片迭代方法最差

從通用性來(lái)說(shuō)，分片迭代的方式是適合任意階的貝塞爾曲線仪际。但是考慮到性能問(wèn)題所以分片迭代的優(yōu)化版是通用性最好的求解方法围小。