Fix issues in Convex Hull algorithm #27020

kallaballa · 2025-03-06T05:37:10Z

Pull Request Readiness Checklist

See: #26952 and #26975

I agree to contribute to the project under Apache 2 License.
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
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

kallaballa · 2025-03-06T05:38:24Z

I created a simpler patch (than for #26975) that is considerably slower but seems to be correct.

kallaballa · 2025-03-06T05:40:32Z

To fix this issue entirely i would propose something like the following:

Preferred signature: easy to be implemented fast and correct. allows for input validation.

template<typename TpointContainer, typename Thull>
void convexHull(TpointContainer& points, std::vector<Thull>& hull, bool clockwise>

Deprecated signature 1: does the same as the preferred signature, only deprecated because the last parameter should be removed.

template<typename TpointContainer, typename Tpoints, typename Thull>
void convexHull(TpointContainer& points, std::vector<Thull>& hull, bool clockwise, bool ignored>

Deprecated signature 2: the original function fixed to the point where it retains behavior as closely as possible while preventing memory errors. probably considerably slower.

void convexHull( InputArray _points, OutputArray _hull, bool clockwise, bool returnPoints )

kallaballa · 2025-03-07T04:21:38Z

Afaics tests fail now when they are using numerical arrays as input. I wouldn't know how to fix that except by explicitly converting (i use _InputArray::copyTo now)... but actually arrays are not documented as possible input for convexHull. How should i proceed?

kallaballa · 2025-03-08T08:35:39Z

There is no array kind. I am puzzled by how to make this work with all the variants.

In short: how can i convert numerical arrays, std::vector<Point_> and cv::Matx_<Point_> via InputArray to a continuous memory region of points? how to distinguish them and perform input validation?
The current approach if seen is to rely on the illegal assumption that:

int arr[2] = {2,3};
Point* pt = (Point*) arr;

Just going through getMat() doesn't work for numerical arrays.

and: how should i handle the discrepancies with the documentation?

asmorkalov · 2025-03-20T09:23:31Z

@mshabunin could you take a look?

asmorkalov · 2025-04-22T08:04:56Z

@mshabunin Could you take a look on it?

mshabunin · 2025-04-28T11:30:46Z

I couldn't reproduce original issue, waiting for more details (see #26952).

kallaballa · 2025-04-28T12:55:02Z

Sorry for the delay. I'll try to continue now but I don't know if i have enough time to finish.
btw. no matter if you can easily reproduce it, those are quite obviously severe issues, don't you think?

kallaballa · 2025-04-28T13:01:06Z

i am just asking because i wonder... you wouldn't ask for a reproducer if it was something like std::vector({0,1,2})[99] (and i think it is even worse). anyway i am on it.

asmorkalov · 2025-05-13T05:16:46Z

Friendly reminder.

asmorkalov · 2025-05-13T05:21:26Z

modules/imgproc/src/convhull.cpp

-        for( i = 0; i < nout; i++ )
-            *(Point*)(hull.ptr() + i*step) = data0[hullbuf[i]];
+    } else {
+        _hull.create(nout, 1, _hull.type());


_hull.type() may be undefined, e.g. in Python case of it output is just cv::Mat. The original approach works better here.

I am not sure how this should work without violating C++. we are not allowed to guess the size and layout of any object (after all a Point object is more than just 2 ints).

asmorkalov · 2025-05-13T05:23:46Z

modules/imgproc/src/convhull.cpp

+        for(int i = 0; i < bl_count-1; i++ )
+            hullbuf[nout++] = int(&pointer[bl_stack[i]] - pointer);
+        for(int i = br_count-1; i > 0; i-- )
+            hullbuf[nout++] = int(&pointer[br_stack[i]] - pointer);


&pointer[bl_stack[i]] - pointer is just bl_stack[i], right?

nice catch! thx

asmorkalov · 2025-05-13T05:24:55Z

modules/imgproc/src/convhull.cpp

+        for(int i = 0; i < tl_count-1; i++ )
+            hullbuf[nout++] = int(&pointer[tl_stack[i]] - pointer);
+        for(int i = tr_count - 1; i > 0; i-- )
+            hullbuf[nout++] = int(&pointer[tr_stack[i]] - pointer);


pointer[tl_stack[i]] - pointer is just tl_stack[i], right?

nice catch! thx

asmorkalov · 2025-06-18T08:11:43Z

@kallaballa Friendly reminder.

kallaballa · 2025-08-05T06:44:46Z

before i can continue: is the documentation authoritative or not? if not could you update it so i have a fixed reference to how this should actually work?

kallaballa · 2025-08-05T14:24:01Z

I somehow cause problems with the java bindings. would someone have a hint on how to fix this?

https://pullrequest.opencv.org/buildbot/builders/precommit_linux64/builds/112467/steps/compile%20release/logs/stdio

    [javac] /build/precommit_linux64/build/modules/java/jar/opencv/java/org/opencv/imgproc/Imgproc.java:8295: error: method convexHull(MatOfPoint,MatOfInt,boolean) is already defined in class Imgproc
    [javac]     public static void convexHull(MatOfPoint points, MatOfInt hull, boolean clockwise) {
    [javac]                        ^
    [javac] /build/precommit_linux64/build/modules/java/jar/opencv/java/org/opencv/imgproc/Imgproc.java:8301: error: method convexHull(MatOfPoint,MatOfInt) is already defined in class Imgproc
    [javac]     public static void convexHull(MatOfPoint points, MatOfInt hull) {
    [javac]                        ^
    [javac] /build/precommit_linux64/build/modules/java/jar/opencv/java/org/opencv/imgproc/Imgproc.java:8312: error: method convexHull(MatOfPoint,MatOfInt,boolean) is already defined in class Imgproc
    [javac]     public static void convexHull(MatOfPoint points, MatOfInt hull, boolean clockwise) {
    [javac]                        ^
    [javac] /build/precommit_linux64/build/modules/java/jar/opencv/java/org/opencv/imgproc/Imgproc.java:8318: error: method convexHull(MatOfPoint,MatOfInt) is already defined in class Imgproc
    [javac]     public static void convexHull(MatOfPoint points, MatOfInt hull) {
    [javac]                        ^
    [javac] /build/precommit_linux64/build/modules/java/jar/opencv/java/org/opencv/imgproc/Imgproc.java:8329: error: method convexHull(MatOfPoint,MatOfInt,boolean) is already defined in class Imgproc
    [javac]     public static void convexHull(MatOfPoint points, MatOfInt hull, boolean clockwise) {
    [javac]                        ^
    [javac] /build/precommit_linux64/build/modules/java/jar/opencv/java/org/opencv/imgproc/Imgproc.java:8335: error: method convexHull(MatOfPoint,MatOfInt) is already defined in class Imgproc
    [javac]     public static void convexHull(MatOfPoint points, MatOfInt hull) {
    [javac]

asmorkalov · 2025-08-07T09:02:03Z

modules/imgproc/include/opencv2/imgproc.hpp

+CV_EXPORTS_W void convexHull( InputArray points, std::vector<int>& hull, bool clockwise = false, bool returnPoints = true );
+CV_EXPORTS_W void convexHull( InputArray points, std::vector<Point>& hull, bool clockwise = false, bool returnPoints = true );
+CV_EXPORTS_W void convexHull( InputArray points, std::vector<Point2f>& hull, bool clockwise = false, bool returnPoints = true );


Why do you need the overloads?

That is my workaround (that allows me to use meta-programming behind the scenes and avoid OutputArray while having static input validation) for the problems i have:

#27020 (comment)
#27020 (comment)

Fix issues in convHull algorithm

64ba08e

kallaballa added 5 commits March 6, 2025 06:44

remove dead code

85ed780

Prefer Mat over vector in hull creation

8fc3799

Reuse outputarray type

8f46f21

allow Mat for hulls

b11cedb

Removed another check

6ae1ea1

opencv-alalek added pr: needs test New functionality requires minimal tests set category: imgproc labels Mar 6, 2025

kallaballa force-pushed the convexhullpointer branch from a408412 to 6ae1ea1 Compare March 6, 2025 10:38

kallaballa marked this pull request as ready for review March 8, 2025 08:35

asmorkalov requested a review from mshabunin March 11, 2025 09:27

asmorkalov added this to the 4.12.0 milestone Mar 11, 2025

asmorkalov assigned mshabunin Apr 22, 2025

asmorkalov reviewed May 13, 2025

View reviewed changes

asmorkalov modified the milestones: 4.12.0, 4.13.0 Jun 19, 2025

kallaballa added 2 commits August 4, 2025 18:57

further refined the convex hull code

54d1aa0

fixed sort comparator and made some minor improvements

b3eed4d

kallaballa and others added 5 commits August 5, 2025 10:18

Merge branch 'opencv:4.x' into convexhullpointer

5d98a98

more improvements to convexHull

1624b56

fixed interfacing issues in convexHull

412c899

improved hull copying for convexHull

77026b2

fixed warnings and better container handling

fea78e8

reverted cvConvexHull2 and placed safeguards

a3ac8fd

asmorkalov reviewed Aug 7, 2025

View reviewed changes

Uh oh!

Fix issues in Convex Hull algorithm #27020

Are you sure you want to change the base?

Fix issues in Convex Hull algorithm #27020

Conversation

kallaballa commented Mar 6, 2025 • edited by asmorkalov Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Pull Request Readiness Checklist

Uh oh!

kallaballa commented Mar 6, 2025

Uh oh!

kallaballa commented Mar 6, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Preferred signature: easy to be implemented fast and correct. allows for input validation.

Deprecated signature 1: does the same as the preferred signature, only deprecated because the last parameter should be removed.

Deprecated signature 2: the original function fixed to the point where it retains behavior as closely as possible while preventing memory errors. probably considerably slower.

Uh oh!

kallaballa commented Mar 7, 2025

Uh oh!

kallaballa commented Mar 8, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

asmorkalov commented Mar 20, 2025

Uh oh!

asmorkalov commented Apr 22, 2025

Uh oh!

mshabunin commented Apr 28, 2025

Uh oh!

kallaballa commented Apr 28, 2025

Uh oh!

kallaballa commented Apr 28, 2025

Uh oh!

asmorkalov commented May 13, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

asmorkalov commented Jun 18, 2025

Uh oh!

kallaballa commented Aug 5, 2025

Uh oh!

kallaballa commented Aug 5, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

kallaballa commented Mar 6, 2025 •

edited by asmorkalov

Loading

kallaballa commented Mar 6, 2025 •

edited

Loading

kallaballa commented Mar 8, 2025 •

edited

Loading