| /*M/////////////////////////////////////////////////////////////////////////////////////// |
| // |
| // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. |
| // |
| // By downloading, copying, installing or using the software you agree to this license. |
| // If you do not agree to this license, do not download, install, |
| // copy or use the software. |
| // |
| // |
| // Intel License Agreement |
| // For Open Source Computer Vision Library |
| // |
| // Copyright (C) 2000, Intel Corporation, all rights reserved. |
| // Third party copyrights are property of their respective owners. |
| // |
| // Redistribution and use in source and binary forms, with or without modification, |
| // are permitted provided that the following conditions are met: |
| // |
| // * Redistribution's of source code must retain the above copyright notice, |
| // this list of conditions and the following disclaimer. |
| // |
| // * Redistribution's in binary form must reproduce the above copyright notice, |
| // this list of conditions and the following disclaimer in the documentation |
| // and/or other materials provided with the distribution. |
| // |
| // * The name of Intel Corporation may not be used to endorse or promote products |
| // derived from this software without specific prior written permission. |
| // |
| // This software is provided by the copyright holders and contributors "as is" and |
| // any express or implied warranties, including, but not limited to, the implied |
| // warranties of merchantability and fitness for a particular purpose are disclaimed. |
| // In no event shall the Intel Corporation or contributors be liable for any direct, |
| // indirect, incidental, special, exemplary, or consequential damages |
| // (including, but not limited to, procurement of substitute goods or services; |
| // loss of use, data, or profits; or business interruption) however caused |
| // and on any theory of liability, whether in contract, strict liability, |
| // or tort (including negligence or otherwise) arising in any way out of |
| // the use of this software, even if advised of the possibility of such damage. |
| // |
| //M*/ |
| #include "_cv.h" |
| |
| typedef struct |
| { |
| int bottom; |
| int left; |
| float height; |
| float width; |
| float base_a; |
| float base_b; |
| } |
| icvMinAreaState; |
| |
| #define CV_CALIPERS_MAXHEIGHT 0 |
| #define CV_CALIPERS_MINAREARECT 1 |
| #define CV_CALIPERS_MAXDIST 2 |
| |
| /*F/////////////////////////////////////////////////////////////////////////////////////// |
| // Name: icvRotatingCalipers |
| // Purpose: |
| // Rotating calipers algorithm with some applications |
| // |
| // Context: |
| // Parameters: |
| // points - convex hull vertices ( any orientation ) |
| // n - number of vertices |
| // mode - concrete application of algorithm |
| // can be CV_CALIPERS_MAXDIST or |
| // CV_CALIPERS_MINAREARECT |
| // left, bottom, right, top - indexes of extremal points |
| // out - output info. |
| // In case CV_CALIPERS_MAXDIST it points to float value - |
| // maximal height of polygon. |
| // In case CV_CALIPERS_MINAREARECT |
| // ((CvPoint2D32f*)out)[0] - corner |
| // ((CvPoint2D32f*)out)[1] - vector1 |
| // ((CvPoint2D32f*)out)[0] - corner2 |
| // |
| // ^ |
| // | |
| // vector2 | |
| // | |
| // |____________\ |
| // corner / |
| // vector1 |
| // |
| // Returns: |
| // Notes: |
| //F*/ |
| |
| /* we will use usual cartesian coordinates */ |
| static void |
| icvRotatingCalipers( CvPoint2D32f* points, int n, int mode, float* out ) |
| { |
| float minarea = FLT_MAX; |
| float max_dist = 0; |
| char buffer[32]; |
| int i, k; |
| CvPoint2D32f* vect = (CvPoint2D32f*)cvAlloc( n * sizeof(vect[0]) ); |
| float* inv_vect_length = (float*)cvAlloc( n * sizeof(inv_vect_length[0]) ); |
| int left = 0, bottom = 0, right = 0, top = 0; |
| int seq[4] = { -1, -1, -1, -1 }; |
| |
| /* rotating calipers sides will always have coordinates |
| (a,b) (-b,a) (-a,-b) (b, -a) |
| */ |
| /* this is a first base bector (a,b) initialized by (1,0) */ |
| float orientation = 0; |
| float base_a; |
| float base_b = 0; |
| |
| float left_x, right_x, top_y, bottom_y; |
| CvPoint2D32f pt0 = points[0]; |
| |
| left_x = right_x = pt0.x; |
| top_y = bottom_y = pt0.y; |
| |
| for( i = 0; i < n; i++ ) |
| { |
| double dx, dy; |
| |
| if( pt0.x < left_x ) |
| left_x = pt0.x, left = i; |
| |
| if( pt0.x > right_x ) |
| right_x = pt0.x, right = i; |
| |
| if( pt0.y > top_y ) |
| top_y = pt0.y, top = i; |
| |
| if( pt0.y < bottom_y ) |
| bottom_y = pt0.y, bottom = i; |
| |
| CvPoint2D32f pt = points[(i+1) & (i+1 < n ? -1 : 0)]; |
| |
| dx = pt.x - pt0.x; |
| dy = pt.y - pt0.y; |
| |
| vect[i].x = (float)dx; |
| vect[i].y = (float)dy; |
| inv_vect_length[i] = (float)(1./sqrt(dx*dx + dy*dy)); |
| |
| pt0 = pt; |
| } |
| |
| //cvbInvSqrt( inv_vect_length, inv_vect_length, n ); |
| |
| /* find convex hull orientation */ |
| { |
| double ax = vect[n-1].x; |
| double ay = vect[n-1].y; |
| |
| for( i = 0; i < n; i++ ) |
| { |
| double bx = vect[i].x; |
| double by = vect[i].y; |
| |
| double convexity = ax * by - ay * bx; |
| |
| if( convexity != 0 ) |
| { |
| orientation = (convexity > 0) ? 1.f : (-1.f); |
| break; |
| } |
| ax = bx; |
| ay = by; |
| } |
| assert( orientation != 0 ); |
| } |
| base_a = orientation; |
| |
| /*****************************************************************************************/ |
| /* init calipers position */ |
| seq[0] = bottom; |
| seq[1] = right; |
| seq[2] = top; |
| seq[3] = left; |
| /*****************************************************************************************/ |
| /* Main loop - evaluate angles and rotate calipers */ |
| |
| /* all of edges will be checked while rotating calipers by 90 degrees */ |
| for( k = 0; k < n; k++ ) |
| { |
| /* sinus of minimal angle */ |
| /*float sinus;*/ |
| |
| /* compute cosine of angle between calipers side and polygon edge */ |
| /* dp - dot product */ |
| float dp0 = base_a * vect[seq[0]].x + base_b * vect[seq[0]].y; |
| float dp1 = -base_b * vect[seq[1]].x + base_a * vect[seq[1]].y; |
| float dp2 = -base_a * vect[seq[2]].x - base_b * vect[seq[2]].y; |
| float dp3 = base_b * vect[seq[3]].x - base_a * vect[seq[3]].y; |
| |
| float cosalpha = dp0 * inv_vect_length[seq[0]]; |
| float maxcos = cosalpha; |
| |
| /* number of calipers edges, that has minimal angle with edge */ |
| int main_element = 0; |
| |
| /* choose minimal angle */ |
| cosalpha = dp1 * inv_vect_length[seq[1]]; |
| maxcos = (cosalpha > maxcos) ? (main_element = 1, cosalpha) : maxcos; |
| cosalpha = dp2 * inv_vect_length[seq[2]]; |
| maxcos = (cosalpha > maxcos) ? (main_element = 2, cosalpha) : maxcos; |
| cosalpha = dp3 * inv_vect_length[seq[3]]; |
| maxcos = (cosalpha > maxcos) ? (main_element = 3, cosalpha) : maxcos; |
| |
| /*rotate calipers*/ |
| { |
| //get next base |
| int pindex = seq[main_element]; |
| float lead_x = vect[pindex].x*inv_vect_length[pindex]; |
| float lead_y = vect[pindex].y*inv_vect_length[pindex]; |
| switch( main_element ) |
| { |
| case 0: |
| base_a = lead_x; |
| base_b = lead_y; |
| break; |
| case 1: |
| base_a = lead_y; |
| base_b = -lead_x; |
| break; |
| case 2: |
| base_a = -lead_x; |
| base_b = -lead_y; |
| break; |
| case 3: |
| base_a = -lead_y; |
| base_b = lead_x; |
| break; |
| default: assert(0); |
| } |
| } |
| /* change base point of main edge */ |
| seq[main_element] += 1; |
| seq[main_element] = (seq[main_element] == n) ? 0 : seq[main_element]; |
| |
| |
| switch (mode) |
| { |
| case CV_CALIPERS_MAXHEIGHT: |
| { |
| /* now main element lies on edge alligned to calipers side */ |
| |
| /* find opposite element i.e. transform */ |
| /* 0->2, 1->3, 2->0, 3->1 */ |
| int opposite_el = main_element ^ 2; |
| |
| float dx = points[seq[opposite_el]].x - points[seq[main_element]].x; |
| float dy = points[seq[opposite_el]].y - points[seq[main_element]].y; |
| float dist; |
| |
| if( main_element & 1 ) |
| dist = (float)fabs(dx * base_a + dy * base_b); |
| else |
| dist = (float)fabs(dx * (-base_b) + dy * base_a); |
| |
| if( dist > max_dist ) |
| max_dist = dist; |
| |
| break; |
| } |
| case CV_CALIPERS_MINAREARECT: |
| /* find area of rectangle */ |
| { |
| float height; |
| float area; |
| |
| /* find vector left-right */ |
| float dx = points[seq[1]].x - points[seq[3]].x; |
| float dy = points[seq[1]].y - points[seq[3]].y; |
| |
| /* dotproduct */ |
| float width = dx * base_a + dy * base_b; |
| |
| /* find vector left-right */ |
| dx = points[seq[2]].x - points[seq[0]].x; |
| dy = points[seq[2]].y - points[seq[0]].y; |
| |
| /* dotproduct */ |
| height = -dx * base_b + dy * base_a; |
| |
| area = width * height; |
| if( area <= minarea ) |
| { |
| float *buf = (float *) buffer; |
| |
| minarea = area; |
| /* leftist point */ |
| ((int *) buf)[0] = seq[3]; |
| buf[1] = base_a; |
| buf[2] = width; |
| buf[3] = base_b; |
| buf[4] = height; |
| /* bottom point */ |
| ((int *) buf)[5] = seq[0]; |
| buf[6] = area; |
| } |
| break; |
| } |
| } /*switch */ |
| } /* for */ |
| |
| switch (mode) |
| { |
| case CV_CALIPERS_MINAREARECT: |
| { |
| float *buf = (float *) buffer; |
| |
| float A1 = buf[1]; |
| float B1 = buf[3]; |
| |
| float A2 = -buf[3]; |
| float B2 = buf[1]; |
| |
| float C1 = A1 * points[((int *) buf)[0]].x + points[((int *) buf)[0]].y * B1; |
| float C2 = A2 * points[((int *) buf)[5]].x + points[((int *) buf)[5]].y * B2; |
| |
| float idet = 1.f / (A1 * B2 - A2 * B1); |
| |
| float px = (C1 * B2 - C2 * B1) * idet; |
| float py = (A1 * C2 - A2 * C1) * idet; |
| |
| out[0] = px; |
| out[1] = py; |
| |
| out[2] = A1 * buf[2]; |
| out[3] = B1 * buf[2]; |
| |
| out[4] = A2 * buf[4]; |
| out[5] = B2 * buf[4]; |
| } |
| break; |
| case CV_CALIPERS_MAXHEIGHT: |
| { |
| out[0] = max_dist; |
| } |
| break; |
| } |
| |
| cvFree( &vect ); |
| cvFree( &inv_vect_length ); |
| } |
| |
| |
| CV_IMPL CvBox2D |
| cvMinAreaRect2( const CvArr* array, CvMemStorage* storage ) |
| { |
| CvMemStorage* temp_storage = 0; |
| CvBox2D box; |
| CvPoint2D32f* points = 0; |
| |
| CV_FUNCNAME( "cvMinAreaRect2" ); |
| |
| memset(&box, 0, sizeof(box)); |
| |
| __BEGIN__; |
| |
| int i, n; |
| CvSeqReader reader; |
| CvContour contour_header; |
| CvSeqBlock block; |
| CvSeq* ptseq = (CvSeq*)array; |
| CvPoint2D32f out[3]; |
| |
| if( CV_IS_SEQ(ptseq) ) |
| { |
| if( !CV_IS_SEQ_POINT_SET(ptseq) && |
| (CV_SEQ_KIND(ptseq) != CV_SEQ_KIND_CURVE || !CV_IS_SEQ_CONVEX(ptseq) || |
| CV_SEQ_ELTYPE(ptseq) != CV_SEQ_ELTYPE_PPOINT )) |
| CV_ERROR( CV_StsUnsupportedFormat, |
| "Input sequence must consist of 2d points or pointers to 2d points" ); |
| if( !storage ) |
| storage = ptseq->storage; |
| } |
| else |
| { |
| CV_CALL( ptseq = cvPointSeqFromMat( |
| CV_SEQ_KIND_GENERIC, array, &contour_header, &block )); |
| } |
| |
| if( storage ) |
| { |
| CV_CALL( temp_storage = cvCreateChildMemStorage( storage )); |
| } |
| else |
| { |
| CV_CALL( temp_storage = cvCreateMemStorage(1 << 10)); |
| } |
| |
| if( !CV_IS_SEQ_CONVEX( ptseq )) |
| { |
| CV_CALL( ptseq = cvConvexHull2( ptseq, temp_storage, CV_CLOCKWISE, 1 )); |
| } |
| else if( !CV_IS_SEQ_POINT_SET( ptseq )) |
| { |
| CvSeqWriter writer; |
| |
| if( !CV_IS_SEQ(ptseq->v_prev) || !CV_IS_SEQ_POINT_SET(ptseq->v_prev)) |
| CV_ERROR( CV_StsBadArg, |
| "Convex hull must have valid pointer to point sequence stored in v_prev" ); |
| cvStartReadSeq( ptseq, &reader ); |
| cvStartWriteSeq( CV_SEQ_KIND_CURVE|CV_SEQ_FLAG_CONVEX|CV_SEQ_ELTYPE(ptseq->v_prev), |
| sizeof(CvContour), CV_ELEM_SIZE(ptseq->v_prev->flags), |
| temp_storage, &writer ); |
| |
| for( i = 0; i < ptseq->total; i++ ) |
| { |
| CvPoint pt = **(CvPoint**)(reader.ptr); |
| CV_WRITE_SEQ_ELEM( pt, writer ); |
| } |
| |
| ptseq = cvEndWriteSeq( &writer ); |
| } |
| |
| n = ptseq->total; |
| |
| CV_CALL( points = (CvPoint2D32f*)cvAlloc( n*sizeof(points[0]) )); |
| cvStartReadSeq( ptseq, &reader ); |
| |
| if( CV_SEQ_ELTYPE( ptseq ) == CV_32SC2 ) |
| { |
| for( i = 0; i < n; i++ ) |
| { |
| CvPoint pt; |
| CV_READ_SEQ_ELEM( pt, reader ); |
| points[i].x = (float)pt.x; |
| points[i].y = (float)pt.y; |
| } |
| } |
| else |
| { |
| for( i = 0; i < n; i++ ) |
| { |
| CV_READ_SEQ_ELEM( points[i], reader ); |
| } |
| } |
| |
| if( n > 2 ) |
| { |
| icvRotatingCalipers( points, n, CV_CALIPERS_MINAREARECT, (float*)out ); |
| box.center.x = out[0].x + (out[1].x + out[2].x)*0.5f; |
| box.center.y = out[0].y + (out[1].y + out[2].y)*0.5f; |
| box.size.height = (float)sqrt((double)out[1].x*out[1].x + (double)out[1].y*out[1].y); |
| box.size.width = (float)sqrt((double)out[2].x*out[2].x + (double)out[2].y*out[2].y); |
| box.angle = (float)atan2( -(double)out[1].y, (double)out[1].x ); |
| } |
| else if( n == 2 ) |
| { |
| box.center.x = (points[0].x + points[1].x)*0.5f; |
| box.center.y = (points[0].y + points[1].y)*0.5f; |
| double dx = points[1].x - points[0].x; |
| double dy = points[1].y - points[0].y; |
| box.size.height = (float)sqrt(dx*dx + dy*dy); |
| box.size.width = 0; |
| box.angle = (float)atan2( -dy, dx ); |
| } |
| else |
| { |
| if( n == 1 ) |
| box.center = points[0]; |
| } |
| |
| box.angle = (float)(box.angle*180/CV_PI); |
| |
| __END__; |
| |
| cvReleaseMemStorage( &temp_storage ); |
| cvFree( &points ); |
| |
| return box; |
| } |
| |
