Excel Circle Packing

Excel Circle Packing is a fun VBA application to play around with circles and try to fit them all inside the smallest possible square in Excel. The program helps players fit circles more easily by adjusting their position when near the edge of the square or avoiding overlapping with other circles when possible. Depending on the number of circles selected, packing them inside the square without looking at the solution can be quite challenging. However, if you give up, there are solutions for some of the combinations in this other page.

Circle Packing

Circle packing consists of arranging circles on a surface to maximize area coverage without overlapping. The most efficient way to pack all circles is usually not that obvious. The mathematical problem varies depending on the surface (e.g., a square, other circle, other geometries) and whether the circles are of the same size or not. In this article, we focus on packing circles of the same size into the smallest possible square.

The mathematical problem of packing n circles into the smallest possible square is equivalent to the problem of arranging n points in a unit square to get the largest minimal separation between the points. That minimal separation is designated with d_n and has been calculated by mathematicians. Once the separation is known, the side of the square L can be calculated as L = 2 + 2 / d_n. The values for L and d_n, as well as other parameters for up to 30 circles are saved in a hidden sheet in the file available for download at the bottom of this post. That’s used to calculate the dimensions of the square and circles in Excel Circle Packing.

 

Adding Shapes

We can add a shape to the active sheet as indicated below. That adds an auto shape of the specified type to a location in the worksheet determined by the distance from the top-left corner of the sheet, and with specified dimensions (width and height).

ActiveSheet.Shapes.AddShape ShapeType, Left, Top, Width, Height

 

The ShapeType can be specified with the index or name of the auto shape. As we aim to have a square, the width and height of a rectangular shape are the same. They are denoted with L, which is calculated as explained earlier. The left and top position of the square is determined with x and y (anywhere in the sheet).

 ActiveSheet.Shapes.AddShape 1, x, y, L, L  'msoShapeRectangle

 

Similarly, we can add circles using the same statement. In this case, the type is an oval shape (index 9). You can find the full list of Microsoft auto shapes in this other page: Auto Shape Type Enumeration

 ActiveSheet.Shapes.AddShape 9, x, y, d, d  'msoShapeOval

 

The width and height are also the same in order to make a perfect circle. The variable d corresponds to the diameter of the circle. Circles are filled with random RGB colors and labeled with consecutive numbers. Each circle gets the name “Circle“ along its number so that it can be identified later in other macros.

Timer

A simple timer is used to check the time it takes to pack all circles. The first macro (SetTimer) calls another macro after one second has elapsed.

 Application.OnTime Now + TimeValue("00:00:01"), "MoveTimer"

 

The second macro (MoveTimer) updates the time and closes the loop calling again SetTimer. This is a very basic timer routine that can only update the time in seconds, minutes, or hours, as per the TimeValue function.

The timer is also used to call other macros that check the position of shapes and re-position them when needed. Those other macros also check if the shapes overlap and ultimately confirm if they all fit the square without overlapping. 

 

Fit Shapes

The macro FitShape is used to help players position the circles more easily. It actually repositions the selected shape when near the edge of the square or when overlapping with other shapes. But that only happens if an oval shape is selected, which can be checked with the condition below. If selected, the shape is identified with Selection.ShapeRange and assigned to an object variable.

 
  Dim shp As Shape
  If TypeName(Selection) = "Oval" Then
      Set shp = ActiveSheet.Shapes(Selection.ShapeRange.Name)
      …
  End If
 

The macro then compares the position and dimension properties of the square with those of the selected circle and moves the shape to fit the edge when is less than 5 points aside. The oval shapes are perfect circles so they fit into a square. Therefore, the position of both shapes can be easily compared with the properties Left, Top, Width, and Height.

 

Note that variables storing the position and dimension of shapes are declared as Single to keep decimals. When comparing though, we are rounding the number to reduce uncertainty.

 

Control Overlap

To check if the circles overlap we need to calculate the distance between the centers of each circle (or only those that are inside the square). The distance between two circles is the hypotenuse of a right triangle drawn between the two centers and a third point that forms a 90 degree angle. The hypotenuse is then calculated following Pythagoras theorem.

h² = a² + b²

 

where a is the horizontal difference and b is the vertical difference or sides of the triangle. We can use the Left and Top properties of the oval shapes to calculate the hypotenuse as shown below, since those points form the exact same right triangle.

  hLen = shp1.Left - shp2.Left
  vLen = shp1.Top - shp2.Top
  hypo = Sqr(hLen ^ 2 + vLen ^ 2)
 

If the hypotenuse is lower than twice the circle radius (or the diameter), the circles overlap. The macro then moves the selected circle away to avoid overlapping when possible. The updated horizontal and vertical distance to avoid overlapping can be calculated as a function of the sine and cosine of the angle of the right triangle.

 

  If hypo < shp1.Width Then 'circle overlaps with other circle
      'angle of right triangle between circle centers                   
      If hLen <> 0 Then deg = Atn(vLen / hLen) Else deg = Atn(vLen) 
      new_vLen = shp1.Width * Sin(deg)
      new_hLen = shp1.Width * Cos(deg)
      'adjust position (simplified)
      shp1.Left = shp2.Left + hLen
      shp1.Top = shp2.Top + vLen
  End If
 

 

Confirm Packing

While the first macro (FitShape) only checks the position of the selected shape, the other macro (CheckFit) checks the position of all oval shapes against the square and themselves. This allows to warn when they overlap and confirm if they are all inside the square. The macro uses the calculations explained earlier to check the distance between circles and warns whenever any of them overlap. When that happens, it is helpful to use the keyboard arrows to move the shape slightly if the first macro could not adjust it. Finally, if all circles are within the boundaries of the square and there is no overlap, the circles have successfully been packed and the timer stops.

 

Download the file below to play circle packing in Excel and try your best before checking the solution. Some of the solutions are quite straight forward (e.g., 4, 9, 16), but some are more challenging and not that obvious. If you give up, you can check some of the solutions in this other page.

 

Download Excel Circle Packing