For some, it would be a dream come true: for almost a whole week, you get to work on any project you like. You pick the tech, you choose the APIs, you define the requirements. Build whatever you want.
I think of all the things I had to tackle in my move to Commit—and there were a few—the onboarding project was the one that loomed largest in my mind. I had no idea what I wanted to do. No idea. And I had to come up with one. Quickly.
I read the proposals and watched the demos of previous onboarding projects looking for inspiration. None came. I delved into my own career history trying to come up with variations on earlier work projects. Nothing. I tried to imagine tools or apps I would find helpful in my day-to-day life. Nada.
At the very least, I could make myself useful while I waited for inspiration to strike. There had been a posting on Slack stating people interested in React and Next.js could help update the marketing site. Perhaps something in the project backlog might trigger an aha moment.
One ticket addressed the implementation of a new section that discussed Commit’s commitment to open source. Accompanying this text were photos of all the engineers who had dedicated some of their time to this project. At small resolutions, the photos would be arranged in a grid but, if there was enough room at larger resolutions, the photos should be scattered in what I can only describe as a “pleasing” layout. There was no discernable pattern and that was the point. In the mockup, each photo maintained a respectful distance between each other, and between themselves and the text block. The photos wrapped around the text block, gently hugging it.
This layout screamed: “Hard-code me.” But what would happen if another photo were to be added to the set? A space that previously held N photos would have to squeeze in N+1 photos. The existing photos shuffled around to make way for the new one. Any hard-coded solution would have to be completely redone.
There had to be a better way (cue the 90s infomercials). A solution that could accommodate any reasonable number of photos. And any adjustments to the length of the text block. And, indeed, the dimensions for the box that contained both the text and the photos. Something programmatic.
If there was a programmatic solution, it wouldn’t fit into the usual lexicon of code algorithms. It would be more about math than about data structures or tech stacks or APIs. The solution—and finding it—was guaranteed to be interesting.
I had my project.
My first problem
My first problem was to describe what I was looking at. How were the photos arranged? Was there a word or phrase I could use—other than “pleasing” or “pretty”—to describe the arrangement and help me look for solutions that would produce this layout?
What struck me was that nearest neighbours all seemed to be separated by the same distance. They were uniformly spaced, Armed with this, I started looking for algorithms that would generate equally spaced points.
Almost right away, I found exactly what I was looking for. However at the time I dismissed it because of a minor issue. What I found was Poisson disk sampling. Given an empty space and a minimum separation between points, implementations of Poisson disk sampling generate points in that space where no two points are closer than the minimum separation. Which is exactly what I was looking for. Almost. Instead of a set minimum separation and no set number of points, I had a set number of points and no set minimum separation. So I discarded that approach and moved on.
Chasing my tail
I actually spent a couple days going down increasingly ridiculous rabbit holes. I started looking at algorithms that might generate a uniformly spaced point set as a by-product of something else. I thought about physics simulations of point charges held in a charged box—my theory being that the repellant forces would cause the points to seek equilibrium. They did but it was heavily dependent on the arrangement of charges on the containing box. So I removed the charges on the box and added a weak attraction force that worked longer distances to keep the system bound. I was unwittingly going down the n-body route, which doesn’t find a static solution. I tried another solution where I started with a random arrangement of points and slightly increased the shortest separations and slightly decreased the longest separations. This would eventually trend towards a solution. After a million-plus iterations. I was getting nowhere.
I realized that I should be looking for a solution that solves the uniform separation problem as its primary concern as opposed to coming to a solution as a by-product of doing something else. So I returned to Poisson disk sampling. I realized that I could iterate towards a solution by starting with a particular minimum separation, generating a solution point set, and then adjusting the separation distance up or down depending on whether I had generated too many or too few points. I could iterate until the number of points equalled the number of photos.
The covering space for the points would be the dimensions of the HTML element. To prevent photos from overlapping the text block, I added the concept of zones of exclusion—square boxes inside the covering space that points couldn’t occupy. The zone of exclusion would be a box around the text that also included padding to prevent the photos from being placed too close to it.
I found a fast O(n) implementation of Poisson disk sampling (specifically, Roberts’ improvement on Bridson’s Algorithm). The original code’s use of four maximum samples before rejection is fine when there is a large open space to fill, but it imperfectly fills smaller spaces (i.e., where the minimum separation to covering space ratio is higher) with lots of boundaries created by zones of exclusion, so I increased it to eight samples. I also made the position of the first sample point random to provide more variety in the solutions. With judicious selection of a starting minimum separation and adjustment amount per iteration, I found that I could generate a good solution (the number of points generated equaled the number of photos I had) in five to eight iterations. If the final separation was less than a particular amount (about 0.7 times the diagonal of the photo image elements), the photos would seem too crowded, so I would default to a grid arrangement.
Once I had a solution I was happy with, I packaged the core code up as a node module (the first I had ever made).
Bringing it together
Finally, I integrated the solution into the site (learning some React along the way). The HTML consists of a container element with a child that holds the text and a list that contains all the photo elements. By default, the list of photos is arranged in a grid pattern using flexbox. But above a particular viewport width, the pretty scatter algorithm takes over. The parent element of the photo list becomes the covering space and any additional children of this element (i.e., the text container) become zones of exclusion with the dimensions of the zone set by the element’s margin box. The photos are positioned absolutely with respect to the covering space element and are centred on the points derived by the Poisson disk sampling.
The node module is still a bit rough. Documentation is, well, non-existent. There are a few magic numbers used in the calculations (the starting minimum separation and the smallest acceptable minimum separations) that should be completely derivable from inputs to the system.
Overall, I am extremely happy that my hackathon project found me. I enjoyed the difficulty of the problem and its variety. It was difficult enough to be a challenge but not so difficult that I was stuck and felt I wasn’t making progress. And the variety meant that there were different pieces (React coding, CSS layout, Node module packaging, and the algorithm) I could work on when I did get frustrated on one aspect.
We hire Software Engineers to build their careers with promising early-stage startups. Join the waitlist today!
Chris Nott has worked in the internet industry as a frontend Engineer since its beginning in the mid-1990s. He is passionate about stretching the bounds of technology to solve interesting and complex problems. Away from the computer, Chris enjoys immersive experiences involving wilderness and cultures.