給定兩個非連接（比如不相交）的凸多邊形 P 和 Q， 目標是找到擁有最小距離的點對 (p,q) （p 屬于 P 且 q 屬于 Q）。
事實上， 多邊形非連接十分重要， 因為我們所說的多邊形包含其內部。 如果多邊形相交， 那么最小距離就變得沒有意義了。 然而， 這個問題的另一個版本， 凸多邊形頂點對間最小距離對于相交和非相交的情況都有解存在。
回到我們的主問題： 直觀的， 確定最小距離的點不可能包含在多邊形的內部。 與最大距離問題相似， 我們有如下結論：
兩個凸多邊形 P 和 Q 之間的最小距離由多邊形間的對踵點對確立。 存在凸多邊形間的三種多邊形間的對踵點對， 因此就有三種可能存在的最小距離模式：
“頂點-頂點”的情況
“頂點-邊”的情況
“邊-邊”的情況
換句話說， 確定最小距離的點對不一定必須是頂點。 下面的三個圖例表明了以上結論：
  
給定結果， 一個基于旋轉卡殼的算法自然而然的產生了:
考慮如下的算法， 算法的輸入是兩個分別有 m 和 n 個順時針給定頂點的凸多邊形 P 和 Q。
計算 P 上 y 坐標值最小的頂點（稱為 yminP ） 和 Q 上 y 坐標值最大的頂點（稱為 ymaxQ）。
為多邊形在 yminP 和 ymaxQ 處構造兩條切線 LP 和 LQ 使得他們對應的多邊形位于他們的右側。 此時 LP 和 LQ 擁有不同的方向， 并且 yminP 和 ymaxQ 成為了多邊形間的一個對踵點對。
計算距離(yminP,ymaxQ) 并且將其維護為當前最小值。
順時針同時旋轉平行線直到其中一個與其所在的多邊形的邊重合。
如果只有一條線與邊重合， 那么只需要計算“頂點-邊”對踵點對和“頂點-頂點”對踵點對距離。 都將他們與當前最小值比較， 如果小于當前最小值則進行替換更新。 如果兩條切線都與邊重合， 那么情況就更加復雜了。 如果邊“交疊”， 也就是可以構造一條與兩條邊都相交的公垂線（但不是在頂點處相交）， 那么就計算“邊-邊”距離。 否則計算三個新的“頂點-頂點”對踵點對距離。 所有的這些距離都與當前最小值進行比較， 若小于當前最小值則更新替換。
重復執行步驟4和步驟5， 直到新的點對為(yminP,ymaxQ)。
輸出最大距離。
旋轉卡殼模式保證了所有的對踵點對（和所有可能的子情況）都被考慮到。 此外， 整個算法擁有現行的時間復雜度， 因為（除了初始化）， 只有與頂點數同數量級的操作步數需要執行。
最小距離和最大距離的問題表明了旋轉卡殼模型可以用在不同的條件下（與先前的直徑和寬度問題比較）。 這個模型可以應用于兩個多邊形的問題中。
“最小盒子”問題（最小面積外接矩形）通過同一多邊形上兩個正交切線集合展示了另一種條件下旋轉卡殼的應用。
轉自http://blog.csdn.net/ACMaker/archive/2008/10/29/3178696.aspx
  POJ 3608
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#define eps 1e-8
using namespace std;
struct pt
{
double x,y;
}pp[2][30000],poly[2][30000];
double cross(pt a,pt b,pt c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int dblcmp(double x)
{
if(fabs(x)<eps)
return 0;
else return x<0?-1:1;
}
double dist(pt a,pt b)
{
return (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);
}
bool cmp1(pt a,pt b)
{
int x=dblcmp(cross(pp[0][0],a,b));
if(x==0)
return dist(pp[0][0],a)<dist(pp[0][0],b);
return x>0;
}
bool cmp2(pt a,pt b)
{
int x=dblcmp(cross(pp[1][0],a,b));
if(x==0)
return dist(pp[1][0],a)<dist(pp[1][0],b);
return x>0;
}
int p,q,p0,q0,n,m;
int next1[30000],next2[30000];
double dot(pt a,pt b,pt c)
{
return (b.x-a.x)*(c.x-a.x)+(b.y-a.y)*(c.y-a.y);
}
double dis(pt a,pt b,pt c)
{
if(dot(a,b,c)>dist(a,b)+eps||dot(a,b,c)<-eps)
return min(dist(c,b),dist(c,a));
else return fabs(cross(a,b,c)*cross(a,b,c)/dist(a,b));
}
double polldis(int p,int q)
{
return min(min(dis(poly[0][p],poly[0][next1[p]],poly[1][q]),dis(poly[0][p],poly[0][next1[p]],poly[1][next2[q]])),min(dis(poly[1][q],poly[1][next2[q]],poly[0][p]),dis(poly[1][q],poly[1][next2[q]],poly[0][next1[p]])));
}
int TB(int n,int s)
{
int swap=0;
int i;
for(i=0;i<n;i++)
{
if(pp[s][i].y<pp[s][swap].y||(pp[s][i].y==pp[s][swap].y&&pp[s][i].x<pp[s][swap].x))
swap=i;
}
poly[s][0]=pp[s][0];
pp[s][0]=pp[s][swap];
pp[s][swap]=poly[s][0];
if(s==0)
sort(&pp[0][0],&pp[0][n],cmp1);
else
sort(&pp[1][0],&pp[1][n],cmp2);
poly[s][0]=pp[s][0];
poly[s][1]=pp[s][1];
int top=1;
for(i=2;i<n;i++)
{
while(top>0&&dblcmp(cross(poly[s][top-1],poly[s][top],pp[s][i]))<=0)
top--;
poly[s][++top]=pp[s][i];
}
int tt=1;
for(i=1;i<=top;i++)
{
if(!(poly[s][i].x==poly[s][i-1].x&&poly[s][i].y==poly[s][i-1].y))
poly[s][tt++]=poly[s][i];
}
return tt;
}
double RC()
{
double mi=1e15;
p=p0=0;
q=0;
while(cross(poly[0][p],poly[0][next1[p]],poly[1][next2[q]])>cross(poly[0][p],poly[0][next1[p]],poly[1][q]))
q=next2[q];
q0=q;
while(1)
{
p=next1[p];
if(dis(poly[0][p],poly[0][next1[p]],poly[1][q])<mi)
mi=dis(poly[0][p],poly[0][next1[p]],poly[1][q]);
while(cross(poly[0][p],poly[0][next1[p]],poly[1][next2[q]])>cross(poly[0][p],poly[0][next1[p]],poly[1][q]))
{
q=next2[q];
if(dis(poly[0][p],poly[0][next1[p]],poly[1][q])<mi)
mi=dis(poly[0][p],poly[0][next1[p]],poly[1][q]);
if(p==p0&&q==q0)
{
return mi;
}
}
if(fabs(cross(poly[0][p],poly[0][next1[p]],poly[1][next2[q]])-cross(poly[0][p],poly[0][next1[p]],poly[1][q]))<eps)
{
mi=min(mi,polldis(p,q));
}
if(p==p0)
break;
}
return mi;
}
double RC2()
{
double mi=1e15;
q=q0=0;
p=0;
while(cross(poly[1][q],poly[1][next2[q]],poly[0][next1[p]])>cross(poly[1][q],poly[1][next2[q]],poly[0][p]))
p=next1[p];
p0=p;
while(1)
{
q=next2[q];
if(dis(poly[1][q],poly[1][next2[q]],poly[0][p])<mi)
mi=dis(poly[1][q],poly[1][next2[q]],poly[0][p]);
while(cross(poly[1][q],poly[1][next2[q]],poly[0][next1[p]])>cross(poly[1][q],poly[1][next2[q]],poly[0][p]))
{
p=next1[p];
if(dis(poly[1][q],poly[1][next2[q]],poly[0][p])<mi)
mi=dis(poly[1][q],poly[1][next2[q]],poly[0][p]);
if(p==p0&&q==q0)
{
return mi;
}
}
if(fabs(cross(poly[1][q],poly[1][next2[q]],poly[0][next1[p]])-cross(poly[1][q],poly[1][next2[q]],poly[0][p]))<eps)
{
mi=min(mi,polldis(p,q));
}
if(q==q0)
break;
}
return mi;
}
int main()
{
int i;
while(scanf("%d%d",&n,&m)&&(n||m))
{
for(i=0;i<n;i++)
{
scanf("%lf %lf",&pp[0][i].x,&pp[0][i].y);
}
for(i=0;i<m;i++)
{
scanf("%lf %lf",&pp[1][i].x,&pp[1][i].y);
}
int t1=n,t2=m;
n=TB(t1,0);
m=TB(t2,1);
for(i=0;i<n;i++)
next1[i]=(i+1)%n;
for(i=0;i<m;i++)
next2[i]=(i+1)%m;
printf("%.5f\n",sqrt(min(RC(),RC2())));
}
}
|