# Maximum Inscribed Circle using Distance Transform (Scripts) 1.0

Average Rating
User Rating:
Visitors Rating:
My rating:

See full specifications

## Maximum Inscribed Circle using Distance Transform (Scripts) Publisher's description

### Or in other words, "largest inner circle" , "maximum empty circle" etc.

Maximum Inscribed Circle

Or in other words, "largest inner circle" , "maximum empty circle" etc.

This is a very common problem in computational geometry, and it is not simple to solve efficiently.

Addressing 2D image/contour processing, I couldn't find a good implementation on the web. Generally, the reasonable way of solving this problem is to make use of Voronoi Diagrams, which are generally O(nlogn).

After analyzing the problem a bit, I noticed that the problem can easily and approximately be solved using well-known distance transform.

Here is how:

The computational aim can be written as:

(x, y) maximizes r = min_{i} r_{i}
where r_i = ||(x_i, y_i) в?’ (x, y)|| and d_i = r_i в?’ r

(x_i, y_i): Pairs data points
(x, y), r : Pair, scalar circle centre and radius

In non-mathematical terms:

1. The center of the maximum inscribed circle will lie inside the polygon
2. The center of such a circle will be furthest from any point on the edges of the polygon.

So we seek for the point that lies inside the polygon and has maximal distance to the closest edge. This is exactly the maximum value of the pixel (of DT) that lies inside the contour.

Notice that this approach is completely in-precise. It is only pixel-precise and never subpixel accurate. However, unlike optimization approaches, it does guarantee a global convergence. In the case of ambiguity, any of the solutions will be valid.

To detect the points inside the region, inpolygon remains very slow. So, I make use of the great code of Darren Engwirda, here. As well as being contained in this package, it can also be downloaded from:
http://www.mathworks.com/matlabcentral/fileexchange/10391-fast-points-in-polygon-test

Here are other implemnatations, which are more accurate, but much slower than my approach (only slower in Matalb of course!)

http://www.mathworks.com/matlabcentral/fil...e/2794-cvoronoi

Using "Largest pixel that doesn't cross any point" approach:

--------

Here is a sample call:

[R cx cy]=max_inscribed_circle(I)

The max_inscribed_circle function, finds the boundaries of the image, traces them and retrieves a boundary, where neighboring pixels follow each other. It uses the points on the boundary to compute the maximum inscribed circle

Cheers,

#### System Requirements:

MATLAB 7.9 (2009b)
Program Release Status: New Release
Program Install Support: Install and Uninstall

#### Maximum Inscribed Circle using Distance Transform (Scripts) Tags:

Click on a tag to find related softwares

## Most Popular

ASK, OOK, FSK, BPSK, QPSK, 8PSK modulation 1.1
ASK, OOK, FSK, BPSK, QPSK, 8PSK modulation contain several functions for digital modulation simulation
Simulink Communication Labs 1.1
Simulink Communication Labs allows you to learn communication systems in greater depth.
M-QAM modulation and demodulation 1.1
M-QAM modulation and demodulation is the QAM modulation and demodulation tech.
LZW Compression/Decompression 1.1
LZW Compression/Decompression - Updated LZW compressor and decompressor with reasonable performance
InSPIRE utility to plot a 2D displacement field (Scripts) 1.0
This program plots the deformation field (displace vectors) contained in vector.txt.