Ask Your Question
4

I need a maxEnclosingCircle function

asked 2012-07-31 02:58:13 -0500

seiko gravatar image

Maybe somebody thoutght to implement this function? Open CV does not have something like this, just minEnclosingCircle. I need to send an array of points (contour) and return the maximum enclosing circle. Thank you!

edit retag flag offensive close merge delete

Comments

Are the contours convex?

Rui Marques gravatar imageRui Marques ( 2012-08-01 05:18:50 -0500 )edit

5 answers

Sort by ยป oldest newest most voted
7

answered 2012-07-31 03:13:20 -0500

sammy gravatar image

updated 2012-10-07 06:19:51 -0500

Have a look at this:

class Circle
{
public:
     Circle(cv::Point center_, float radius_) : center(center_), radius(radius_){}

     cv::Point2d center;
     double radius;
}

Circle maxEnclosingCircle(const std::vector<Point>& pts)
{
     return Circle(cv::Point(0,0), Inf);
}

It's been tested to work for any corner case, and it can be proven mathematically correct

edit flag offensive delete link more

Comments

1

@sammy: LOL! that's a good one!

Adi gravatar imageAdi ( 2012-07-31 03:39:54 -0500 )edit

How does this work, can it be illustrated by an example? Thank

jsxyhelu gravatar imagejsxyhelu ( 2018-08-05 22:53:38 -0500 )edit
1

answered 2012-10-05 05:35:36 -0500

HugoRune gravatar image

updated 2012-10-06 04:45:08 -0500

I think you can find the maximum enclosed circle using the minEnclosingCircle function and a geometric inversion

First you need to know a point P which you define to be in the circle you seek, for example the centroid of your polygon.
(If you do not have a point which you define to be inside the maximum enclosed circle, then I believe there are arbitrarily many solutions)

  • do an inversion around an arbitrary circle with the center P,
  • then find the minimum enclosing circle for your inverted points
  • then undo the inversion

The inverse of your minimum enclosing circle should now be a maximum enclosed circle for the original points.

This will only find the maximum enclosed circle for the pointset though, not for the polygon, so if your polygon is self-intersecting or has an otherwise complicated shape, this will not give the desired results

edit flag offensive delete link more
0

answered 2013-05-02 07:46:03 -0500

updated 2013-05-02 08:10:56 -0500

Seiko,

unless you posted this question some months ago I still stumbled into the same unanswered question. My answer would be: Why don't you simply

  1. do a distance transform (in python for example using ndimage.distance_transform_edt explained here some way down the page)

  2. take the point with the largest distance as center and

  3. take the corresponding distance as the radius?

The result should be a fastly computed maximum enclosed circle for all types of polygons. Or am I wrong somehow? Greets, Frank

#   +++calculate maximum enclosed circle+++

def maxEnclosedCircle(binent): 
# binent is an array where the shape of interest has a value larger than 0

    #distance transform
    dist = ndimage.distance_transform_edt(binent>0)

    #set radius to largest distance

    radius=np.amax(dist)

    #get index
    flatind=np.argmax(dist)#index of flattened arrays
    ind=np.unravel(flatind,dist.size)#convert to 2D index

    #check if multiple maxima exist and how many
    a=len(dist[dist==radius])

    return ind,radius,a
edit flag offensive delete link more
0

answered 2018-07-20 09:32:45 -0500

updated 2018-07-26 02:01:52 -0500

image description

#include "stdafx.h"
#include <iostream>

using namespace std;
using namespace cv;

VP FindBigestContour(Mat src){    
    int imax = 0; 
    int imaxcontour = -1; 
    std::vector<std::vector<cv::Point>>contours;    
    findContours(src,contours,CV_RETR_LIST,CV_CHAIN_APPROX_SIMPLE);
    for (int i=0;i<contours.size();i++){
        int itmp =  contourArea(contours[i]);
        if (imaxcontour < itmp ){
            imax = i;
            imaxcontour = itmp;
        }
    }
    return contours[imax];
}
int main(int argc, char* argv[])
{
    Mat src = imread("e:/template/cloud.png");
    Mat temp;
    cvtColor(src,temp,COLOR_BGR2GRAY);
    threshold(temp,temp,100,255,THRESH_OTSU);
    imshow("src",temp);
    VP VPResult = FindBigestContour(temp);
    int dist = 0;
    int maxdist = 0;
    Point center;
    for(int i=0;i<src.cols;i++)
    {
        for(int j=0;j<src.rows;j++)
        {
            dist = pointPolygonTest(VPResult,cv::Point(i,j),true);
            if(dist>maxdist)
            {
                maxdist=dist;
                center=cv::Point(i,j);
            }
        }
    }
    circle(src,center,maxdist,Scalar(0,0,255));
    imshow("dst",src);
    waitKey();
}
edit flag offensive delete link more

Comments

i think this is what you want,may the code be help you.

jsxyhelu gravatar imagejsxyhelu ( 2018-07-20 09:34:04 -0500 )edit
0

answered 2012-07-31 07:05:58 -0500

Michael Burdinov gravatar image

updated 2012-08-01 03:24:18 -0500

seiko, I guess you talked about maximum enclosed circle, not maximum enclosing circle (as sammy pointed out that maximum enclosing circle is infinite). Maximum enclosed circle is a compilicate problem, more complicate than minimum enclosing circle. Consider that you have to take edges into acount, and that there might be all kinds of self intersections in polygon. Are you sure this is what you need? Maybe your problem is acctually simpler than that.

edit flag offensive delete link more
Login/Signup to Answer

Question Tools

2 followers

Stats

Asked: 2012-07-31 02:58:13 -0500

Seen: 3,241 times

Last updated: Jul 26 '18