凸包多边形最小外切矩形算法

admin

1. 暴力算法
2. 遍历每一条边构造包围矩形比较面积大小。就是构造包围矩形，取到投影点到边以及垂直边上取距离最远两点距离即可
4. /* min value */
5. #define FLT采用MIN 1.175494351e-38F
6. /* max value */
7. #define FLT采用MAX 3.402823466e+38F
9. struct OBB {
10.     Point u[2]; //x, y轴
11.     Point c; //中心点
12.     float e[2]; //半长，半宽
13. };
15. float MinAreaRec(Point *pts, int ptsNum, OBB &obb) {
17.     float minArea = FLT采用MAX;
19.     for(int i = 0, j = ptsNum - 1; i < ptsNum; j = i, i++) {//遍历边
20.         Point u0 = pts[i] - pts[j]; //构造边
21.         u0 = u0/Length(u0);
22.         Point u1 = Point(0-u0.y, u0.x); //与u0垂直
23.         float min0 = 0.0f, max0 = 0.0f, min1 = 0.0f, max1 = 0.0f;
25.         for(int k = 0; k < ptsNum; k++) {//遍历点
26.             Point d = pts[k] - pts[j];
27.             //投影在u0
28.             float dot = Dot(d, u0);
29.             if(dot < min0) min0 = dot;
30.             if(dot > max0) max0 = dot;
31.             //投影在u1
32.             dot = Dot(d, u1);
33.             if(dot < min1) min1 = dot;
34.             if(dot > max1) max1 = dot;
35.         }
37.         float area = (max0 - min0) * (max1 - min1);
38.         if( area < minArea ) {
39.             minArea = area;
40.             obb.c = pts[j] + ( u0 * (max0 + min0) + u1 * (max1 + min1) )*0.5f;
41.             obb.u[0] = u0;
42.             obb.u[1] = u1;
43.             obb.e[0] = (max0 - min0)*0.5f;
44.             obb.e[1] = (max1 - min1)*0.5f;
45.         }
46.     }
48.     return minArea;
50. }
52. Point * GetOBBPoints(OBB obb) {//获取OBB四个顶点坐标
53.     Point *pts = new Point [4];
54.     pts[0] = obb.c + ( obb.u[0] * obb.e[0] + obb.u[1] * obb.e[1] );
55.     pts[1] = obb.c + ( obb.u[0] * obb.e[0] - obb.u[1] * obb.e[1] );
56.     pts[2] = obb.c - ( obb.u[0] * obb.e[0] + obb.u[1] * obb.e[1] );
57.     pts[3] = obb.c + ( obb.u[1] * obb.e[1] - obb.u[0] * obb.e[0] );
58.     return pts;
60. }
70. 旋转卡尺（旋转卡壳）算法
71. 使用旋转卡尺算法可将计算凸多边形的最小包围矩形的时间消耗减少很多..
73. 取坐标上两极值点构成平行线，旋转两线，当线与多边形一条边重合时，计算构成矩形面积。
75. 继续旋转，直至旋转角度超过 90 度。取最小面积。
77. 该算法仅对凸体有效（暴力法对凸体凹体均有效），因此需要先计算凸体，该算法的时间复杂度受限于凸体的计算过程
79. float Cos(Point v, Point p1) {
80.     float dot = Dot(v, p1);
81.     float cos = dot/(Length(v)*Length(p1));
82.     return cos;
83. }
85. void Setu0u1(Point e, Point &u0, Point &u1) {
86.     //以e方向为x轴方向，设定xy轴
87.     u0 = e / Length(e);
88.     u1 = Point( 0 - u0.y, u0.x);
89. }
91. int GetMinAngleIndex(int imin1, int imax0, int imax1, int imin0,
92.                      Point* e, Point u0, Point u1) {
93.     //返回旋转角度最小（cos值最大）的点的下标
94.     int imin采用angle采用index = 0;
96.     float cos = 0, maxCos = FLT采用MIN;
97.     cos = Cos(e[imin1], u0);
98.     if(cos > maxCos){maxCos = cos; imin采用angle采用index = imin1; }
100.     cos = Cos(e[imax0], u1);
101.     if(cos > maxCos){maxCos = cos; imin采用angle采用index = imax0; }
102.     cos = Cos(e[imax1], Point(0-u0.x, 0-u0.y));
103.     if(cos > maxCos){maxCos = cos; imin采用angle采用index = imax1; }
104.     cos = Cos(e[imin0], Point(0-u1.x, 0-u1.y));
105.     if(cos > maxCos){maxCos = cos; imin采用angle采用index = imin0; }
106.     return imin采用angle采用index;
108. }
110. void SetMinMax(Point*pts, int i, int iu, Point u0, Point u1,
111.                float &max0, float &min0, float &max1,
112.                int & new采用imax0, int &new采用imin0, int &new采用imax1)
114. {
115.     //找到x轴投影最大最小，y轴投影最大的长度（y轴最小则是重合边上点，长度为0）
116.     //以及极值点在pts中的下标
117.     Point d =  pts[i] - pts[iu];
118.     float dist0 = Dot( d, u0);
119.     if(dist0 > max0){ max0 = dist0; new采用imax0 = i; }
120.     if(dist0 < min0){ min0 = dist0; new采用imin0 = i; }
122.     float dist1 = Dot( d, u1);
123.     if(dist1 > max1){ max1 = dist1; new采用imax1 = i; }
124. }
126. float MinAreaRec2(Point *pts, int ptsNum, OBB &obb) {//旋转卡壳算法
127.     //必须是凸包
128.     float minArea = FLT采用MAX;
129.     //初始化边e
130.     Point *e = new Point[ ptsNum ];
131.     for(int i = 0; i < ptsNum; i++) {
132.         e[i] = pts[(i+1)%ptsNum] - pts[i];
133.     }
134.     int iu = 0; //以e[0]为重合边
135.     //初始化u0 u1
136.     Point u0, u1;
137.     Setu0u1(e[iu], u0, u1);
139.     int imax0 = 0, imax1 = 0, imin0 = 0, imin1 = 0;
140.     float min0 = FLT采用MAX, max0 = FLT采用MIN,
141.           max1 = FLT采用MIN, min1 = 0; //min1其实可以不需要设定的，始终为0
142.                                     //只是为了理解方便加上
143.                                     //要去掉则需要把下方用到的min1都改为0
145.     //求三个极值坐标
146.     for( int i = 0; i < ptsNum; i++) {
147.         SetMinMax(pts, i, iu, u0, u1,
148.                max0, min0, max1,
149.                imax0, imin0, imax1) ;
150.     }
152.     for(int i = 0; i < ptsNum ; i++) {
153.         int iminangle = 0;
154.         iminangle = GetMinAngleIndex((iu+1)%ptsNum, imax0, imax1, imin0, e, u0, u1);
155.         if(iminangle == 0)break; //旋转回了初始点 没必要继续
157.         if(iminangle == imax0){imax0 = (iu + 1)%ptsNum; iu = iminangle; }
158.         else if(iminangle == imax1){imax1 = (iu + 1)%ptsNum; iu = iminangle; }
159.         else if(iminangle == imin0){imin0 = (iu + 1)%ptsNum; iu = iminangle; }
160.         else if(iminangle == (iu+1)%ptsNum){iu = (iu+1)%ptsNum; }
162.         Setu0u1(e[iu], u0, u1); //重设u0u1
164.         //维护三个极值点
165.         int new采用imax0 = imax0, new采用imax1 = imax1, new采用imin0 = imin0;
166.         min0 =FLT采用MAX, max0 = FLT采用MIN, max1 = FLT采用MIN;
168.         //确定原先imax0在新坐标系中是什么极值
169.         SetMinMax(pts, imax0, iu, u0, u1,
170.                max0, min0, max1,
171.                new采用imax0, new采用imin0, new采用imax1) ;
172.         //确定原先imax1在新坐标系中是什么极值
173.         SetMinMax(pts, imax1, iu, u0, u1,
174.                max0, min0, max1,
175.                new采用imax0, new采用imin0, new采用imax1) ;
176.         //确定原先imin0在新坐标系中是什么极值
177.         SetMinMax(pts, imin0, iu, u0, u1,
178.                max0, min0, max1,
179.                new采用imax0, new采用imin0, new采用imax1) ;
181.         imax0 = new采用imax0;
182.         imax1 = new采用imax1;
183.         imin0 = new采用imin0;
184.         //维护完毕
186.         //求面积 设置obb
187.         float area = (max0 - min0)*(max1 - min1);
188.         if(area < minArea) {
189.             minArea = area;
191.             obb.e[0] = (max0 - min0)*0.5f;
192.             obb.e[1] = (max1 - min1)*0.5f;
193.             obb.u[0] = u0;
194.             obb.u[1] = u1;
195.             obb.c = pts[iu] + ( u0 * (max0 + min0) + u1 * (max1 + min1) )*0.5f;
196.         }
197.     }
198.     return minArea;
199. }
200. 复制
201. 拿到了四个点, 其他的就好说了, 从主体上裁切 出矩形, 然后平行到 90° 就 OK 了.

复制代码