Code covered by the BSD License  

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from
Maximum Inscribed Circle using Voronoi Diagram

Be the first to rate this file! 17 Downloads (last 30 days) File Size: 13.2 KB File ID: #32543 Version: 1.0
image thumbnail

Maximum Inscribed Circle using Voronoi Diagram

by

Tolga Birdal (view profile)

 

A fast, subpixel accurate largest inner circle detection using Voronoi Diagrams

| Watch this File

File Information
Description

A sample application and a function for solving the maximum inscribed circle problem.
Unlike my other submission "Maximum Inscribed Circle using Distance Transform" (at http://www.mathworks.com/matlabcentral/fileexchange/30805-maximum-inscribed-circle-using-distance-transform), this algorithm is subpixel accurate. It operates only on the polygon and not the image points. Therefore, if the polygon is given in sub-pixels, the result will be accurate.
I use an O(n log(n)) algorithm as follows:
- Construct the Voronoi Diagram of the polygon.
- For Voronoi nodes which are inside the polygon:
- Find the node with the maximum distance to edges in P. This node is the centre of the maximum inscribed circle.
 
 For more details on the problem itself please checkout my previous submission as mentioned above.
 
 To speed things up, replace "inpolygon" function by Bruno Lunog's faster implementation "2D polygon interior detection" :
 http://www.mathworks.com/matlabcentral/fileexchange/27840-2d-polygon-interior-detection
 
 Copyright (c) 2011, Tolga Birdal <http://www.tbirdal.me>

Acknowledgements

Fast Points In Polygon Test and Maximum Inscribed Circle Using Distance Transform inspired this file.

Required Products Image Processing Toolbox
MATLAB release MATLAB 7.9 (R2009b)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (2)
02 May 2016 Shanmukha Challa

Hello, thanks for the code
It worked well with an image I'm working .
But when I use other Image it's giving me an error.
It says:

Error using delaunay
At least three input points must be provided to define a triangular mesh.

Error in voronoi (line 84)
tri = delaunay(x,y);

Error in max_circle>find_inner_circle (line 55)
[vx,vy]=voronoi(x,y);

Error in max_circle (line 42)
[cx,cy,r]=find_inner_circle(contour(:,2),contour(:,1));

What do I do?

Comment only
18 Oct 2013 Kai Angermueller

This work very well for many shapes. But for a simple triangle or square it finds circles that are not entirely inside the shape

Comment only

Contact us