In Spring 2013, I designed and implemented the user-interface for Agrisaurus, a web app that aimed to make gardening simple and data-driven. During my time there, I was asked to improve the plant-placement algorithm that we used to circle-pack plants into rectangular garden beds.
The Problem: The original Agrisaurus plant placement algorithm generated planting-maps with small crops, like carrots and onions, spread throughout the garden to fill in gaps where other crops didn’t fit. This was space-efficient, but confusing for users who expected to find all the plants of a given crop in the same general region.
The Goal: Traditionally, gardeners solved this problem by marking off a rectangular region of their garden and labeling it “onions” but our premise at Agrisaurus was that we could arrange crops more efficiently by intelligently circle-packing them. Thus, we needed a solution that would cluster small crops of the same type into tightly packed groups without disrupting our ability to efficiently pack other, larger plants, like tomatoes and kale, according to their height and radius.
To start, I read our documentation on the plant placement algorithm and did a little bit of research on circle-packing. I learned that, in unbounded space, it is most space-efficient to pack circles of equal diameter in a hexagonal arrangement. If you go to Home Depot or pass by a shipping yard, you’re likely to see bundles of pipes packed like this.
I figured this was our best bet since the space between existing plants in the garden would be arbitrarily shaped. However, I still had to figure out how to integrate it with our standard placement algorithm, which was designed to pack circles of differing diameter while also accounting for the shadow cast by each plant.
My first solution was to use the standard placement algorithm to place a single plant of the given crop. Then, by testing collisions at the appropriate locations around the first plant, I could place additional plants of that crop in a hexagonal grid until all plants were placed or all space in the region was exhausted. This solution hexagonally packed crops around existing crops in any shape necessary but was difficult for a user to manually alter since it arranged the crops in such strange shapes.
I proposed that it would be more convenient for users if we grouped the plants into 7-plant hexagonal groups that the user could move around as a single unit. My project manager agreed, so I devised a second solution wherein we used the standard placement algorithm to find space for an imaginary plant with 3x the small crop’s diameter. By adjusting the returned location for the overestimation of this circle, I was able to perfectly nestle the hexagonal groups into the crevices between existing plants. I then wrote a routine that would attempt to place subsequent hexagonal groups at any of the six “latching points” around the first hexagonal group.
And voila! Crop clusters that are space-efficient, user friendly, and aesthetically pleasing!