Monday, September 07, 2009

How to: Draw the Voronoi Diagram

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

Drawing Voronoi diagrams by hand has renewed my interest in the stuff. There are lots of scripts out there for making instant vector crystal foam in just about any modeling or CAD platform, but it's more interesting for me right now to slow it down, take it step by step, and really try to understand the geometries involved. More a heuristic than an algorithm, executing it demands and reinforces the kind of zoned out close attention that almost becomes the whole point of drawing in the first place. The artifact that you get at the end it is just an unexpected bonus: the physical record left by the process of thinking out loud on paper. Below is a rough pseudocode (thanks, mike!) for building it up from a set of points.

(1) Input Sites (2) Connect Nearest Neighbors (shortest line wins) (3) Find Center Points
(4) Draw Perpendicular Bisectors (5) Trace Cells (6) voila

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

(2) The next step is to connect the sites to all of their nearest neighbors without making a line that crosses another. This is known technically as the Delauney Triangulation, and it's maybe the most difficult part. One way to do it might be by brute force - connect every site to every other site, make a true all-to-all rhizomatic meshwork, and then start deleting lines that are too long. This is how a machine might attack the problem, 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 start 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 it.

Image via wikipedia

This also takes too long, and circumcircles are hard to draw, so I found a method that's faster, and still mostly accurate. Since no lines on the Delauney triangulation can cross, just eyeball it until you run into a condition as in the above, where you have to decide if FD or AE is correct, the shorter line always 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 draw the perpendicular bisector for each Delauney line. This is where careful accuracy, in finding the centerpoints, and in drawing a tight 90 degree angle, pays off. If everything has been done correctly, there will always be 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 it land exactly where it's supposed to is extremely satisfying. Watching it 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 work out, but just don't: evidence of some hidden monster in the process, a flaw in the heuristic, or a breakdown of the pseudocode.

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

(6) Sit back and congratulate yourself while contemplating your hard earned tangle of fat distorted honeycomb.

I've found in practice that it's best to use different 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. Blue and red mechanical pencil leads are pretty easy to get. I made this drawing to practice, using a pepper grinder above the drafting table to get random input sites:

The wall drawing below was made for the Current Gallery's Abandon Ship show. 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 year 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 move ahead to build a hotel on the site. I was very glad to get the chance to do a wall drawing, having just visited again, for the second time, Sol LeWitt's ephemeral 'Drawing Series—Composite, Part I–IV, #1–24, A+B' at Dia Beacon. These pieces foreground the disconnect and shifts between the different types of time at play here: the almost instantaneous time of conception, the time spent to absorb the system, process 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 across painted gypsum. I wonder if the assistants were well paid.

The five hours or so it took to carry out the Current Gallery piece were well spent: not an all nighter, but a late nighter. Friends brought food and beer, with other people coming and going, cutting holes in the building's floor, 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 web and post a link in the comments]]

[[[Edit 2: for more, see also: Analog Voronoi Grid Distortion with Magnets]]]

Anonymous said...

Gave this a try last night, strangely satisfying in a 'i don't know what i'm doing but its kind fun way' Thanks for the process.

Jack Lyons said...
This comment has been removed by a blog administrator.
sevensixfive said...

@anonymous - post pics!

@jack - draw it and post pics!

epologee said...

Awesome! Thanks for the explanation of the Delaunay triangulation, apart from the Voronoi drawings! I'm not a native English speaker and my math knowledge is limited. I was looking for this in a recent project, but settled for a solution without the Delaunay principle, because I just didn't know it was called that way :) http://tinyurl.com/nq7swr

Feel like doing it again but correct this time, thanks!

Anonymous said...

explain again, how does this help me get a job?

Anonymous said...

What about application? I could imagine a case where you had hundreds or thousands of data points. What if you randomly sampled a small number, say 10, and did a Voronoi with just those. Would the results allow you to put every data point into a managable number of classes?

But if you did this twice or more, wouldn't you come up with different classifications each time?

Joseph Francis said...

Something between hand drawing it and running a program: letting Photoshop radial grads and the 'lighten' blend mode do the heavy lifting.

http://www.digitalartform.com/archives/2009/06/simulating_voro.html

Anonymous said...

