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#include "precomp.hpp"
42#include "opencv2/core/hal/intrin.hpp"
43
44using namespace cv;
45
46CV_IMPL CvRect
47cvMaxRect( const CvRect* rect1, const CvRect* rect2 )
48{
49 if( rect1 && rect2 )
50 {
51 cv::Rect max_rect;
52 int a, b;
53
54 max_rect.x = a = rect1->x;
55 b = rect2->x;
56 if( max_rect.x > b )
57 max_rect.x = b;
58
59 max_rect.width = a += rect1->width;
60 b += rect2->width;
61
62 if( max_rect.width < b )
63 max_rect.width = b;
64 max_rect.width -= max_rect.x;
65
66 max_rect.y = a = rect1->y;
67 b = rect2->y;
68 if( max_rect.y > b )
69 max_rect.y = b;
70
71 max_rect.height = a += rect1->height;
72 b += rect2->height;
73
74 if( max_rect.height < b )
75 max_rect.height = b;
76 max_rect.height -= max_rect.y;
77 return cvRect(rc: max_rect);
78 }
79 else if( rect1 )
80 return *rect1;
81 else if( rect2 )
82 return *rect2;
83 else
84 return cvRect(x: 0,y: 0,width: 0,height: 0);
85}
86
87
88CV_IMPL void
89cvBoxPoints( CvBox2D box, CvPoint2D32f pt[4] )
90{
91 if( !pt )
92 CV_Error( cv::Error::StsNullPtr, "NULL vertex array pointer" );
93 cv::RotatedRect(box).points(pts: (cv::Point2f*)pt);
94}
95
96
97double cv::pointPolygonTest( InputArray _contour, Point2f pt, bool measureDist )
98{
99 CV_INSTRUMENT_REGION();
100
101 double result = 0;
102 Mat contour = _contour.getMat();
103 int i, total = contour.checkVector(elemChannels: 2), counter = 0;
104 int depth = contour.depth();
105 CV_Assert( total >= 0 && (depth == CV_32S || depth == CV_32F));
106
107 bool is_float = depth == CV_32F;
108 double min_dist_num = FLT_MAX, min_dist_denom = 1;
109 Point ip(cvRound(value: pt.x), cvRound(value: pt.y));
110
111 if( total == 0 )
112 return measureDist ? -DBL_MAX : -1;
113
114 const Point* cnt = contour.ptr<Point>();
115 const Point2f* cntf = (const Point2f*)cnt;
116
117 if( !is_float && !measureDist && ip.x == pt.x && ip.y == pt.y )
118 {
119 // the fastest "purely integer" branch
120 Point v0, v = cnt[total-1];
121
122 for( i = 0; i < total; i++ )
123 {
124 v0 = v;
125 v = cnt[i];
126
127 if( (v0.y <= ip.y && v.y <= ip.y) ||
128 (v0.y > ip.y && v.y > ip.y) ||
129 (v0.x < ip.x && v.x < ip.x) )
130 {
131 if( ip.y == v.y && (ip.x == v.x || (ip.y == v0.y &&
132 ((v0.x <= ip.x && ip.x <= v.x) || (v.x <= ip.x && ip.x <= v0.x)))) )
133 return 0;
134 continue;
135 }
136
137 int64 dist = static_cast<int64>(ip.y - v0.y)*(v.x - v0.x)
138 - static_cast<int64>(ip.x - v0.x)*(v.y - v0.y);
139 if( dist == 0 )
140 return 0;
141 if( v.y < v0.y )
142 dist = -dist;
143 counter += dist > 0;
144 }
145
146 result = counter % 2 == 0 ? -1 : 1;
147 }
148 else
149 {
150 Point2f v0, v;
151
152 if( is_float )
153 {
154 v = cntf[total-1];
155 }
156 else
157 {
158 v = cnt[total-1];
159 }
160
161 if( !measureDist )
162 {
163 for( i = 0; i < total; i++ )
164 {
165 double dist;
166 v0 = v;
167 if( is_float )
168 v = cntf[i];
169 else
170 v = cnt[i];
171
172 if( (v0.y <= pt.y && v.y <= pt.y) ||
173 (v0.y > pt.y && v.y > pt.y) ||
174 (v0.x < pt.x && v.x < pt.x) )
175 {
176 if( pt.y == v.y && (pt.x == v.x || (pt.y == v0.y &&
177 ((v0.x <= pt.x && pt.x <= v.x) || (v.x <= pt.x && pt.x <= v0.x)))) )
178 return 0;
179 continue;
180 }
181
182 dist = (double)(pt.y - v0.y)*(v.x - v0.x) - (double)(pt.x - v0.x)*(v.y - v0.y);
183 if( dist == 0 )
184 return 0;
185 if( v.y < v0.y )
186 dist = -dist;
187 counter += dist > 0;
188 }
189
190 result = counter % 2 == 0 ? -1 : 1;
191 }
192 else
193 {
194 for( i = 0; i < total; i++ )
195 {
196 double dx, dy, dx1, dy1, dx2, dy2, dist_num, dist_denom = 1;
197
198 v0 = v;
199 if( is_float )
200 v = cntf[i];
201 else
202 v = cnt[i];
203
204 dx = v.x - v0.x; dy = v.y - v0.y;
205 dx1 = pt.x - v0.x; dy1 = pt.y - v0.y;
206 dx2 = pt.x - v.x; dy2 = pt.y - v.y;
207
208 if( dx1*dx + dy1*dy <= 0 )
209 dist_num = dx1*dx1 + dy1*dy1;
210 else if( dx2*dx + dy2*dy >= 0 )
211 dist_num = dx2*dx2 + dy2*dy2;
212 else
213 {
214 dist_num = (dy1*dx - dx1*dy);
215 dist_num *= dist_num;
216 dist_denom = dx*dx + dy*dy;
217 }
218
219 if( dist_num*min_dist_denom < min_dist_num*dist_denom )
220 {
221 min_dist_num = dist_num;
222 min_dist_denom = dist_denom;
223 if( min_dist_num == 0 )
224 break;
225 }
226
227 if( (v0.y <= pt.y && v.y <= pt.y) ||
228 (v0.y > pt.y && v.y > pt.y) ||
229 (v0.x < pt.x && v.x < pt.x) )
230 continue;
231
232 dist_num = dy1*dx - dx1*dy;
233 if( dy < 0 )
234 dist_num = -dist_num;
235 counter += dist_num > 0;
236 }
237
238 result = std::sqrt(x: min_dist_num/min_dist_denom);
239 if( counter % 2 == 0 )
240 result = -result;
241 }
242 }
243
244 return result;
245}
246
247
248CV_IMPL double
249cvPointPolygonTest( const CvArr* _contour, CvPoint2D32f pt, int measure_dist )
250{
251 cv::AutoBuffer<double> abuf;
252 cv::Mat contour = cv::cvarrToMat(arr: _contour, copyData: false, allowND: false, coiMode: 0, buf: &abuf);
253 return cv::pointPolygonTest(contour: contour, pt, measureDist: measure_dist != 0);
254}
255
256/*
257 This code is described in "Computational Geometry in C" (Second Edition),
258 Chapter 7. It is not written to be comprehensible without the
259 explanation in that book.
260
261 Written by Joseph O'Rourke.
262 Last modified: December 1997
263 Questions to orourke@cs.smith.edu.
264 --------------------------------------------------------------------
265 This code is Copyright 1997 by Joseph O'Rourke. It may be freely
266 redistributed in its entirety provided that this copyright notice is
267 not removed.
268 --------------------------------------------------------------------
269 */
270
271namespace cv
272{
273typedef enum { Pin, Qin, Unknown } tInFlag;
274
275static int areaSign( Point2f a, Point2f b, Point2f c )
276{
277 static const double eps = 1e-5;
278 double area2 = (b.x - a.x) * (double)(c.y - a.y) - (c.x - a.x ) * (double)(b.y - a.y);
279 return area2 > eps ? 1 : area2 < -eps ? -1 : 0;
280}
281
282//---------------------------------------------------------------------
283// Returns true iff point c lies on the closed segment ab.
284// Assumes it is already known that abc are collinear.
285//---------------------------------------------------------------------
286static bool between( Point2f a, Point2f b, Point2f c )
287{
288 Point2f ba, ca;
289
290 // If ab not vertical, check betweenness on x; else on y.
291 if ( a.x != b.x )
292 return ((a.x <= c.x) && (c.x <= b.x)) ||
293 ((a.x >= c.x) && (c.x >= b.x));
294 else
295 return ((a.y <= c.y) && (c.y <= b.y)) ||
296 ((a.y >= c.y) && (c.y >= b.y));
297}
298
299enum LineSegmentIntersection
300{
301 LS_NO_INTERSECTION = 0,
302 LS_SINGLE_INTERSECTION = 1,
303 LS_OVERLAP = 2,
304 LS_ENDPOINT_INTERSECTION = 3
305};
306
307static LineSegmentIntersection parallelInt( Point2f a, Point2f b, Point2f c, Point2f d, Point2f& p, Point2f& q )
308{
309 LineSegmentIntersection code = LS_OVERLAP;
310 if( areaSign(a, b, c) != 0 )
311 code = LS_NO_INTERSECTION;
312 else if( between(a, b, c) && between(a, b, c: d))
313 p = c, q = d;
314 else if( between(a: c, b: d, c: a) && between(a: c, b: d, c: b))
315 p = a, q = b;
316 else if( between(a, b, c) && between(a: c, b: d, c: b))
317 p = c, q = b;
318 else if( between(a, b, c) && between(a: c, b: d, c: a))
319 p = c, q = a;
320 else if( between(a, b, c: d) && between(a: c, b: d, c: b))
321 p = d, q = b;
322 else if( between(a, b, c: d) && between(a: c, b: d, c: a))
323 p = d, q = a;
324 else
325 code = LS_NO_INTERSECTION;
326 return code;
327}
328
329// Finds intersection of two line segments: (a, b) and (c, d).
330static LineSegmentIntersection intersectLineSegments( Point2f a, Point2f b, Point2f c,
331 Point2f d, Point2f& p, Point2f& q )
332{
333 double denom = (a.x - b.x) * (double)(d.y - c.y) - (a.y - b.y) * (double)(d.x - c.x);
334
335 // If denom is zero, then segments are parallel: handle separately.
336 if( denom == 0. )
337 return parallelInt(a, b, c, d, p, q);
338
339 double num = (d.y - a.y) * (double)(a.x - c.x) + (a.x - d.x) * (double)(a.y - c.y);
340 double s = num / denom;
341
342 num = (b.y - a.y) * (double)(a.x - c.x) + (c.y - a.y) * (double)(b.x - a.x);
343 double t = num / denom;
344
345 p.x = (float)(a.x + s*(b.x - a.x));
346 p.y = (float)(a.y + s*(b.y - a.y));
347 q = p;
348
349 return s < 0. || s > 1. || t < 0. || t > 1. ? LS_NO_INTERSECTION :
350 s == 0. || s == 1. || t == 0. || t == 1. ? LS_ENDPOINT_INTERSECTION : LS_SINGLE_INTERSECTION;
351}
352
353static tInFlag inOut( Point2f p, tInFlag inflag, int aHB, int bHA, Point2f*& result )
354{
355 if( p != result[-1] )
356 *result++ = p;
357 // Update inflag.
358 return aHB > 0 ? Pin : bHA > 0 ? Qin : inflag;
359}
360
361//---------------------------------------------------------------------
362// Advances and prints out an inside vertex if appropriate.
363//---------------------------------------------------------------------
364static int advance( int a, int *aa, int n, bool inside, Point2f v, Point2f*& result )
365{
366 if( inside && v != result[-1] )
367 *result++ = v;
368 (*aa)++;
369 return (a+1) % n;
370}
371
372static void addSharedSeg( Point2f p, Point2f q, Point2f*& result )
373{
374 if( p != result[-1] )
375 *result++ = p;
376 if( q != result[-1] )
377 *result++ = q;
378}
379
380// Note: The function and subroutings use direct pointer arithmetics instead of arrays indexing.
381// Each loop iteration may push to result array up to 3 times.
382// It means that we need +3 spare result elements against result_size
383// to catch agorithmic overflow and prevent actual result array overflow.
384static int intersectConvexConvex_( const Point2f* P, int n, const Point2f* Q, int m,
385 Point2f* result, int result_size, float* _area )
386{
387 Point2f* result0 = result;
388 // P has n vertices, Q has m vertices.
389 int a=0, b=0; // indices on P and Q (resp.)
390 Point2f Origin(0,0);
391 tInFlag inflag=Unknown; // {Pin, Qin, Unknown}: which inside
392 int aa=0, ba=0; // # advances on a & b indices (after 1st inter.)
393 bool FirstPoint=true;// Is this the first point? (used to initialize).
394 Point2f p0; // The first point.
395 *result++ = Point2f(FLT_MAX, FLT_MAX);
396
397 do
398 {
399 // Computations of key variables.
400 int a1 = (a + n - 1) % n; // a-1, b-1 (resp.)
401 int b1 = (b + m - 1) % m;
402
403 Point2f A = P[a] - P[a1], B = Q[b] - Q[b1]; // directed edges on P and Q (resp.)
404
405 int cross = areaSign( a: Origin, b: A, c: B ); // sign of z-component of A x B
406 int aHB = areaSign( a: Q[b1], b: Q[b], c: P[a] ); // a in H(b).
407 int bHA = areaSign( a: P[a1], b: P[a], c: Q[b] ); // b in H(A);
408
409 // If A & B intersect, update inflag.
410 Point2f p, q;
411 LineSegmentIntersection code = intersectLineSegments( a: P[a1], b: P[a], c: Q[b1], d: Q[b], p, q );
412 if( code == LS_SINGLE_INTERSECTION || code == LS_ENDPOINT_INTERSECTION )
413 {
414 if( inflag == Unknown && FirstPoint )
415 {
416 aa = ba = 0;
417 FirstPoint = false;
418 p0 = p;
419 *result++ = p;
420 }
421 inflag = inOut( p, inflag, aHB, bHA, result );
422 }
423
424 //-----Advance rules-----
425
426 // Special case: A & B overlap and oppositely oriented.
427 if( code == LS_OVERLAP && A.ddot(pt: B) < 0 )
428 {
429 addSharedSeg( p, q, result );
430 return (int)(result - result0);
431 }
432
433 // Special case: A & B parallel and separated.
434 if( cross == 0 && aHB < 0 && bHA < 0 )
435 return (int)(result - result0);
436
437 // Special case: A & B collinear.
438 else if ( cross == 0 && aHB == 0 && bHA == 0 ) {
439 // Advance but do not output point.
440 if ( inflag == Pin )
441 b = advance( a: b, aa: &ba, n: m, inside: inflag == Qin, v: Q[b], result );
442 else
443 a = advance( a, aa: &aa, n, inside: inflag == Pin, v: P[a], result );
444 }
445
446 // Generic cases.
447 else if( cross >= 0 )
448 {
449 if( bHA > 0)
450 a = advance( a, aa: &aa, n, inside: inflag == Pin, v: P[a], result );
451 else
452 b = advance( a: b, aa: &ba, n: m, inside: inflag == Qin, v: Q[b], result );
453 }
454 else
455 {
456 if( aHB > 0)
457 b = advance( a: b, aa: &ba, n: m, inside: inflag == Qin, v: Q[b], result );
458 else
459 a = advance( a, aa: &aa, n, inside: inflag == Pin, v: P[a], result );
460 }
461 // Quit when both adv. indices have cycled, or one has cycled twice.
462 }
463 while ( ((aa < n) || (ba < m)) && (aa < 2*n) && (ba < 2*m) && ((int)(result - result0) <= result_size) );
464
465 // Deal with special cases: not implemented.
466 if( inflag == Unknown )
467 {
468 // The boundaries of P and Q do not cross.
469 // ...
470 }
471
472 int nr = (int)(result - result0);
473 if (nr > result_size)
474 {
475 *_area = -1.f;
476 return -1;
477 }
478
479 double area = 0;
480 Point2f prev = result0[nr-1];
481 for(int i = 1; i < nr; i++ )
482 {
483 result0[i-1] = result0[i];
484 area += (double)prev.x*result0[i].y - (double)prev.y*result0[i].x;
485 prev = result0[i];
486 }
487
488 *_area = (float)(area*0.5);
489
490 if( result0[nr-2] == result0[0] && nr > 1 )
491 nr--;
492 return nr-1;
493}
494
495}
496
497float cv::intersectConvexConvex( InputArray _p1, InputArray _p2, OutputArray _p12, bool handleNested )
498{
499 CV_INSTRUMENT_REGION();
500
501 Mat p1 = _p1.getMat(), p2 = _p2.getMat();
502 CV_Assert( p1.depth() == CV_32S || p1.depth() == CV_32F );
503 CV_Assert( p2.depth() == CV_32S || p2.depth() == CV_32F );
504
505 int n = p1.checkVector(elemChannels: 2, depth: p1.depth(), requireContinuous: true);
506 int m = p2.checkVector(elemChannels: 2, depth: p2.depth(), requireContinuous: true);
507
508 CV_Assert( n >= 0 && m >= 0 );
509
510 if( n < 2 || m < 2 )
511 {
512 _p12.release();
513 return 0.f;
514 }
515
516 AutoBuffer<Point2f> _result(n + m + n+m+1+3);
517 Point2f* fp1 = _result.data();
518 Point2f* fp2 = fp1 + n;
519 Point2f* result = fp2 + m;
520
521 int orientation = 0;
522
523 for( int k = 1; k <= 2; k++ )
524 {
525 Mat& p = k == 1 ? p1 : p2;
526 int len = k == 1 ? n : m;
527 Point2f* dst = k == 1 ? fp1 : fp2;
528
529 Mat temp(p.size(), CV_MAKETYPE(CV_32F, p.channels()), dst);
530 p.convertTo(m: temp, CV_32F);
531 CV_Assert( temp.ptr<Point2f>() == dst );
532 Point2f diff0 = dst[0] - dst[len-1];
533 for( int i = 1; i < len; i++ )
534 {
535 double s = diff0.cross(pt: dst[i] - dst[i-1]);
536 if( s != 0 )
537 {
538 if( s < 0 )
539 {
540 orientation++;
541 flip( src: temp, dst: temp, flipCode: temp.rows > 1 ? 0 : 1 );
542 }
543 break;
544 }
545 }
546 }
547
548 float area = 0.f;
549 int nr = intersectConvexConvex_(P: fp1, n, Q: fp2, m, result, result_size: n+m+1, area: &area);
550
551 if (nr < 0)
552 {
553 // The algorithm did not converge, e.g. some of inputs is not convex
554 _p12.release();
555 return -1.f;
556 }
557
558 if( nr == 0 )
559 {
560 if( !handleNested )
561 {
562 _p12.release();
563 return 0.f;
564 }
565
566 bool intersected = false;
567
568 // check if all of fp2's vertices is inside/on the edge of fp1.
569 int nVertices = 0;
570 for (int i=0; i<m; ++i)
571 nVertices += pointPolygonTest(contour: _InputArray(fp1, n), pt: fp2[i], measureDist: false) >= 0;
572
573 // if all of fp2's vertices is inside/on the edge of fp1.
574 if (nVertices == m)
575 {
576 intersected = true;
577 result = fp2;
578 nr = m;
579 }
580 else // otherwise check if fp2 is inside fp1.
581 {
582 nVertices = 0;
583 for (int i=0; i<n; ++i)
584 nVertices += pointPolygonTest(contour: _InputArray(fp2, m), pt: fp1[i], measureDist: false) >= 0;
585
586 // // if all of fp1's vertices is inside/on the edge of fp2.
587 if (nVertices == n)
588 {
589 intersected = true;
590 result = fp1;
591 nr = n;
592 }
593 }
594
595 if (!intersected)
596 {
597 _p12.release();
598 return 0.f;
599 }
600
601 area = (float)contourArea(contour: _InputArray(result, nr), oriented: false);
602 }
603
604 if( _p12.needed() )
605 {
606 Mat temp(nr, 1, CV_32FC2, result);
607 // if both input contours were reflected,
608 // let's orient the result as the input vectors
609 if( orientation == 2 )
610 flip(src: temp, dst: temp, flipCode: 0);
611
612 temp.copyTo(m: _p12);
613 }
614 return (float)fabs(x: area);
615}
616
617static Rect maskBoundingRect( const Mat& img )
618{
619 CV_Assert( img.depth() <= CV_8S && img.channels() == 1 );
620
621 Size size = img.size();
622 int xmin = size.width, ymin = -1, xmax = -1, ymax = -1, i, j, k;
623
624 for( i = 0; i < size.height; i++ )
625 {
626 const uchar* _ptr = img.ptr(y: i);
627 const uchar* ptr = (const uchar*)alignPtr(ptr: _ptr, n: 4);
628 int have_nz = 0, k_min, offset = (int)(ptr - _ptr);
629 j = 0;
630 offset = MIN(offset, size.width);
631 for( ; j < offset; j++ )
632 if( _ptr[j] )
633 {
634 if( j < xmin )
635 xmin = j;
636 if( j > xmax )
637 xmax = j;
638 have_nz = 1;
639 }
640 if( offset < size.width )
641 {
642 xmin -= offset;
643 xmax -= offset;
644 size.width -= offset;
645 j = 0;
646 for( ; j <= xmin - 4; j += 4 )
647 if( *((int*)(ptr+j)) )
648 break;
649 for( ; j < xmin; j++ )
650 if( ptr[j] )
651 {
652 xmin = j;
653 if( j > xmax )
654 xmax = j;
655 have_nz = 1;
656 break;
657 }
658 k_min = MAX(j-1, xmax);
659 k = size.width - 1;
660 for( ; k > k_min && (k&3) != 3; k-- )
661 if( ptr[k] )
662 break;
663 if( k > k_min && (k&3) == 3 )
664 {
665 for( ; k > k_min+3; k -= 4 )
666 if( *((int*)(ptr+k-3)) )
667 break;
668 }
669 for( ; k > k_min; k-- )
670 if( ptr[k] )
671 {
672 xmax = k;
673 have_nz = 1;
674 break;
675 }
676 if( !have_nz )
677 {
678 j &= ~3;
679 for( ; j <= k - 3; j += 4 )
680 if( *((int*)(ptr+j)) )
681 break;
682 for( ; j <= k; j++ )
683 if( ptr[j] )
684 {
685 have_nz = 1;
686 break;
687 }
688 }
689 xmin += offset;
690 xmax += offset;
691 size.width += offset;
692 }
693 if( have_nz )
694 {
695 if( ymin < 0 )
696 ymin = i;
697 ymax = i;
698 }
699 }
700
701 if( xmin >= size.width )
702 xmin = ymin = 0;
703 return Rect(xmin, ymin, xmax - xmin + 1, ymax - ymin + 1);
704}
705
706// Calculates bounding rectangle of a point set or retrieves already calculated
707static Rect pointSetBoundingRect( const Mat& points )
708{
709 int npoints = points.checkVector(elemChannels: 2);
710 int depth = points.depth();
711 CV_Assert(npoints >= 0 && (depth == CV_32F || depth == CV_32S));
712
713 int xmin = 0, ymin = 0, xmax = -1, ymax = -1, i;
714 bool is_float = depth == CV_32F;
715
716 if( npoints == 0 )
717 return Rect();
718
719#if CV_SIMD // TODO: enable for CV_SIMD_SCALABLE, loop tail related.
720 if( !is_float )
721 {
722 const int32_t* pts = points.ptr<int32_t>();
723 int64_t firstval = 0;
724 std::memcpy(dest: &firstval, src: pts, n: sizeof(pts[0]) * 2);
725 v_int32 minval, maxval;
726 minval = maxval = v_reinterpret_as_s32(a: vx_setall_s64(v: firstval)); //min[0]=pt.x, min[1]=pt.y, min[2]=pt.x, min[3]=pt.y
727 for( i = 1; i <= npoints - VTraits<v_int32>::vlanes()/2; i+= VTraits<v_int32>::vlanes()/2 )
728 {
729 v_int32 ptXY2 = vx_load(ptr: pts + 2 * i);
730 minval = v_min(a: ptXY2, b: minval);
731 maxval = v_max(a: ptXY2, b: maxval);
732 }
733 minval = v_min(a: v_reinterpret_as_s32(a: v_expand_low(a: v_reinterpret_as_u32(a: minval))), b: v_reinterpret_as_s32(a: v_expand_high(a: v_reinterpret_as_u32(a: minval))));
734 maxval = v_max(a: v_reinterpret_as_s32(a: v_expand_low(a: v_reinterpret_as_u32(a: maxval))), b: v_reinterpret_as_s32(a: v_expand_high(a: v_reinterpret_as_u32(a: maxval))));
735 if( i <= npoints - VTraits<v_int32>::vlanes()/4 )
736 {
737 v_int32 ptXY = v_reinterpret_as_s32(a: v_expand_low(a: v_reinterpret_as_u32(a: vx_load_low(ptr: pts + 2 * i))));
738 minval = v_min(a: ptXY, b: minval);
739 maxval = v_max(a: ptXY, b: maxval);
740 i += VTraits<v_int64>::vlanes()/2;
741 }
742 for(int j = 16; j < VTraits<v_uint8>::vlanes(); j*=2)
743 {
744 minval = v_min(a: v_reinterpret_as_s32(a: v_expand_low(a: v_reinterpret_as_u32(a: minval))), b: v_reinterpret_as_s32(a: v_expand_high(a: v_reinterpret_as_u32(a: minval))));
745 maxval = v_max(a: v_reinterpret_as_s32(a: v_expand_low(a: v_reinterpret_as_u32(a: maxval))), b: v_reinterpret_as_s32(a: v_expand_high(a: v_reinterpret_as_u32(a: maxval))));
746 }
747 xmin = v_get0(v: minval);
748 xmax = v_get0(v: maxval);
749 ymin = v_get0(v: v_reinterpret_as_s32(a: v_expand_high(a: v_reinterpret_as_u32(a: minval))));
750 ymax = v_get0(v: v_reinterpret_as_s32(a: v_expand_high(a: v_reinterpret_as_u32(a: maxval))));
751#if CV_SIMD_WIDTH > 16
752 if( i < npoints )
753 {
754 v_int32x4 minval2, maxval2;
755 minval2 = maxval2 = v_reinterpret_as_s32(v_expand_low(v_reinterpret_as_u32(v_load_low(pts + 2 * i))));
756 for( i++; i < npoints; i++ )
757 {
758 v_int32x4 ptXY = v_reinterpret_as_s32(v_expand_low(v_reinterpret_as_u32(v_load_low(pts + 2 * i))));
759 minval2 = v_min(ptXY, minval2);
760 maxval2 = v_max(ptXY, maxval2);
761 }
762 xmin = min(xmin, v_get0(minval2));
763 xmax = max(xmax, v_get0(maxval2));
764 ymin = min(ymin, v_get0(v_reinterpret_as_s32(v_expand_high(v_reinterpret_as_u32(minval2)))));
765 ymax = max(ymax, v_get0(v_reinterpret_as_s32(v_expand_high(v_reinterpret_as_u32(maxval2)))));
766 }
767#endif // CV_SIMD
768 }
769 else
770 {
771 const float* pts = points.ptr<float>();
772 int64_t firstval = 0;
773 std::memcpy(dest: &firstval, src: pts, n: sizeof(pts[0]) * 2);
774 v_float32 minval, maxval;
775 minval = maxval = v_reinterpret_as_f32(a: vx_setall_s64(v: firstval)); //min[0]=pt.x, min[1]=pt.y, min[2]=pt.x, min[3]=pt.y
776 for( i = 1; i <= npoints - VTraits<v_float32>::vlanes()/2; i+= VTraits<v_float32>::vlanes()/2 )
777 {
778 v_float32 ptXY2 = vx_load(ptr: pts + 2 * i);
779 minval = v_min(a: ptXY2, b: minval);
780 maxval = v_max(a: ptXY2, b: maxval);
781 }
782 minval = v_min(a: v_reinterpret_as_f32(a: v_expand_low(a: v_reinterpret_as_u32(a: minval))), b: v_reinterpret_as_f32(a: v_expand_high(a: v_reinterpret_as_u32(a: minval))));
783 maxval = v_max(a: v_reinterpret_as_f32(a: v_expand_low(a: v_reinterpret_as_u32(a: maxval))), b: v_reinterpret_as_f32(a: v_expand_high(a: v_reinterpret_as_u32(a: maxval))));
784 if( i <= npoints - VTraits<v_float32>::vlanes()/4 )
785 {
786 v_float32 ptXY = v_reinterpret_as_f32(a: v_expand_low(a: v_reinterpret_as_u32(a: vx_load_low(ptr: pts + 2 * i))));
787 minval = v_min(a: ptXY, b: minval);
788 maxval = v_max(a: ptXY, b: maxval);
789 i += VTraits<v_float32>::vlanes()/4;
790 }
791 for(int j = 16; j < VTraits<v_uint8>::vlanes(); j*=2)
792 {
793 minval = v_min(a: v_reinterpret_as_f32(a: v_expand_low(a: v_reinterpret_as_u32(a: minval))), b: v_reinterpret_as_f32(a: v_expand_high(a: v_reinterpret_as_u32(a: minval))));
794 maxval = v_max(a: v_reinterpret_as_f32(a: v_expand_low(a: v_reinterpret_as_u32(a: maxval))), b: v_reinterpret_as_f32(a: v_expand_high(a: v_reinterpret_as_u32(a: maxval))));
795 }
796 xmin = cvFloor(value: v_get0(v: minval));
797 xmax = cvFloor(value: v_get0(v: maxval));
798 ymin = cvFloor(value: v_get0(v: v_reinterpret_as_f32(a: v_expand_high(a: v_reinterpret_as_u32(a: minval)))));
799 ymax = cvFloor(value: v_get0(v: v_reinterpret_as_f32(a: v_expand_high(a: v_reinterpret_as_u32(a: maxval)))));
800#if CV_SIMD_WIDTH > 16
801 if( i < npoints )
802 {
803 v_float32x4 minval2, maxval2;
804 minval2 = maxval2 = v_reinterpret_as_f32(v_expand_low(v_reinterpret_as_u32(v_load_low(pts + 2 * i))));
805 for( i++; i < npoints; i++ )
806 {
807 v_float32x4 ptXY = v_reinterpret_as_f32(v_expand_low(v_reinterpret_as_u32(v_load_low(pts + 2 * i))));
808 minval2 = v_min(ptXY, minval2);
809 maxval2 = v_max(ptXY, maxval2);
810 }
811 xmin = min(xmin, cvFloor(v_get0(minval2)));
812 xmax = max(xmax, cvFloor(v_get0(maxval2)));
813 ymin = min(ymin, cvFloor(v_get0(v_reinterpret_as_f32(v_expand_high(v_reinterpret_as_u32(minval2))))));
814 ymax = max(ymax, cvFloor(v_get0(v_reinterpret_as_f32(v_expand_high(v_reinterpret_as_u32(maxval2))))));
815 }
816#endif
817 }
818#else
819 const Point* pts = points.ptr<Point>();
820 Point pt = pts[0];
821
822 if( !is_float )
823 {
824 xmin = xmax = pt.x;
825 ymin = ymax = pt.y;
826
827 for( i = 1; i < npoints; i++ )
828 {
829 pt = pts[i];
830
831 if( xmin > pt.x )
832 xmin = pt.x;
833
834 if( xmax < pt.x )
835 xmax = pt.x;
836
837 if( ymin > pt.y )
838 ymin = pt.y;
839
840 if( ymax < pt.y )
841 ymax = pt.y;
842 }
843 }
844 else
845 {
846 Cv32suf v;
847 // init values
848 xmin = xmax = CV_TOGGLE_FLT(pt.x);
849 ymin = ymax = CV_TOGGLE_FLT(pt.y);
850
851 for( i = 1; i < npoints; i++ )
852 {
853 pt = pts[i];
854 pt.x = CV_TOGGLE_FLT(pt.x);
855 pt.y = CV_TOGGLE_FLT(pt.y);
856
857 if( xmin > pt.x )
858 xmin = pt.x;
859
860 if( xmax < pt.x )
861 xmax = pt.x;
862
863 if( ymin > pt.y )
864 ymin = pt.y;
865
866 if( ymax < pt.y )
867 ymax = pt.y;
868 }
869
870 v.i = CV_TOGGLE_FLT(xmin); xmin = cvFloor(v.f);
871 v.i = CV_TOGGLE_FLT(ymin); ymin = cvFloor(v.f);
872 // because right and bottom sides of the bounding rectangle are not inclusive
873 // (note +1 in width and height calculation below), cvFloor is used here instead of cvCeil
874 v.i = CV_TOGGLE_FLT(xmax); xmax = cvFloor(v.f);
875 v.i = CV_TOGGLE_FLT(ymax); ymax = cvFloor(v.f);
876 }
877#endif
878
879 return Rect(xmin, ymin, xmax - xmin + 1, ymax - ymin + 1);
880}
881
882
883cv::Rect cv::boundingRect(InputArray array)
884{
885 CV_INSTRUMENT_REGION();
886
887 Mat m = array.getMat();
888 return m.depth() <= CV_8U ? maskBoundingRect(img: m) : pointSetBoundingRect(points: m);
889}
890
891
892/* Calculates bounding rectangle of a point set or retrieves already calculated */
893CV_IMPL CvRect
894cvBoundingRect( CvArr* array, int update )
895{
896 cv::Rect rect;
897 CvContour contour_header;
898 CvSeq* ptseq = 0;
899 CvSeqBlock block;
900
901 CvMat stub, *mat = 0;
902 int calculate = update;
903
904 if( CV_IS_SEQ( array ))
905 {
906 ptseq = (CvSeq*)array;
907 if( !CV_IS_SEQ_POINT_SET( ptseq ))
908 CV_Error( cv::Error::StsBadArg, "Unsupported sequence type" );
909
910 if( ptseq->header_size < (int)sizeof(CvContour))
911 {
912 update = 0;
913 calculate = 1;
914 }
915 }
916 else
917 {
918 mat = cvGetMat( arr: array, header: &stub );
919 if( CV_MAT_TYPE(mat->type) == CV_32SC2 ||
920 CV_MAT_TYPE(mat->type) == CV_32FC2 )
921 {
922 ptseq = cvPointSeqFromMat(CV_SEQ_KIND_GENERIC, mat, contour_header: &contour_header, block: &block);
923 mat = 0;
924 }
925 else if( CV_MAT_TYPE(mat->type) != CV_8UC1 &&
926 CV_MAT_TYPE(mat->type) != CV_8SC1 )
927 CV_Error( cv::Error::StsUnsupportedFormat,
928 "The image/matrix format is not supported by the function" );
929 update = 0;
930 calculate = 1;
931 }
932
933 if( !calculate )
934 return ((CvContour*)ptseq)->rect;
935
936 if( mat )
937 {
938 rect = cvRect(rc: maskBoundingRect(img: cv::cvarrToMat(arr: mat)));
939 }
940 else if( ptseq->total )
941 {
942 cv::AutoBuffer<double> abuf;
943 rect = cvRect(rc: pointSetBoundingRect(points: cv::cvarrToMat(arr: ptseq, copyData: false, allowND: false, coiMode: 0, buf: &abuf)));
944 }
945 if( update )
946 ((CvContour*)ptseq)->rect = cvRect(rc: rect);
947 return cvRect(rc: rect);
948}
949

Provided by KDAB

Privacy Policy
Improve your Profiling and Debugging skills
Find out more

source code of opencv/modules/imgproc/src/geometry.cpp