For the last six or eight months, off and on, I’ve been trying to write some code that will create a Voronoi diagram from a set of random points, inspired by Amit Patel’s Polygonal Map Generation demo. In the last week or so, I had a bit of a break-through, in that I finally managed to get an implementation of Fortune’s Algorithm put together that would actually work and generate the Voronoi edges and vertices correctly so that I could render them. Since most of the existing implementations I’ve been trying to work from are either broken or an enormous pain in the ass to try to understand, I’m planning on writing up my implementation, once I’m finally happy with it. I’ve still got a fair way to go, since right now I’m only outputting the graph edges and vertices successfully, and while that renders prettily, I haven’t gotten to the point that I have all of the really useful graph connectivity information being output yet. Hopefully, if everything goes well, I’ll manage to finish that up by the end of the week, but this has proven to be a real bugger of a problem to solve.
As I mentioned, most of the implementations I’ve studied are either incomplete or broken. Particularly, I haven’t found an example yet that correctly clips the edges of the generated Voronoi polygons to a rectangular area. So long as all you care about is rendering the graph to the screen, this isn’t a big problem, since most 2D graphics libraries will happily draw lines that extend beyond the drawable area of the screen. However, if you’re trying to subdivide a rectangular region into Voronoi polygons, its kind of nice to have your edges actually clipped to that region. What I’m envisioning doing with this code eventually is using it to render 3D maps, subdivided into territories, but with an overlaid rectangular grid for moving units – think of the strategic map in Total War games or Lords of the Realm.
After I got frustrated with trying to make the broken clipping code I was working from perform correctly, I trolled Google and came across the Cohen-Sutherland line-clipping algorithm. This looked to be exactly what I needed, and wonder of wonders, the Wikipedia page actually featured a readable, reasonable example, rather than the obtuse academic pseudo-code you usually find there (see the Fortune’s Algorithm article…). The only thing I would caution you about with the Wikipedia example is that it uses a coordinate system where the origin is the lower-left bounds of a rectangle as usually encountered in mathematics, rather than the upper-left origin we commonly use in computer graphics, so some tweaking is necessary.
The code for this example can be downloaded from my github repository, at https://github.com/ericrrichards/dx11.git. The algorithm is included in the Algorithms project, while the example code is in the CohenSutherlandExample project. The example code is a quick-and-dirty mess of GDI drawing code, so I’m going to focus on the algorithm code.
After clipping:
