Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fitting Spheres into Arbitrary Geometry

  1. Sep 20, 2010 #1

    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!

  2. jcsd
  3. Sep 26, 2010 #2
    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 F1, ..., Fn be faces of the polytope. Let u1, ..., un be unit normals to the faces, and t1, ... tn 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:

    ti > (x DOT ui) + 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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Fitting Spheres into Arbitrary Geometry
  1. Best Fit (Replies: 1)