Merge pull request #26974 from klosteraner:Fix-IntersectConvexConvex

klosteraner · web-flow · commit 43112409ef0b · 2025-06-28T22:06:42.000+03:00
Issue 26972: Proper treatment of float values in intersectConvexConvex #26974 As outlined in #26972 the function `intersectConvexConvex()` may not work as expected in the corner case, where two polygons intersect at a corner. A concrete example is given that I added as unit test. The unit test would fail without the proposed bug fix. I recommend porting the fix to all versions. Now concerning the fix: When digging into the implementation I found, that when the line intersections are computed, openCV currently does not apply floating point comparison syntax, but pretends that line end points are exact. Instead I replaced the formulation using the eps that is already used in another component of the function in line.277: `epx=1e-5`. IMO that is solid enough, definitely better than assuming an exact floating point comparison is possible. As a follow up I would suggest to use a scalable eps, s.t. also cases with high floating point numbers would be less error prone. However that would need to be done in all relevant sub steps, not just the line intersection code. So for me outside the scope of this fix. ### Pull Request Readiness Checklist See details at https://github.com/opencv/opencv/wiki/How_to_contribute#making-a-good-pull-request - [x] I agree to contribute to the project under Apache 2 License. - [x] To the best of my knowledge, the proposed patch is not based on a code under GPL or another license that is incompatible with OpenCV - [x] The PR is proposed to the proper branch - [ ] There is a reference to the original bug report and related work - [ ] There is accuracy test, performance test and test data in opencv_extra repository, if applicable Patch to opencv_extra has the same branch name. - [ ] The feature is well documented and sample code can be built with the project CMake
diff --git a/modules/imgproc/src/geometry.cpp b/modules/imgproc/src/geometry.cpp
@@ -330,20 +330,20 @@ static LineSegmentIntersection parallelInt( Point2f a, Point2f b, Point2f c, Poi
 static LineSegmentIntersection intersectLineSegments( Point2f a, Point2f b, Point2f c,
                                                       Point2f d, Point2f& p, Point2f& q )
 {
-    double denom = (a.x - b.x) * (double)(d.y - c.y) - (a.y - b.y) * (double)(d.x - c.x);
+    double denom = ((double)a.x - b.x) * ((double)d.y - c.y) - ((double)a.y - b.y) * ((double)d.x - c.x);
 
     // If denom is zero, then segments are parallel: handle separately.
     if( denom == 0. )
         return parallelInt(a, b, c, d, p, q);
 
-    double num = (d.y - a.y) * (double)(a.x - c.x) + (a.x - d.x) * (double)(a.y - c.y);
+    double num = ((double)d.y - a.y) * ((double)a.x - c.x) + ((double)a.x - d.x) * ((double)a.y - c.y);
     double s = num / denom;
 
-    num = (b.y - a.y) * (double)(a.x - c.x) + (c.y - a.y) * (double)(b.x - a.x);
+    num = ((double)b.y - a.y) * ((double)a.x - c.x) + ((double)c.y - a.y) * ((double)b.x - a.x);
     double t = num / denom;
 
-    p.x = (float)(a.x + s*(b.x - a.x));
-    p.y = (float)(a.y + s*(b.y - a.y));
+    p.x = (float)(a.x + s*((double)b.x - a.x));
+    p.y = (float)(a.y + s*((double)b.y - a.y));
     q = p;
 
     return s < 0. || s > 1. || t < 0. || t > 1. ? LS_NO_INTERSECTION :
diff --git a/modules/imgproc/test/test_intersectconvexconvex.cpp b/modules/imgproc/test/test_intersectconvexconvex.cpp
@@ -292,5 +292,27 @@ TEST(Imgproc_IntersectConvexConvex, not_convex)
     EXPECT_LE(area, 0.f);
 }
 
+// The intersection was not properly detected when one line sneaked its way in through an edge point
+TEST(Imgproc_IntersectConvexConvex, intersection_at_line_transition)
+{
+    std::vector<cv::Point2f> convex1 = {
+        {  -1.7604526f,  -0.00028443217f },
+        {1276.5778f   ,   0.2091252f},
+        {1276.4617f   , 719.27f},
+        {  -1.8754264f, 719.06866f}
+
+    };
+    std::vector<cv::Point2f> convex2 = {
+        {   0.f ,   0.f },
+        {1280.f ,   0.f },
+        {1280.f , 720.f},
+        {   0.f , 720.f }
+    };
+    std::vector<cv::Point> intersection;
+
+    float area = cv::intersectConvexConvex(convex1, convex2, intersection, false);
+    EXPECT_GE(cv::contourArea(convex1), area);
+    EXPECT_GE(cv::contourArea(convex2), area);
+}
 } // namespace
 } // opencv_test
