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 | |
44 | using namespace cv; |
45 | |
46 | CV_IMPL CvRect |
47 | cvMaxRect( 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 | |
88 | CV_IMPL void |
89 | cvBoxPoints( 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 | |
97 | double 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 | |
248 | CV_IMPL double |
249 | cvPointPolygonTest( 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 | |
271 | namespace cv |
272 | { |
273 | typedef enum { Pin, Qin, Unknown } tInFlag; |
274 | |
275 | static 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 | //--------------------------------------------------------------------- |
286 | static 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 | |
299 | enum LineSegmentIntersection |
300 | { |
301 | LS_NO_INTERSECTION = 0, |
302 | LS_SINGLE_INTERSECTION = 1, |
303 | LS_OVERLAP = 2, |
304 | LS_ENDPOINT_INTERSECTION = 3 |
305 | }; |
306 | |
307 | static 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). |
330 | static 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 | |
353 | static 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 | //--------------------------------------------------------------------- |
364 | static 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 | |
372 | static 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. |
384 | static 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 | |
497 | float 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 | |
617 | static 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 |
707 | static 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 | |
883 | cv::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 */ |
893 | CV_IMPL CvRect |
894 | cvBoundingRect( CvArr* array, int update ) |
895 | { |
896 | cv::Rect rect; |
897 | CvContour ; |
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 | |