insphere

Inscribed sphere, entirely inside the facets of a 3-d convex hull

Description

This was written as an extension of my incircle code. It computes the maximal radius inscribed sphere, i.e., the sphere that fits entirely inside the facets of the polyhedron defined by a convex hull in three dimensions. There will generally be four facets that are tangent to the sphere itself.

As an example, here is the in-sphere generated for the convex hull of some random points in the unit cube.

xyz = rand(100,3);
tri = convhulln(xyz);
[Center,R] = insphere(xyz,tri)
 
Center =
      0.50135 0.52118 0.5235

R =
      0.4717

A sphere in the unit 3-cube would have center roughly at [1/2, 1/2, 1/2], and a radius of roughly 1/2, so the result is entirely consistent. Plot the result to generate the screenshot:

[phi,theta] = meshgrid(linspace(0,2*pi,30),linspace(0,pi,20));
xs = R*cos(theta).*sin(phi) + Center(1);
ys = R*sin(theta).*sin(phi) + Center(2);
zs = R*cos(phi) + Center(3);
h = surf(xs,ys,zs);
set(h,'facealpha',.25,'edgecolor','none')
hold on
k = unique(tri(:));
plot3(xyz(k,1),xyz(k,2),xyz(k,3),'o')
E = [tri(:,1:2);tri(:,[1 3]);tri(:,2:3)];
h = patch([xyz(E(:,1),1),xyz(E(:,2),1)]', ...
      [xyz(E(:,1),2),xyz(E(:,2),2)]', ...
      [xyz(E(:,1),3),xyz(E(:,2),3)]','-');
set(h,'edgecolor','r','facecolor','none')
axis equal
xlabel X
ylabel Y
zlabel Z
title 'Convex hull, with polygon in-sphere'
grid on
hold off

The algorithm uses linear programming (much like incircle.m) combined with a set of slack variables, one slack variable for each facet of the convex hull. One additional slack variable can be viewed as the radius of the maximal sphere itself.

Acknowledgements

The author wishes to acknowledge the following in the creation of this submission:
Minimum Radius Bounding Sphere, incircle.m

• Required Products: Optimization Toolbox
• MATLAB release: MATLAB 7.5 (R2007b)
• Other Files: insphere.m, ; license.txt

[Óscar J. Rubio Martín]

Great extension, thank you so much.