a question from《learning opencv3》 chapter 14

asked 2018-07-25 01:44:05 -0500

Hi,i have some problem when soloving a question from《learning opencv3》 chapter 14

the question is

  1. We can find the extremal points (i.e., the two points that are farthest apart) in a closed contour of N points by comparing the distance of each point to every other point.

    a. What is the complexity of such an algorithm?

    b. Explain how you can do this faster.

I think ,the answer of a is O(N*N) (am i right),but to b,the only idea i can think out is

Finding the convex hull of the contour, do the algorithm above at the convex hull .

ami i right?or better solution?



edit retag flag offensive close merge delete


I would look for extremal points by only comparing to the direct neighbourhood of the contour, lets say 50 points to left and 50 to right. To me it makes no sence if you have a large object, to compare the distance between a possible extremal point and the other side of the object, far away from the actual points. A convex hull would work, but in principle it will not reduce the amount of points that much.

StevenPuttemans gravatar imageStevenPuttemans ( 2018-07-25 03:50:46 -0500 )edit

but the " the two points that are farthest apart" must not be direct neighbourhood. sorry i did not get your idea.

jsxyhelu gravatar imagejsxyhelu ( 2018-07-25 06:11:53 -0500 )edit

ow sorry, did not read with attention. Extremal points are for me points that deviate from a general outline or trajectory, but it seems here, that they want the actual 2 points that are the farthest away from eachother. No idea how to speed that up xD

StevenPuttemans gravatar imageStevenPuttemans ( 2018-07-25 06:43:13 -0500 )edit

use boundingRect?

LBerger gravatar imageLBerger ( 2018-07-25 06:45:01 -0500 )edit

boundingRect sounds good,but boundingRect is a function of RotatedRect and we use minAreaRect to get it.

 RotatedRect minRect = minAreaRect( Mat(contours[i]) );
 Point2f rect_points[4];
 minRect.points( rect_points );

Finally minAreaRect is basd on hull

cv::RotatedRect cv::minAreaRect( InputArray _points )

    Mat hull;
    Point2f out[3];
    RotatedRect box;

    convexHull(_points, hull, true, true);

    if( hull.depth() != CV_32F )
        Mat temp;
        hull.convertTo(temp, CV_32F);
        hull = temp;
jsxyhelu gravatar imagejsxyhelu ( 2018-07-25 08:17:09 -0500 )edit