給定兩個(gè)非連接（比如不相交）的凸多邊形 P 和 Q， 目標(biāo)是找到擁有最小距離的點(diǎn)對 (p,q) （p 屬于 P 且 q 屬于 Q）。

事實(shí)上， 多邊形非連接十分重要， 因?yàn)槲覀兯f的多邊形包含其內(nèi)部。 如果多邊形相交， 那么最小距離就變得沒有意義了。 然而， 這個(gè)問題的另一個(gè)版本， 凸多邊形頂點(diǎn)對間最小距離對于相交和非相交的情況都有解存在。

回到我們的主問題： 直觀的， 確定最小距離的點(diǎn)不可能包含在多邊形的內(nèi)部。 與最大距離問題相似， 我們有如下結(jié)論：

兩個(gè)凸多邊形 P 和 Q 之間的最小距離由多邊形間的對踵點(diǎn)對確立。 存在凸多邊形間的三種多邊形間的對踵點(diǎn)對， 因此就有三種可能存在的最小距離模式：
“頂點(diǎn)-頂點(diǎn)”的情況
“頂點(diǎn)-邊”的情況
“邊-邊”的情況

換句話說， 確定最小距離的點(diǎn)對不一定必須是頂點(diǎn)。 下面的三個(gè)圖例表明了以上結(jié)論： 
   
  
給定結(jié)果， 一個(gè)基于旋轉(zhuǎn)卡殼的算法自然而然的產(chǎn)生了:
考慮如下的算法， 算法的輸入是兩個(gè)分別有 m 和 n 個(gè)順時(shí)針給定頂點(diǎn)的凸多邊形 P 和 Q。
計(jì)算 P 上 y 坐標(biāo)值最小的頂點(diǎn)（稱為 yminP ） 和 Q 上 y 坐標(biāo)值最大的頂點(diǎn)（稱為 ymaxQ）。
為多邊形在 yminP 和 ymaxQ 處構(gòu)造兩條切線 LP 和 LQ 使得他們對應(yīng)的多邊形位于他們的右側(cè)。 此時(shí) LP 和 LQ 擁有不同的方向， 并且 yminP 和 ymaxQ 成為了多邊形間的一個(gè)對踵點(diǎn)對。
計(jì)算距離(yminP,ymaxQ) 并且將其維護(hù)為當(dāng)前最小值。
順時(shí)針同時(shí)旋轉(zhuǎn)平行線直到其中一個(gè)與其所在的多邊形的邊重合。
如果只有一條線與邊重合， 那么只需要計(jì)算“頂點(diǎn)-邊”對踵點(diǎn)對和“頂點(diǎn)-頂點(diǎn)”對踵點(diǎn)對距離。 都將他們與當(dāng)前最小值比較， 如果小于當(dāng)前最小值則進(jìn)行替換更新。 如果兩條切線都與邊重合， 那么情況就更加復(fù)雜了。 如果邊“交疊”， 也就是可以構(gòu)造一條與兩條邊都相交的公垂線（但不是在頂點(diǎn)處相交）， 那么就計(jì)算“邊-邊”距離。 否則計(jì)算三個(gè)新的“頂點(diǎn)-頂點(diǎn)”對踵點(diǎn)對距離。 所有的這些距離都與當(dāng)前最小值進(jìn)行比較， 若小于當(dāng)前最小值則更新替換。
重復(fù)執(zhí)行步驟4和步驟5， 直到新的點(diǎn)對為(yminP,ymaxQ)。
輸出最大距離。
旋轉(zhuǎn)卡殼模式保證了所有的對踵點(diǎn)對（和所有可能的子情況）都被考慮到。 此外， 整個(gè)算法擁有現(xiàn)行的時(shí)間復(fù)雜度， 因?yàn)椋ǔ顺跏蓟?只有與頂點(diǎn)數(shù)同數(shù)量級的操作步數(shù)需要執(zhí)行。

最小距離和最大距離的問題表明了旋轉(zhuǎn)卡殼模型可以用在不同的條件下（與先前的直徑和寬度問題比較）。 這個(gè)模型可以應(yīng)用于兩個(gè)多邊形的問題中。
“最小盒子”問題（最小面積外接矩形）通過同一多邊形上兩個(gè)正交切線集合展示了另一種條件下旋轉(zhuǎn)卡殼的應(yīng)用。  

轉(zhuǎn)自http://blog.csdn.net/ACMaker/archive/2008/10/29/3178696.aspx

POJ 3608