mirrors/opencv

Merge pull request #28548 from 0AnshuAditya0:fix-minEnclosingCircle-welzl-28546

imgproc: fix minEnclosingCircle O(n^3) worst case by adding Welzl shuffle #28548

Welzl’s algorithm requires random permutation of input points to achieve expected O(n) time. Without shuffling, sorted inputs such as those produced by findContours() trigger O(n^3) worst case.

Fix: copy input to std::vector and apply cv::randShuffle() before processing. Uses OpenCV’s RNG so cv::setRNGSeed() ensures reproducible behavior.

Original benchmark (5088 contour points, Release, AVX2): findContours output: 3.93 ms → 0.033 ms (119x speedup) Random points: 0.051 ms → 0.049 ms (no regression)

Perf test results (this PR, Release, AVX2): | Input | N | Time | |——-|—|——| | Sequential circle points | 10000 | 0.03 ms | | Sequential circle points | 5000 | 0.01 ms | | Random points (CV_32F) | 100000 | 1.87 ms | | Random points (CV_32S) | 100000 | 2.81 ms |

Fixes #28546

Pull Request Readiness Checklist

See details at https://github.com/opencv/opencv/wiki/How_to_contribute#making-a-good-pull-request

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

OpenCV: Open Source Computer Vision Library

Resources

Homepage: https://opencv.org
- Courses: https://opencv.org/courses
Docs: https://docs.opencv.org/4.x/
Q&A forum: https://forum.opencv.org
- previous forum (read only): http://answers.opencv.org
Issue tracking: https://github.com/opencv/opencv/issues
Additional OpenCV functionality: https://github.com/opencv/opencv_contrib
Donate to OpenCV: https://opencv.org/support/

Contributing

Please read the contribution guidelines before starting work on a pull request.

Summary of the guidelines:

One pull request per issue;
Choose the right base branch;
Include tests and documentation;
Clean up “oops” commits before submitting;
Follow the coding style guide.

Additional Resources

Submit your OpenCV-based project for inclusion in Community Friday on opencv.org
Subscribe to the OpenCV YouTube Channel featuring OpenCV Live, an hour-long streaming show
Follow OpenCV on LinkedIn for daily posts showing the state-of-the-art in computer vision & AI
Apply to be an OpenCV Volunteer to help organize events and online campaigns as well as amplify them
Follow OpenCV on Mastodon in the Fediverse
Follow OpenCV on Twitter
OpenCV.ai: Computer Vision and AI development services from the OpenCV team.