I needed to reduce the number of vertices of the convex hull so that the additional area was minimal, andall vertices of the original contour enter the new contour.

Description

Initially in the contour of n vertices, at each stage we consider the intersection points of the lines formed by each adjacent edges. Each of these intersection points will form a triangle with vertices through which lines pass. Let's choose a triangle with the minimum area and merge the two vertices at the intersection point. We continue until there are more vertices than the specified number of sides of the approximated polygon.

Complexity:

Using a std::priority_queue or std::set time complexity is(O(n*ln(n)), memoryO(n),
n - number of vertices in convex hull.

count of sides - the number of points by which we must reduce.

Comment

If epsilon_percentage more 0, algorithm can return more values thanside.
Algorithm returns OutputArray. If OutputArray.type() equals 0, algorithm returns values with InputArray.type().
New test uses image which are not in opencv_extra, needs to be added.

Pull Request Readiness Checklist

See details athttps://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

added ApproxBoundingPoly

d5664d7

Napkin-AI mentioned this pull request

May 19, 2024

Added extra image for PR approxBoundingPolyopencv/opencv_extra#1179

Closed

asmorkalov added this to the4.11.0 milestone

May 20, 2024

asmorkalov added feature category: imgproc labels

May 20, 2024

Copy link

Contributor

asmorkalov commentedMay 20, 2024

2024-05-20T07:02:31.6292590Z /usr/bin/ccache /usr/bin/c++  -DCVAPI_EXPORTS -D_USE_MATH_DEFINES -D__OPENCV_BUILD=1 -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -I/home/ci/opencv/modules/imgproc/include -Imodules/imgproc -I/home/ci/opencv/modules/core/include -isystem . -isystem /usr/include/eigen3 -fsigned-char -W -Wall -Wreturn-type -Wnon-virtual-dtor -Waddress -Wsequence-point -Wformat -Wformat-security -Wmissing-declarations -Wundef -Winit-self -Wpointer-arith -Wshadow -Wsign-promo -Wuninitialized -Wsuggest-override -Wno-delete-non-virtual-dtor -Wno-comment -Wimplicit-fallthrough=3 -Wno-strict-overflow -fdiagnostics-show-option -pthread -fomit-frame-pointer -ffunction-sections -fdata-sections    -fvisibility=hidden -fvisibility-inlines-hidden -O3 -DNDEBUG  -DNDEBUG -fPIC   -std=c++11 -MD -MT modules/imgproc/CMakeFiles/opencv_imgproc.dir/src/approx.cpp.o -MF modules/imgproc/CMakeFiles/opencv_imgproc.dir/src/approx.cpp.o.d -o modules/imgproc/CMakeFiles/opencv_imgproc.dir/src/approx.cpp.o -c /home/ci/opencv/modules/imgproc/src/approx.cpp2024-05-20T07:02:31.6304361Z /home/ci/opencv/modules/imgproc/src/approx.cpp:911:5: warning: no previous declaration for 'int recalculation(std::vector<neighbours>&, int, float&, float&, float&)' [-Wmissing-declarations]2024-05-20T07:02:31.6306865Z   911 | int recalculation(std::vector<neighbours>& hull, int vertex_id, float& area_, float& x, float& y)2024-05-20T07:02:31.6308049Z       |     ^~~~~~~~~~~~~2024-05-20T07:02:31.6309995Z /home/ci/opencv/modules/imgproc/src/approx.cpp:937:6: warning: no previous declaration for 'void update(std::vector<neighbours>&, int)' [-Wmissing-declarations]2024-05-20T07:02:31.6311937Z   937 | void update(std::vector<neighbours>& hull, int vertex_id)2024-05-20T07:02:31.6312786Z       |      ^~~~~~2024-05-20T07:02:31.6314499Z /home/ci/opencv/modules/imgproc/src/approx.cpp: In function 'void cv::approxBoundingPoly(cv::InputArray, cv::OutputArray, int, float, bool)':2024-05-20T07:02:31.6316797Z /home/ci/opencv/modules/imgproc/src/approx.cpp:982:68: error: wrong number of template arguments (0, should be 1)2024-05-20T07:02:31.6318495Z   982 |     std::priority_queue<changes, std::vector<changes>, std::greater<>> areas;2024-05-20T07:02:31.6319575Z       |                                                                    ^2024-05-20T07:02:31.6320448Z In file included from /usr/include/c++/9/string:48,2024-05-20T07:02:31.6321542Z                  from /home/ci/opencv/modules/core/include/opencv2/core/cvstd.hpp:56,2024-05-20T07:02:31.6322846Z                  from /home/ci/opencv/modules/core/include/opencv2/core/base.hpp:58,2024-05-20T07:02:31.6324092Z                  from /home/ci/opencv/modules/core/include/opencv2/core.hpp:53,2024-05-20T07:02:31.6325320Z                  from /home/ci/opencv/modules/imgproc/include/opencv2/imgproc.hpp:46,2024-05-20T07:02:31.6326962Z                  from /home/ci/opencv/modules/imgproc/src/precomp.hpp:46,2024-05-20T07:02:31.6328036Z                  from /home/ci/opencv/modules/imgproc/src/approx.cpp:41:2024-05-20T07:02:31.6329752Z /usr/include/c++/9/bits/stl_function.h:371:12: note: provided for 'template<class _Tp> struct std::greater'2024-05-20T07:02:31.6331199Z   371 |     struct greater : public binary_function<_Tp, _Tp, bool>2024-05-20T07:02:31.6332062Z       |            ^~~~~~~2024-05-20T07:02:31.6333159Z /home/ci/opencv/modules/imgproc/src/approx.cpp:982:69: error: template argument 3 is invalid2024-05-20T07:02:31.6334653Z   982 |     std::priority_queue<changes, std::vector<changes>, std::greater<>> areas;2024-05-20T07:02:31.6335715Z       |                                                                     ^~2024-05-20T07:02:31.6337626Z /home/ci/opencv/modules/imgproc/src/approx.cpp:1016:19: error: request for member 'push' in 'areas', which is of non-class type 'int'2024-05-20T07:02:31.6339419Z  1016 |             areas.push(changes(area, vertex_id, Point2f(new_x, new_y)));2024-05-20T07:02:31.6340356Z       |                   ^~~~2024-05-20T07:02:31.6341978Z /home/ci/opencv/modules/imgproc/src/approx.cpp:1022:30: error: request for member 'top' in 'areas', which is of non-class type 'int'2024-05-20T07:02:31.6343539Z  1022 |         changes base = areas.top();2024-05-20T07:02:31.6344259Z       |                              ^~~2024-05-20T07:02:31.6345922Z /home/ci/opencv/modules/imgproc/src/approx.cpp:1027:19: error: request for member 'pop' in 'areas', which is of non-class type 'int'2024-05-20T07:02:31.6347456Z  1027 |             areas.pop();2024-05-20T07:02:31.6348355Z       |                   ^~~2024-05-20T07:02:31.6350005Z /home/ci/opencv/modules/imgproc/src/approx.cpp:1032:19: error: request for member 'pop' in 'areas', which is of non-class type 'int'2024-05-20T07:02:31.6351520Z  1032 |             areas.pop();2024-05-20T07:02:31.6352145Z       |                   ^~~2024-05-20T07:02:31.6353772Z /home/ci/opencv/modules/imgproc/src/approx.cpp:1040:19: error: request for member 'push' in 'areas', which is of non-class type 'int'2024-05-20T07:02:31.6355556Z  1040 |             areas.push(changes(area, vertex_id, Point2f(new_x, new_y)));2024-05-20T07:02:31.6356470Z       |                   ^~~~

Napkin-AI added2 commits

May 20, 2024 19:10

add template and change assert

bafcfd6

type conversion

812623d

Copy link

Contributor

asmorkalov commentedMay 21, 2024

Run cd c:\GHA-OCV-2\_work\opencv\opencv\build && python %CI_SCRIPTS%\warnings-handling.pyC:\GHA-OCV-2\_work\opencv\opencv\opencv\modules\imgproc\src\approx.cpp(989): warning C4244: 'initializing': conversion from 'double' to 'float', possible loss of dataC:\GHA-OCV-2\_work\opencv\opencv\opencv\modules\imgproc\src\approx.cpp(996): warning C4244: 'argument': conversion from '_Tp' to '_Tp', possible loss of dataC:\GHA-OCV-2\_work\opencv\opencv\opencv\modules\imgproc\src\approx.cpp(996): warning C4244: 'argument': conversion from '_Tp' to '_Tp', possible loss of dataC:\GHA-OCV-2\_work\opencv\opencv\opencv\modules\imgproc\src\approx.cpp(1075): warning C4244: 'argument': conversion from 'float' to '_Tp', possible loss of dataC:\GHA-OCV-2\_work\opencv\opencv\opencv\modules\imgproc\src\approx.cpp(1075): warning C4244: 'argument': conversion from 'float' to '_Tp', possible loss of data