Furthest Pair of Points 最遠兩點配對

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

Naïve Method 樸素法

樸素法是利用排列組合的方式找出最遠兩點的距離。如果有n個點，每一點需要與(n-1)個點進行配對，因此樸素法需要進行n * (n - 1)次配對。
樸素法的複雜度為 。

Rotating Calipers 旋轉卡尺

步驟ㄧ：找出凸包

旋轉卡尺是在找出凸包後，在最大Y值與最小Y值畫上兩條水平線L1與L2。

步驟二：計算並記錄

計算並記錄最大Y值與最小Y值的兩點距離d(p,q)。
如果同一條線上有兩個點以上，L1由左至右，L2由右至左計算。

步驟三：旋轉

確定同一條線上都已經計算過後，將兩條線L1與L2順時鐘旋轉，直到L1或L2碰到下一點。
重複步驟二及步驟三直到L1及L2回到初始位置(L1旋轉至L2，L2旋轉至L1)。

步驟四：導出最遠配對

當L1及L2回到初始位置(L1旋轉至L2，L2旋轉至L1)後，最遠距離的兩點配對即為最遠配對。

完整步驟圖

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