Merge pull request #25725 from asmorkalov:as/intersectConvexConvex_fix

asmorkalov · web-flow · commit 0a12c7d9dea2 · 2024-06-16T17:07:01.000+03:00
Fixed result buffer overflow in intersectConvexConvex_ for non-convex input
diff --git a/modules/imgproc/include/opencv2/imgproc.hpp b/modules/imgproc/include/opencv2/imgproc.hpp
@@ -4251,7 +4251,7 @@ Examples of how intersectConvexConvex works
 When false, no intersection is found. If the polygons share a side or the vertex of one polygon lies on an edge
 of the other, they are not considered nested and an intersection will be found regardless of the value of handleNested.
 
-@returns Absolute value of area of intersecting polygon
+@returns Area of intersecting polygon. May be negative, if algorithm has not converged, e.g. non-convex input.
 
 @note intersectConvexConvex doesn't confirm that both polygons are convex and will return invalid results if they aren't.
  */
diff --git a/modules/imgproc/src/geometry.cpp b/modules/imgproc/src/geometry.cpp
@@ -377,9 +377,12 @@ static void addSharedSeg( Point2f p, Point2f q, Point2f*& result )
         *result++ = q;
 }
 
-
+// Note: The function and subroutings use direct pointer arithmetics instead of arrays indexing.
+// Each loop iteration may push to result array up to 3 times.
+// It means that we need +3 spare result elements against result_size
+// to catch agorithmic overflow and prevent actual result array overflow.
 static int intersectConvexConvex_( const Point2f* P, int n, const Point2f* Q, int m,
-                                   Point2f* result, float* _area )
+                                   Point2f* result, int result_size, float* _area )
 {
     Point2f* result0 = result;
     // P has n vertices, Q has m vertices.
@@ -457,7 +460,7 @@ static int intersectConvexConvex_( const Point2f* P, int n, const Point2f* Q, in
         }
         // Quit when both adv. indices have cycled, or one has cycled twice.
     }
-    while ( ((aa < n) || (ba < m)) && (aa < 2*n) && (ba < 2*m) );
+    while ( ((aa < n) || (ba < m)) && (aa < 2*n) && (ba < 2*m) && ((int)(result - result0) <= result_size) );
 
     // Deal with special cases: not implemented.
     if( inflag == Unknown )
@@ -466,10 +469,16 @@ static int intersectConvexConvex_( const Point2f* P, int n, const Point2f* Q, in
         // ...
     }
 
-    int i, nr = (int)(result - result0);
+    int nr = (int)(result - result0);
+    if (nr > result_size)
+    {
+        *_area = -1.f;
+        return -1;
+    }
+
     double area = 0;
     Point2f prev = result0[nr-1];
