For a game I've been working on, I need to subdivide a square region into a bounded voronoi diagram, but anything besides brute forcing the process is extremely complex to implement (fortune's algorithm and divide&conquer specifically). Unfortunately, I'm dealing with a 1024x1024 grid, with approximately 2048 sites. The brute force approach takes ten minutes to compute this. I would really appreciate it if someone could point me in the direction of a library that uses one of the O(nlogn) algorithms, so that I need not reinvent the wheel and can generate the data in realistic timeframes for a video game.

All I need the library to do is take a set of sites, generate closed cells about those sites corresponding the voronoi diagram, and then return the coordinates of the vertices that correspond to each site. I have found several libraries and implementations, but most are not remotely geared for anything approaching this, or are so badly documented that attempting to retrieve this information is almost impossible. For licensing, I do intend to sell the art and resources associated with the game, but I see no reason not to include the source code with the distribution (thus, even GPL'd libraries are fine).

I have looked over several libraries, but unless you can also direct me towards a tutorial that clearly documents their usage for this or a nearly identical purpose, I dont see a way to utelize them:

• Boost::polygon::sweepline hasn't been released yet, does not close border cells, and obfuscates the site/vertex relation
  
• Voro++ seems robust, but is meant for 3D and isn't clear about how to operate in 2D
  
• QHull is an external application, not a linkable library
  
• GNU 'GITS' has very unclear documentation. A C++ wrapper would probably be a great aide.
  
• CGAL is one I have yet to fully investigate, but a cursory look suggests it's anything but lightweight or appropriate.
  

As I understand it Voronoi implementations are pretty common, but I'm having one heck of a time trying to find one that I can use. I'd use any of the above as well, so long as I could just get an explanation that doesn't involve reverse engineering the entire library. I appreciate any help I get on the matter.

Edit: I thought I would add a few details: I dont care about mathematical accuracy, this is not a physics simulation - I care only about speed. The only data I need from the diagram is the x and y coordinate of each vertex and which sites they belong to. Anything else is superfluous to my needs.

If by QHull you mean http://www.qhull.org/, then from what I can tell, the source is available.

Boost::polygon Voronoi will be available in the 1.52 release candidate (5th November).
You can start playing with beta-release candidate: http://sourceforge.net/projects/boost/files/boost/1.52.0.beta.1/

BTW, it already closes border cells. Also not sure, what you mean by obfuscated site/vertex relation?

I'm posting this just in case anyone has similar issues or needs (I hate finding dead threads with the same problem I have).

I wound up using Voro++. It is 3D only so far as I can tell, but by having all the seeds on a plane effectively renders it 2D. The vertices are duplicated, but at least I can extract the xy coordinates and simply discard the Z. That was all I really needed.

I spent a large amount of time trying to get Boost::polygon to work as I needed it to, as it was by far the most transparent of everything I looked at. It's been a while since I did the work, but I believe I reworked the class to assign a unique ID I could trace, but unfortunately it lost this information somewhere down the line (possibly a memcpy between pointers I couldn't track down). It's also very unintuitively designed. Perhaps with a bit more documentation I could have done better, but after getting frustrated I tried Voro++ on a whim and had working code in minutes.

As for what I meant by obfuscated site/vertex relation is simply that it's almost impossible to tell which site relates to which vertex without brute force distance checking each one, as far as I recall. It generates the diagram very, but not in a format I could use (I cared about the polygons, not the graph).