Have you tried looking into any "plane sweep" algorithms to make these? They're a lot more efficient, possibly harder to understand. Google "Fortune's plane sweep algorithm." Yeah, these are pretty cool. Nicely done!

sevensixfive said...

Hi Anonymous - Yep, I did look at Fortune's Algorithm, it's pretty interesting. I didn't think it would be useful for hand drawing, because it requires a lot of testing and refining to find the lines. More suited to a machine than a person. Humans are still better at 'reckoning' than computers.

Unknown said...

Where can i find a software that would automatically generate the voronoi diagram for a given set of points? I tried the link, but i need something where i can define the control points accurately. maybe something that works with AutoCAD? I'm doing it manually but after seeing how fast it can be done automatically i really want to find a software!

Anonymous said...

Great help tnx!!

Unknown said...

thanks thanks thanks so much for a very lucid explanation!!

runescape gold said...
runescape accounts said...
wangqian said...

Very informative and trustworthy blog. Please keep updating with great posts like this one. I

have booked marked your site and am about to email it to a few friends of mine that I know

luna gold
cheap luna gold
luna gold
luna gold
cheap luna gold
luna gold
luna gold
shaiya money
cheap shaiya money
shaiya money
shaiya money
cheap shaiya money
shaiya money
shaiya money

combattery84 said...
combattery84 said...
Arlen said...

The eve online isk game eve isk has electric cigarette and features electronic cigarette players. electronic cigarettes is wholesale designer handbags in wholesale replica handbags. cheap coach handbags Guide will cheap handbags wholesale an wholesale designer sunglasses the stepper drivers economy,stepper motor suggestions stepping motor. CNC Router kits is very magic slim you herbal xenicol lose meizitang your lida daidaihua, super slim pomegrante, zhen de shou,2 day diet japan lingzhi.imelda perfect slim,fat loss jimpness beauty,fruit & plant weight loss capsule item at that station.

Anonymous said...

I just want to emphasize the good work on this , has excellent views and a clear vision of what you are looking for
earn diploma at home | online english course

woodworking plans said...

I used the following algorithm to draw the voronoi diagram. First of all, for each set of three points, I calculate the orthocentre of the three points. That is, I calculate the point which is equidistant from all three points. Then, for each orthocentre x, I check all the points in P, to make sure that the three points used to find x are the three closest points of P to x. If they are not, I reject x from consideration. It is not needed to draw the voronoi diagram

This comment has been removed by the author.
Juegos said...

In my opinion you have good drawing skills, the Voronoi diagrams are pretty complex geometric models.

Rob@ multi picture frames said...

This is a nice tutorial and looks really fun to make. this I have to try. Thanks a lot.

Cabin Plans said...

Nice post :)At first look this is a bit complicated but is it really? :)

Jaime said...

Tina asked, and though I doubt she'll ever read it with all the spam cluttering the comments, if you are after software for Voronoi diagrams, Delaunay triangulations, or convex hull, the standard thing is qhull (http://www.qhull.org).

It's free, open source, and it's what Matlab and Mathematica use to do these kind of calculations.

Interesting to note that the most often used computerized way of doing Voronois and Delaunays projects the points onto a paraboloid in a space of one more dimension, and then finds the convex hull of the projected points: not something that will work by hand too good...

David Eppstein said...

Re: where you have to decide if FD or AE is correct, the shorter line always wins.: this is false. For a counterexample, let ADF be an acute isosceles triangle whose base DF is less than its height, and place E outside the triangle very close to the midpoint of DF.

You're repeating an error original made by Shamos, though, so you're in good company.

CNA Traning said...

I recently came across your blog and have been reading along. I thought I would leave my first comment. I dont know what to say except that I have enjoyed,Yes, it’s all about little adjustments along the way. That’s how truly great products become truly great products. And of course, the process always continues as people have different wants/needs.

Cna Certification

louis vuitton spring summer 2010 collection said...

Discover Louis Vuitton collections online: luggage, handbags, wallets, shoes ...

nemuda said...
auto insurance quotes said...

This is a vey interesting post. I knew people could draw this diagrams so easily. Now I can do too, cool.

Anonymous said...

