When studying geometries and patterns in natural systems, eventually you will probably stumble across what is known as the Circle Packing Problem. Like many formal arrangements discussed on this blog, my first introduction to this problem was again through Phillip Ball’s series Nature’s Patterns: A Tapestry in Three Parts where he notes the optimal arrangement of similarly sized circles or bubbles is on a hexagonal grid, which is something bees have known for much longer than mathematicians, one of whom Joseph Louis Lagrange ‘proved’ this was the best arrangement in 1773.
.svg)
This is also close to the optimal spacing between plants of a single species, something that farmers, foresters, and orchard keepers have also known for millennia, but described in these images from the Elements of Forestry by Franklin Benjamin Hough in 1882.
Optimizing the spacing between plants is something which starts to get quite complicated when you are dealing with multiple species, and which gets extremely complicated once you start to account for seasonal variation in growth, size, habit, and the positive and negative effects of companion plants on their neighbors, or the fact that opportunistic plants (i.e. weeds) will take advantage of any gaps in the pattern to try and establish themselves where they are not wanted, at least by the gardener, farmer, or designer.
Getting the right spacing initially, then, can reduce long-term maintenance costs associated with removing unwanted plants, so farmers will often plant more than what is strictly required early in the growing season, which may require thinning the planting at some point, but this initial higher investment in planting, and costs associated with thinning the planting later, still outweigh the negative effects of allowing opportunistic weeds to establish themselves and potentially choke out all of the desirable plants.
This is a somewhat long preamble to the circle packing algorithms which I am going to discuss here, but the point I want to convey is that this seemingly abstract mathematical problem *could* have potential application to landscape design, forming part of a computer generated planting design, for example.
There is no single best algorithm to deal with circle packing, partly because there are different kinds of circle packing problems to begin with. We already know a hexagonal pattern is best for circles of uniform dimension tessellating a uniform 2D plane, but what about circles of two different sizes? Three different sizes? Variable sizes within a range? packing within an irregular boundary, etc. etc.
The exploration below is part of a small series of experiments I did to find an easy and quick way to pack circles in an area without too much advanced computation, physics, or studies of complex topologies (relationships) between circles and their neighbors.
For all of these experiments, I will be populating a 30×40 unit area using the Pop2D component, with a random seed of 50. This isn’t that important unless you want to try and replicate my results exactly. The initial script development shows a random population of 100 points, but each method is tested as well with 500 and 1000 points to test the efficiency of the method.
Part 1 – Circle Packing with Closest Point
After setting up the initial point population with the Pop2D component, the population of points in a grafted points container are compared with the same set of points in a flattened points container using the Closest Points component, with the Number of closest points to find set at ‘2’. The ‘D’ output gives us the distance to the closest point in the set at Index 1, with Index 0 being the distance of each point to itself, which is always zero. So to get the proper distance, we simply use a List Item component to list item index 1.
Once this is done, we are going to draw a circle using the Circle component at each point in the population. The circle’s Radius will be determined by the lesser of either:
a) half the distance to the closest point, i.e. our List Item result Divided by 2., or
b) the distance between the point itself and the boundary of our population. This is found by using the Curve Closest Point component.
To find the lesser of a) and b) above, we use the Minimum component. The Result of this is fed into the circle radius. That’s it!
When testing this algorithm’s efficiency, we find a relatively low coverage of around 50%, significantly below the 90% efficiency of uniform circle packing in a hexagonal structure. More specifically, we have 47.4% coverage in the 100 point test, increasing to 52.7 in the 500 point test, and finally to 53.2% with 1000 points. The main cause for the increased efficiency with more points is because of the low coverage offered by the circles very close to the initial boundary edge, and this effect is magnified with a relatively low initial population. To reduce this phenomenon, we could offset the initial curve a small amount before using Pop2D, but we still won’t significantly increase coverage above an amount in the low 50s.
Part 2 – Circle Packing with Iterative Growth of Circle Radius
The proximity to the edge curve, however, is not the only thing limiting coverage efficiency. You will notice upon inspecting the results of our first attempt, especially at the 100 circle resolution, that most of the circles cannot get larger without overlapping their neighbors, but many of the circles indeed can get larger. Some of the potential candidates are shown with sketched in black arrows below.
This led to my second attempt at a circle packing algorithm. The idea was to iteratively ‘grow’ the circles from the initial points, increasing the radius by a very small amount each time until the circle touches its neighbor, at which point the circle stops increasing its radius. I developed an algorithm with the fundamental logic of the Growing Lines Example 10.3 to test just that. I will not show the results here but more advanced users can try replicating my process.
Needless to say, however, the results were not that much better with an efficiency of 53.2 at 100 points, 58.7 at 500 points, and 60.3 at 1000 points. The increased efficiency with more points is again a factor of the points too close to the edges not developing large enough circles, but this problem begins to disappear at higher densities but efficiency is still limited. It is definitely an improvement in efficiency over the first approach, but it also takes a bit of time to run the script, at least in Grasshopper.
Part 3 – Circle Packing with Voronoi Diagram – Cell Center + Curve Closest Point
The inspiration for the third approach that I tried came about after imposing a Voronoi diagram on my initial point population, which is where I will start this particular example.
You’ll remember that the Voronoi diagram represents a series of line segments which are drawn to be equidistant from the two closest points in a collection of points. You’ll notice that our circles from the first algorithm touch the line segments of the Voronoi diagram at precisely one point, specifically at the edge that is closest to the initial point center. If we aren’t being too strict about where our circle centers are, however, we could shift our circles within the Voronoi cells to allow them more room to grow!
So here, instead of using the initial random population as our centers, we use these to draw a Voronoi diagram. We then use the Area component to find the center of each Voronoi cell, and in a similar process to algorithm 1, we use the Curve Closest Point component to find the minimum distance from this new center to the cell’s edge.
Once this is done, we draw our circles with this distance as our circle radius. No need to check the boundary edge distance, since this was fed into our initial Voronoi diagram.
With this new but simple strategy, we now have a coverage efficiency at a rather consistent 62%, specifically 62.5% at 100, 62.4% at 500, 62.6 at 1000. The small variations don’t represent a consistent trend as the point density increases, and since the problem with the boundary circles doesn’t pop up with this approach, we can be fairly confident we will get similar results regardless of density. This approach is slightly better than the iterative growth of circles from the previous example, and is quite a bit simpler both logically and in terms of computational resources. The downside is that if the center points of our circles is something important to us, this approach is probably not the best. Otherwise, it yields pretty good results! Could they be better though?
Part 4 – Circle Packing with Voronoi Diagram – Circle through 3 Closest Edge Points to Cell Center
This final approach attempts to improve the process a bit by maximizing the number of circle tangents while still relying on the underlying logic of the Voronoi system. When looking at the results of the previous test, you may see a few points where the circle could take up more space in its Voronoi cell without going out. I’ve identified a few of these in an image showing the results of the previous algorithm overlaid with the initial Voronoi diagram, with two short lines showing where tangents could be established to increase circle size.
The solution I came up with is not perfect (more on this later) but is good enough for now. Starting as in the previous example, once we draw our initial Voronoi diagram and find the centers of the cells with Area, we use the Explode component to break down our cell edges into individual segments. In this particular case, there were between 4-10 segments in each cell. I then found the closest point on each of the edges to the center using Curve Closest Point.
After this, we will have a number of closest points based on the number of segments in the initial cell. We sort our list of closest points associated with each cell based on the list of distances from smallest to larges, using the Sort component with K (the sorting key) governed by our distance list, and A (the list to sort) being our points. We then use List Item to produce our three closest points. We could have three iterations of the List Item component, but an easier way is to zoom into the outputs and add outputs for the starting index (i) +1 and i+2.
Once this is done, I now have three points with which to draw my circles instead of using the cell center. I do this with the Circle 3Pt component.
When analyzing the efficiency of this approach, we get results about 10% better than with the previous approach, rather consistently at 71% (71.1 for 100 points, 71.2 for 500 points, 71.1 for 1000 points). This is 20% more efficient than our first algorithm.
There are a few problems, however, you can see that in a few cases, the circle will slightly escape its overlapping with our edge boundary, or with a neighbor ever so slightly. I don’t think for most applications this is a huge problem, but a different approach to selecting our three points for the circle which excludes circles overlapping the cell edges could help, but this would be quite complex to code. If anyone has any simple solutions, let me know, but otherwise, I think this is a good starting point for efficiently populating an area with circles of varying sizes!
