多边形最小外接矩形算法概要.ppt

多边形最小外接矩形算法,程鹏飞,题目：给出求一个多边形最小外接矩形的算法并证明求得的是最小外接矩形.最小外接矩形英文简称为SMBR(smallestminimumboundingrectangle),它和MBR(minimumboundingrectangle)不一样.MBR是指以多边形顶点中的最大与最小坐标为顶点围成的矩形,其边和坐标轴平行.而SMBR的边则不一定平行于坐标轴,但是它的面积应该是所有外接矩形中最小的.,用途：用于加速搜索速度，对多边形进行快速捕捉。大大减少运算量，提高了系统的响应速度。举例：游戏图标的捕捉等。,各种算法：一、旋转法。每次以固定角旋转边界点，旋转后求出一个面积的MBR。然后求出最小的MBR。问题的缺点就是：第一不一定能找到准确的SMBR。第二算法的精度与所选取的旋转角度有关，一旦选取角度过大精度上就会有问题，但选择的精度太小就会影响算法的效率。,二、最佳拟和直线算法。反求建模中的形状特征分析田怀文李涛（西南交通大学机械学院成都610031）设直线L为y=kx+b。所谓最佳拟合直线是指在多边形所在的平面中，存在直线L，使得多边形各顶点到直线L的距离平方和为最小。,其缺点是：第一当多边形为由两个等边三角形构成的菱形时，该算法运算结构不成立。但是更多边的情况未推算。第二其算法复杂度相当高。,、思路：（1）求一个多边形的最小外接矩形一定（简称MABR）和求该多边形的凸包的MABR等价-这一条似乎无可辩驳-所以我们可以先求出凸包，把问题转化为求凸多边形的MABR；（2）猜想一个凸多边形的MABR的一边至少过该凸多边形的一边-这是我们需要证明的。,（3）如此，我们可以通过旋转坐标系的方法，把经过每一条边的最小外接矩形求出来，然后比较面积大小，就可以取得该多边形的最小外接矩形。如果能证明这个命题，问题就解决了。,3、理论证明：假设多边形的最小外接矩形不过多边形的一条边，则多边形最多有四个顶点在外接矩形上，它可分为三种情况。,一，多边形有两个顶点在矩形上。,旋转外接矩形d度（d45度）则新外接矩形与长对角线的加角为c度（c45度）得到另一个外接矩形（用虚线表示）。新外接矩形的面积表示为a2*cosc*sinc=0.5*a2*sin(2c)当c45度时，该面积为递增函数。所以肯定可以将外接矩形旋转直到与多边形的一条边重合为止。故在该情况下，最小外接矩形必过多边形的一条边。,二，多边形有三个顶点在矩形上。,设ab边的夹角为r，a与矩形的夹角为p（这里的a为长边，b为短边），这样保证p的角度在0到45度。则矩形的面积可表示为a*cosp*b*cos(0.5pir-p)=0.5ab*(sin(2p+r)+sinr)由正铉曲线其角范围在rr+0.5pi之间且函数为凸函数。所以其在p接近0oorp接近45度时取最小值。所以我们认为只有当它旋转到过多边形一条边时才有可能去的最小。他在不过多边形变的情况下无法达到最小值。,三，多边形有四个点在矩形上。,我们假设最小矩形过多边形的四个点。则该最小矩形的面积可由a（连接两短边上的顶点）和b（连接长边上的两个顶点）来表示。其面积公式为：s=a*sinp*b*sin(Pi-(0.5Pi-p)-(pi-r)=-absinp*cos(2p+r)=0.5*ab(sin(r)-sin(2p+r)其中r固定为两轴夹角中的锐角。P为对角线与矩形边的夹角为可变量（取锐角并且大于45度）。且当p趋近于45度时达到最小值。即在此情况下多边形不可能达到最小值。,综上所述，在上述三种情况中，矩形的最小值不可能在其不过一边的情况下产生。所以，最小矩形必过多边形一边。,算法：一、先算出多边形对应的凸包。其中算法包括卷格雷厄姆方法，包裹法，分治算法等等。二、对所求凸包按边旋转求出其MBR，并计算其面积。找出最小面积。,参