You can also use the Filter by Time tool on the left column to narrow the search results by time and see stories published within the last hour, day, or week. Choose “Past Day” in the news search result page for the query “obama,” you’ll see only results published within the last day.
Thank youNike Air Max 90
Wholesale Nike Shoes
Christian Louboutin Boots
Sexy High Heels
Christian Louboutin High heels
Yves Saint Laurent High heels
Tory Burch High heels
Christian Louboutin High Heel

akif said...

sohbet
netlog
canli sohbet
sohbet
chat odalari

ww2 uniform said...

A vast selection of reproduction WW2 German uniforms, Waffen SS Camouflage, Winter reversible parka coats, smocks and service shirts,tunics, overcoats.

Anonymous said...
Anonymous said...

Happy to see this article as it is just what I have looking for and I am looking forward to another great article from you. As a fashion girl or lady, you must choose a right hair straightener from
ghd uk to make you more attractive. You may be interested in chi us.
Welcome to chi hair.
You can choose Nike Shoes from Air Max Shoes

Anonymous said...

We all know that online shopping is a convenient option for buying high end electronics items within one's budget.|p90x workout|leisure furniture|sexy halloween costumes china It allows us to get great deals on a wide range of electronics like cell phones for sale,Video Camera, Camcorder, replacement laptop battery wholesale, Portable MP3 players,Home theatre, audio system etc. Many of these online electronics store,sexy lingerie wholesale|p90x diet|leather sexy lingerie|outdoor sofa provide cheap and discount products. Through online china electronics wholesale store shopping, we can enjoy a great shopping experience for our desired electronics from the comforts of our home.workout routines|p90x diet|Leather corset|leisure furniture There are lots of advantages of purchasing electronics items online like discounts, freebies etc. But we should consider a lot of things while we are shopping online.

Our Online China Electronics Wholesale Store Supply High Quality Audio Video players Wholesale,Chalean Extreme|halloween costumes manufacturers|outdoor sofa Digital Photo Frames, Our Audio Video Players for Sale is Low Price,P90X|halloween costumes manufacturers|patio furniture So You Can Save Huge on Your Purchases, And You Can Enjoy a Pleasant Audio-Visual Trip!

Anonymous said...

The ensemble drama about young adults growing up in Beverly Hills is a blend of romantic drama and subject matter that crosses all cultural boundaries.
Stargate SG-1 Season 1-10
The Shield Season 1-7
Without A Trace Season 1-5
24 Season 1-8 DVD

Anonymous said...

The Christian Louboutin Heels can help you become sexy and elegant. christian louboutin 2011 sandals are regarded since the symbolic representation of attractive and elegant.christian louboutin wedgesIt is especially suitable for the women who wear the christian louboutin evening shoes at the first time. These christian louboutin pumps combine top quality, reasonable price and fashional design, which is your best choice Artist who promoted his collection of luxury christian louboutin classic
in earlier 90s. No 1 can disregard the existence in the style world, World-famous red-colored soles and christian louboutin peep toe are shaped features. However, you can by no means overlook the beautiful. You do not even need to go inside environment, as well as your slim,christian louboutin thong sandalsgorgeous and graceful legs may be effortlessly discovered in people's eyes.!Welcome to our christian louboutin store.

online casino roulette said...

Quite helpful material, thank you for this post.

Kamagra Gel reviews said...

Thanks for your article, very useful information.

Bob said...

how to become a dentist

Timmy said...

Nice, thanks for explaining the diagram
how to become a physical therapist

Rita said...

At last i got the explaination of this diagram. THANK YOU

Tod said...

Nice explaination
dental hygienist schools

Iga said...

It's so simple :)
Toronto traffic ticket

Montatna said...

great, very simple to understand
Mississauga Dance Classes

Dr.Jerkins said...

Allright!! At last I found it!! Hooray
Psychology Schools`

acne said...

Grat explanation and fascinating how it relates to everything. thank you.

how to get rid of acne fast

watch jersey shore said...

Great post thanks for the read!

Your Escort Agency offers exclusive and most beautiful London escort girls of various nationalities.

Anonymous said...

I think that's great!
Zoom Kobe VI

what is the best video editing software said...

Using the best antivirus software be able to aid en route for decrease the quantity of guidance workers destitution. What is the best photo editing software

Anonymous said...

I would like to appreciate the great work done by You pf changs coupons

Anonymous said...

I would like to appreciate the great work done by You pf changs coupons