# I need a maxEnclosingCircle function

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 close merge delete

Are the contours convex?

( 2012-08-01 05:18:50 -0500 )edit

Sort by » oldest newest most voted

Have a look at this:

class Circle
{
public:

cv::Point2d center;
}

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

more

1

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

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

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

( 2018-08-05 22:53:38 -0500 )edit

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

more

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)

#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


more

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

more

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

( 2018-07-20 09:34:04 -0500 )edit

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.

more

Official site

GitHub

Wiki

Documentation