Radius of the sphere inscribed at the corner of an irregular polyhedron

This is more about Mathematics than Matlab, but I am coding using Matlab. I appreciate any kind of help.

I am looking for the mathematical formula to calculate the radius of a sphere that can be inscribed at the corner of an irregular polyhedron ? There can be several radius, but the sphere should not protrude out of the polyhedron. In 2D it is easy to implement as only two edges are associated with a vertex. The radius is purely based on the corner angle. But I need for 3D where the corner vertex has n number of faces and the angles are not all equal.

Thank you in advance, Sincerely, Sumana

Answer 1

[Image Analyst]

You can make a solid out of your vertex definitions, then you can use bwdist() to get the distance transform. The max of the distance transform is the radius of the largest sphere that will fit into your polyhedron.

[Image Analyst]

For the first question, I believe it will. It's standard morphology and I can't think of any counter examples where it wouldn't work. For the second question, I don't think it matters. It doesn't care. It just gives you the distance to the closest side. Like if you had a 3-D multipointed star (a spiky ball), it would give you the ball that would fit at the center, and it will touch at least 3 sides or vertices. That said, I've just used it in 2-D but I believe all the concepts would also work in 3-D. If you can describe a solid where it wouldn't work, I'd be willing to listen.

[sumana]

Hi, thank you so much for the answer. It would be great if you could elaborate it a little bit (may be an example or a link where some explanation is provided). I apologize for my ignorance. Thank you once again.

[Image Analyst]

What data are you starting with?

[sumana]

I have all the 3D vertices. Thank you.

[Image Analyst]

First research how to get a solid volume from that. I don't do that in 3-D so I'm not sure off the top of my head how you'd do it.

[sumana]

Hi, I used Sven Holcombe's function surf2solid to create a solid like the attached.

[Image Analyst]

Despite the fact that it says "SURF2SOLID(...,'PropertyName',VALUE,...) makes a solid volume from thin surface", I don't think it does. If you take the output of this function, do you get a 3-D array? I doubt it.

[Sven]

Hi Sumana, ImageAnalyst is right - I don't think my surf2solid is applicable here.

Here's an example of what IA is talking about with the distance map. It uses inpolyhedron instead, and will get the best-placed sphere inside a polyhedron (at least within the pxSize tolerance):

% Make faces and vertices
verts = [
    0  0  0
    10 0  0
    11 8  0
    9  12 0
    3  7  0
    6  6  5];
faces = [
    1  3  2
    1  4  3
    1  5  4
    1  2  6
    2  3  6
    3  4  6
    4  5  6
    5  1  6];

% Show the triangulation
figure, hold on
patch('faces',faces,'vertices',verts,'FaceColor','g','FaceAlpha',0.5)
axis image

% Sample a grid through the region of interest
pxSize = 0.1;
xSamps = 0:pxSize:11;
ySamps = 0:pxSize:10;
zSamps = -0.1:pxSize:5;

% Make a distance map from the edges
in = inpolyhedron(faces,verts,xSamps,ySamps,zSamps);
inDist = bwdist(~in);

% The maximum of the distance map gets the position to put a sphere
[maxRadPx,maxInd] = max(inDist(:));
maxRad = pxSize*maxRadPx;
[yInd,xInd,zInd] = ind2sub(size(in),maxInd);
centXYZ = [xSamps(xInd),ySamps(yInd),zSamps(zInd)];

% Build and show the sphere
[X,Y,Z] = sphere(30);
surf(X*maxRad + centXYZ(1),Y*maxRad + centXYZ(2), Z*maxRad + centXYZ(3))

If you need the circle to explicitly never touch the sides, just reduce the maxRad by one pxSize.

I know you're looking for a mathematical formula, but it's not going to be a simple one. This paper describes a potential algorithm but it's not straightforward, which is why IA (and me too) suggest going with the bwdist approach.

[Image Analyst]

bwdist() will work, but first you need to get a 3-D digital volumetric image. But I don't know how to create such a volumetric image from a set of 3-D vertex points. Maybe you could ask tech support.

[sumana]

Thank you Sven, I truely appreciate the help. This is definitely one of the methods to get the radius. Very useful code. Thank you.

[sumana]

Hi Sven,

I was wondering why for the below vertex and faces the sphere is outside of the volume ? v_new =[1.1406 -0.2822 -0.6430; 0.5412 0.4604 0.6889; 0.4970 0.0695 0.7283; 0.3039 -0.6663 0.8086; -0.4781 0.0484 0.7862; 0.0106 0.7567 0.6914]; f_new=[1 2 3; 1 3 4; 1 4 5; 1 5 6; 1 6 2; 3 4 5; 2 3 5; 2 5 6]; like in fig 1.

And for the below vertices and faces the radius is zero so there is no sphere:

v_new=[ -1.2447 -0.2718 -0.2752; -0.3506 -0.9481 -0.1062; -0.4711 -0.1870 -0.9955; -0.7644 0.4948 -0.4761; -0.7186 -0.0521 0.4532]; f_new=[1 2 3; 1 3 4; 1 4 5; 1 5 2; 2 3 4; 2 4 5];

Could you please help ? Thank you