# Fitting Spheres into Arbitrary Geometry

• pvanderson
In summary, the conversation discusses using MATLAB to pack spheres within a given geometry by developing an algorithm to plot and track spheres that fit within the boundaries of the model. The difficulty lies in determining which spheres are completely within the boundary and which are outside of it. If the polytope is convex, the task is simpler by using unit normals and distance from the origin. However, if the polytope is not convex, the process becomes more complicated. Having information about the polytope in terms of face normals and distance from the origin can make the task easier.
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

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.

## What is the concept of "Fitting Spheres into Arbitrary Geometry"?

The concept of "Fitting Spheres into Arbitrary Geometry" is a mathematical problem that involves finding the best-fitting sphere that can be inscribed or circumscribed within a given arbitrary shape or geometry.

## What are the applications of "Fitting Spheres into Arbitrary Geometry" in real-world scenarios?

This concept has various applications in fields such as computer graphics, computer-aided design (CAD), and medical imaging. It can also be used in material science to determine the packing efficiency of particles.

## What are the challenges of "Fitting Spheres into Arbitrary Geometry"?

One of the main challenges is determining the exact coordinates of the center of the best-fitting sphere. This involves complex mathematical calculations and can be computationally expensive.

## What are some commonly used algorithms for "Fitting Spheres into Arbitrary Geometry"?

Some commonly used algorithms include the Least Squares Fitting Algorithm, the Iterative Fitting Algorithm, and the Hough Transform Algorithm.

## Are there any limitations to "Fitting Spheres into Arbitrary Geometry"?

Yes, one limitation is that this method only works for convex shapes. It also assumes that the shape is continuous and has a smooth surface, which may not be the case for all real-world objects.

• Differential Geometry
Replies
1
Views
290
• Set Theory, Logic, Probability, Statistics
Replies
7
Views
4K
• Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K
• Sci-Fi Writing and World Building
Replies
52
Views
4K
• MATLAB, Maple, Mathematica, LaTeX
Replies
14
Views
3K
• Quantum Interpretations and Foundations
Replies
12
Views
1K
Replies
7
Views
2K
• Differential Equations
Replies
1
Views
2K
• Special and General Relativity
Replies
40
Views
2K
• Topology and Analysis
Replies
4
Views
2K