| Description |
Computation of the in-circle of a convex polygon in two dimensions is done neatly here as an application of linear programming. (LINPROG from the optimization toolbox.) The INCIRCLE code formulates the problem as an LP with slack variables, one each for the distance from the center of the circle to each edge of the convex hull, then one final slack variable to maximize the overall smallest distance among of all of those distances. This mini-max problem generates the in-circle. (A similar scheme could be used to generate an in-sphere in higher dimensions.)
Given a general set of points in no special order, INCIRCLE will compute the convex hull for you, then compute the in-circle for the hull. If the hull is already generated, or if you simply have a known convex polygon, then INCIRCLE can use the data in any form provided.
In this example as the sample size approaches infinity, an asymptotic estimate of the center would lie at [0.5 0.5], with a radius approaching 0.5.
[C,R] = incircle(rand(1000,1),rand(1000,1))
C =
0.50191 0.49999
R =
0.49788
Next is an example with normally distributed points. The center is expected to lie roughly at [1,-2.5]. An a-priori estimate of the radius would be on the order of 2 or 3. (Think of the expected radius of a 99% confidence ellipse for a bivariate normal distribution.) I'll compute the convex hull in advance in this example so that I can plot it too.
x = randn(100,1) + 1;
y = randn(100,1) - 2.5;
H = convhull(x,y);
[C,R] = incircle([x,y],H)
C =
1.0212 -2.3458
R =
2.1329
Plot the in-circle along with the hull. (Shown as the screenshot for this submission.) As one would expect, the in-circle will be tangent to at least three of the edges of the enclosing polygon.
t = linspace(0,2*pi,200);
xc = R*cos(t) + C(1);
yc = R*sin(t) + C(2);
plot(x(H),y(H),'-r',x,y,'ko')
patch(xc,yc,'g','edgecolor','b','facealpha',0.25)
axis equal
xlabel X
ylabel Y
title 'Convex hull, with polygon in-circle'
grid on |
