我有一些地理數據（下面的圖像顯示了河流的路徑為紅點），我想用多段三次貝塞爾曲線近似。通過對計算器等問題，在這里和這里我發現由Philip J.施耐德從“圖形寶石”的算法。我成功地實現了它并且可以報告即使有數千個點它也非?？臁２恍业氖?，速度帶來了一些缺點，即裝配非常不合適。請考慮以下圖形：多段貝塞爾曲線紅點是我的原始數據，藍線是由Schneider算法創建的多段貝塞爾曲線。如您所見，算法的輸入是一個容差，至少與綠線表示的一樣高。然而，該算法創建了具有太多急轉彎的貝塞爾曲線。你也會在圖像中看到這些不必要的急轉彎。很容易想象，對于所示數據，具有較小急轉彎的貝塞爾曲線，同時仍保持最大公差條件（僅將貝塞爾曲線稍微推向品紅色箭頭的方向）。問題似乎是算法從我的原始數據中選取數據點作為各個貝塞爾曲線的終點（品紅箭頭指示一些嫌疑人）。貝塞爾曲線的端點受此限制，我正在尋找的是一種算法，它使用具有兩個約束的多段貝塞爾曲線來近似我的數據：多段貝塞爾曲線絕不能超過數據點一定距離（由Schneider算法提供）多段貝塞爾曲線絕不能產生過于尖銳的曲率。檢查此標準的一種方法是沿多段貝塞爾曲線滾動具有最小曲率半徑的圓，并檢查它是否沿其路徑接觸曲線的所有部分。雖然看起來有更好的方法涉及一階和二階導數的叉積我發現可以創造更好擬合的解決方案或者僅適用于單個貝塞爾曲線（并且省略了如何在多段貝塞爾曲線中找到每個貝塞爾曲線的良好起點和終點的問題）或者不允許最小曲率約束。我認為最小曲率約束是這里的棘手條件。這是另一個例子（這是手繪而不是100％精確）：一些例子讓我們假設圖一顯示曲率約束（圓必須適合整個曲線）以及任何數據點與曲線的最大距離（恰好是綠色圓的半徑）。圖2中紅色路徑的成功近似顯示為藍色。該近似值符合曲率條件（圓可以在整個曲線內滾動并在任何地方觸摸它）以及距離條件（以綠色顯示）。圖3顯示了路徑的不同近似值。雖然它符合距離條件但很明顯圓圈不再適合曲率。圖4顯示了一條不可能用給定約束近似的路徑，因為它太尖了。該示例應該說明為了正確地近似路徑中的一些尖轉彎，算法必須選擇不屬于路徑的控制點。圖3顯示，如果選擇沿路徑的控制點，則不能再滿足曲率約束。此示例還顯示算法必須退出某些輸入，因為無法使用給定的約束來近似它。這個問題是否存在解決方案？解決方案不一定要快。如果需要一天時間來處理1000點，那就沒問題了。解決方案也不必是最佳的，因為它必須導致最小二乘擬合。最后，我將用C和Python實現它，但我也可以閱讀大多數其他語言。