如何判斷一個點是否在給定容差內的二次Bézier曲線上？

我正在爲Bézier曲線編寫一個庫。我已經可以將曲線作爲一定分辨率下的一組點來計算，但我現在需要做相反的處理;檢測給定點是否在給定容差範圍內的曲線上（例如0.0001）。 有沒有一個簡單的數學函數可以做到這一點？如何判斷一個點是否在給定容差內的二次Bézier曲線上？

請短語你的答案在接受兩個參數（x和y）函數的形式（仍然被認爲是「開」從曲線的距離）的公差和輸出布爾？

來源

2017-02-03 Ben Leggiero

簡答：不，因爲你使用的是IEEE浮點數，而不是完美的數學表達式。所以，你真正想要的是一個評估，告訴你*你的觀點距離曲線有多近，這樣你就可以決定「足夠接近」是指「開」。就象素渲染曲線而言，0.1的距離幾乎「在曲線上」。或者做一下@方程式，但是你仍然需要看看'tx'和'ty'值是多少*實際*點，以及這些和你自己的點之間的距離。 –

作爲次要評論：您使用的是哪種語言，因爲它很可能已經存在貝塞爾曲線庫，並且您的努力將會更好地使用它們，並且如果它們在特定環境中有缺陷，則有助於改進它們。=） –

謝謝請注意，@ Mike'Pomax'Kamermans！如果有幫助，我會使用'BigDecimal'的相同算法。此外，這是在** Kotlin **。 –

對於定義爲

C（T）= P 0（1-T）^ 2 + 2P1t（1-T）+ P2T^2 = P 0 + 2（P1-P0二次貝塞爾曲線）T +（P0-2P1 + P2）噸^ 2，

對於給定的點Q躺在C（T）必須存在0和1之間對於t的溶液，其滿足

（P0-Q）+2（P1-P0）t +（P0-2P1 + P2）t^2 = 0

因此，可以嘗試找到共同實根爲以下兩個方程

（P0X-2P1x + 2P2x）噸^ 2 + 2（P1X-P0X）T +（P0X-QX）= 0
（P0y-2P1y + 2P2y）噸^ 2 + 2（P1Y-P0y）T +（P0y-QY）= 0

如果這樣的共同的實根存在，它是0和1之間，它意味着點Q位於曲線上。

對於三次貝塞爾曲線，您可以按照類似的方式執行此過程，但您必須找到三次方程的根。

來源

2017-02-04 23:25:14 fang

請注意，這是一個數學問題的好答案，但不足以解決編程問題：在IEEE浮點域中，幾乎沒有完美的解決方案，根據數學不是這樣的，「應該」在曲線上。所以你仍然需要一個epsilon檢查;或者通過評估這一點，然後查看距離原點有多遠，找到的「tx」和「ty」值處的座標是多少，或者您需要計算該點與曲線的距離，然後進行基於epsilon的決策關於該距離是否足夠小以將該點視爲「在曲線上」 –

您能否以採用兩個參數（x和y）和公差（距離曲線仍然考慮的距離）的函數形式來回答您的答案「）並輸出一個布爾值？ –

您想要在曲線上找到最接近該點的參數，然後就可以找到距離。如果你有貝塞爾曲線B（t）和一個點P，然後解決

（PB（t））的⋅ B'（T）= 0

對於二次貝塞爾這給出了一個可以通過分析求解的三次方程。或者，您可以使用迭代求解器。最小距離是|| P-B（t）||。

來源

2017-03-12 14:35:32 kuribas

你可以用一個函數的形式來描述你的答案，這個函數需要兩個參數（x和y）和一個容差（曲線的距離仍然被認爲是「on」）並且輸出一個布爾值？ –

上面的公式給你一個分析函數，但它可能不是你想要的。由於四捨五入誤差，即使使用穩定的立方根求解器，結果可能也不準確，因爲從bernstein基變換到功率基是不穩定的。例如，這裏是一個描述找到點投影的迭代方法的論文：http://www.geometrie.tugraz.at/wallner/sproj.pdf然後你的公式變成|| P - 最接近（B，P）| | kuribas

我並不十分在意舍入錯誤。有什麼辦法可以把它變成'f（x，y，tolerance）：boolean'？ –

您可以利用在https://pomax.github.io/bezierinfo/#projections上描述的「距離曲線」方法，但是會爲任何座標找到一個單一的t值。對於「曲線上的這一點？」這很好（多個t值不會改變答案; 0表示曲線偏離，1表示曲線上，2或更多曲線仍然在曲線上）。

對於t（我假設您爲了只計算一次繪製座標而不是每次繪製曲線時已經執行的效率）而在幾個（相對接近的間隔）值處取樣曲線，以及然後用最接近的t得出結果，開始走彎曲，減少距離，直到找到最小距離（走路的方式取決於你：你可以做一個粗到細的步行，或者開始很好，或者根據曲線切線確定跳動的距離等）。

然後你的結果字面上只是return minDistance <= tolerance。

來源

2017-03-21 20:42:58

如何判斷一個點是否在給定容差內的二次Bézier曲線上？

回答

相關問題