Hand-Drawn Voronoi Diagrams

49,533

549

44

Posted

Introduction: Hand-Drawn Voronoi Diagrams

Rainy Day Challenge

Runner Up in the
Rainy Day Challenge

If you are into modern art, architecture, digital fabrication, or even geography then there is a good chance that you have stumbled across something called a Voronoi diagram. These honeycomb-like, asymmetric, mesh shapes are used in many types of mathematical analyses as well as to create interesting fill patterns in things like furniture and wall panels. In this quick Instructable I will show you how to create these unique diagrams by hand. That's right. Just you, some paper, a ruler, and some sharp pencils. The old-fashioned way.

Generating these patterns takes seconds on the computer, so drawing one manually may seem a bit ridiculous. However, I can guarantee you that drawing one by hand is the best possible way to learn how these ingenious little guys work. It is also a relatively simple, fun, and relaxing process that is perfect for a rainy day or a long, boring meeting.

As with most of my Instructables, I like to start out with a brief lesson. The subject today is history (and some math, of course). Let's get started.

[Project Video]

Step 1: Russian Math Bros

Georgy Voronoy was a Russian mathematician. The diagram that bears his name is used to divide a plane filled with unique nodes into separate regions. The cool thing about these regions is that at any point within them, you are closer to the node they contain than any other node, and, at any point along their boundaries, you are equidistant to at least two nodes. This makes them very useful for many applications such as mapping and zoning.

Boris Delaunay, another Russian mathematician and a student of Voronoy's, developed a method for connecting the same nodes into triangular regions, which is essential in the process of creating Voronoi diagrams. The key thing in a Delaunay triangulation is that, in each triangle generated, no other nodes exist within the circumcircle of that particular triangle. This is a fancy way of saying that each triangle is formed by connecting each node to its nearest neighbors.

Oddly enough, Delaunay was also an accomplished mountain climber, which may explain why his triangulation method is often used to build the TIN surfaces used to model terrain in 3D. We'll save that for another day...

For those of you wondering about that goofy circumcircle...it is a circle that intersects each of a triangle's vertices. Its center is located where the perpendicular bisectors of each of the three sides intersect, and its radius is the distance from this point to any one of the three vertices. Although we won't necessarily have to draw all the circumcircles later, the center points just mentioned will be very important. More on that as it comes.

So, thanks to these two cool dudes, we can perform some pretty awesome analyses and make some interesting looking artwork as well.

If you would like to read up a little more then here are some links:

Delaunay Triangulation: https://en.wikipedia.org/wiki/Delaunay_triangulat...

Voronoi Pattern: https://en.wikipedia.org/wiki/Voronoi_diagram

Boris Delaunay: https://en.wikipedia.org/wiki/Boris_Delaunay

Georgy Voronoy: https://en.wikipedia.org/wiki/Georgy_Voronoy

Step 2: Materials Needed

Tools and materials needed to produce a basic sketch are very minimal. Using these as a guideline you can easily scale up to a larger format or medium.

  • Pen(s) or Pencil(s) - 4 colors recommended
  • Paper
  • Ruler
  • Square or Protractor
  • Compass (optional)
  • Thick marker (optional)

Step 3: Loads of Nodes

We'll begin by drawing some dots. The only important guideline is that you place them as randomly as possible. Maximum and minimum point spacing should be determined based on your individual goals. Tighter spacing will produce a smaller shapes in the final pattern. Conversely, loose spacing will produce larger shapes. More dots = more complexity = more time. Your call.

Your nodes don't have to be a particular size so long as you can distinguish them later.

PRO-TIP: Having difficulty with the randomness? Sprinkle a pinch of any dry, granular, dark material (pepper, sand, sprinkles, etc.) on top of you paper and place a node wherever the pieces fall. You could also spell out a name, trace points on a map, or any number of other things.

Step 4: Delaunay Triangulation

This may be the most difficult part of the entire process. As was mentioned previously, we need to connect each node to its nearest neighbors, forming a network of triangles.

Another way to describe "nearest neighbors" is that, at a given node, we want to connect it to the the two adjacent nodes that make up a triangle with the smallest area possible. To do otherwise would mean that other nodes will fall within our circumcircle, which is wrong. With most points, finding the nearest neighbors is very intuitive. For those that are not so obvious, use your ruler to compare distances between other nodes in question.

