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 凸包