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 // License Agreement 11 // For Open Source Computer Vision Library 12 // 13 // Copyright (C) 2000-2008, Intel Corporation, all rights reserved. 14 // Copyright (C) 2008-2011, Willow Garage Inc., all rights reserved. 15 // Third party copyrights are property of their respective owners. 16 // 17 // @Authors 18 // Nghia Ho, nghiaho12 (at) yahoo.com 19 // 20 // Redistribution and use in source and binary forms, with or without modification, 21 // are permitted provided that the following conditions are met: 22 // 23 // * Redistribution's of source code must retain the above copyright notice, 24 // this list of conditions and the following disclaimer. 25 // 26 // * Redistribution's in binary form must reproduce the above copyright notice, 27 // this list of conditions and the following disclaimer in the documentation 28 // and/or other materials provided with the distribution. 29 // 30 // * The name of OpenCV Foundation may not be used to endorse or promote products 31 // derived from this software without specific prior written permission. 32 // 33 // This software is provided by the copyright holders and contributors "as is" and 34 // any express or implied warranties, including, but not limited to, the implied 35 // warranties of merchantability and fitness for a particular purpose are disclaimed. 36 // In no event shall the OpenCV Foundation or contributors be liable for any direct, 37 // indirect, incidental, special, exemplary, or consequential damages 38 // (including, but not limited to, procurement of substitute goods or services; 39 // loss of use, data, or profits; or business interruption) however caused 40 // and on any theory of liability, whether in contract, strict liability, 41 // or tort (including negligence or otherwise) arising in any way out of 42 // the use of this software, even if advised of the possibility of such damage. 43 // 44 //M*/ 45 #include "precomp.hpp" 46 47 namespace cv 48 { 49 50 int rotatedRectangleIntersection( const RotatedRect& rect1, const RotatedRect& rect2, OutputArray intersectingRegion ) 51 { 52 const float samePointEps = 0.00001f; // used to test if two points are the same 53 54 Point2f vec1[4], vec2[4]; 55 Point2f pts1[4], pts2[4]; 56 57 std::vector <Point2f> intersection; 58 59 rect1.points(pts1); 60 rect2.points(pts2); 61 62 int ret = INTERSECT_FULL; 63 64 // Specical case of rect1 == rect2 65 { 66 bool same = true; 67 68 for( int i = 0; i < 4; i++ ) 69 { 70 if( fabs(pts1[i].x - pts2[i].x) > samePointEps || (fabs(pts1[i].y - pts2[i].y) > samePointEps) ) 71 { 72 same = false; 73 break; 74 } 75 } 76 77 if(same) 78 { 79 intersection.resize(4); 80 81 for( int i = 0; i < 4; i++ ) 82 { 83 intersection[i] = pts1[i]; 84 } 85 86 Mat(intersection).copyTo(intersectingRegion); 87 88 return INTERSECT_FULL; 89 } 90 } 91 92 // Line vector 93 // A line from p1 to p2 is: p1 + (p2-p1)*t, t=[0,1] 94 for( int i = 0; i < 4; i++ ) 95 { 96 vec1[i].x = pts1[(i+1)%4].x - pts1[i].x; 97 vec1[i].y = pts1[(i+1)%4].y - pts1[i].y; 98 99 vec2[i].x = pts2[(i+1)%4].x - pts2[i].x; 100 vec2[i].y = pts2[(i+1)%4].y - pts2[i].y; 101 } 102 103 // Line test - test all line combos for intersection 104 for( int i = 0; i < 4; i++ ) 105 { 106 for( int j = 0; j < 4; j++ ) 107 { 108 // Solve for 2x2 Ax=b 109 float x21 = pts2[j].x - pts1[i].x; 110 float y21 = pts2[j].y - pts1[i].y; 111 112 float vx1 = vec1[i].x; 113 float vy1 = vec1[i].y; 114 115 float vx2 = vec2[j].x; 116 float vy2 = vec2[j].y; 117 118 float det = vx2*vy1 - vx1*vy2; 119 120 float t1 = (vx2*y21 - vy2*x21) / det; 121 float t2 = (vx1*y21 - vy1*x21) / det; 122 123 // This takes care of parallel lines 124 if( cvIsInf(t1) || cvIsInf(t2) || cvIsNaN(t1) || cvIsNaN(t2) ) 125 { 126 continue; 127 } 128 129 if( t1 >= 0.0f && t1 <= 1.0f && t2 >= 0.0f && t2 <= 1.0f ) 130 { 131 float xi = pts1[i].x + vec1[i].x*t1; 132 float yi = pts1[i].y + vec1[i].y*t1; 133 134 intersection.push_back(Point2f(xi,yi)); 135 } 136 } 137 } 138 139 if( !intersection.empty() ) 140 { 141 ret = INTERSECT_PARTIAL; 142 } 143 144 // Check for vertices from rect1 inside recct2 145 for( int i = 0; i < 4; i++ ) 146 { 147 // We do a sign test to see which side the point lies. 148 // If the point all lie on the same sign for all 4 sides of the rect, 149 // then there's an intersection 150 int posSign = 0; 151 int negSign = 0; 152 153 float x = pts1[i].x; 154 float y = pts1[i].y; 155 156 for( int j = 0; j < 4; j++ ) 157 { 158 // line equation: Ax + By + C = 0 159 // see which side of the line this point is at 160 float A = -vec2[j].y; 161 float B = vec2[j].x; 162 float C = -(A*pts2[j].x + B*pts2[j].y); 163 164 float s = A*x+ B*y+ C; 165 166 if( s >= 0 ) 167 { 168 posSign++; 169 } 170 else 171 { 172 negSign++; 173 } 174 } 175 176 if( posSign == 4 || negSign == 4 ) 177 { 178 intersection.push_back(pts1[i]); 179 } 180 } 181 182 // Reverse the check - check for vertices from rect2 inside recct1 183 for( int i = 0; i < 4; i++ ) 184 { 185 // We do a sign test to see which side the point lies. 186 // If the point all lie on the same sign for all 4 sides of the rect, 187 // then there's an intersection 188 int posSign = 0; 189 int negSign = 0; 190 191 float x = pts2[i].x; 192 float y = pts2[i].y; 193 194 for( int j = 0; j < 4; j++ ) 195 { 196 // line equation: Ax + By + C = 0 197 // see which side of the line this point is at 198 float A = -vec1[j].y; 199 float B = vec1[j].x; 200 float C = -(A*pts1[j].x + B*pts1[j].y); 201 202 float s = A*x + B*y + C; 203 204 if( s >= 0 ) 205 { 206 posSign++; 207 } 208 else 209 { 210 negSign++; 211 } 212 } 213 214 if( posSign == 4 || negSign == 4 ) 215 { 216 intersection.push_back(pts2[i]); 217 } 218 } 219 220 // Get rid of dupes 221 for( int i = 0; i < (int)intersection.size()-1; i++ ) 222 { 223 for( size_t j = i+1; j < intersection.size(); j++ ) 224 { 225 float dx = intersection[i].x - intersection[j].x; 226 float dy = intersection[i].y - intersection[j].y; 227 double d2 = dx*dx + dy*dy; // can be a really small number, need double here 228 229 if( d2 < samePointEps*samePointEps ) 230 { 231 // Found a dupe, remove it 232 std::swap(intersection[j], intersection.back()); 233 intersection.pop_back(); 234 j--; // restart check 235 } 236 } 237 } 238 239 if( intersection.empty() ) 240 { 241 return INTERSECT_NONE ; 242 } 243 244 // If this check fails then it means we're getting dupes, increase samePointEps 245 CV_Assert( intersection.size() <= 8 ); 246 247 Mat(intersection).copyTo(intersectingRegion); 248 249 return ret; 250 } 251 252 } // end namespace 253