September 5, 2011

my Voronoi

I recently learned of something known as a Voronoi tessellation. This is a really intriguing way of dividing a space up into a group of cells. The grid basically consists of a set of constructor points (the black dots in the pictures below) that are in some way distributed into the available space (randomly in this case). Each cell consists of all the points that are closer to a particular constructor than any other constructor. This creates natural divisions in the space that define the "personal space" of each constructor. This pattern represents a certain kind of equilibrium and is one of those things that occurs extensively in nature. In the crowding of cells for example. Understanding it allows those patterns to be uncovered and taken advantage of. I've read that it is used in determining which cell tower a cell phone is closest to (each tower being a constructor and the phone being a regular point in the grid).

In any case, I wanted to write my own algorithm to generate these patterns. I would have liked to have done this in a formal mathematical way. I settled for a more procedural approach. I wound up making two arrays. One to store the constructor points and one to store a random color for each constructor. I then iterate through every point in the grid. For each point I check its distance to every constructor and save the index of the nearest one. I then use that index to get a color and set the current pixel to that color.  This approach could be improved as it has some obvious inefficiencies. It's also not nearly as cool as defining the regions mathematically would be but it dose effectively display Voronoi tessellations for the given constructor points.

Here are some examples of the output:

 Read more to see more examples.

No comments:

Post a Comment