convhull.cpp

00001 /*M///////////////////////////////////////////////////////////////////////////////////////
00002 //
00003 //  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
00004 //
00005 //  By downloading, copying, installing or using the software you agree to this license.
00006 //  If you do not agree to this license, do not download, install,
00007 //  copy or use the software.
00008 //
00009 //
00010 //                        Intel License Agreement
00011 //                For Open Source Computer Vision Library
00012 //
00013 // Copyright (C) 2000, Intel Corporation, all rights reserved.
00014 // Third party copyrights are property of their respective owners.
00015 //
00016 // Redistribution and use in source and binary forms, with or without modification,
00017 // are permitted provided that the following conditions are met:
00018 //
00019 //   * Redistribution's of source code must retain the above copyright notice,
00020 //     this list of conditions and the following disclaimer.
00021 //
00022 //   * Redistribution's in binary form must reproduce the above copyright notice,
00023 //     this list of conditions and the following disclaimer in the documentation
00024 //     and/or other materials provided with the distribution.
00025 //
00026 //   * The name of Intel Corporation may not be used to endorse or promote products
00027 //     derived from this software without specific prior written permission.
00028 //
00029 // This software is provided by the copyright holders and contributors "as is" and
00030 // any express or implied warranties, including, but not limited to, the implied
00031 // warranties of merchantability and fitness for a particular purpose are disclaimed.
00032 // In no event shall the Intel Corporation or contributors be liable for any direct,
00033 // indirect, incidental, special, exemplary, or consequential damages
00034 // (including, but not limited to, procurement of substitute goods or services;
00035 // loss of use, data, or profits; or business interruption) however caused
00036 // and on any theory of liability, whether in contract, strict liability,
00037 // or tort (including negligence or otherwise) arising in any way out of
00038 // the use of this software, even if advised of the possibility of such damage.
00039 //
00040 //M*/
00041 
00042 #include "precomp.hpp"
00043 #include <iostream>
00044 
00045 namespace cv
00046 {
00047 
00048 template<typename _Tp>
00049 static int Sklansky_( Point_<_Tp>** array, int start, int end, int* stack, int nsign, int sign2 )
00050 {
00051     int incr = end > start ? 1 : -1;
00052     // prepare first triangle
00053     int pprev = start, pcur = pprev + incr, pnext = pcur + incr;
00054     int stacksize = 3;
00055 
00056     if( start == end ||
00057        (array[start]->x == array[end]->x &&
00058         array[start]->y == array[end]->y) )
00059     {
00060         stack[0] = start;
00061         return 1;
00062     }
00063 
00064     stack[0] = pprev;
00065     stack[1] = pcur;
00066     stack[2] = pnext;
00067 
00068     end += incr; // make end = afterend
00069 
00070     while( pnext != end )
00071     {
00072         // check the angle p1,p2,p3
00073         _Tp cury = array[pcur]->y;
00074         _Tp nexty = array[pnext]->y;
00075         _Tp by = nexty - cury;
00076 
00077         if( CV_SIGN( by ) != nsign )
00078         {
00079             _Tp ax = array[pcur]->x - array[pprev]->x;
00080             _Tp bx = array[pnext]->x - array[pcur]->x;
00081             _Tp ay = cury - array[pprev]->y;
00082             _Tp convexity = ay*bx - ax*by; // if >0 then convex angle
00083 
00084             if( CV_SIGN( convexity ) == sign2 && (ax != 0 || ay != 0) )
00085             {
00086                 pprev = pcur;
00087                 pcur = pnext;
00088                 pnext += incr;
00089                 stack[stacksize] = pnext;
00090                 stacksize++;
00091             }
00092             else
00093             {
00094                 if( pprev == start )
00095                 {
00096                     pcur = pnext;
00097                     stack[1] = pcur;
00098                     pnext += incr;
00099                     stack[2] = pnext;
00100                 }
00101                 else
00102                 {
00103                     stack[stacksize-2] = pnext;
00104                     pcur = pprev;
00105                     pprev = stack[stacksize-4];
00106                     stacksize--;
00107                 }
00108             }
00109         }
00110         else
00111         {
00112             pnext += incr;
00113             stack[stacksize-1] = pnext;
00114         }
00115     }
00116 
00117     return --stacksize;
00118 }
00119 
00120 
00121 template<typename _Tp>
00122 struct CHullCmpPoints
00123 {
00124     bool operator()(const Point_<_Tp>* p1, const Point_<_Tp>* p2) const
00125     { return p1->x < p2->x || (p1->x == p2->x && p1->y < p2->y); }
00126 };
00127 
00128 
00129 void convexHull( InputArray _points, OutputArray _hull, bool clockwise, bool returnPoints )
00130 {
00131     Mat points = _points.getMat();
00132     int i, total = points.checkVector(2), depth = points.depth(), nout = 0;
00133     int miny_ind = 0, maxy_ind = 0;
00134     CV_Assert(total >= 0 && (depth == CV_32F || depth == CV_32S));
00135 
00136     if( total == 0 )
00137     {
00138         _hull.release();
00139         return;
00140     }
00141 
00142     returnPoints = !_hull.fixedType() ? returnPoints : _hull.type() != CV_32S;
00143 
00144     bool is_float = depth == CV_32F;
00145     AutoBuffer<Point*> _pointer(total);
00146     AutoBuffer<int>  _stack(total + 2), _hullbuf(total);
00147     Point** pointer = _pointer;
00148     Point2f ** pointerf = (Point2f **)pointer;
00149     Point* data0 = points.ptr<Point>();
00150     int* stack = _stack;
00151     int* hullbuf = _hullbuf;
00152 
00153     CV_Assert(points.isContinuous());
00154 
00155     for( i = 0; i < total; i++ )
00156         pointer[i] = &data0[i];
00157 
00158     // sort the point set by x-coordinate, find min and max y
00159     if( !is_float )
00160     {
00161         std::sort(pointer, pointer + total, CHullCmpPoints<int>());
00162         for( i = 1; i < total; i++ )
00163         {
00164             int y = pointer[i]->y;
00165             if( pointer[miny_ind]->y > y )
00166                 miny_ind = i;
00167             if( pointer[maxy_ind]->y < y )
00168                 maxy_ind = i;
00169         }
00170     }
00171     else
00172     {
00173         std::sort(pointerf, pointerf + total, CHullCmpPoints<float>());
00174         for( i = 1; i < total; i++ )
00175         {
00176             float y = pointerf[i]->y;
00177             if( pointerf[miny_ind]->y > y )
00178                 miny_ind = i;
00179             if( pointerf[maxy_ind]->y < y )
00180                 maxy_ind = i;
00181         }
00182     }
00183 
00184     if( pointer[0]->x == pointer[total-1]->x &&
00185         pointer[0]->y == pointer[total-1]->y )
00186     {
00187         hullbuf[nout++] = 0;
00188     }
00189     else
00190     {
00191         // upper half
00192         int *tl_stack = stack;
00193         int tl_count = !is_float ?
00194             Sklansky_( pointer, 0, maxy_ind, tl_stack, -1, 1) :
00195             Sklansky_( pointerf, 0, maxy_ind, tl_stack, -1, 1);
00196         int *tr_stack = stack + tl_count;
00197         int tr_count = !is_float ?
00198             Sklansky_( pointer, total-1, maxy_ind, tr_stack, -1, -1) :
00199             Sklansky_( pointerf, total-1, maxy_ind, tr_stack, -1, -1);
00200 
00201         // gather upper part of convex hull to output
00202         if( !clockwise )
00203         {
00204             std::swap( tl_stack, tr_stack );
00205             std::swap( tl_count, tr_count );
00206         }
00207 
00208         for( i = 0; i < tl_count-1; i++ )
00209             hullbuf[nout++] = int(pointer[tl_stack[i]] - data0);
00210         for( i = tr_count - 1; i > 0; i-- )
00211             hullbuf[nout++] = int(pointer[tr_stack[i]] - data0);
00212         int stop_idx = tr_count > 2 ? tr_stack[1] : tl_count > 2 ? tl_stack[tl_count - 2] : -1;
00213 
00214         // lower half
00215         int *bl_stack = stack;
00216         int bl_count = !is_float ?
00217             Sklansky_( pointer, 0, miny_ind, bl_stack, 1, -1) :
00218             Sklansky_( pointerf, 0, miny_ind, bl_stack, 1, -1);
00219         int *br_stack = stack + bl_count;
00220         int br_count = !is_float ?
00221             Sklansky_( pointer, total-1, miny_ind, br_stack, 1, 1) :
00222             Sklansky_( pointerf, total-1, miny_ind, br_stack, 1, 1);
00223 
00224         if( clockwise )
00225         {
00226             std::swap( bl_stack, br_stack );
00227             std::swap( bl_count, br_count );
00228         }
00229 
00230         if( stop_idx >= 0 )
00231         {
00232             int check_idx = bl_count > 2 ? bl_stack[1] :
00233             bl_count + br_count > 2 ? br_stack[2-bl_count] : -1;
00234             if( check_idx == stop_idx || (check_idx >= 0 &&
00235                                           pointer[check_idx]->x == pointer[stop_idx]->x &&
00236                                           pointer[check_idx]->y == pointer[stop_idx]->y) )
00237             {
00238                 // if all the points lie on the same line, then
00239                 // the bottom part of the convex hull is the mirrored top part
00240                 // (except the exteme points).
00241                 bl_count = MIN( bl_count, 2 );
00242                 br_count = MIN( br_count, 2 );
00243             }
00244         }
00245 
00246         for( i = 0; i < bl_count-1; i++ )
00247             hullbuf[nout++] = int(pointer[bl_stack[i]] - data0);
00248         for( i = br_count-1; i > 0; i-- )
00249             hullbuf[nout++] = int(pointer[br_stack[i]] - data0);
00250     }
00251 
00252     if( !returnPoints )
00253         Mat(nout, 1, CV_32S, hullbuf).copyTo(_hull);
00254     else
00255     {
00256         _hull.create(nout, 1, CV_MAKETYPE(depth, 2));
00257         Mat hull = _hull.getMat();
00258         size_t step = !hull.isContinuous() ? hull.step[0] : sizeof(Point);
00259         for( i = 0; i < nout; i++ )
00260             *(Point*)(hull.ptr() + i*step) = data0[hullbuf[i]];
00261     }
00262 }
00263 
00264 
00265 void convexityDefects( InputArray _points, InputArray _hull, OutputArray _defects )
00266 {
00267     Mat points = _points.getMat();
00268     int i, j = 0, npoints = points.checkVector(2, CV_32S);
00269     CV_Assert( npoints >= 0 );
00270 
00271     if( npoints <= 3 )
00272     {
00273         _defects.release();
00274         return;
00275     }
00276 
00277     Mat hull = _hull.getMat();
00278     int hpoints = hull.checkVector(1, CV_32S);
00279     CV_Assert( hpoints > 2 );
00280 
00281     const Point* ptr = points.ptr<Point>();
00282     const int* hptr = hull.ptr<int>();
00283     std::vector<Vec4i> defects;
00284 
00285     // 1. recognize co-orientation of the contour and its hull
00286     bool rev_orientation = ((hptr[1] > hptr[0]) + (hptr[2] > hptr[1]) + (hptr[0] > hptr[2])) != 2;
00287 
00288     // 2. cycle through points and hull, compute defects
00289     int hcurr = hptr[rev_orientation ? 0 : hpoints-1];
00290     CV_Assert( 0 <= hcurr && hcurr < npoints );
00291 
00292     for( i = 0; i < hpoints; i++ )
00293     {
00294         int hnext = hptr[rev_orientation ? hpoints - i - 1 : i];
00295         CV_Assert( 0 <= hnext && hnext < npoints );
00296 
00297         Point pt0 = ptr[hcurr], pt1 = ptr[hnext];
00298         double dx0 = pt1.x - pt0.x;
00299         double dy0 = pt1.y - pt0.y;
00300         double scale = dx0 == 0 && dy0 == 0 ? 0. : 1./std::sqrt(dx0*dx0 + dy0*dy0);
00301 
00302         int defect_deepest_point = -1;
00303         double defect_depth = 0;
00304         bool is_defect = false;
00305 
00306         for(;;)
00307         {
00308             // go through points to achieve next hull point
00309             j++;
00310             j &= j >= npoints ? 0 : -1;
00311             if( j == hnext )
00312                 break;
00313 
00314             // compute distance from current point to hull edge
00315             double dx = ptr[j].x - pt0.x;
00316             double dy = ptr[j].y - pt0.y;
00317             double dist = fabs(-dy0*dx + dx0*dy) * scale;
00318 
00319             if( dist > defect_depth )
00320             {
00321                 defect_depth = dist;
00322                 defect_deepest_point = j;
00323                 is_defect = true;
00324             }
00325         }
00326 
00327         if( is_defect )
00328         {
00329             int idepth = cvRound(defect_depth*256);
00330             defects.push_back(Vec4i (hcurr, hnext, defect_deepest_point, idepth));
00331         }
00332 
00333         hcurr = hnext;
00334     }
00335 
00336     Mat(defects).copyTo(_defects);
00337 }
00338 
00339 
00340 template<typename _Tp>
00341 static bool isContourConvex_( const Point_<_Tp>* p, int n )
00342 {
00343     Point_<_Tp> prev_pt = p[(n-2+n) % n];
00344     Point_<_Tp> cur_pt = p[n-1];
00345 
00346     _Tp dx0 = cur_pt.x - prev_pt.x;
00347     _Tp dy0 = cur_pt.y - prev_pt.y;
00348     int orientation = 0;
00349 
00350     for( int i = 0; i < n; i++ )
00351     {
00352         _Tp dxdy0, dydx0;
00353         _Tp dx, dy;
00354 
00355         prev_pt = cur_pt;
00356         cur_pt = p[i];
00357 
00358         dx = cur_pt.x - prev_pt.x;
00359         dy = cur_pt.y - prev_pt.y;
00360         dxdy0 = dx * dy0;
00361         dydx0 = dy * dx0;
00362 
00363         // find orientation
00364         // orient = -dy0 * dx + dx0 * dy;
00365         // orientation |= (orient > 0) ? 1 : 2;
00366         orientation |= (dydx0 > dxdy0) ? 1 : ((dydx0 < dxdy0) ? 2 : 3);
00367         if( orientation == 3 )
00368             return false;
00369 
00370         dx0 = dx;
00371         dy0 = dy;
00372     }
00373 
00374     return true;
00375 }
00376 
00377 
00378 bool isContourConvex( InputArray _contour )
00379 {
00380     Mat contour = _contour.getMat();
00381     int total = contour.checkVector(2), depth = contour.depth();
00382     CV_Assert(total >= 0 && (depth == CV_32F || depth == CV_32S));
00383 
00384     if( total == 0 )
00385         return false;
00386 
00387     return depth == CV_32S ?
00388     isContourConvex_(contour.ptr<Point>(), total ) :
00389     isContourConvex_(contour.ptr<Point2f >(), total );
00390 }
00391 
00392 }
00393 
00394 CV_IMPL CvSeq*
00395 cvConvexHull2( const CvArr* array, void* hull_storage,
00396                int orientation, int return_points )
00397 {
00398     union { CvContour* c; CvSeq* s; } hull;
00399     hull.s = 0;
00400 
00401     CvMat* mat = 0;
00402     CvContour contour_header;
00403     CvSeq hull_header;
00404     CvSeqBlock block, hullblock;
00405     CvSeq* ptseq = 0;
00406     CvSeq* hullseq = 0;
00407 
00408     if( CV_IS_SEQ( array ))
00409     {
00410         ptseq = (CvSeq*)array;
00411         if( !CV_IS_SEQ_POINT_SET( ptseq ))
00412             CV_Error( CV_StsBadArg, "Unsupported sequence type" );
00413         if( hull_storage == 0 )
00414             hull_storage = ptseq->storage;
00415     }
00416     else
00417     {
00418         ptseq = cvPointSeqFromMat( CV_SEQ_KIND_GENERIC, array, &contour_header, &block );
00419     }
00420 
00421     if( CV_IS_STORAGE( hull_storage ))
00422     {
00423         if( return_points )
00424         {
00425             hullseq = cvCreateSeq(CV_SEQ_KIND_CURVE|CV_SEQ_ELTYPE(ptseq)|
00426                                   CV_SEQ_FLAG_CLOSED|CV_SEQ_FLAG_CONVEX,
00427                                   sizeof(CvContour), sizeof(CvPoint),(CvMemStorage*)hull_storage );
00428         }
00429         else
00430         {
00431             hullseq = cvCreateSeq(
00432                                   CV_SEQ_KIND_CURVE|CV_SEQ_ELTYPE_PPOINT|
00433                                   CV_SEQ_FLAG_CLOSED|CV_SEQ_FLAG_CONVEX,
00434                                   sizeof(CvContour), sizeof(CvPoint*), (CvMemStorage*)hull_storage );
00435         }
00436     }
00437     else
00438     {
00439         if( !CV_IS_MAT( hull_storage ))
00440             CV_Error(CV_StsBadArg, "Destination must be valid memory storage or matrix");
00441 
00442         mat = (CvMat*)hull_storage;
00443 
00444         if( (mat->cols != 1 && mat->rows != 1) || !CV_IS_MAT_CONT(mat->type))
00445             CV_Error( CV_StsBadArg,
00446                      "The hull matrix should be continuous and have a single row or a single column" );
00447 
00448         if( mat->cols + mat->rows - 1 < ptseq->total )
00449             CV_Error( CV_StsBadSize, "The hull matrix size might be not enough to fit the hull" );
00450 
00451         if( CV_MAT_TYPE(mat->type) != CV_SEQ_ELTYPE(ptseq) &&
00452            CV_MAT_TYPE(mat->type) != CV_32SC1 )
00453             CV_Error( CV_StsUnsupportedFormat,
00454                      "The hull matrix must have the same type as input or 32sC1 (integers)" );
00455 
00456         hullseq = cvMakeSeqHeaderForArray(
00457                                           CV_SEQ_KIND_CURVE|CV_MAT_TYPE(mat->type)|CV_SEQ_FLAG_CLOSED,
00458                                           sizeof(hull_header), CV_ELEM_SIZE(mat->type), mat->data.ptr,
00459                                           mat->cols + mat->rows - 1, &hull_header, &hullblock );
00460         cvClearSeq( hullseq );
00461     }
00462 
00463     int hulltype = CV_SEQ_ELTYPE(hullseq);
00464     int total = ptseq->total;
00465     if( total == 0 )
00466     {
00467         if( mat )
00468             CV_Error( CV_StsBadSize,
00469                      "Point sequence can not be empty if the output is matrix" );
00470         return hull.s;
00471     }
00472 
00473     cv::AutoBuffer<double> _ptbuf;
00474     cv::Mat h0;
00475     cv::convexHull(cv::cvarrToMat(ptseq, false, false, 0, &_ptbuf), h0,
00476                    orientation == CV_CLOCKWISE, CV_MAT_CN(hulltype) == 2);
00477 
00478 
00479     if( hulltype == CV_SEQ_ELTYPE_PPOINT )
00480     {
00481         const int* idx = h0.ptr<int>();
00482         int ctotal = (int)h0.total();
00483         for( int i = 0; i < ctotal; i++ )
00484         {
00485             void* ptr = cvGetSeqElem(ptseq, idx[i]);
00486             cvSeqPush( hullseq, &ptr );
00487         }
00488     }
00489     else
00490         cvSeqPushMulti(hullseq, h0.ptr(), (int)h0.total());
00491 
00492     if( mat )
00493     {
00494         if( mat->rows > mat->cols )
00495             mat->rows = hullseq->total;
00496         else
00497             mat->cols = hullseq->total;
00498     }
00499     else
00500     {
00501         hull.s = hullseq;
00502         hull.c->rect = cvBoundingRect( ptseq,
00503                                        ptseq->header_size < (int)sizeof(CvContour) ||
00504                                        &ptseq->flags == &contour_header.flags );
00505     }
00506 
00507     return hull.s;
00508 }
00509 
00510 
00511 /* contour must be a simple polygon */
00512 /* it must have more than 3 points  */
00513 CV_IMPL CvSeq* cvConvexityDefects( const CvArr* array,
00514                                   const CvArr* hullarray,
00515                                   CvMemStorage* storage )
00516 {
00517     CvSeq* defects = 0;
00518 
00519     int i, index;
00520     CvPoint* hull_cur;
00521 
00522     /* is orientation of hull different from contour one */
00523     int rev_orientation;
00524 
00525     CvContour contour_header;
00526     CvSeq hull_header;
00527     CvSeqBlock block, hullblock;
00528     CvSeq *ptseq = (CvSeq*)array, *hull = (CvSeq*)hullarray;
00529 
00530     CvSeqReader hull_reader;
00531     CvSeqReader ptseq_reader;
00532     CvSeqWriter writer;
00533     int is_index;
00534 
00535     if( CV_IS_SEQ( ptseq ))
00536     {
00537         if( !CV_IS_SEQ_POINT_SET( ptseq ))
00538             CV_Error( CV_StsUnsupportedFormat,
00539                      "Input sequence is not a sequence of points" );
00540         if( !storage )
00541             storage = ptseq->storage;
00542     }
00543     else
00544     {
00545         ptseq = cvPointSeqFromMat( CV_SEQ_KIND_GENERIC, array, &contour_header, &block );
00546     }
00547 
00548     if( CV_SEQ_ELTYPE( ptseq ) != CV_32SC2 )
00549         CV_Error( CV_StsUnsupportedFormat, "Floating-point coordinates are not supported here" );
00550 
00551     if( CV_IS_SEQ( hull ))
00552     {
00553         int hulltype = CV_SEQ_ELTYPE( hull );
00554         if( hulltype != CV_SEQ_ELTYPE_PPOINT && hulltype != CV_SEQ_ELTYPE_INDEX )
00555             CV_Error( CV_StsUnsupportedFormat,
00556                      "Convex hull must represented as a sequence "
00557                      "of indices or sequence of pointers" );
00558         if( !storage )
00559             storage = hull->storage;
00560     }
00561     else
00562     {
00563         CvMat* mat = (CvMat*)hull;
00564 
00565         if( !CV_IS_MAT( hull ))
00566             CV_Error(CV_StsBadArg, "Convex hull is neither sequence nor matrix");
00567 
00568         if( (mat->cols != 1 && mat->rows != 1) ||
00569            !CV_IS_MAT_CONT(mat->type) || CV_MAT_TYPE(mat->type) != CV_32SC1 )
00570             CV_Error( CV_StsBadArg,
00571                      "The matrix should be 1-dimensional and continuous array of int's" );
00572 
00573         if( mat->cols + mat->rows - 1 > ptseq->total )
00574             CV_Error( CV_StsBadSize, "Convex hull is larger than the point sequence" );
00575 
00576         hull = cvMakeSeqHeaderForArray(
00577                                        CV_SEQ_KIND_CURVE|CV_MAT_TYPE(mat->type)|CV_SEQ_FLAG_CLOSED,
00578                                        sizeof(CvContour), CV_ELEM_SIZE(mat->type), mat->data.ptr,
00579                                        mat->cols + mat->rows - 1, &hull_header, &hullblock );
00580     }
00581 
00582     is_index = CV_SEQ_ELTYPE(hull) == CV_SEQ_ELTYPE_INDEX;
00583 
00584     if( !storage )
00585         CV_Error( CV_StsNullPtr, "NULL storage pointer" );
00586 
00587     defects = cvCreateSeq( CV_SEQ_KIND_GENERIC, sizeof(CvSeq), sizeof(CvConvexityDefect), storage );
00588 
00589     if( ptseq->total < 4 || hull->total < 3)
00590     {
00591         //CV_ERROR( CV_StsBadSize,
00592         //    "point seq size must be >= 4, convex hull size must be >= 3" );
00593         return defects;
00594     }
00595 
00596     /* recognize co-orientation of ptseq and its hull */
00597     {
00598         int sign = 0;
00599         int index1, index2, index3;
00600 
00601         if( !is_index )
00602         {
00603             CvPoint* pos = *CV_SEQ_ELEM( hull, CvPoint*, 0 );
00604             index1 = cvSeqElemIdx( ptseq, pos );
00605 
00606             pos = *CV_SEQ_ELEM( hull, CvPoint*, 1 );
00607             index2 = cvSeqElemIdx( ptseq, pos );
00608 
00609             pos = *CV_SEQ_ELEM( hull, CvPoint*, 2 );
00610             index3 = cvSeqElemIdx( ptseq, pos );
00611         }
00612         else
00613         {
00614             index1 = *CV_SEQ_ELEM( hull, int, 0 );
00615             index2 = *CV_SEQ_ELEM( hull, int, 1 );
00616             index3 = *CV_SEQ_ELEM( hull, int, 2 );
00617         }
00618 
00619         sign += (index2 > index1) ? 1 : 0;
00620         sign += (index3 > index2) ? 1 : 0;
00621         sign += (index1 > index3) ? 1 : 0;
00622 
00623         rev_orientation = (sign == 2) ? 0 : 1;
00624     }
00625 
00626     cvStartReadSeq( ptseq, &ptseq_reader, 0 );
00627     cvStartReadSeq( hull, &hull_reader, rev_orientation );
00628 
00629     if( !is_index )
00630     {
00631         hull_cur = *(CvPoint**)hull_reader.prev_elem;
00632         index = cvSeqElemIdx( ptseq, (char*)hull_cur, 0 );
00633     }
00634     else
00635     {
00636         index = *(int*)hull_reader.prev_elem;
00637         hull_cur = CV_GET_SEQ_ELEM( CvPoint, ptseq, index );
00638     }
00639     cvSetSeqReaderPos( &ptseq_reader, index );
00640     cvStartAppendToSeq( defects, &writer );
00641 
00642     /* cycle through ptseq and hull with computing defects */
00643     for( i = 0; i < hull->total; i++ )
00644     {
00645         CvConvexityDefect defect;
00646         int is_defect = 0;
00647         double dx0, dy0;
00648         double depth = 0, scale;
00649         CvPoint* hull_next;
00650 
00651         if( !is_index )
00652             hull_next = *(CvPoint**)hull_reader.ptr;
00653         else
00654         {
00655             int t = *(int*)hull_reader.ptr;
00656             hull_next = CV_GET_SEQ_ELEM( CvPoint, ptseq, t );
00657         }
00658 
00659         dx0 = (double)hull_next->x - (double)hull_cur->x;
00660         dy0 = (double)hull_next->y - (double)hull_cur->y;
00661         assert( dx0 != 0 || dy0 != 0 );
00662         scale = 1./std::sqrt(dx0*dx0 + dy0*dy0);
00663 
00664         defect.start = hull_cur;
00665         defect.end = hull_next;
00666 
00667         for(;;)
00668         {
00669             /* go through ptseq to achieve next hull point */
00670             CV_NEXT_SEQ_ELEM( sizeof(CvPoint), ptseq_reader );
00671 
00672             if( ptseq_reader.ptr == (schar*)hull_next )
00673                 break;
00674             else
00675             {
00676                 CvPoint* cur = (CvPoint*)ptseq_reader.ptr;
00677 
00678                 /* compute distance from current point to hull edge */
00679                 double dx = (double)cur->x - (double)hull_cur->x;
00680                 double dy = (double)cur->y - (double)hull_cur->y;
00681 
00682                 /* compute depth */
00683                 double dist = fabs(-dy0*dx + dx0*dy) * scale;
00684 
00685                 if( dist > depth )
00686                 {
00687                     depth = dist;
00688                     defect.depth_point = cur;
00689                     defect.depth = (float)depth;
00690                     is_defect = 1;
00691                 }
00692             }
00693         }
00694         if( is_defect )
00695         {
00696             CV_WRITE_SEQ_ELEM( defect, writer );
00697         }
00698 
00699         hull_cur = hull_next;
00700         if( rev_orientation )
00701         {
00702             CV_PREV_SEQ_ELEM( hull->elem_size, hull_reader );
00703         }
00704         else
00705         {
00706             CV_NEXT_SEQ_ELEM( hull->elem_size, hull_reader );
00707         }
00708     }
00709 
00710     return cvEndWriteSeq( &writer );
00711 }
00712 
00713 
00714 CV_IMPL int
00715 cvCheckContourConvexity( const CvArr* array )
00716 {
00717     CvContour contour_header;
00718     CvSeqBlock block;
00719     CvSeq* contour = (CvSeq*)array;
00720 
00721     if( CV_IS_SEQ(contour) )
00722     {
00723         if( !CV_IS_SEQ_POINT_SET(contour))
00724             CV_Error( CV_StsUnsupportedFormat,
00725                      "Input sequence must be polygon (closed 2d curve)" );
00726     }
00727     else
00728     {
00729         contour = cvPointSeqFromMat(CV_SEQ_KIND_CURVE|
00730             CV_SEQ_FLAG_CLOSED, array, &contour_header, &block );
00731     }
00732 
00733     if( contour->total == 0 )
00734         return -1;
00735 
00736     cv::AutoBuffer<double> _buf;
00737     return cv::isContourConvex(cv::cvarrToMat(contour, false, false, 0, &_buf)) ? 1 : 0;
00738 }
00739 
00740 /* End of file. */
00741