Shape Packing Applet

The Applet

Instructions

This applet uses a Simulated Annealing algorithm to simulate a collection of identical shapes inside a larger shape. The code currently supports circles and regular polygons but the user interfaces restricts the latter to those with 3, 4, 5, 6, 7 and 8 sides. There are 4 user interface controls;

Control	Action
"Num Shapes" Slider	This changes the number of small shapes in the simulation. Values range from 2 to 40.
"Temperature" Slider	This changes the temperature of the simulation which controls how freely the shapes move around. If you start of with a too low a temperature you risk freezing the shapes into position before they have chance to find a neet arangement. It is best to start with temperatures that allow the shapes to move around relatively freely and then cool them down when it looks like thry've found a likely arrangement.
"Shape" button	This changes the type of the small shapes. It steps through the sequence Triangle, Circle, Square, Pentagon, Hexagon, Heptagon, Octagon.
"Container" button	This changes the shape of the Container. It steps through the sequence Triangle, Circle, Square, Pentagon, Hexagon, Heptagon, Octagon.

Explanation

The algorithm dates back to my days in chemistry when I used to use Monte Carlo calculations to calculate the thermodynamic properties of collections of atoms and molecules. A big problem when using this method at low temperatures and high densities is that the particles tend to get stuck in non-equilibrium configurations.

In this simulation the object is not so much to calculate the thermodynamic properties of the ensemble but to try and find the best packing of the smaller shapes inside the larger one. To do this we have to define an energy for a configuration in such a way that the minimum energy configuration corresponds to the best packing.

The energy employed here is infinite if two shapes overlap or a shape is not entirely inside the container. Non overlapping shapes inside the container have zero energy. An additional contrubution is made by the size of the shapes, being equal to minus the common radius.

The tendency to freeze in non optimal arrangements is provided by the temperature slider. It is best to run the simulation at moderate temperature so that the shapes get the chcnage to move around. When it looks like they are close to a solution the temperature can be reduced to optimise it.

This method can't guarantee to get the best answer and only give an approximate value of the ratio of the shapes sizes (The size of a shape in this calculation is the radius of its circumcircle). Running the same simulation a number of times can show the range of possible and their rough packing efficiency. The really keen can take the best and calculate the precise efficiency from there.

Moves

At each step of the simulation on of the following possible movement types is chosen;

Move	A shape is moved by a random vector. If the new position overlaps none of the other shapes and is inside the container the move is applied.
Rotate	A shape is rotated through a random angle. If the new position overlaps none of the other shapes and is inside the container the move is applied.
Shrink	The shapes all get smaller and move closer to the centre of the container. There is no posibility of an overlap but this process involves an increase in energy of the system proportional the the change in radius of the shapes. The change is only accepted if exp (-dE/T) > randon [0,1]. (exp is "e to the power of", dE is the change in energy, T is the temperature and random [0,1] is a random number chosen uniformly on the range 0 to 1.)
Grow	The shapes all get bigger and move away from the centre of the container. If all the shapes are still in the container the move is accepted. The energy decreases during this operation.
Slide	The shapes all slide the same distance along a random vector. If all the shapes are still in the container the move is accepted.
Rotate Container	Rotates the container. If all the shapes are still inside the change is accepted.

The Readout

There are three lines of text output at the bottom left of the applet.

Steps	The number of iterations so far, including those where the new configuration has been rejected.
Best	The smallest ratio of the radius of circumcircle of the container to that of the circumcircle of the shape found so far.
Ratio	The current ratio of the radii of the circumcircles.