我有一些地理數(shù)據(jù)（下面的圖像顯示了河流的路徑為紅點(diǎn)），我想用多段三次貝塞爾曲線近似。通過(guò)對(duì)計(jì)算器等問(wèn)題，在這里和這里我發(fā)現(xiàn)由Philip J.施耐德從“圖形寶石”的算法。我成功地實(shí)現(xiàn)了它并且可以報(bào)告即使有數(shù)千個(gè)點(diǎn)它也非?？?。不幸的是，速度帶來(lái)了一些缺點(diǎn)，即裝配非常不合適。請(qǐng)考慮以下圖形：多段貝塞爾曲線紅點(diǎn)是我的原始數(shù)據(jù)，藍(lán)線是由Schneider算法創(chuàng)建的多段貝塞爾曲線。如您所見(jiàn)，算法的輸入是一個(gè)容差，至少與綠線表示的一樣高。然而，該算法創(chuàng)建了具有太多急轉(zhuǎn)彎的貝塞爾曲線。你也會(huì)在圖像中看到這些不必要的急轉(zhuǎn)彎。很容易想象，對(duì)于所示數(shù)據(jù)，具有較小急轉(zhuǎn)彎的貝塞爾曲線，同時(shí)仍保持最大公差條件（僅將貝塞爾曲線稍微推向品紅色箭頭的方向）。問(wèn)題似乎是算法從我的原始數(shù)據(jù)中選取數(shù)據(jù)點(diǎn)作為各個(gè)貝塞爾曲線的終點(diǎn)（品紅箭頭指示一些嫌疑人）。貝塞爾曲線的端點(diǎn)受此限制，我正在尋找的是一種算法，它使用具有兩個(gè)約束的多段貝塞爾曲線來(lái)近似我的數(shù)據(jù)：多段貝塞爾曲線絕不能超過(guò)數(shù)據(jù)點(diǎn)一定距離（由Schneider算法提供）多段貝塞爾曲線絕不能產(chǎn)生過(guò)于尖銳的曲率。檢查此標(biāo)準(zhǔn)的一種方法是沿多段貝塞爾曲線滾動(dòng)具有最小曲率半徑的圓，并檢查它是否沿其路徑接觸曲線的所有部分。雖然看起來(lái)有更好的方法涉及一階和二階導(dǎo)數(shù)的叉積我發(fā)現(xiàn)可以創(chuàng)造更好擬合的解決方案或者僅適用于單個(gè)貝塞爾曲線（并且省略了如何在多段貝塞爾曲線中找到每個(gè)貝塞爾曲線的良好起點(diǎn)和終點(diǎn)的問(wèn)題）或者不允許最小曲率約束。我認(rèn)為最小曲率約束是這里的棘手條件。這是另一個(gè)例子（這是手繪而不是100％精確）：一些例子讓我們假設(shè)圖一顯示曲率約束（圓必須適合整個(gè)曲線）以及任何數(shù)據(jù)點(diǎn)與曲線的最大距離（恰好是綠色圓的半徑）。圖2中紅色路徑的成功近似顯示為藍(lán)色。該近似值符合曲率條件（圓可以在整個(gè)曲線內(nèi)滾動(dòng)并在任何地方觸摸它）以及距離條件（以綠色顯示）。圖3顯示了路徑的不同近似值。雖然它符合距離條件但很明顯圓圈不再適合曲率。圖4顯示了一條不可能用給定約束近似的路徑，因?yàn)樗饬恕Ｔ撌纠龖?yīng)該說(shuō)明為了正確地近似路徑中的一些尖轉(zhuǎn)彎，算法必須選擇不屬于路徑的控制點(diǎn)。圖3顯示，如果選擇沿路徑的控制點(diǎn)，則不能再滿足曲率約束。此示例還顯示算法必須退出某些輸入，因?yàn)闊o(wú)法使用給定的約束來(lái)近似它。這個(gè)問(wèn)題是否存在解決方案？解決方案不一定要快。如果需要一天時(shí)間來(lái)處理1000點(diǎn)，那就沒(méi)問(wèn)題了。解決方案也不必是最佳的，因?yàn)樗仨殞?dǎo)致最小二乘擬合。最后，我將用C和Python實(shí)現(xiàn)它，但我也可以閱讀大多數(shù)其他語(yǔ)言。
3 回答
德瑪西亞99
TA貢獻(xiàn)1770條經(jīng)驗(yàn) 獲得超3個(gè)贊
多邊形化數(shù)據(jù)
找到點(diǎn)的順序，這樣你就可以找到彼此最近的點(diǎn)，并嘗試連接“按線”。避免回到原點(diǎn)
計(jì)算沿路徑的推導(dǎo)
它是“線”的方向變化，你達(dá)到局部最小值或最大值就有你的控制點(diǎn)......這樣做是為了減少輸入數(shù)據(jù)（只留下控制點(diǎn)）。
曲線
現(xiàn)在使用這些點(diǎn)作為控制點(diǎn)。我強(qiáng)烈建議兩者的插值多項(xiàng)式x和y單獨(dú)的插值多項(xiàng)式，例如：
x=a0+a1*t+a2*t*t+a3*t*t*t
y=b0+b1*t+b2*t*t+b3*t*t*t
在哪里a0..a3計(jì)算如下：
d1=0.5*(p2.x-p0.x);
d2=0.5*(p3.x-p1.x);
a0=p1.x;
a1=d1;
a2=(3.0*(p2.x-p1.x))-(2.0*d1)-d2;
a3=d1+d2+(2.0*(-p2.x+p1.x));
b0 .. b3 以相同的方式計(jì)算，但當(dāng)然使用y坐標(biāo)
p0..p3 是三次插值曲線的控制點(diǎn)
t =<0.0,1.0>是曲線參數(shù)從。p1到p2
這確保了位置和第一次推導(dǎo)是連續(xù)的（c1），你也可以使用BEZIER，但它不會(huì)像這樣好。
[edit1]過(guò)于尖銳的邊緣是一個(gè)很大的問(wèn)題
要解決此問(wèn)題，您可以在獲取控制點(diǎn)之前從數(shù)據(jù)集中刪除點(diǎn)。我現(xiàn)在可以想到兩種方法：選擇對(duì)你更好的方法
從第一個(gè)推導(dǎo)過(guò)高的數(shù)據(jù)集中刪除點(diǎn)
dx/dl或者坐標(biāo)dy/dl在哪里x,y，l是曲線長(zhǎng)度（沿著它的路徑）。從曲線推導(dǎo)精確計(jì)算曲率半徑是棘手的
從數(shù)據(jù)集中刪除導(dǎo)致曲率半徑太小的點(diǎn)
計(jì)算相鄰線段（黑線）中點(diǎn)的交點(diǎn)。像圖像上的垂直軸（紅線）它的距離和連接點(diǎn)（藍(lán)線）是曲率半徑。當(dāng)曲率半徑小時(shí)，你的極限移除那個(gè)點(diǎn)......
曲率半徑
現(xiàn)在，如果你真的只需要BEZIER立方體，那么你可以將我的插值立方體轉(zhuǎn)換為BEZIER立方體，如下所示：
// ---------------------------------------------------------------------------
// x=cx[0]+(t*cx[1])+(tt*cx[2])+(ttt*cx[3]); // cubic x=f(t), t = <0,1>
// ---------------------------------------------------------------------------
// cubic matrix bz4 = it4
// ---------------------------------------------------------------------------
// cx[0]= ( x0) = ( X1)
// cx[1]= (3.0*x1)-(3.0*x0) = (0.5*X2) -(0.5*X0)
// cx[2]= (3.0*x2)-(6.0*x1)+(3.0*x0) = -(0.5*X3)+(2.0*X2)-(2.5*X1)+( X0)
// cx[3]= ( x3)-(3.0*x2)+(3.0*x1)-( x0) = (0.5*X3)-(1.5*X2)+(1.5*X1)-(0.5*X0)
// ---------------------------------------------------------------------------
const double m=1.0/6.0;
double x0,y0,x1,y1,x2,y2,x3,y3;
x0 = X1; y0 = Y1;
x1 = X1-(X0-X2)*m; y1 = Y1-(Y0-Y2)*m;
x2 = X2+(X1-X3)*m; y2 = Y2+(Y1-Y3)*m;
x3 = X2; y3 = Y2;
largeQ
TA貢獻(xiàn)2039條經(jīng)驗(yàn) 獲得超8個(gè)贊
我不認(rèn)為它回答了我的問(wèn)題。為了使我的問(wèn)題更清楚，我添加了另一個(gè)圖形示例。更確切地說(shuō)，我不認(rèn)為你的解決方案可以遵守曲率約束，因?yàn)樗x擇路徑的點(diǎn)作為曲線的控制點(diǎn)。我的例子表明，對(duì)于一些非常尖的路徑，有必要選擇除輸入路徑之外的控制點(diǎn)。
添加回答
舉報(bào)
0/150
提交
取消