-    for( i = 1; i < nr; i++ )
+    for(int i = 1; i < nr; i++ )
     {
         result0[i-1] = result0[i];
         area += (double)prev.x*result0[i].y - (double)prev.y*result0[i].x;
@@ -504,9 +513,11 @@ float cv::intersectConvexConvex( InputArray _p1, InputArray _p2, OutputArray _p1
         return 0.f;
     }
 
-    AutoBuffer<Point2f> _result(n*2 + m*2 + 1);
-    Point2f *fp1 = _result.data(), *fp2 = fp1 + n;
+    AutoBuffer<Point2f> _result(n + m + n+m+1+3);
+    Point2f* fp1 = _result.data();
+    Point2f* fp2 = fp1 + n;
     Point2f* result = fp2 + m;
+
     int orientation = 0;
 
     for( int k = 1; k <= 2; k++ )
@@ -535,7 +546,15 @@ float cv::intersectConvexConvex( InputArray _p1, InputArray _p2, OutputArray _p1
     }
 
     float area = 0.f;
-    int nr = intersectConvexConvex_(fp1, n, fp2, m, result, &area);
+    int nr = intersectConvexConvex_(fp1, n, fp2, m, result, n+m+1, &area);
+
+    if (nr < 0)
+    {
+        // The algorithm did not converge, e.g. some of inputs is not convex
+        _p12.release();
+        return -1.f;
+    }
+
     if( nr == 0 )
     {
         if( !handleNested )
diff --git a/modules/imgproc/test/test_intersectconvexconvex.cpp b/modules/imgproc/test/test_intersectconvexconvex.cpp
@@ -255,6 +255,42 @@ TEST(Imgproc_IntersectConvexConvex, intersection_4)
     EXPECT_NEAR(area, 391500, std::numeric_limits<float>::epsilon());
 }
 
+// The inputs are not convex and cuased buffer overflow
+// See https://github.com/opencv/opencv/issues/25259
+TEST(Imgproc_IntersectConvexConvex, not_convex)
+{
+    std::vector<cv::Point2f> convex1 = {
+        { 46.077175f , 228.66121f  }, {  5.428622f , 250.05899f  }, {207.51741f  , 109.645676f },
+        {175.94789f  ,  32.6566f   }, {217.4915f   , 252.66176f  }, {187.09386f  ,   6.3988557f},
+        { 52.20488f  ,  69.266205f }, { 38.188286f , 134.48068f  }, {246.4742f   ,  31.41043f  },
+        {178.97946f  , 169.52287f  }, {103.40764f  , 153.30397f  }, {160.67746f  ,  17.166115f },
+        {152.44255f  , 135.35f     }, {197.03804f  , 193.04782f  }, {248.28397f  ,  56.821487f },
+        { 10.907227f ,  82.55291f  }, {109.67949f  ,  70.7405f   }, { 58.96842f  , 150.132f    },
+        {150.7613f   , 129.54753f  }, {254.98463f  , 228.21748f  }, {139.02563f  , 193.89336f  },
+        { 84.79946f  , 162.25363f  }, { 39.83567f  ,  44.626484f }, {107.034996f , 209.38887f  },
+        { 67.61073f  ,  17.119232f }, {208.8617f   ,  33.67367f  }, {182.65207f  ,   8.291072f },
+        { 72.89319f  ,  42.51845f  }, {202.4902f   , 123.97209f  }, { 79.945076f , 140.99268f  },
+        {225.8952f   ,  66.226326f }, { 34.08404f  , 219.2208f   }, {243.1221f   ,  60.95162f  }
+    };
+    std::vector<cv::Point2f> convex2 = {
+        {144.33624f  , 247.15732f  }, {  5.656847f ,  17.461054f }, {230.54338f  ,   2.0446582f},
+        {143.0578f   , 215.27856f  }, {250.44626f  ,  82.54287f  }, {  0.3846766f,  11.101262f },
+        { 70.81022f  ,  17.243904f }, { 77.18812f  ,  75.760666f }, {190.34933f  , 234.30962f  },
+        {230.10204f  , 133.67998f  }, { 58.903755f , 252.96451f  }, {213.57228f  , 155.7058f   },
+        {190.80992f  , 212.90802f  }, {203.4356f   ,  36.55016f  }, { 32.276424f ,   2.5646307f},
+        { 39.73823f  ,  87.23782f  }, {112.46902f  , 101.81753f  }, { 58.154305f , 238.40395f  },
+        {187.01064f  ,  96.24343f  }, { 44.42692f  ,  10.573529f }, {118.76949f  , 233.35114f  },
+        { 86.26109f  , 120.93148f  }, {217.94751f  , 130.5933f   }, {148.2687f   ,  68.56015f  },
+        {187.44174f  , 214.32857f  }, {247.19875f  , 180.8494f   }, { 17.986013f ,  61.451443f },
+        {254.74344f  , 204.71747f  }, {211.92726f  , 132.0139f   }, { 51.36624f  , 116.63085f  },
+        { 83.80044f  , 124.20074f  }, {122.125854f ,  25.182402f }, { 39.08164f  , 180.08517f  }
+    };
+    std::vector<cv::Point> intersection;
+
+    float area = cv::intersectConvexConvex(convex1, convex2, intersection, false);
+    EXPECT_TRUE(intersection.empty());
+    EXPECT_LE(area, 0.f);
+}
 
 } // namespace
 } // opencv_test
