Voronoi Diagram How to Draw

As has been written here before, Voronoi diagrams, as a geometric model are fascinating considering they can be used to draw almost literally everything: from prison cell telephone networks to radiolaria, at every calibration: from quantum foam to cosmic cream. Even the regular lattices and solids, cubes, tetrahedra, and the ways in which they combine, can all be seen equally special cases of three dimensional Voronoi. It's hard not to get mystical about it, simply information technology's really but the contemporary equivalent of the countless ideal gridded space of modernism or the renaissance, just more exotic and malleable. Geometry is Civilization.

Cartoon Voronoi diagrams by paw has renewed my interest in the stuff. There are lots of scripts out there for making instant vector crystal foam in only near any modeling or CAD platform, but it'south more interesting for me correct at present to ho-hum information technology down, take it step past step, and actually try to understand the geometries involved. More a heuristic than an algorithm, executing it demands and reinforces the kind of zoned out shut attention that almost becomes the whole point of drawing in the first place. The artifact that yous go at the stop information technology is just an unexpected bonus: the physical tape left by the process of thinking out loud on paper. Beneath is a crude pseudocode (thank you, mike!) for building it up from a fix of points.

(one) Input Sites (2) Connect Nearest Neighbors (shortest line wins) (3) Find Center Points
(iv) Draw Perpendicular Bisectors (five) Trace Cells (half dozen) voila

(1) The input points, step one, are called sites, labeled here A, B, C, etc.

(2) The next pace is to connect the sites to all of their nearest neighbors without making a line that crosses another. This is known technically equally the Delauney Triangulation, and it'south maybe the most difficult part. 1 fashion to exercise it might be by beast strength - connect every site to every other site, brand a true all-to-all rhizomatic meshwork, and and then start deleting lines that are too long. This is how a machine might attack the trouble, but it becomes too hard for a human to execute when the number of sites jumps into the double digits. Another algorithmic method is to offset with a test triangle of sites and draw their circumcircle, the circle that hits all three sites, rejecting the triangle if the circle contains another site within information technology.

Image via wikipedia

This also takes too long, and circumcircles are hard to describe, and then I found a method that's faster, and still mostly accurate. Since no lines on the Delauney triangulation tin can cantankerous, just eyeball information technology until you encounter a status as in the above, where y'all have to make up one's mind if FD or AE is correct, the shorter line e'er wins. This is obvious in the example, but sometimes this needs some careful measuring in the field.

(3) Step three is to find and mark the centerpoint of every line on the Delauney graph.

(4) The fourth step is to describe the perpendicular bisector for each Delauney line. This is where conscientious accuracy, in finding the centerpoints, and in drawing a tight xc degree angle, pays off. If everything has been washed correctly, at that place will always exist three lines converging at a point, unless the input sites are on a perfectly regular rectangular grid. Drawing the last line of the three and watching information technology land exactly where it'south supposed to is extremely satisfying. Watching information technology miss can mean going back all the way to step two and flipping the Delauney graph for the triangle. Some mistakes are instructive, reminding you to take your time and think about the moves, but some are more interesting, for being completely inexplicable. A few places in these drawings, I've run into conditions that should piece of work out, merely just don't: evidence of some hidden monster in the procedure, a flaw in the heuristic, or a breakup of the pseudocode.

(v) The fifth step is to retrace the outline of each Voronoi cell from the perpendicular bisectors. There volition be one cell for every site, and at the end, each cell is just the set of all area points that are closer to its site than any of the other sites, as illustrated in the last console: A' -> A, B' -> B, etc.

(half-dozen) Sit dorsum and congratulate yourself while contemplating your hard earned tangle of fat distorted honeycomb.

I've found in practice that information technology'southward best to apply dissimilar colors for the input sites, the Delauney lines, and the bisectors, unless driving yourself completely crosseyed mad is something you have the time and inclination to do. Bluish and scarlet mechanical pencil leads are pretty easy to go. I made this cartoon to exercise, using a pepper grinder above the drafting tabular array to get random input sites:

The wall drawing below was made for the Current Gallery's Abandon Ship evidence. It measures about 3' x 5'. The input sites here were the roughly patched holes and marks left by all the previous exhibits and shows in the space's three twelvemonth existence as a gallery. Before that, the building was a chocolate factory. This piece will be demolished along with the rest of the show when (if) plans motility ahead to build a hotel on the site. I was very glad to become the chance to exercise a wall drawing, having just visited again, for the second time, Sol LeWitt's ephemeral 'Drawing Series—Blended, Part I–IV, #i–24, A+B' at Dia Buoy. These pieces foreground the disconnect and shifts between the different types of time at play here: the near instantaneous fourth dimension of conception, the time spent to blot the system, procedure the clues, unlock and understand the method, and the implied slow time spent to execute the drawing itself: a person, on a scaffold, pulling graphite repeatedly beyond painted gypsum. I wonder if the administration were well paid.

The five hours or so it took to conduct out the Electric current Gallery slice were well spent: not an all nighter, only a tardily nighter. Friends brought food and beer, with other people coming and going, cutting holes in the building'due south flooring, plastering the backside with xeroxed drawings, and making Seussian maggots crawl from the walls and ceiling.

[[Edit: If anyone else has tried this, put some pics of it on the spider web and postal service a link in the comments]]

[[[Edit two: for more, meet also: Analog Voronoi Grid Baloney with Magnets]]]

neelyagetwoubding.blogspot.com

Source: http://765.blogspot.com/2009/09/how-to-draw-voronoi-diagram.html