As you begin to connect nodes and form triangles things will start getting easier. You will likely encounter scenarios where there are no other options other than to connect two nodes and complete an already partially formed triangle. Just be sure that you don't leave any non-triangular shapes between your nodes and don't ever cross another line (triangles can't share spaces).

I think the Delaunay diagram looks fairly cool on its own, but let's keep going. We don't want our old pal Georgy to get jealous.

Step 5: Stuck in the Middle

Once all of the nodes are connected, our next task is to draw the perpendicular bisectors for each line. The obvious first step in achieving this is to divide each line in half. Do this using the ruler and a different color pen/pencil.

Measuring each line and calculating the midpoint, one-by-one, makes this a somewhat tedious step. For this reason, I used a small tickmark to mark all of the midpoints before proceeding to the next step.

PRO-TIP: User nax left a great tip for finding the perpendicular bisectors using a compass. Basically, what you do is place the point of your compass on one of the the nodes, extend it roughly past the middle of the segment, and draw an arc above and below the line. Then you repeat the same process for the point on the opposite end of the segment. The perpendicular bisector will pass through the points where the arcs intersect. I think this is a superior method than my own, but you can decide for yourself. You can read more about it in the comments below. Thanks nax for pointing this out!

Step 6: Bisector Inspector

Using the square and the same color you used to mark the midpoints, draw a line through each midpoint and perpendicular to the line it bisects. These are the lines that will form the boundaries of the Voronoi pattern.

This has the potential to get sloppy really fast, so take your time and be aware that the perpendicular bisection lines for each side of each triangle will intersect at a single point. Recall, this single point is the center of the circumcircle for that triangle. Neat, huh?

Optional Step: If you still don't believe me about this whole circumcircle thing, or would just like to check your work thus far, grab a compass and test it out. A circle drawn with its center at the intersection of the three lines you just drew and a radius of the distance to one of the points in the triangle should intersect the other two points in the triangle perfectly.

Step 7: Connect the Dots (again)

It is finally time to reveal the Voronoi diagram! To do so all we need to do is start connecting each of the points where the three bisectors intersect (crazy cool circumcircle centerpoints). The lines you draw to connect them will follow the paths of the perpendicular bisector lines you drew in the last step.

I find it easiest to start on a prominent, central node where the bounding region is well-defined and intuitive.

A fourth color pen or a thicker line will help bring out your pattern against the busy background. However, a thick-tipped marker works the best.

And with that you are DONE! Way to go! Georgy would be so proud!

Step 8: Roll Your Own

Besides these basic sketches, there are many, many applications for Voronoi diagrams (and Delaunay triangulations too!). Pictured above are a few of my own creations.

Mastery of this technique will allow those of you without large format CNC machines or digital design tools to create and incorporate these patterns into your own handmade pieces. Please post a picture below in the comments of any Voronoi art, maps, etc. that you create.

Step 9: Wrapping It Up

I hope that you had fun learning about these cool diagrams and even more fun drawing them. Other than some sweet looking sketches I hope I have left you with a solid understanding and appreciation for how they come to be. Now not only will you be able to recognize them anywhere, but you will be able to explain to those lesser informed about how they work and how easy they are to create.

I use each of these patterns in a lot of other work I do, so chances are you will see them again in a future Instructable. Please follow me so you don't miss out.

Thanks again for reading!

5 People Made This Project!

Recommendations

  • Trash to Treasure

    Trash to Treasure
  • Microcontroller Contest

    Microcontroller Contest
  • Science of Cooking

    Science of Cooking
user

We have a be nice policy.
Please be positive and constructive.

Tips

Questions

33 Comments

It´s amazing the way things get together. So cool!

Thanks! They are a lot of fun to make, and it's always exciting because you never really know how they'll turn out.

Like snowflakes, no two are ever the same. Really great 'ible and history to fill in. I totally believe in the manual method first to cement in the concepts, and you did it very well. Thanks for sharing!

Great documentation skills!! Love the choice of music and the project is excellent :D Thanks for sharing.

Thanks! I was worried that the music may be too much for some people, but I'm happy to hear you liked it!

To carry your images into 3 Dimentional art and excite those who dont understand maths ,make any rough shape using straight or crocked lines with wire ,all joining especially around outside and immerse fully in a kids bubble blowing fluid and watch natures maths work everything out for you.making intersecting joining lines and bubbles

Photograph it,make a solid model from your photo ,then everyone will think you a mathematical,architectual Genius, Just for Fun

great project, arts and maths together