I need a maxEnclosingCircle function

edit savecancel

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

#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();
}

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

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.

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