• entries
    64
  • comments
    46
  • views
    80411

Voronoi Diagrams

Sign in to follow this  
ericrrichards22

2273 views

A little over two years ago, I first saw Amit Patel's article on Polygonal Map Generation, and thought it was incredibly cool. The use of Voronoi regions created a very nice, slightly irregular look, compared to grid-based terrains. At the time, I had just finished up working on my DX11 random terrain code, and it looked like a fun project to try to tackle.

I then proceeded to spend several months messing around with different implementations of Fortune's Algorithm in C# to get started and generate the Voronoi polygons used to generate a terrain along the lines of Amit's example. At this point, I've lost track of all of the different versions that I've sort of melded together to produce the code that I've ended up with in the end, but some of the more influential are:


  • The original implementation of the algorithm by Steve Fortune
  • This JS version by Nicolas Garcia Belmonte
  • This C++ version, which is a port of the ActionScript version used in the original Amit Patel map generator.
    The original goal was to create a map generator, suitable for a kind of overworld/strategic level map. But, alas, life happened, and I got bogged down before I got that far. I did, however, wind up with a fairly cool tool for generating Voronoi diagrams. Because I had spent so much time trying to iron out bugs in my implementation of the algorithm, I ended up producing a WinForms application that allows you to step through the algorithm one iteration at a time, visualizing the sites that are added to the diagram, the vertices and edges, as well as the position of the beach and sweep lines. Eventually I also worked in options to show the circles through three sites that define where a Voronoi vertex is located, as well as the Delauney triangulation of the sites.
    72_voronoi.PNG
    Voronoi regions, with the edges drawn in white, and the sites as the blue points.

    72_delauney.PNG
    Delauney triangulation, with triangle edges in green.

    72_both.PNG
    Showing both the Voronoi regions and the Delauney triangles.

    I won't pretend that this code is fantastic, but it's kind of interesting, and I worked at it for quite a while, so better to have it out here than moldering on a hard drive somewhere. If you'd like to see the source, it is available on GitHub. You can also download the executable below if you like - I make no promises that it will work everywhere, but it is a pretty standard .Net 4.5 Windows Forms application. I've also got some videos below the fold, if you'd like to see this in action.

    Download Voronoi


    Read more...

Sign in to follow this  


3 Comments


Recommended Comments

Very cool stuff. Thanks for sharing. A friend of mine at work is doing something similar in a side project. I'll definitely be sending him this post. :)

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now