1 /*M///////////////////////////////////////////////////////////////////////////////////////
2 //
3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
4 //
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.
8 //
9 //
10 // Intel License Agreement
11 // For Open Source Computer Vision Library
12 //
13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
14 // Third party copyrights are property of their respective owners.
15 //
16 // Redistribution and use in source and binary forms, with or without modification,
17 // are permitted provided that the following conditions are met:
18 //
19 // * Redistribution's of source code must retain the above copyright notice,
20 // this list of conditions and the following disclaimer.
21 //
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.
25 //
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.
28 //
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.
39 //
40 //M*/
41
42 #include "_cv.h"
43
44 static int
icvSklansky_32s(CvPoint ** array,int start,int end,int * stack,int nsign,int sign2)45 icvSklansky_32s( CvPoint** array, int start, int end, int* stack, int nsign, int sign2 )
46 {
47 int incr = end > start ? 1 : -1;
48 /* prepare first triangle */
49 int pprev = start, pcur = pprev + incr, pnext = pcur + incr;
50 int stacksize = 3;
51
52 if( start == end ||
53 (array[start]->x == array[end]->x &&
54 array[start]->y == array[end]->y) )
55 {
56 stack[0] = start;
57 return 1;
58 }
59
60 stack[0] = pprev;
61 stack[1] = pcur;
62 stack[2] = pnext;
63
64 end += incr; /* make end = afterend */
65
66 while( pnext != end )
67 {
68 /* check the angle p1,p2,p3 */
69 int cury = array[pcur]->y;
70 int nexty = array[pnext]->y;
71 int by = nexty - cury;
72
73 if( CV_SIGN(by) != nsign )
74 {
75 int ax = array[pcur]->x - array[pprev]->x;
76 int bx = array[pnext]->x - array[pcur]->x;
77 int ay = cury - array[pprev]->y;
78 int convexity = ay*bx - ax*by;/* if >0 then convex angle */
79
80 if( CV_SIGN(convexity) == sign2 && (ax != 0 || ay != 0) )
81 {
82 pprev = pcur;
83 pcur = pnext;
84 pnext += incr;
85 stack[stacksize] = pnext;
86 stacksize++;
87 }
88 else
89 {
90 if( pprev == start )
91 {
92 pcur = pnext;
93 stack[1] = pcur;
94 pnext += incr;
95 stack[2] = pnext;
96 }
97 else
98 {
99 stack[stacksize-2] = pnext;
100 pcur = pprev;
101 pprev = stack[stacksize-4];
102 stacksize--;
103 }
104 }
105 }
106 else
107 {
108 pnext += incr;
109 stack[stacksize-1] = pnext;
110 }
111 }
112
113 return --stacksize;
114 }
115
116
117 static int
icvSklansky_32f(CvPoint2D32f ** array,int start,int end,int * stack,int nsign,int sign2)118 icvSklansky_32f( CvPoint2D32f** array, int start, int end, int* stack, int nsign, int sign2 )
119 {
120 int incr = end > start ? 1 : -1;
121 /* prepare first triangle */
122 int pprev = start, pcur = pprev + incr, pnext = pcur + incr;
123 int stacksize = 3;
124
125 if( start == end ||
126 (array[start]->x == array[end]->x &&
127 array[start]->y == array[end]->y) )
128 {
129 stack[0] = start;
130 return 1;
131 }
132
133 stack[0] = pprev;
134 stack[1] = pcur;
135 stack[2] = pnext;
136
137 end += incr; /* make end = afterend */
138
139 while( pnext != end )
140 {
141 /* check the angle p1,p2,p3 */
142 float cury = array[pcur]->y;
143 float nexty = array[pnext]->y;
144 float by = nexty - cury;
145
146 if( CV_SIGN( by ) != nsign )
147 {
148 float ax = array[pcur]->x - array[pprev]->x;
149 float bx = array[pnext]->x - array[pcur]->x;
150 float ay = cury - array[pprev]->y;
151 float convexity = ay*bx - ax*by;/* if >0 then convex angle */
152
153 if( CV_SIGN( convexity ) == sign2 && (ax != 0 || ay != 0) )
154 {
155 pprev = pcur;
156 pcur = pnext;
157 pnext += incr;
158 stack[stacksize] = pnext;
159 stacksize++;
160 }
161 else
162 {
163 if( pprev == start )
164 {
165 pcur = pnext;
166 stack[1] = pcur;
167 pnext += incr;
168 stack[2] = pnext;
169
170 }
171 else
172 {
173 stack[stacksize-2] = pnext;
174 pcur = pprev;
175 pprev = stack[stacksize-4];
176 stacksize--;
177 }
178 }
179 }
180 else
181 {
182 pnext += incr;
183 stack[stacksize-1] = pnext;
184 }
185 }
186
187 return --stacksize;
188 }
189
190 typedef int (*sklansky_func)( CvPoint** points, int start, int end,
191 int* stack, int sign, int sign2 );
192
193 #define cmp_pts( pt1, pt2 ) \
194 ((pt1)->x < (pt2)->x || ((pt1)->x <= (pt2)->x && (pt1)->y < (pt2)->y))
CV_IMPLEMENT_QSORT(icvSortPointsByPointers_32s,CvPoint *,cmp_pts)195 static CV_IMPLEMENT_QSORT( icvSortPointsByPointers_32s, CvPoint*, cmp_pts )
196 static CV_IMPLEMENT_QSORT( icvSortPointsByPointers_32f, CvPoint2D32f*, cmp_pts )
197
198 static void
199 icvCalcAndWritePtIndices( CvPoint** pointer, int* stack, int start, int end,
200 CvSeq* ptseq, CvSeqWriter* writer )
201 {
202 CV_FUNCNAME( "icvCalcAndWritePtIndices" );
203
204 __BEGIN__;
205
206 int i, incr = start < end ? 1 : -1;
207 int idx, first_idx = ptseq->first->start_index;
208
209 for( i = start; i != end; i += incr )
210 {
211 CvPoint* ptr = (CvPoint*)pointer[stack[i]];
212 CvSeqBlock* block = ptseq->first;
213 while( (unsigned)(idx = (int)(ptr - (CvPoint*)block->data)) >= (unsigned)block->count )
214 {
215 block = block->next;
216 if( block == ptseq->first )
217 CV_ERROR( CV_StsError, "Internal error" );
218 }
219 idx += block->start_index - first_idx;
220 CV_WRITE_SEQ_ELEM( idx, *writer );
221 }
222
223 __END__;
224 }
225
226
227 CV_IMPL CvSeq*
cvConvexHull2(const CvArr * array,void * hull_storage,int orientation,int return_points)228 cvConvexHull2( const CvArr* array, void* hull_storage,
229 int orientation, int return_points )
230 {
231 union { CvContour* c; CvSeq* s; } hull;
232 CvPoint** pointer = 0;
233 CvPoint2D32f** pointerf = 0;
234 int* stack = 0;
235
236 CV_FUNCNAME( "cvConvexHull2" );
237
238 hull.s = 0;
239
240 __BEGIN__;
241
242 CvMat* mat = 0;
243 CvSeqReader reader;
244 CvSeqWriter writer;
245 CvContour contour_header;
246 union { CvContour c; CvSeq s; } hull_header;
247 CvSeqBlock block, hullblock;
248 CvSeq* ptseq = 0;
249 CvSeq* hullseq = 0;
250 int is_float;
251 int* t_stack;
252 int t_count;
253 int i, miny_ind = 0, maxy_ind = 0, total;
254 int hulltype;
255 int stop_idx;
256 sklansky_func sklansky;
257
258 if( CV_IS_SEQ( array ))
259 {
260 ptseq = (CvSeq*)array;
261 if( !CV_IS_SEQ_POINT_SET( ptseq ))
262 CV_ERROR( CV_StsBadArg, "Unsupported sequence type" );
263 if( hull_storage == 0 )
264 hull_storage = ptseq->storage;
265 }
266 else
267 {
268 CV_CALL( ptseq = cvPointSeqFromMat(
269 CV_SEQ_KIND_GENERIC, array, &contour_header, &block ));
270 }
271
272 if( CV_IS_STORAGE( hull_storage ))
273 {
274 if( return_points )
275 {
276 CV_CALL( hullseq = cvCreateSeq(
277 CV_SEQ_KIND_CURVE|CV_SEQ_ELTYPE(ptseq)|
278 CV_SEQ_FLAG_CLOSED|CV_SEQ_FLAG_CONVEX,
279 sizeof(CvContour), sizeof(CvPoint),(CvMemStorage*)hull_storage ));
280 }
281 else
282 {
283 CV_CALL( hullseq = cvCreateSeq(
284 CV_SEQ_KIND_CURVE|CV_SEQ_ELTYPE_PPOINT|
285 CV_SEQ_FLAG_CLOSED|CV_SEQ_FLAG_CONVEX,
286 sizeof(CvContour), sizeof(CvPoint*), (CvMemStorage*)hull_storage ));
287 }
288 }
289 else
290 {
291 if( !CV_IS_MAT( hull_storage ))
292 CV_ERROR(CV_StsBadArg, "Destination must be valid memory storage or matrix");
293
294 mat = (CvMat*)hull_storage;
295
296 if( (mat->cols != 1 && mat->rows != 1) || !CV_IS_MAT_CONT(mat->type))
297 CV_ERROR( CV_StsBadArg,
298 "The hull matrix should be continuous and have a single row or a single column" );
299
300 if( mat->cols + mat->rows - 1 < ptseq->total )
301 CV_ERROR( CV_StsBadSize, "The hull matrix size might be not enough to fit the hull" );
302
303 if( CV_MAT_TYPE(mat->type) != CV_SEQ_ELTYPE(ptseq) &&
304 CV_MAT_TYPE(mat->type) != CV_32SC1 )
305 CV_ERROR( CV_StsUnsupportedFormat,
306 "The hull matrix must have the same type as input or 32sC1 (integers)" );
307
308 CV_CALL( hullseq = cvMakeSeqHeaderForArray(
309 CV_SEQ_KIND_CURVE|CV_MAT_TYPE(mat->type)|CV_SEQ_FLAG_CLOSED,
310 sizeof(contour_header), CV_ELEM_SIZE(mat->type), mat->data.ptr,
311 mat->cols + mat->rows - 1, &hull_header.s, &hullblock ));
312
313 cvClearSeq( hullseq );
314 }
315
316 total = ptseq->total;
317 if( total == 0 )
318 {
319 if( mat )
320 CV_ERROR( CV_StsBadSize,
321 "Point sequence can not be empty if the output is matrix" );
322 EXIT;
323 }
324
325 cvStartAppendToSeq( hullseq, &writer );
326
327 is_float = CV_SEQ_ELTYPE(ptseq) == CV_32FC2;
328 hulltype = CV_SEQ_ELTYPE(hullseq);
329 sklansky = !is_float ? (sklansky_func)icvSklansky_32s :
330 (sklansky_func)icvSklansky_32f;
331
332 CV_CALL( pointer = (CvPoint**)cvAlloc( ptseq->total*sizeof(pointer[0]) ));
333 CV_CALL( stack = (int*)cvAlloc( (ptseq->total + 2)*sizeof(stack[0]) ));
334 pointerf = (CvPoint2D32f**)pointer;
335
336 cvStartReadSeq( ptseq, &reader );
337
338 for( i = 0; i < total; i++ )
339 {
340 pointer[i] = (CvPoint*)reader.ptr;
341 CV_NEXT_SEQ_ELEM( ptseq->elem_size, reader );
342 }
343
344 // sort the point set by x-coordinate, find min and max y
345 if( !is_float )
346 {
347 icvSortPointsByPointers_32s( pointer, total, 0 );
348 for( i = 1; i < total; i++ )
349 {
350 int y = pointer[i]->y;
351 if( pointer[miny_ind]->y > y )
352 miny_ind = i;
353 if( pointer[maxy_ind]->y < y )
354 maxy_ind = i;
355 }
356 }
357 else
358 {
359 icvSortPointsByPointers_32f( pointerf, total, 0 );
360 for( i = 1; i < total; i++ )
361 {
362 float y = pointerf[i]->y;
363 if( pointerf[miny_ind]->y > y )
364 miny_ind = i;
365 if( pointerf[maxy_ind]->y < y )
366 maxy_ind = i;
367 }
368 }
369
370 if( pointer[0]->x == pointer[total-1]->x &&
371 pointer[0]->y == pointer[total-1]->y )
372 {
373 if( hulltype == CV_SEQ_ELTYPE_PPOINT )
374 {
375 CV_WRITE_SEQ_ELEM( pointer[0], writer );
376 }
377 else if( hulltype == CV_SEQ_ELTYPE_INDEX )
378 {
379 int index = 0;
380 CV_WRITE_SEQ_ELEM( index, writer );
381 }
382 else
383 {
384 CvPoint pt = pointer[0][0];
385 CV_WRITE_SEQ_ELEM( pt, writer );
386 }
387 goto finish_hull;
388 }
389
390 /*upper half */
391 {
392 int *tl_stack = stack;
393 int tl_count = sklansky( pointer, 0, maxy_ind, tl_stack, -1, 1 );
394 int *tr_stack = tl_stack + tl_count;
395 int tr_count = sklansky( pointer, ptseq->total - 1, maxy_ind, tr_stack, -1, -1 );
396
397 /* gather upper part of convex hull to output */
398 if( orientation == CV_COUNTER_CLOCKWISE )
399 {
400 CV_SWAP( tl_stack, tr_stack, t_stack );
401 CV_SWAP( tl_count, tr_count, t_count );
402 }
403
404 if( hulltype == CV_SEQ_ELTYPE_PPOINT )
405 {
406 for( i = 0; i < tl_count - 1; i++ )
407 CV_WRITE_SEQ_ELEM( pointer[tl_stack[i]], writer );
408
409 for( i = tr_count - 1; i > 0; i-- )
410 CV_WRITE_SEQ_ELEM( pointer[tr_stack[i]], writer );
411 }
412 else if( hulltype == CV_SEQ_ELTYPE_INDEX )
413 {
414 CV_CALL( icvCalcAndWritePtIndices( pointer, tl_stack,
415 0, tl_count-1, ptseq, &writer ));
416 CV_CALL( icvCalcAndWritePtIndices( pointer, tr_stack,
417 tr_count-1, 0, ptseq, &writer ));
418 }
419 else
420 {
421 for( i = 0; i < tl_count - 1; i++ )
422 CV_WRITE_SEQ_ELEM( pointer[tl_stack[i]][0], writer );
423
424 for( i = tr_count - 1; i > 0; i-- )
425 CV_WRITE_SEQ_ELEM( pointer[tr_stack[i]][0], writer );
426 }
427 stop_idx = tr_count > 2 ? tr_stack[1] : tl_count > 2 ? tl_stack[tl_count - 2] : -1;
428 }
429
430 /* lower half */
431 {
432 int *bl_stack = stack;
433 int bl_count = sklansky( pointer, 0, miny_ind, bl_stack, 1, -1 );
434 int *br_stack = stack + bl_count;
435 int br_count = sklansky( pointer, ptseq->total - 1, miny_ind, br_stack, 1, 1 );
436
437 if( orientation != CV_COUNTER_CLOCKWISE )
438 {
439 CV_SWAP( bl_stack, br_stack, t_stack );
440 CV_SWAP( bl_count, br_count, t_count );
441 }
442
443 if( stop_idx >= 0 )
444 {
445 int check_idx = bl_count > 2 ? bl_stack[1] :
446 bl_count + br_count > 2 ? br_stack[2-bl_count] : -1;
447 if( check_idx == stop_idx || (check_idx >= 0 &&
448 pointer[check_idx]->x == pointer[stop_idx]->x &&
449 pointer[check_idx]->y == pointer[stop_idx]->y) )
450 {
451 /* if all the points lie on the same line, then
452 the bottom part of the convex hull is the mirrored top part
453 (except the exteme points).*/
454 bl_count = MIN( bl_count, 2 );
455 br_count = MIN( br_count, 2 );
456 }
457 }
458
459 if( hulltype == CV_SEQ_ELTYPE_PPOINT )
460 {
461 for( i = 0; i < bl_count - 1; i++ )
462 CV_WRITE_SEQ_ELEM( pointer[bl_stack[i]], writer );
463
464 for( i = br_count - 1; i > 0; i-- )
465 CV_WRITE_SEQ_ELEM( pointer[br_stack[i]], writer );
466 }
467 else if( hulltype == CV_SEQ_ELTYPE_INDEX )
468 {
469 CV_CALL( icvCalcAndWritePtIndices( pointer, bl_stack,
470 0, bl_count-1, ptseq, &writer ));
471 CV_CALL( icvCalcAndWritePtIndices( pointer, br_stack,
472 br_count-1, 0, ptseq, &writer ));
473 }
474 else
475 {
476 for( i = 0; i < bl_count - 1; i++ )
477 CV_WRITE_SEQ_ELEM( pointer[bl_stack[i]][0], writer );
478
479 for( i = br_count - 1; i > 0; i-- )
480 CV_WRITE_SEQ_ELEM( pointer[br_stack[i]][0], writer );
481 }
482 }
483
484 finish_hull:
485 CV_CALL( cvEndWriteSeq( &writer ));
486
487 if( mat )
488 {
489 if( mat->rows > mat->cols )
490 mat->rows = hullseq->total;
491 else
492 mat->cols = hullseq->total;
493 }
494 else
495 {
496 hull.s = hullseq;
497 hull.c->rect = cvBoundingRect( ptseq,
498 ptseq->header_size < (int)sizeof(CvContour) ||
499 &ptseq->flags == &contour_header.flags );
500
501 /*if( ptseq != (CvSeq*)&contour_header )
502 hullseq->v_prev = ptseq;*/
503 }
504
505 __END__;
506
507 cvFree( &pointer );
508 cvFree( &stack );
509
510 return hull.s;
511 }
512
513
514 /* contour must be a simple polygon */
515 /* it must have more than 3 points */
516 CV_IMPL CvSeq*
cvConvexityDefects(const CvArr * array,const CvArr * hullarray,CvMemStorage * storage)517 cvConvexityDefects( const CvArr* array,
518 const CvArr* hullarray,
519 CvMemStorage* storage )
520 {
521 CvSeq* defects = 0;
522
523 CV_FUNCNAME( "cvConvexityDefects" );
524
525 __BEGIN__;
526
527 int i, index;
528 CvPoint* hull_cur;
529
530 /* is orientation of hull different from contour one */
531 int rev_orientation;
532
533 CvContour contour_header;
534 union { CvContour c; CvSeq s; } hull_header;
535 CvSeqBlock block, hullblock;
536 CvSeq *ptseq = (CvSeq*)array, *hull = (CvSeq*)hullarray;
537
538 CvSeqReader hull_reader;
539 CvSeqReader ptseq_reader;
540 CvSeqWriter writer;
541 int is_index;
542
543 if( CV_IS_SEQ( ptseq ))
544 {
545 if( !CV_IS_SEQ_POINT_SET( ptseq ))
546 CV_ERROR( CV_StsUnsupportedFormat,
547 "Input sequence is not a sequence of points" );
548 if( !storage )
549 storage = ptseq->storage;
550 }
551 else
552 {
553 CV_CALL( ptseq = cvPointSeqFromMat(
554 CV_SEQ_KIND_GENERIC, array, &contour_header, &block ));
555 }
556
557 if( CV_SEQ_ELTYPE( ptseq ) != CV_32SC2 )
558 CV_ERROR( CV_StsUnsupportedFormat,
559 "Floating-point coordinates are not supported here" );
560
561 if( CV_IS_SEQ( hull ))
562 {
563 int hulltype = CV_SEQ_ELTYPE( hull );
564 if( hulltype != CV_SEQ_ELTYPE_PPOINT && hulltype != CV_SEQ_ELTYPE_INDEX )
565 CV_ERROR( CV_StsUnsupportedFormat,
566 "Convex hull must represented as a sequence "
567 "of indices or sequence of pointers" );
568 if( !storage )
569 storage = hull->storage;
570 }
571 else
572 {
573 CvMat* mat = (CvMat*)hull;
574
575 if( !CV_IS_MAT( hull ))
576 CV_ERROR(CV_StsBadArg, "Convex hull is neither sequence nor matrix");
577
578 if( (mat->cols != 1 && mat->rows != 1) ||
579 !CV_IS_MAT_CONT(mat->type) || CV_MAT_TYPE(mat->type) != CV_32SC1 )
580 CV_ERROR( CV_StsBadArg,
581 "The matrix should be 1-dimensional and continuous array of int's" );
582
583 if( mat->cols + mat->rows - 1 > ptseq->total )
584 CV_ERROR( CV_StsBadSize, "Convex hull is larger than the point sequence" );
585
586 CV_CALL( hull = cvMakeSeqHeaderForArray(
587 CV_SEQ_KIND_CURVE|CV_MAT_TYPE(mat->type)|CV_SEQ_FLAG_CLOSED,
588 sizeof(CvContour), CV_ELEM_SIZE(mat->type), mat->data.ptr,
589 mat->cols + mat->rows - 1, &hull_header.s, &hullblock ));
590 }
591
592 is_index = CV_SEQ_ELTYPE(hull) == CV_SEQ_ELTYPE_INDEX;
593
594 if( !storage )
595 CV_ERROR( CV_StsNullPtr, "NULL storage pointer" );
596
597 CV_CALL( defects = cvCreateSeq( CV_SEQ_KIND_GENERIC, sizeof(CvSeq),
598 sizeof(CvConvexityDefect), storage ));
599
600 if( ptseq->total < 4 || hull->total < 3)
601 {
602 //CV_ERROR( CV_StsBadSize,
603 // "point seq size must be >= 4, convex hull size must be >= 3" );
604 EXIT;
605 }
606
607 /* recognize co-orientation of ptseq and its hull */
608 {
609 int sign = 0;
610 int index1, index2, index3;
611
612 if( !is_index )
613 {
614 CvPoint* pos = *CV_SEQ_ELEM( hull, CvPoint*, 0 );
615 CV_CALL( index1 = cvSeqElemIdx( ptseq, pos ));
616
617 pos = *CV_SEQ_ELEM( hull, CvPoint*, 1 );
618 CV_CALL( index2 = cvSeqElemIdx( ptseq, pos ));
619
620 pos = *CV_SEQ_ELEM( hull, CvPoint*, 2 );
621 CV_CALL( index3 = cvSeqElemIdx( ptseq, pos ));
622 }
623 else
624 {
625 index1 = *CV_SEQ_ELEM( hull, int, 0 );
626 index2 = *CV_SEQ_ELEM( hull, int, 1 );
627 index3 = *CV_SEQ_ELEM( hull, int, 2 );
628 }
629
630 sign += (index2 > index1) ? 1 : 0;
631 sign += (index3 > index2) ? 1 : 0;
632 sign += (index1 > index3) ? 1 : 0;
633
634 rev_orientation = (sign == 2) ? 0 : 1;
635 }
636
637 cvStartReadSeq( ptseq, &ptseq_reader, 0 );
638 cvStartReadSeq( hull, &hull_reader, rev_orientation );
639
640 if( !is_index )
641 {
642 hull_cur = *(CvPoint**)hull_reader.prev_elem;
643 index = cvSeqElemIdx( ptseq, (char*)hull_cur, 0 );
644 }
645 else
646 {
647 index = *(int*)hull_reader.prev_elem;
648 hull_cur = CV_GET_SEQ_ELEM( CvPoint, ptseq, index );
649 }
650 cvSetSeqReaderPos( &ptseq_reader, index );
651 cvStartAppendToSeq( defects, &writer );
652
653 /* cycle through ptseq and hull with computing defects */
654 for( i = 0; i < hull->total; i++ )
655 {
656 CvConvexityDefect defect;
657 int is_defect = 0;
658 double dx0, dy0;
659 double depth = 0, scale;
660 CvPoint* hull_next;
661
662 if( !is_index )
663 hull_next = *(CvPoint**)hull_reader.ptr;
664 else
665 {
666 int t = *(int*)hull_reader.ptr;
667 hull_next = CV_GET_SEQ_ELEM( CvPoint, ptseq, t );
668 }
669
670 dx0 = (double)hull_next->x - (double)hull_cur->x;
671 dy0 = (double)hull_next->y - (double)hull_cur->y;
672 assert( dx0 != 0 || dy0 != 0 );
673 scale = 1./sqrt(dx0*dx0 + dy0*dy0);
674
675 defect.start = hull_cur;
676 defect.end = hull_next;
677
678 for(;;)
679 {
680 /* go through ptseq to achieve next hull point */
681 CV_NEXT_SEQ_ELEM( sizeof(CvPoint), ptseq_reader );
682
683 if( ptseq_reader.ptr == (schar*)hull_next )
684 break;
685 else
686 {
687 CvPoint* cur = (CvPoint*)ptseq_reader.ptr;
688
689 /* compute distance from current point to hull edge */
690 double dx = (double)cur->x - (double)hull_cur->x;
691 double dy = (double)cur->y - (double)hull_cur->y;
692
693 /* compute depth */
694 double dist = fabs(-dy0*dx + dx0*dy) * scale;
695
696 if( dist > depth )
697 {
698 depth = dist;
699 defect.depth_point = cur;
700 defect.depth = (float)depth;
701 is_defect = 1;
702 }
703 }
704 }
705 if( is_defect )
706 {
707 CV_WRITE_SEQ_ELEM( defect, writer );
708 }
709
710 hull_cur = hull_next;
711 if( rev_orientation )
712 {
713 CV_PREV_SEQ_ELEM( hull->elem_size, hull_reader );
714 }
715 else
716 {
717 CV_NEXT_SEQ_ELEM( hull->elem_size, hull_reader );
718 }
719 }
720
721 defects = cvEndWriteSeq( &writer );
722
723 __END__;
724
725 return defects;
726 }
727
728
729 CV_IMPL int
cvCheckContourConvexity(const CvArr * array)730 cvCheckContourConvexity( const CvArr* array )
731 {
732 int flag = -1;
733
734 CV_FUNCNAME( "cvCheckContourConvexity" );
735
736 __BEGIN__;
737
738 int i;
739 int orientation = 0;
740 CvSeqReader reader;
741 CvContour contour_header;
742 CvSeqBlock block;
743 CvSeq* contour = (CvSeq*)array;
744
745 if( CV_IS_SEQ(contour) )
746 {
747 if( !CV_IS_SEQ_POLYGON(contour))
748 CV_ERROR( CV_StsUnsupportedFormat,
749 "Input sequence must be polygon (closed 2d curve)" );
750 }
751 else
752 {
753 CV_CALL( contour = cvPointSeqFromMat(
754 CV_SEQ_KIND_CURVE|CV_SEQ_FLAG_CLOSED, array, &contour_header, &block ));
755 }
756
757 if( contour->total == 0 )
758 EXIT;
759
760 cvStartReadSeq( contour, &reader, 0 );
761
762 flag = 1;
763
764 if( CV_SEQ_ELTYPE( contour ) == CV_32SC2 )
765 {
766 CvPoint *prev_pt = (CvPoint*)reader.prev_elem;
767 CvPoint *cur_pt = (CvPoint*)reader.ptr;
768
769 int dx0 = cur_pt->x - prev_pt->x;
770 int dy0 = cur_pt->y - prev_pt->y;
771
772 for( i = 0; i < contour->total; i++ )
773 {
774 int dxdy0, dydx0;
775 int dx, dy;
776
777 /*int orient; */
778 CV_NEXT_SEQ_ELEM( sizeof(CvPoint), reader );
779 prev_pt = cur_pt;
780 cur_pt = (CvPoint *) reader.ptr;
781
782 dx = cur_pt->x - prev_pt->x;
783 dy = cur_pt->y - prev_pt->y;
784 dxdy0 = dx * dy0;
785 dydx0 = dy * dx0;
786
787 /* find orientation */
788 /*orient = -dy0 * dx + dx0 * dy;
789 orientation |= (orient > 0) ? 1 : 2;
790 */
791 orientation |= (dydx0 > dxdy0) ? 1 : ((dydx0 < dxdy0) ? 2 : 3);
792
793 if( orientation == 3 )
794 {
795 flag = 0;
796 break;
797 }
798
799 dx0 = dx;
800 dy0 = dy;
801 }
802 }
803 else
804 {
805 assert( CV_SEQ_ELTYPE(contour) == CV_32FC2 );
806
807 CvPoint2D32f *prev_pt = (CvPoint2D32f*)reader.prev_elem;
808 CvPoint2D32f *cur_pt = (CvPoint2D32f*)reader.ptr;
809
810 float dx0 = cur_pt->x - prev_pt->x;
811 float dy0 = cur_pt->y - prev_pt->y;
812
813 for( i = 0; i < contour->total; i++ )
814 {
815 float dxdy0, dydx0;
816 float dx, dy;
817
818 /*int orient; */
819 CV_NEXT_SEQ_ELEM( sizeof(CvPoint2D32f), reader );
820 prev_pt = cur_pt;
821 cur_pt = (CvPoint2D32f*) reader.ptr;
822
823 dx = cur_pt->x - prev_pt->x;
824 dy = cur_pt->y - prev_pt->y;
825 dxdy0 = dx * dy0;
826 dydx0 = dy * dx0;
827
828 /* find orientation */
829 /*orient = -dy0 * dx + dx0 * dy;
830 orientation |= (orient > 0) ? 1 : 2;
831 */
832 orientation |= (dydx0 > dxdy0) ? 1 : ((dydx0 < dxdy0) ? 2 : 3);
833
834 if( orientation == 3 )
835 {
836 flag = 0;
837 break;
838 }
839
840 dx0 = dx;
841 dy0 = dy;
842 }
843 }
844
845 __END__;
846
847 return flag;
848 }
849
850
851 /* End of file. */
852