Fitting Spheres into Arbitrary Geometry

[pvanderson]

Hello,

I am constructing a MATLAB script to tightly pack an arbitrary given geometry with spheres of a predefined radius. Coordinates of the vertices of the geometry (a polyhedral model) are given; I am thereby developing an algorithm to plot/track all spheres that fit within the boundaries of the model (defined only by the provided vertex data).

I have successfully tested a script that eliminates all spheres that are "crossing" the model boundary; my difficulty, however, lies within teaching MATLAB how to distinguish spheres that are fully within the boundary from spheres that lie entirely exterior to it. What conditions/techniques could I use to (relatively simply) tell MATLAB not to track a sphere if it lies completely outside of the given vertex/boundary data? I aim to construct a grid of spheres that entirely encompasses the geometry and thereafter have the code systematically eliminate spheres that lie upon or outside of the given vertex/boundary data. Only the spheres lying completely within are plotted/tracked!

I seem to be pulling my hair out over this one. Any assistance would be greatly appreciated!


Paul

 

[jgm340]

If your polytope is convex, then your job isn't too hard. Assume first that the origin lies in the interior of the polytope. Let F₁, ..., F_n be faces of the polytope. Let u₁, ..., u_n be unit normals to the faces, and t₁, ... t_n be the distance of each face from the origin.

Let r be the radius of a sphere about x. Then the sphere of radius r about x is contained in the polytope if and only if:

t_i > (x DOT u_i) + r

for each i.

If your polytope is not convex, then it's more complicated.

I'm not sure what exactly you have to work with in terms of information about the polytope, but it will make everything easier if you have it in terms of face normals/distance from the origin.