iT邦幫忙

1

[筆記本: 演算法] 多邊形篇 Part 3 - Furthest Pair of Points 最遠兩點配對

Furthest Pair of Points 最遠兩點配對

顧名思義,這個演算法在n個點中,找出擁有最長距離的的兩點。
這個方法可以利用凸包的特性,因為凸包上所有的點是包圍所有點的多邊形,因此最遠的兩點一定是凸包的其中兩點。
傳送門:凸包解釋

https://ithelp.ithome.com.tw/upload/images/20181220/20113622WVbXBZuL30.png

Naïve Method 樸素法

樸素法是利用排列組合的方式找出最遠兩點的距離。如果有n個點,每一點需要與(n-1)個點進行配對,因此樸素法需要進行n * (n - 1)次配對。
樸素法的複雜度為https://ithelp.ithome.com.tw/upload/images/20181220/20113622hZRLb6JII4.png
https://ithelp.ithome.com.tw/upload/images/20181220/201136224oEFzYinEJ.png

Rotating Calipers 旋轉卡尺

步驟ㄧ:找出凸包

旋轉卡尺是在找出凸包後,在最大Y值與最小Y值畫上兩條水平線L1與L2。
https://ithelp.ithome.com.tw/upload/images/20181220/201136227Fw4MEKmMG.png

步驟二:計算並記錄

計算並記錄最大Y值與最小Y值的兩點距離d(p,q)。
如果同一條線上有兩個點以上,L1由左至右,L2由右至左計算。
https://ithelp.ithome.com.tw/upload/images/20181220/20113622ogumiCFeMQ.png

步驟三:旋轉

確定同一條線上都已經計算過後,將兩條線L1與L2順時鐘旋轉,直到L1或L2碰到下一點。
重複步驟二及步驟三直到L1及L2回到初始位置(L1旋轉至L2,L2旋轉至L1)。
https://ithelp.ithome.com.tw/upload/images/20181220/20113622ZYIofKLRr4.png

步驟四:導出最遠配對

當L1及L2回到初始位置(L1旋轉至L2,L2旋轉至L1)後,最遠距離的兩點配對即為最遠配對。
https://ithelp.ithome.com.tw/upload/images/20181220/20113622xhc73PxPqY.png

完整步驟圖

https://ithelp.ithome.com.tw/upload/images/20181220/20113622j1N5A1YMDb.png

傳送門:[筆記本: 演算法] 多邊形篇 Part 1 - Simple Polygon 簡單多邊形
傳送門:[筆記本: 演算法] 多邊形篇 Part 2 - Convex Hull 凸包


尚未有邦友留言

立即登入留言