1 /*M///////////////////////////////////////////////////////////////////////////////////////
3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
5 // By downloading, copying, installing or using the software you agree to this license.
6 // If you do not agree to this license, do not download, install,
7 // copy or use the software.
10 // Intel License Agreement
11 // For Open Source Computer Vision Library
13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
14 // Third party copyrights are property of their respective owners.
16 // Redistribution and use in source and binary forms, with or without modification,
17 // are permitted provided that the following conditions are met:
19 // * Redistribution's of source code must retain the above copyright notice,
20 // this list of conditions and the following disclaimer.
22 // * Redistribution's in binary form must reproduce the above copyright notice,
23 // this list of conditions and the following disclaimer in the documentation
24 // and/or other materials provided with the distribution.
26 // * The name of Intel Corporation may not be used to endorse or promote products
27 // derived from this software without specific prior written permission.
29 // This software is provided by the copyright holders and contributors "as is" and
30 // any express or implied warranties, including, but not limited to, the implied
31 // warranties of merchantability and fitness for a particular purpose are disclaimed.
32 // In no event shall the Intel Corporation or contributors be liable for any direct,
33 // indirect, incidental, special, exemplary, or consequential damages
34 // (including, but not limited to, procurement of substitute goods or services;
35 // loss of use, data, or profits; or business interruption) however caused
36 // and on any theory of liability, whether in contract, strict liability,
37 // or tort (including negligence or otherwise) arising in any way out of
38 // the use of this software, even if advised of the possibility of such damage.
41 #include "precomp.hpp"
54 #define CV_CALIPERS_MAXHEIGHT 0
55 #define CV_CALIPERS_MINAREARECT 1
56 #define CV_CALIPERS_MAXDIST 2
58 /*F///////////////////////////////////////////////////////////////////////////////////////
59 // Name: icvRotatingCalipers
61 // Rotating calipers algorithm with some applications
65 // points - convex hull vertices ( any orientation )
66 // n - number of vertices
67 // mode - concrete application of algorithm
68 // can be CV_CALIPERS_MAXDIST or
69 // CV_CALIPERS_MINAREARECT
70 // left, bottom, right, top - indexes of extremal points
72 // In case CV_CALIPERS_MAXDIST it points to float value -
73 // maximal height of polygon.
74 // In case CV_CALIPERS_MINAREARECT
75 // ((CvPoint2D32f*)out)[0] - corner
76 // ((CvPoint2D32f*)out)[1] - vector1
77 // ((CvPoint2D32f*)out)[0] - corner2
91 /* we will use usual cartesian coordinates */
93 icvRotatingCalipers( CvPoint2D32f* points, int n, int mode, float* out )
95 float minarea = FLT_MAX;
99 CvPoint2D32f* vect = (CvPoint2D32f*)cvAlloc( n * sizeof(vect[0]) );
100 float* inv_vect_length = (float*)cvAlloc( n * sizeof(inv_vect_length[0]) );
101 int left = 0, bottom = 0, right = 0, top = 0;
102 int seq[4] = { -1, -1, -1, -1 };
104 /* rotating calipers sides will always have coordinates
105 (a,b) (-b,a) (-a,-b) (b, -a)
107 /* this is a first base bector (a,b) initialized by (1,0) */
108 float orientation = 0;
112 float left_x, right_x, top_y, bottom_y;
113 CvPoint2D32f pt0 = points[0];
115 left_x = right_x = pt0.x;
116 top_y = bottom_y = pt0.y;
118 for( i = 0; i < n; i++ )
123 left_x = pt0.x, left = i;
125 if( pt0.x > right_x )
126 right_x = pt0.x, right = i;
129 top_y = pt0.y, top = i;
131 if( pt0.y < bottom_y )
132 bottom_y = pt0.y, bottom = i;
134 CvPoint2D32f pt = points[(i+1) & (i+1 < n ? -1 : 0)];
139 vect[i].x = (float)dx;
140 vect[i].y = (float)dy;
141 inv_vect_length[i] = (float)(1./sqrt(dx*dx + dy*dy));
146 //cvbInvSqrt( inv_vect_length, inv_vect_length, n );
148 /* find convex hull orientation */
150 double ax = vect[n-1].x;
151 double ay = vect[n-1].y;
153 for( i = 0; i < n; i++ )
155 double bx = vect[i].x;
156 double by = vect[i].y;
158 double convexity = ax * by - ay * bx;
162 orientation = (convexity > 0) ? 1.f : (-1.f);
168 assert( orientation != 0 );
170 base_a = orientation;
172 /*****************************************************************************************/
173 /* init calipers position */
178 /*****************************************************************************************/
179 /* Main loop - evaluate angles and rotate calipers */
181 /* all of edges will be checked while rotating calipers by 90 degrees */
182 for( k = 0; k < n; k++ )
184 /* sinus of minimal angle */
187 /* compute cosine of angle between calipers side and polygon edge */
188 /* dp - dot product */
189 float dp0 = base_a * vect[seq[0]].x + base_b * vect[seq[0]].y;
190 float dp1 = -base_b * vect[seq[1]].x + base_a * vect[seq[1]].y;
191 float dp2 = -base_a * vect[seq[2]].x - base_b * vect[seq[2]].y;
192 float dp3 = base_b * vect[seq[3]].x - base_a * vect[seq[3]].y;
194 float cosalpha = dp0 * inv_vect_length[seq[0]];
195 float maxcos = cosalpha;
197 /* number of calipers edges, that has minimal angle with edge */
198 int main_element = 0;
200 /* choose minimal angle */
201 cosalpha = dp1 * inv_vect_length[seq[1]];
202 maxcos = (cosalpha > maxcos) ? (main_element = 1, cosalpha) : maxcos;
203 cosalpha = dp2 * inv_vect_length[seq[2]];
204 maxcos = (cosalpha > maxcos) ? (main_element = 2, cosalpha) : maxcos;
205 cosalpha = dp3 * inv_vect_length[seq[3]];
206 maxcos = (cosalpha > maxcos) ? (main_element = 3, cosalpha) : maxcos;
211 int pindex = seq[main_element];
212 float lead_x = vect[pindex].x*inv_vect_length[pindex];
213 float lead_y = vect[pindex].y*inv_vect_length[pindex];
214 switch( main_element )
235 /* change base point of main edge */
236 seq[main_element] += 1;
237 seq[main_element] = (seq[main_element] == n) ? 0 : seq[main_element];
242 case CV_CALIPERS_MAXHEIGHT:
244 /* now main element lies on edge alligned to calipers side */
246 /* find opposite element i.e. transform */
247 /* 0->2, 1->3, 2->0, 3->1 */
248 int opposite_el = main_element ^ 2;
250 float dx = points[seq[opposite_el]].x - points[seq[main_element]].x;
251 float dy = points[seq[opposite_el]].y - points[seq[main_element]].y;
254 if( main_element & 1 )
255 dist = (float)fabs(dx * base_a + dy * base_b);
257 dist = (float)fabs(dx * (-base_b) + dy * base_a);
259 if( dist > max_dist )
264 case CV_CALIPERS_MINAREARECT:
265 /* find area of rectangle */
270 /* find vector left-right */
271 float dx = points[seq[1]].x - points[seq[3]].x;
272 float dy = points[seq[1]].y - points[seq[3]].y;
275 float width = dx * base_a + dy * base_b;
277 /* find vector left-right */
278 dx = points[seq[2]].x - points[seq[0]].x;
279 dy = points[seq[2]].y - points[seq[0]].y;
282 height = -dx * base_b + dy * base_a;
284 area = width * height;
285 if( area <= minarea )
287 float *buf = (float *) buffer;
291 ((int *) buf)[0] = seq[3];
297 ((int *) buf)[5] = seq[0];
307 case CV_CALIPERS_MINAREARECT:
309 float *buf = (float *) buffer;
317 float C1 = A1 * points[((int *) buf)[0]].x + points[((int *) buf)[0]].y * B1;
318 float C2 = A2 * points[((int *) buf)[5]].x + points[((int *) buf)[5]].y * B2;
320 float idet = 1.f / (A1 * B2 - A2 * B1);
322 float px = (C1 * B2 - C2 * B1) * idet;
323 float py = (A1 * C2 - A2 * C1) * idet;
328 out[2] = A1 * buf[2];
329 out[3] = B1 * buf[2];
331 out[4] = A2 * buf[4];
332 out[5] = B2 * buf[4];
335 case CV_CALIPERS_MAXHEIGHT:
343 cvFree( &inv_vect_length );
348 cvMinAreaRect2( const CvArr* array, CvMemStorage* storage )
350 cv::Ptr<CvMemStorage> temp_storage;
352 cv::AutoBuffer<CvPoint2D32f> _points;
353 CvPoint2D32f* points;
355 memset(&box, 0, sizeof(box));
359 CvContour contour_header;
361 CvSeq* ptseq = (CvSeq*)array;
364 if( CV_IS_SEQ(ptseq) )
366 if( !CV_IS_SEQ_POINT_SET(ptseq) &&
367 (CV_SEQ_KIND(ptseq) != CV_SEQ_KIND_CURVE ||
368 CV_SEQ_ELTYPE(ptseq) != CV_SEQ_ELTYPE_PPOINT ))
369 CV_Error( CV_StsUnsupportedFormat,
370 "Input sequence must consist of 2d points or pointers to 2d points" );
372 storage = ptseq->storage;
376 ptseq = cvPointSeqFromMat( CV_SEQ_KIND_GENERIC, array, &contour_header, &block );
381 temp_storage = cvCreateChildMemStorage( storage );
385 temp_storage = cvCreateMemStorage(1 << 10);
388 ptseq = cvConvexHull2( ptseq, temp_storage, CV_CLOCKWISE, 1 );
393 cvStartReadSeq( ptseq, &reader );
395 if( CV_SEQ_ELTYPE( ptseq ) == CV_32SC2 )
397 for( i = 0; i < n; i++ )
400 CV_READ_SEQ_ELEM( pt, reader );
401 points[i].x = (float)pt.x;
402 points[i].y = (float)pt.y;
407 for( i = 0; i < n; i++ )
409 CV_READ_SEQ_ELEM( points[i], reader );
415 icvRotatingCalipers( points, n, CV_CALIPERS_MINAREARECT, (float*)out );
416 box.center.x = out[0].x + (out[1].x + out[2].x)*0.5f;
417 box.center.y = out[0].y + (out[1].y + out[2].y)*0.5f;
418 box.size.width = (float)sqrt((double)out[1].x*out[1].x + (double)out[1].y*out[1].y);
419 box.size.height = (float)sqrt((double)out[2].x*out[2].x + (double)out[2].y*out[2].y);
420 box.angle = (float)atan2( (double)out[1].y, (double)out[1].x );
424 box.center.x = (points[0].x + points[1].x)*0.5f;
425 box.center.y = (points[0].y + points[1].y)*0.5f;
426 double dx = points[1].x - points[0].x;
427 double dy = points[1].y - points[0].y;
428 box.size.width = (float)sqrt(dx*dx + dy*dy);
430 box.angle = (float)atan2( dy, dx );
435 box.center = points[0];
438 box.angle = (float)(box.angle*180/CV_PI);