如何計算線條和曲線的最近點？ ..或曲線和曲線？

Question

給定一條直線和一條二次貝塞爾曲線的點，如何計算它們的最近點？

Answer 1

我只是想給你一些提示，在案例Q.B.Curve //段： 得到一個足夠快的計算，我想你應該首先考慮爲你的算法使用一種'邊界框'。 說P0是QB曲線，P2與第二點，P1的控制點，和P3P4線段然後的第一點：從P0

1. 計算距離，P1，P2到P3P4
2. 如果P0 OR P2是最近點 - >這是來自P3P4曲線的最近點。結束：=）。
3. 如果P1是最近點，並且Pi（i = 0或1）是第二個最近點，PiPC和P3P4之間的距離是您尋求的距離的估計值，可能根據您的需要足夠精確。
4. 如果您需要更精確：計算P1'，這是Q.B.曲線上離P1最近的點：您發現它應用了t = 0.5的BQC公式。 - >距離PiP1'到P3P4的距離是一個更準確的估計 - 但成本更高 - 。
5. 請注意，如果由P1P1'定義的線與P3P4相交，則P1'是距P3P4最近的QBC點。
6. 如果P1P1' 不相交P3P4，那麼你的運氣了，你必須去艱難地...

現在，如果（當），你需要精度：

思考使用曲線參數上的分治算法： 它離P3P4最近？ P0P1'或P1'P2如果它是P0P1'→t在0和0.5之間，那麼計算P = t = 0.25。 現在哪個離P3P4最近？ P0Pm或PmP1'？如果是PmP1' - >在t = 0.25 + 0.125 = 0.375時計算Pm2，那麼哪個最接近？ PmPm2或Pm2P1'等等 你會很快找到準確的解決方案，就像6次迭代，你的t精度爲0.004！當兩點之間的距離變得低於給定值時，您可能會停止搜索。 （而不是區別兩個參數，因爲參數稍微改變，點可能很遠）實際上，該算法的原理是每次更精確地近似曲線段。首先使用段/段計算，然後（可能）段/曲線計算，並且只有在需要曲線/曲線計算的時候，才能避免無用的計算。

對於曲線/曲線，分而治之也是一個很難解釋的問題，但是您可能會發現它。 ：=）

希望你能找到你的速度/準確性這個良好的平衡：=）

編輯：想我找到了，一般情況下，一個很好的解決方案:-) 你應該重複的（內）每個BQC的邊界三角形 所以我們有三角形T1，點A，B，C有't'參數tA，tB，tC。 和三角形T2，點D，E，F，具有t參數tD，tE，tF。 最初我們有tA = 0 tB = 0.5 tC = 1.0，對於T2 tD = 0，tE = 0.5，tF = 1.0也是一樣的想法是遞歸地調用一個過程，將T1和/或T2分成更小的矩形，直到我們對於達到的精度是可以的。 第一步是計算從T2到T1的距離，並跟蹤每個三角形上距離最近的線段。第一個「技巧」：如果在T1上線段爲AC，則在T1上停止遞歸性，曲線1上的最近點是A或C.如果在T2上最近線段是DF，則停止T2上的遞歸性，曲線2是D或F.如果我們停止遞歸 - >返回距離= min（AD，AF，CD，CF）。那麼如果我們在T1上有遞歸性，並且AB段最近，那麼新的T1變成：A'= AB = tB =（tA + tC）/ 2 = 0.25的曲線1的點，C =在新的T1和新的T2上應用遞歸性，並調用相同的算法。當在T1和T2之間發現的距離減去在先前的T1和T2之間發現的距離低於閾值時停止算法。 函數可能看起來像ComputeDistance（curveParam1，A，C，shouldSplitCurve1，curveParam2，D，F，shouldSplitCurve2，previousDistance），其中點也存儲它們的t參數。

請注意，距離（曲線，段）只是該算法的特定情況，並且您應該實現距離（三角形，三角形）和距離（段，三角形）以使其有效。玩的開心。

Answer 2

的地步，有正常人的比賽是他們最近點。我的意思是你畫一條與該線正交的線。如果該線與曲線正交，則交點爲最近點

Answer 3

1.簡單的方法 - 通過迭代從第一條曲線開始逐點並從第二條曲線開始，然後得到最小值 2 。確定曲線之間距離的數學函數和此函數的計算極限：

