Maximum Inscribed Circle using Voronoi Diagram

A fast, subpixel accurate largest inner circle detection using Voronoi Diagrams
1.5K Downloads
Updated 15 Aug 2011

View License

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>

Cite As

Tolga Birdal (2024). Maximum Inscribed Circle using Voronoi Diagram (https://www.mathworks.com/matlabcentral/fileexchange/32543-maximum-inscribed-circle-using-voronoi-diagram), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2009b
Compatible with any release
Platform Compatibility
Windows macOS Linux
Categories
Find more on Voronoi Diagram in Help Center and MATLAB Answers

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes
1.0.0.0