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:
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:
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:
No comments:
Post a Comment