| Fcur1（t）-Fcur2（t）| - > 0

Fs是矢量。

我認爲，我們可以計算出本作確定的極值，並得到最近和farest點

我想想這一段時間後，產後全響應的衍生物。

Answer 4

存在着關於從INRIA這個問題上的科學論文：Computing the minimum distance between two Bézier curves（PDF here）

Answer 5

制定你的問題的標準分析方面：你已經有了一個數量減少（距離），所以你制定這樣的一個公式數量並找到一階導數爲零的點。通過使用曲線的參數p，使用單個參數進行參數化，該參數在第一點0和最後一點1之間。

在線情況下，該方程非常簡單：從樣條線方程中獲取x/y座標，並通過向量方程計算與給定線的距離（標量乘以線的法線）。

在曲線的情況下，解析解可能會變得非常複雜。您可能想要使用數字最小化技術，例如Nelder-Mead，或者，因爲您有一維連續問題，簡單的二分法。

Answer 6

我曾經寫過一個工具來完成類似的任務。貝塞爾樣條一般是參數三次多項式。爲了計算立方段和線之間的距離的平方，這只是兩個多項式函數之間距離的平方，本身就是另一個多項式函數！請注意，我說的是距離的平方，而不是平方根。

本質上，對於立方體線段上的任何點，可以計算從該點到該線的距離的平方。這將是一個6階多項式。我們可以最小化距離的平方嗎？是。最小值必須出現在多項式的導數爲零的位置。所以區分，得到一個五階多項式。使用您最喜愛的根查找工具，可以根據數字生成所有根。詹金斯&特勞布，不管。從該組根中選擇正確的解決方案，排除任何複雜的解決方案，並且只在位於所述立方片段內的情況下選擇解決方案。確保排除與距離的局部最大值相對應的點。

所有這些都可以有效地完成，除了多項式根找到器以外不需要使用迭代優化器，因此不需要使用需要起始值的優化工具，只需找到接近該起始值的解決方案。

例如，在三維圖中，我顯示了一組由三維點組成的曲線（用紅色表示），然後我拿了另外一組位於外部圓的點，我計算了最接近指向每條曲線的內部曲線，繪製一條直線到該曲線。這些最小距離點由上述方案產生。

Answer 7

在貝塞爾曲線的情況下和一個線

有三個候選人的最近點到行：

1. 對貝塞爾曲線段中的位置即與該線平行（如果存在這樣的地方），
2. 曲線段的一端，
3. 曲線段的另一端。

測試所有三個;最短距離獲勝。

二貝塞爾曲線

的情況下，如果你想確切的分析結果，或者優化的數值結果是足夠好賴。

分析結果

給定兩個貝塞爾曲線一個（噸）和乙（小號），你可以得到方程的局部定向A'（t）和B'（s）。點對爲其甲 '（噸）= 乙'（小號）是候選，即（噸，小號）該曲線是局部平行。我沒有檢查，但我假定甲 '（噸） - 乙'（小號）= 0可以解析地求解。如果您的曲線與您在示例中顯示的曲線相似，則該方程式應該只有一個解或者沒有解，但可能有兩個（或者在曲線相同但翻譯的情況下無限多） - 在這種情況下你可以忽略它，因爲贏家將始終是曲線段端點之一）。

在類似於上述曲線輪廓大綱的方法中，測試每個點對，再加上曲線段端點。最短距離獲勝。

數值結果

假設在兩個Bézier曲線的點被定義爲甲（噸）和乙（小號）。您想最小化距離d（t,s）= | 甲（噸） - 乙（小號）|。這是一個簡單的雙參數的優化問題：找到小號和噸，最大限度地減少d（噸，小號）與約束0≤噸≤1和0≤小號≤1 。

由於d = SQRT（（XA - 的xB）2 +（YA - YB）²），也可以只是最小化函數˚F（噸，小號）= [d（t,s）]²保存平方根計算。

對於這樣的優化問題有numerous ready-made methods。挑選。

---

注意，在上述兩種情況下，任何高階比二次貝塞爾曲線可以送禮者你比一個極小，所以這是值得提防。從你給的例子看，你的曲線看起來沒有拐點，所以這個問題可能不適用於你的情況。