intersection.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 //                           License Agreement
00011 //                For Open Source Computer Vision Library
00012 //
00013 // Copyright (C) 2000-2008, Intel Corporation, all rights reserved.
00014 // Copyright (C) 2008-2011, Willow Garage Inc., all rights reserved.
00015 // Third party copyrights are property of their respective owners.
00016 //
00017 // @Authors
00018 //      Nghia Ho, nghiaho12@yahoo.com
00019 //
00020 // Redistribution and use in source and binary forms, with or without modification,
00021 // are permitted provided that the following conditions are met:
00022 //
00023 //   * Redistribution's of source code must retain the above copyright notice,
00024 //     this list of conditions and the following disclaimer.
00025 //
00026 //   * Redistribution's in binary form must reproduce the above copyright notice,
00027 //     this list of conditions and the following disclaimer in the documentation
00028 //     and/or other materials provided with the distribution.
00029 //
00030 //   * The name of OpenCV Foundation may not be used to endorse or promote products
00031 //     derived from this software without specific prior written permission.
00032 //
00033 // This software is provided by the copyright holders and contributors "as is" and
00034 // any express or implied warranties, including, but not limited to, the implied
00035 // warranties of merchantability and fitness for a particular purpose are disclaimed.
00036 // In no event shall the OpenCV Foundation or contributors be liable for any direct,
00037 // indirect, incidental, special, exemplary, or consequential damages
00038 // (including, but not limited to, procurement of substitute goods or services;
00039 // loss of use, data, or profits; or business interruption) however caused
00040 // and on any theory of liability, whether in contract, strict liability,
00041 // or tort (including negligence or otherwise) arising in any way out of
00042 // the use of this software, even if advised of the possibility of such damage.
00043 //
00044 //M*/
00045 #include "precomp.hpp"
00046 
00047 namespace cv
00048 {
00049 
00050 int rotatedRectangleIntersection( const RotatedRect& rect1, const RotatedRect& rect2, OutputArray intersectingRegion )
00051 {
00052     const float samePointEps = 0.00001f; // used to test if two points are the same
00053 
00054     Point2f  vec1[4], vec2[4];
00055     Point2f  pts1[4], pts2[4];
00056 
00057     std::vector <Point2f> intersection;
00058 
00059     rect1.points(pts1);
00060     rect2.points(pts2);
00061 
00062     int ret = INTERSECT_FULL;
00063 
00064     // Specical case of rect1 == rect2
00065     {
00066         bool same = true;
00067 
00068         for( int i = 0; i < 4; i++ )
00069         {
00070             if( fabs(pts1[i].x - pts2[i].x) > samePointEps || (fabs(pts1[i].y - pts2[i].y) > samePointEps) )
00071             {
00072                 same = false;
00073                 break;
00074             }
00075         }
00076 
00077         if(same)
00078         {
00079             intersection.resize(4);
00080 
00081             for( int i = 0; i < 4; i++ )
00082             {
00083                 intersection[i] = pts1[i];
00084             }
00085 
00086             Mat(intersection).copyTo(intersectingRegion);
00087 
00088             return INTERSECT_FULL;
00089         }
00090     }
00091 
00092     // Line vector
00093     // A line from p1 to p2 is: p1 + (p2-p1)*t, t=[0,1]
00094     for( int i = 0; i < 4; i++ )
00095     {
00096         vec1[i].x = pts1[(i+1)%4].x - pts1[i].x;
00097         vec1[i].y = pts1[(i+1)%4].y - pts1[i].y;
00098 
00099         vec2[i].x = pts2[(i+1)%4].x - pts2[i].x;
00100         vec2[i].y = pts2[(i+1)%4].y - pts2[i].y;
00101     }
00102 
00103     // Line test - test all line combos for intersection
00104     for( int i = 0; i < 4; i++ )
00105     {
00106         for( int j = 0; j < 4; j++ )
00107         {
00108             // Solve for 2x2 Ax=b
00109             float x21 = pts2[j].x - pts1[i].x;
00110             float y21 = pts2[j].y - pts1[i].y;
00111 
00112             float vx1 = vec1[i].x;
00113             float vy1 = vec1[i].y;
00114 
00115             float vx2 = vec2[j].x;
00116             float vy2 = vec2[j].y;
00117 
00118             float det = vx2*vy1 - vx1*vy2;
00119 
00120             float t1 = (vx2*y21 - vy2*x21) / det;
00121             float t2 = (vx1*y21 - vy1*x21) / det;
00122 
00123             // This takes care of parallel lines
00124             if( cvIsInf(t1) || cvIsInf(t2) || cvIsNaN(t1) || cvIsNaN(t2) )
00125             {
00126                 continue;
00127             }
00128 
00129             if( t1 >= 0.0f && t1 <= 1.0f && t2 >= 0.0f && t2 <= 1.0f )
00130             {
00131                 float xi = pts1[i].x + vec1[i].x*t1;
00132                 float yi = pts1[i].y + vec1[i].y*t1;
00133 
00134                 intersection.push_back(Point2f (xi,yi));
00135             }
00136         }
00137     }
00138 
00139     if( !intersection.empty() )
00140     {
00141         ret = INTERSECT_PARTIAL;
00142     }
00143 
00144     // Check for vertices from rect1 inside recct2
00145     for( int i = 0; i < 4; i++ )
00146     {
00147         // We do a sign test to see which side the point lies.
00148         // If the point all lie on the same sign for all 4 sides of the rect,
00149         // then there's an intersection
00150         int posSign = 0;
00151         int negSign = 0;
00152 
00153         float x = pts1[i].x;
00154         float y = pts1[i].y;
00155 
00156         for( int j = 0; j < 4; j++ )
00157         {
00158             // line equation: Ax + By + C = 0
00159             // see which side of the line this point is at
00160             float A = -vec2[j].y;
00161             float B = vec2[j].x;
00162             float C = -(A*pts2[j].x + B*pts2[j].y);
00163 
00164             float s = A*x+ B*y+ C;
00165 
00166             if( s >= 0 )
00167             {
00168                 posSign++;
00169             }
00170             else
00171             {
00172                 negSign++;
00173             }
00174         }
00175 
00176         if( posSign == 4 || negSign == 4 )
00177         {
00178             intersection.push_back(pts1[i]);
00179         }
00180     }
00181 
00182     // Reverse the check - check for vertices from rect2 inside recct1
00183     for( int i = 0; i < 4; i++ )
00184     {
00185         // We do a sign test to see which side the point lies.
00186         // If the point all lie on the same sign for all 4 sides of the rect,
00187         // then there's an intersection
00188         int posSign = 0;
00189         int negSign = 0;
00190 
00191         float x = pts2[i].x;
00192         float y = pts2[i].y;
00193 
00194         for( int j = 0; j < 4; j++ )
00195         {
00196             // line equation: Ax + By + C = 0
00197             // see which side of the line this point is at
00198             float A = -vec1[j].y;
00199             float B = vec1[j].x;
00200             float C = -(A*pts1[j].x + B*pts1[j].y);
00201 
00202             float s = A*x + B*y + C;
00203 
00204             if( s >= 0 )
00205             {
00206                 posSign++;
00207             }
00208             else
00209             {
00210                 negSign++;
00211             }
00212         }
00213 
00214         if( posSign == 4 || negSign == 4 )
00215         {
00216             intersection.push_back(pts2[i]);
00217         }
00218     }
00219 
00220     // Get rid of dupes
00221     for( int i = 0; i < (int)intersection.size()-1; i++ )
00222     {
00223         for( size_t j = i+1; j < intersection.size(); j++ )
00224         {
00225             float dx = intersection[i].x - intersection[j].x;
00226             float dy = intersection[i].y - intersection[j].y;
00227             double d2 = dx*dx + dy*dy; // can be a really small number, need double here
00228 
00229             if( d2 < samePointEps*samePointEps )
00230             {
00231                 // Found a dupe, remove it
00232                 std::swap(intersection[j], intersection.back());
00233                 intersection.pop_back();
00234                 j--; // restart check
00235             }
00236         }
00237     }
00238 
00239     if( intersection.empty() )
00240     {
00241         return INTERSECT_NONE ;
00242     }
00243 
00244     // If this check fails then it means we're getting dupes, increase samePointEps
00245     CV_Assert( intersection.size() <= 8 );
00246 
00247     Mat(intersection).copyTo(intersectingRegion);
00248 
00249     return ret;
00250 }
00251 
00252 } // end namespace
00253