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. |
However, and I do not at all claim originality in this, I wondered how the same image might look in a different metric. I had only skimmed the first few paragraphs of the wikipedia article I linked above and did not know that an example in Manhattan distance was included when I first produced the initial code. Using different metrics to reexamine the same data in different ways was already a well worn analytic tool for me, so included the ability to output the same points but with different metrics, Manhattan distance in particular, was included matter of fact. |
If you skipped the wikipedia entry, Euclidean distance is a measure between to points using the shortest line possible. Manhattan distance is the distance between to points where movement is only possible parallel to one axis but also only perpendicular to all other axes. To get to a point not colinear in the way described from the initial point being tested, one has to make right angle turns. So, it’s like taking a cab in Manhattan. The City is pretty well a grid, so a cab has to make a few right angle turns to get where you want to go. As you can see, the maps are similar, but they are not the same. We test all the same points but a given non-key point can be considered closer to a different point depending on how we measure distance. Further, the boundaries of a key points influence are markedly different in their behaviour between these two metrics.
It’s fair to say that although the images do look neat, it’s hard to say that the aesthetic effect we were after is possible. For interest’s sake the source images are below: