现有一个任意简单多边形,需要确定一个矩形,使其完全包含这个多边形,并且面积最小.如何高效地把这个矩形找到?

 

 

首先,我们考虑,矩形是否需要贴住多边形的边?感觉上是需要的,因为如果矩形没有靠住某一条边,则"似乎"可以自由滑动,而我们就可以把它滑到一个更小的位置.但这实际上是不对的,考虑以下的情况,或者极端些,对于一个星形多边形,我们简直找不到一条合法的边来靠!

 

因为一般多边形太复杂,不好操作,所以想到将其转化成凸多边形,也就是求这个多边形的凸包.可是在本问题中,一个多边形的凸包是否等价于原多边形呢?答案是肯定的.简单的证明如下:

 

∵由题意得,多边形的每个顶点都必须在矩形任意一条边的一侧
假设矩形上的任意一个点在多边形的"凹下"处,则在这个点环顾多边形的视角>180°
∴过这个点作出的任意直线(看作一个平角)都必然穿过这个多边形,与题意矛盾.
∴矩形上的任意一个点不在多边形"凹下"处
得证.

 

求多边形凸包当然可以求多边形所有顶点的凸包,时间复杂度是O(nlogn),这样并没有用到多边形相对有序的条件,不划算.有一个巧妙的在线算法,即Melkman Algorithm.维护一个两头栈,先取多边形的前3个顶点,其中第1,2个在栈中间,第3个点在栈的两头都存放,保存成这个样子:3 1 2 3.并要使栈的左端的3个点维持向右转,使栈的右端的3个点维持向左转,如果不满足就交换1,2两个点的位置.

 

如图,蓝色的表示当前的凸包,红点表示栈顶的点,对于新来的一个点,如果出现在绿色区域(注意线的颜色,下同),对栈左端进行Graham维护,直到左端的3个点维持右转,如果出现在紫色区域,对栈右端进行Graham维护,直到右端的3个点维持左转,如果出现在黄色区域,就对栈的两头都维护.这样,最后留在栈里的序列就是多边形的凸包了.时间复杂度为O(n).

 

得到了"极端"有序的凸多边形,自然就考虑线形的旋转卡壳算法了.用一个矩形夹住凸多边形,每次旋转四个角度中一个最小的角度,靠住下一条边就行了.不过,我认为这个在实际操作中并不简便易行,喜欢用以下的方法.

 

先把矩形的一条边靠住凸多边形的一条边,再确定其他三条边,或者说其他三边靠住的点(最远点).

 

先说对边,从当前这条边逆时针地走出去,所有的点离这条边的距离总是单调的先越来越远,然后又越来越近.可以发现,因为凸多边形所有点都在当前边的左面,所以如果第N个点到第N+1个点的向量在当前边的左边,正交分解向量,可知下个点会更远些;反之如果在右边,则会更近.因为对边靠住的是离这条边最远的点,所以只要一直走到最远点(下一个点比这个点更近)停下.

 

对于邻边所在的点,也就在是当前这条边方向上最前和最后的点.最前,即该点向量投影在正方向上最大,对应点积值最大;最后,即该点向量投影在负方向上最大,对应点积值最小.同样,这个点积的绝对值也是单增然后单减的,从开始一直走到最前和最后点就可以了.

 

设置4个指针,第一个表示目前贴着的边,然后将其他三个按刚才说的方法走到最远,最前,最后的点.然后不断逆时针移动第一个指针到下一条边,接着判断其他指针,看是否也需要逆时针移动,以保持"三最".当第一个指针转完一圈后,所有的工作就做完了,只要在旋转途中,记录下面积最小值即可.

 

因为每一个指针只转了一圈多一点,所以这一步也是线形的,总的时间复杂度为O(n).