如何確定在一個終點的立方貝塞爾路徑曲率

Question

我一直在使用貝塞爾路徑繪製我需要的曲線的項目。我的項目中的每個基本形狀都包含三條首尾相連的立方貝塞爾曲線，以便斜坡與它們相遇的地方相匹配。

我需要解決的基本問題是由三條貝塞爾曲線構成的複合曲線是否與自身相交。考慮了一段時間後，我發現考慮到曲線的限制，我可以將任務簡化爲其他內容：

三條貝塞爾路徑中的每條路徑的曲率在曲率方向上應該是相對的到它所抵靠的曲線。換句話說，應該有一個拐點，一條貝塞爾曲線與另一條曲線相鄰。如果不是這種情況，我想拒絕生成曲線的參數集並選擇其他集。

在任何情況下，我的基本問題是如何檢測曲線是否存在拐點彼此相鄰的拐點。

在圖中，三條貝塞爾曲線中的每一條都使用不同的顏色顯示。左邊的黑色曲線在與紅色曲線相交處相反的方向上彎曲，但右邊的黑色曲線在相同的方向上曲線。有一個拐點在紅色和左邊黑色曲線相交處，但不在紅色和右邊黑色曲線相交處。

編輯： 下面，我添加了另一個形象，顯示出封閉貝塞爾曲線的多邊形。黑色曲線中顯示的多邊形交叉線測試的是一個拐點，而不是一個循環。我猜測一條曲線與另一條曲線相交可以通過檢查包圍多邊形是否相交來測試，如紅色和藍色曲線所示。

P.S.由於存在一些關於約束的問題，我將在此處列出其中的一些：

• 最左邊的點和最右邊的點具有相同的y值。
• 最左端控制點的x值小於最右端控制點的x值
  。這使得黑色和藍色曲線不會相互交叉。
• 最左邊和最右邊的點的斜率在水平度的+/- 10 之內。
• 黑紅曲線和 紅藍曲線大約在 三分之一分滿曲線。我沒有確切的數字，但是一個樣本界限應該是 紅色曲線左端的x值介於最右邊點的x值的25％ 和40％之間。
• 交點的y值是整個寬度的+/-一小部分 。
• 交叉點處的斜率大於0.6且<爲3.0（正數或 爲負數）。

Answer 1

之一確定性的方式來檢查一個貝塞爾曲線具有雙點或自相交是計算逆方程和評價根，由於貝齊爾曲線的反轉方程始終爲零在自我交叉點。 正如在本例中由T.W.Sederberg –course notes所詳述的那樣。然後，爲了檢測兩個貝塞爾曲線（問題中的紅色和黑色）是否相互交叉，有幾種方法（更容易實現）和bezier clipping（效率和代碼複雜度非常好的平衡），隱含（不是值得）。

但是，更有效的方法可能是將曲線細分爲小線段並找到交點。 Here is one way to do it。特別是當你有興趣知道路徑是否自相交，但不在精確的交點處時。

如果你對分段貝塞爾曲線（或者上面提到的@Pomax的poly-bezier）的CV的位置有明確的假設，你可以嘗試一下你在問題中提到的基於曲率的方法。

下面是與問題類似的路徑上的曲率圖。在類似的情況下，似乎這可能會給你你正在尋找的解決方案。另外，在一個風口浪尖的情況下，看起來這個快速和骯髒的方法仍然工作！

Answer 2

曲率的公式爲適度簡單。你只需要曲率的符號，所以你可以跳過一點數學。你基本上對第一和第二衍生產品交叉產品的信號感興趣。

此簡化僅適用於曲線連接平穩。如果沒有相同的切線，則需要更復雜的測試。

曲線P的曲率符號：

ax = P[1].x - P[0].x;    // a = P1 - P0 
ay = P[1].y - P[0].y; 
bx = P[2].x - P[1].x - ax;   // b = P2 - P1 - a 
by = P[2].y - P[1].y - ay; 
cx = P[3].x - P[2].x - bx*2 - ax; // c = P3 - P2 - 2b - a 
cy = P[3].y - P[2].y - by*2 - ay; 

bc = bx*cy - cx*by; 
ac = ax*cy - cx*ay; 
ab = ax*by - bx*ay; 

r = ab + ac*t + bc*t*t; 

注意，r是所述第一和第二導數和符號的叉積表示曲率的方向。在左曲線的t = 1和右曲線的t = 0處計算r。如果產品是負面的，那麼就有一個拐點。

如果您有曲線U，V和W，其中U是左黑色，V是中紅色，W是右黑色，然後分別計算上面的bc，ac和ab。如果兩個連接都是拐點，則下列測試將爲真：

(Uab+Uac+Ubc)*(Vab) < 0 && (Vab+Vac+Vbc)*(Wab) < 0 

曲率等式有一個我忽略的分母。它不會影響曲率的符號，並且如果曲線是直線，則只會爲零。

數學摘要：

// start with the classic bezier curve equation 
P = (1-t)^3*P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3 
// convert to polynomial 
P = P0 + 3*t*(P1 - P0) + 3*t^2*(P2 - 2*P1 + P0) + t^3*(P3 - 3*P2 + 3*P1 - P0) 
// rename the terms to a,b,c 
P = P0 + 3at + 3btt + cttt 
// find the first and second derivatives 
P' = 3a + 6bt + 3ctt 
P" =  6b + 6ct 
// and the cross product after some reduction 
P' x P" = ab + act + bctt 

Answer 3

假設你有4點：P0，P1，P2和P3，它描述了三次貝塞爾的曲線（CBC的簡稱）。 P0和P3是起點和終點，P1和P2是方向點。

當P0，P1和P2是共線的，然後CBC具有P0拐點。

當P1，P2和P3共線時，則cBC在P3處有一個拐點。

備註。

1）使用向量乘積（P0P1 x P1P2和P1P2 x P2P3分別）檢查共線性。結果應該是一個零長度的向量。

2）避免他們創造一個P0，P1，P2和P3都是共線的情況下，CBC不在常識曲線。

推論。

當P1 = P2時，cBc在兩側都有拐點。

Answer 4

@ Victor Engel：謝謝你的澄清。現在解決方案更加簡單。

總之，看看兩條曲線的轉矩。如果他們拉在一起，就會發生「彎曲」，如果他們反對，「彎曲」會繼續。

備註：字「拐點」和「曲率」這裏有一個更直觀的特性，比嚴格的數學意義，因此使用單引號。

如前，一組點P0，P1，P2，P3限定第一三次Bezier曲線，並Q0，Q1，Q2和 Q3 第二。此外，4個載體：a，b，u，w將是有用的。

a = P2P3 
b = P1P2 
u = Q0Q1 
v = Q1Q2 

我會省略C1連續性檢查，它已經由您完成了。 （這意味着P3 = Q0和一個 X Ù = 0）

最後，TP和Tq的轉矩就會出現。

Tp = b x a 

（「X」表示一個矢量的產品，但在平面TP是像一個簡單的數字，而不是一個向量處理。}

if Tp=0   {very rarely vectors a, b can be parallel.} 
    b = P0P1 
    Tp = b x a 
    if Tp=0 
     No! It's can't be! Who straightened the curve??? 
     STOP 
    endif 
endif 

Tq = u x v 
if Tq=0   {also vectors u, v can be parallel.} 
    v = Q2Q3 
    Tq = u x v 
    if Tq=0 
     Oh no! What happened to my curve??? 
     STOP 
    endif 
endif 

現在最終測試：

if Tp*Tq < 0 then Houston! We have AN "INFLEXION"! 
       else WE CONTINUE THE TURN!