|
|
|
libvoronoi is a C library for calculating the discrete Voronoi diagram of a set of 2D points, lines and line segments. A Voronoi diagram divides up the plane into a set of regions. Every point in a particular region is geometrically closest to one (and only one) of the input points, lines or line segments. Voronoi diagrams are fundamental objects in computational geometry and are widely used in image processing, mesh simplification, non-photorealistic rendering, and many other applications, particularly in computer graphics and vision.
The library's input is simply the list of points, lines and line segments. The output is an image in which every pixel is an index referring to one of the input points, etc. Note that, unlike many traditional Voronoi diagram programs, the output is a discrete image of the diagram, and not a logical description of the diagram's edges. While discrete diagrams are less precise, they are very fast to compute and more convenient in many applications. In addition, the library can optionally compute several important quantities for each Voronoi region, including their areas, centroids ("centres of mass"), and first and second image moments. From this information you can easily get a principal direction of each region or an equivalent oriented rectangle.
The implementation is based on the well-known computer graphics paper Fast computation of generalized Voronoi diagrams using graphics hardware by Hoff and colleagues, published in the proceedings of SIGGRAPH 99. The method uses common graphics hardware to accelerate the computation of the diagrams. libvoronoi uses OpenGL to interface to the graphics hardware. Fortunately, both hardware and software implementation of OpenGL are widely available, making the graphics hardware itself optional. Indeed, using the Mesa software OpenGL renderer, it is possible to render without a display at all, enabling command-line and remote use of the library.
The library is implemented in clean C, with an interface similar in spirit to the popular libpng library. In its current form, I expect it to be portable across current 32 bit architectures, and 64 bit architectures should be possible. In the near future, I plan to add C++ and Python bindings to the library using SWIG.
Check out the Sourceforge project page for news, file releases and CVS access.
You can contact me at ajsecord at users.sourceforge.net.
|
|
|
|