Space Filling Dots - Part 2/2

In the last post we looked at a simple, easy to understand algorithm for filling a space with randomly sized circular dots that don't touch each other.

The results were a rather nice:

Although the algorithm was simple and easy to understand, not minor virtues at all, there was a weakness to the algorithm. Basically, the algorithm was a "keep trying until you get a random dot to fit" which meant that it could sometimes take a very long time to complete - and theoretically could never complete.

Let's try a different algorithm and see if we can fix this weakness.

The Big Idea

The cause of the weakness of the previous algorithm was that we were trying dots that located randomly and had random size.  To fix this head on, we need to know where candidate dots will be so we can plan a methodical filling of the empty space.

This sounds counter-intuitive because we don't want a uniform grid of dots, instead we want a random naturally-packed looking arrangement, like the one from our previous algorithm.

Let's use good old pen and paper sketch out a grid anyway, and see if the idea comes to us.

This grid of dots is just there to help us visualise the grid. These light blue dots aren't going to be the dots we want on our final compositions.

This grid is helpful because it actually does cover the area we're interested in, and is a kind of guide to covering the space. Before we were just trying random positions hoping to cover the space in an unguided way.

As before, a good way to develop an algorithm is to try it by hand ourselves. Let's add a randomly sized coloured dot over the very central blue dot and see where that leads us.

That's actually very helpful. Why? Because the size of the pink dot means it covers four of the neighbouring dots, and that means any new coloured dots can't be started on those already covered dots.

Here's an illustration of this idea.

That's a really helpful insight. It means that even though we use the grid of blue dots to guide us in covering the space, we need to check whether our candidate dot overlaps an existing dot. That's a familiar idea from our previous algorithm.

Let's add another dot and see if doing that helps us uncover more insights.

We've added a valid purple dot, and we can see it doesn't overlap the existing pink dot. That's great. But what can we learn from doing this?

Thinking about big that purple dot could have been, we can see there is an upper limit. That is, we can choose the purple dot's size at random but it can't be so big that it touches the pink dot.

That's a really important realisation!

This suggests that for each blue dot, we keep a note of the distance to the nearest other dot. That way, if we choose to place a dot at a grid point, we know the range from which the size should be randomly picked.

Let's illustrate this idea:

Let's try to write out a recipe:

• create list of grid points, representing potential centres of dots - these are actually dots with:
• initial radius 0 - so they're not real dots yet
• covered status set to false
• nearest dot distance set to a large initial value like 500
• for every grid point:
• if the grid point isn't already covered
• place a dot with size chosen randomly with upper limit of the distance to the nearest dot, or the maximum allowed, whichever is smaller
• update all dots with refreshed distances to the nearest dot

That seems like it should work. Unlike our previous algorithm, we don't need to test whether a dot with random size will overlap any  existing dot, because we keep a note of the distance to the nearest dot. Neat!

Let's see the results:

Hmm... that's not good. What happened?

If we think about it for a while, it becomes clear that the very first grid point at (0,0) is free to have a dot with any radius (up to the maximum allowed). This is because there are no existing dots and so it won't overlap any other dot at all. When it's time to look at the next grid point at (0,1) it is limited in the how big the dot can be, because it is very close to the first dot - it may even be covered already. If it is covered, then the next non-covered grid point will be limited in the dot's size because it is close to the first big dot.

If we continue, we can see that every grid point we visit will be seriously cramped by the previous dot's size. In effect, no dot can be bigger than the distance between two grid points.

How do we fix this?

Well, if we look back out our pen and paper example, the order in which we visited each grid point was random, not in strict order (0,0), (0,1), (0,2) .. etc. This could be complicated to achieve - imagine having to keep track of which grid points we have and haven't yet visited .. randomly. Yikes!

Luckily, there's a really elegant solution. After creating the grid points and placing them in a list, we simply shuffle the list. This doesn't affect the dots or grid points, it just affects their sequence. If we then visit each item in the list, we're actually walking about that grid randomly.

There's a really nice algorithm and short code presented on stackoverflow for shuffling lists, called the Durstenfeld shuffle:

• https://stackoverflow.com/a/12646864

Let's see the effect of shuffling the list if grid points before we try to place dots on them:

That works much better! We now have lots of larger dots, and many more smaller dots fitting in between.

The image still looks different from those our previous algorithm makes. All the dots on the above image are strictly aligned to a rectangular grid. That is, the centres of the dots are perfectly aligned with those on the same row or column.

How do we fix this?

Easy! When we create the initial grid points, instead of giving them coordinates like (0,0), (0,1), (0, 2), etc .. we can jiggle them a little bit by adding a random value in the range -0.5 to +0.5.

Let's see what the results look like now.

Much better -  the random jiggling of the grid points results in a much more natural composition.

Can we refine the algorithm further?

In the previous algorithm we enforced a minimum gap between dots. It resulted in a composition that was rather pleasing. Before we commit to setting a radius we just to check that (nearest - gap) is indeed positive .. if not that means there is no space for a dot.

Let's try it here with a gap of 1.0 - quite large.

And now with a smaller gap of 0.2 - much nicer.

Finally lets enforce a circular boundary like we did with the previous algorithm.

Here's the image from a boundary circle with radius 0.4 the size of the grid array side length. There are 60 grid points along each direction.

The nice thing about this algorithm is that we can tweak the granularity of the grid - here's the result of having 120 grid points along each direction.

Much denser - and still rather nice, because of the enforced gap between each dot.

An AlgorithmThat Always Completes

So after all that hard work we have a different algorithm which produces results as nice as our previous algorithm - but with the additional benefit that this one will always complete .. and is even tuneable in terms of granularity.

The code is online:

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

And here's a nice image with a different colour scheme, and a minimum dot radius of 0.2 also asserted, as well as a minimum gap of 0.2:

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.