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.
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.
Edited by Zouflain, 21 October 2012 - 04:05 PM.