A Voronoi diagram is a visual representation of relative distance between several points on the plane. For a given point on the plane (in most examples and in my examples below the point is coloured black) a colour is assigned, and all surrounding pixels to that point are coloured the assigned shade if they are closer to that point than to another. So, as you get further from a point eventually a given pixel is closer to another point than to the one we were first concerned with, and that pixel is coloured the assigned colour of that other point. So a given pixel is coloured black (usually, but no one can stop you from not doing so if you like) or is coloured the assigned colour of the nearest key point.
So, one can think of the solid colour areas as the area of influence of the point that colour was assigned to that is somewhere within that solid region. That is one way to think about it, see the wikipedia entry linked above for a far better explaination that I have supplied, along with a partial list of applications of these diagrams.
A while ago a friend of mine was talking about ways to tessellate 2 dimensional images for a certain effect he wanted. He was talking to me about this and mentioned he thought interpolating a given image as a Voronoi diagram could give him the effect he wanted if consistent reference points and colour mappings were possible. I wasn’t at the time familiar with these diagrams and read up on them. The first question was if an original image could be discerned from such a diagram, and I offered to throw together a quick proof of concept program (the friend in question is far and away a better programmer than I am, but I have been doing computer imagery for a long time and I also have a formal mathematics education whereas he does not. I still am deeply in his debt for his help in many of my projects).
|Here is an example of what the first images we produced looked like.||
This video describes exactly what mathematicians do and how applied number theory works.
In other words, it’s time for Numberwang!
(Clip from That Mitchell & Webb Look. I did not post the linked clip, so if anyone involved with the show wants the clip removed please contact Youtube directly. Also, one of the greatest comedy sketch shows ever made, so check it out if you get the chance.)
Let’s say I have a function that takes in a real number, adds the negative of one half that real number to itself and returns this new number. Now, take that new number and feed it in to the function. Repeat this as many times as you please and you can see that the output is tending towards zero. Here, zero is an attractor, and zero’s basin of attraction is the entire real number line, not including zero itself (for zero the value is fixed and that’s just boring). An attractor doesn’t have to be a single point, it can be a curve, or a set of a few discrete points, or whatever. A strange attractor is an attractor that is a fractal.
Well, that is at least the cartoon version, as we say.
So, on to that neat result. Let’s say that on the real plane you pick 3 distinct points. Here we will pick them such that they mark the corners of an equilateral triangle, but this is not necessary. Now, place a point at any finite value at all on the real plane. It doesn’t matter where, inside the three points, outside the three points, directly between two points, it doesn’t matter. Now, choose any one of those three points at random (we will call those special points corners). Draw a new point one half of the distance between that first random point and the chosen corner. Now, pick a corner at random, draw a new point half way between that last point and the new chosen corner. Repeat this as many times as you please. We are picking corners at random but a very regular shape starts to emerge.
The shape is this function’s strange attractor, which just happens to be Sierpinski’s Triangle. Sierpinski’s Triangle is classically made by taking an equilateral triangle, finding the midpoint of each side and removing the triangle described from those points from the triangle’s centre. Then do the same with all three new triangles you have. Then with all nine new triangles etc, an infinite number of times. Yet we can approach that same strictly defined shape using a process that is in fact dependent on randomness.
Take a look around and if you’d like, please feel free to contact me here, or use the menu above.