# libvoronoi

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.

## Resources

Check out the Sourceforge
project page for
news, file releases and CVS access.

You can contact me at `ajsecord`

*at* `users.sourceforge.net`

.