這是一個項目中遇到的實際需求。場景是一個智能倉庫管理系統，場景裡面有直線和曲線構成的環穿軌道。環穿軌道上面會有小車運動，背景推動小車的兩個點位A和B，其中A和B都會在軌道上面，前端需要根據這兩個推送點，自動播放小車從A點沿軌道到B點的動畫。下面是項目截圖：
項目中使用的是二次貝塞爾曲線，是以本文也主要以二次貝塞爾曲線為講解重點。要實作上述動畫，需要首先确定A點和B點在曲線上面的比例值ta和tb
最終的需求變成：“根據貝塞爾曲線上的點反算t值”。 大概有以下幾種方法。現假設貝塞爾曲線上的點為點P(後續會用到該點)。
分片疊代
分片疊代是一種近似的方法。我們知道，二次貝塞爾曲線的公式如下：B(t) = (1-t)2 P0 + 2t(1-t) P1 + t2 * P2其中： $t in $[0,1]，P0為二次貝塞爾曲線的起始點，P1為控制點，P2為終止點。
如果你對于上面的知識點不是很熟悉，建議學習貝塞爾曲線相關知識。推薦學習本人的專欄https://xiaozhuanlan.com/canvas, 裡面有專門的章節對貝塞爾曲線進行了全面詳細的講解。本文也是從該專欄的文章中摘錄并适當改編而成的。
從以上公式，我們可以得到，對于任意給定的比例值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值t0和t1，初始值t0 = 0，t1 = 1。
- 取t0和t1的中間值tm = (t0+t1)/2
- 通過tm計算出點Pm，如果Pm和目标點P之間的距離在誤內插補點範圍之内，則tm為需要計算的目标t值。
- 如果上一步Pm和目标點P之間的距離不在誤內插補點範圍之内，則判斷Pm和目标點P的前後順序，如果Pm在目标點P的前面，則把tm指派給t1；否則把tm指派給t0。
- 重複以上步驟直到找到合适的tm值。
上述步驟有一個難點： 如何判斷Pm和目标點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的前面，反之亦然。如下圖所示：
有了以上的結論，我們就找到了判斷Pm和目标點P的前後順序的方法。
如果你對上述結論不熟悉，建議學習貝塞爾曲線的相關知識，推薦學習本人的專欄https://xiaozhuanlan.com/canvas, 裡面有專門的章節對貝塞爾曲線進行了全面詳細的講解。本文也是從該專欄的文章中摘錄并适當改編而成的。
有了這個方法，加上前面描述的二分查找的步驟，可以得出示例代碼如下：
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的方程，則可以表示如下：
- xP = (1-t)2 xP0 + 2t(1-t) xP1 + t2 * xP2
- yP = (1-t)2 yP0 + 2t(1-t) yP1 + t2 * yP2
實際上就是兩個變量t的二次元方程，取上面任意一個方程，帶入相關的值解方程，方程的解即為我們要求的目标t值。
整理方程: xP = (1-t)2 xP0 + 2t(1-t) xP1 + t2 * xP2，可以得出二次方程如下：(xP2 + xP0 - 2 xP1 ) t2 + 2(xP1 - xP0) t + (xP0 - xP) = 0。我們已知二次方程的： at2 + b t + c = 0的解為：
- 如果a = 0，則解為 -c/b
- 如果a != 0，解如下圖所示：
應此令：
- a = (xP2 + xP0 - 2 * xP1 )
- b = 2*(xP1 - xP0)
- c = (xP0 - xP)
- 可以友善求出方程的解。
需要注意的是，二次方程的解可能會有兩個。如果求出的解有兩個怎麼辦呢。 首先我們知道貝塞爾曲線的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: