Space Filling Dots - Part 1/2

Have a look at the following image.

It's a rather nice image. Looking closer, what do we notice?

• The first thing we notice is the image is made of lots of nicely coloured circles - spots. 
• The next thing we notice is that, despite looking randomly placed, they all somehow fall within the boundaries of an imaginary larger circle.
• Looking even closer, it becomes apparent that none of the spots overlap, or even touch each other.

Overall the image is a rather pleasant composition, and gently tickles the viewer's curiosity that the apparently random spots are extremely carefully placed.

Algorithmic Challenge

The idea of filling a space with shapes so that no shapes touches any other is an interesting visual idea as well as an interesting algorithmic challenge.

In fact it's a rather difficult challenge to fill a given space with randomly sized and randomly located shapes that don't touch each other.

Over two posts we'll look at how we can do this. In this post we'll develop a simpler, easier to understand, algorithm that is good-enough, even if it has a bit of a weakness. In the next post we'll look at a slightly more complicated algorithm that doesn't have the same weakness.

Let's dive in!

How Would We Do It By Hand?

A useful technique for working out a challenging algorithm is to imagine how we might do it by hand, with a pencil and paper.

Let's try it.

First we take a piece of paper. What do we do next? Before we can draw any coloured spots we need to know about the big circle they must all stay inside. So let's draw that with a light coloured pencil - a light blue pencil is a good choice.

What next? Do we need a plan before we draw any spot? Probably. But it's not so easy to think of one. So instead, let's just draw a spot and see where that takes us.

Let's choose a random location, and a random size for the spot we're going to draw, and see what it looks like.

As nice as that pink circle is, we can see something's not right. That pink spot is outside the blue circle which acts like a fence or boundary. Any spot we draw must be inside the blue circle.

Let's try again. Let's pick a random location and only draw the spot if the centre of the circle is inside the boundary circle.

That looks better but still something is wrong. The centre of the spot is inside the boundary circle but part of the spot is outside the boundary. So we need to be more strict, and only draw a spot if all of it, not just its centre, is inside the boundary.

Let's try again.

That works!

Now we want to add more spots. Let try adding another spot, chosen with a random location and size, but like before being entirely within the boundary.

Arghh! Something's not right again. Sure, the new spot is entirely inside the blue boundary circle, but it overlaps the spot that's already there.

This means we need a new rule - a new spot must not overlap any existing spot, as well as being entirely within the boundary circle.

If we used this even stricter rule, and continued to add a few circles, we might end up with something like this:

That looks like we're getting there but this isn't quite like the very nice image at the every top. Can you spot the difference?

The difference is that the nice image leaves a small gap between all the spots, but this last image has some spots touching each other. They don't overlap, because of the rule, but they do touch each other.

So let's refine the rule:

• Any new spot must be entirely within the large boundary circle, and ..
• It must not be closer to any other spot than a given gap distance.

If we followed these updated rules, we'd have something like this:

That has a very nice aesthetic! It looks like we have an algorithm sorted out.

Well almost. If we really did choose random sizes for the spots, you can imagine we'd be trying quite a few medium to large spots and failing them because they just didn't fit in the ever reducing empty space. A refinement to the algorithm is to start with a medium size for the spots, say 30 pixels, and reduce the size a little bit for every subsequent spot. That way, as we progress, the spots get smaller and smaller. The chance of these smaller spots being drawn is better than larger spots when the empty space starts filling up. We could, for example multiply the radius by 0.999 after every attempt to draw a spot. Because 0.999 is close to 1, the spots don't get small too rapidly, and we should get a decent mix of spot sizes.

Getting Ready To Code

It's great that we've worked out the algorithm using pen and paper, but we can't turn it into code straight away.

Computer code needs to be precise, unambiguous, and detailed enough to match the small instructions provided by the programming language. We can't just say "do it" or "fill that circular space with dots that don't touch each other".

Let's try to break down our algorithm into smaller steps:

• pick a random spot location
• pick a spot size that's a bit smaller than the previous one
• only draw the spot if it:
• is entirely inside the boundary circle, and
• isn't too close to another spot

That's a good start but still isn't specific enough for code. Let's try again, making each statement even more precise:

• pick a random location inside the boundary circle by:
• choosing a random distance between 0 and the radius of the boundary circle - this is the distance from the centre of the boundary circle
• a random angle around the centre of the boundary circle centre - that's a number between 0 and 360 degrees
• multiply the previous spot radius by 0.999 to get the new radius
• only draw the spot if:
• this distance of the spot plus the radius of the spot are less than the radius of the boundary circle
• the distance between the spot centre and any other spot centre is larger than the sum of the their radii plus a 2 pixel gap

These two last points might not make sense on first reading. Let's talk about them a little more.

Have a look at this picture:

This picture helps explain the condition for a spot to be entirely inside the boundary circle. The distance of the spot centre from the centre of the boundary circle (shown orange) needs to be smaller than the radius of the boundary circle (shown green). That places the centre of the spot inside the boundary, which is great! But it isn't enough to ensure the that the whole spot is inside the boundary. To do that we need to extend that orange distance by the radius of the spot (shown red). The picture makes this clear - if the orange + red distance is less than the green distance, then the spot is entirely inside the boundary.

The next point needs another picture to explain:

The picture makes clear that for two spots not to be overlapping or touching the distance between their centres must be more than sum of their radii. If we want to maintain a minimum gap of 2 pixels between the spots, we can say that the distance between the two spots must be greater than the sum of the radii plus 2 pixels.

Let's look at the same idea a different way. The following picture shows the closest that two dots can be. We can see the 2 pixel gap. We can also see that how the distance between the two dot centres is the sum of the two radii and the gap.

Phew! That needed a bit of work but it's worth the effort. We now have a precise and unambiguous way of deciding if a random spot is inside the boundary or not.

Here's the idea turned into code you can explore:

• https://www.openprocessing.org/sketch/535557

And here's an example of what the code creates:

There's a nice balance of spot sizes, and the colour palette is nice too.

A Guided Tour of the Code

Let's talk through the p5js code, a guided tour as it were.

We start by creating an empty list which will store all the valid circles, the dots that pass the criteria we talked about above. That list is called list_of_circles. We also set useful things like the total number of dots that we want, total_circles = 800, and the radius of the invisible boundary circle, outer_circle_r = 250.

We then enter a loop, repeating 800 times, once for every dot we want to draw. But before we do start the loop we set the dot radius to be 30 pixels. It'll get smaller as the loop progresses.

Inside the loop we pick a random dot - by randomly picking its distance from the centre of the boundary circle, and it's angle around that that centre. We could have used (x, y) coordinates but the alternative (distance, angle) polar coordinates are slightly more convenient. The distance could be anything between 0 and the radius of the boundary circle. The angle could be anything between 0 and 360 degrees.

Once we have a candidate dot we first test that it is inside the boundary circle. If it outside the main circle we make a note by setting a variable success = false. That variable success is set to true before a random dot is picked.

If that test passed, we proceed to check that the candidate dot doesn't get too close to any previous dot. How do we do that? Although we haven't done it yet, successfully placed dots will all be placed in the list list_of_circles, so we simply work through every one of these and check that the candidate dot isn't too close. The code that works through the list is for (c of list_of_circles) {}. It's a bit like a for loop but is simpler - it just repeats the code inside {} for every item in the list. If the candidate circle is too close to an existing dot, we set the variable success = false, and break out of the loop because we don't need to check any more dots.

If at this point success = false, it means that the candidate circle was either outside the boundary circle, or is too close to another dot. So this candidate dot is no good. We need to go back and pick another random candidate dot. This whole idea of "keep repeating until you get it right" matches the code do {...} while (success == false).

If success was left as true, that means the candidate dot fits nicely in the space. So we add it to the end of the list list_of_circles. That means later candidate dot are tested against this one too.

But what exactly are we adding to the list? The code says list_of_circles.push(new Circle(d*cos(a), d*sin(a), r)). What we're pushing to the end of the list is a new object created with the location and radius of the candidate dot. That cos() and sin() simply converts the polar coordinates to (x,y) coordinates. That object is just data representing a dot, with it's location, size and also colour. On creating a new dot object, a random colour is chosen from a specified hue range. That's why all the dots are similarly coloured.

Finally, after 800 dots have been added, we use another loop to draw them all. The dot object has one method and that's to draw a circle using it's own data (location, size, colour).

Here's an image that results from using a broader colour range.

A Weakness

The algorithm we have developed is fairly simple and easy to understand - we simply try random circles, discarding the ones that don't fit, until we have enough circles drawn.

Simplicity and understandability are great virtues for an algorithm.

But there is a weakness. Because the candidate dots are chosen at random, it is possible that many many keep failing the tests to see if they fit nicely. This is inefficient. It is possible that he algorithm finishes quickly - or takes a very very long time. The more dots we place, the less space there is left, and the more likely that candidate dots fail to fit. Theoretically, it is possible that the algorithm never completes.

Next time we'll try a different approach that is not quite as simple as this one, but does avoid this weakness.