README

The OpenVoronoi project aims to produce an algorithm for calculating
the 2D voronoi-diagram for point, line-segment, and circular-arc sites.
Currently point-sites work well and line-segment sites are being worked
on. The incremental topology-oriented algorithm is used 
(see References).

Voronoi diagrams are used for many purposes in computational geometry,
but the motivation for OpenVoronoi has mainly been 2D offset-generation
for cnc mill toolpath calcuations.

The OpenVoronoi project is at 
https://github.com/aewallin/openvoronoi

The mailing-list for OpenVoronoi is at
https://groups.google.com/forum/?hl=en#!forum/opencamlib

Dependencies
git (required only for the version-string)
cmake
Boost graph library
Boost python (if python bindings are built)
libQD ( a quad-precision arithmetic library). Available as package 
"liqd-dev" on ubuntu. See "http://crd.lbl.gov/~dhbailey/mpdist/

Build instructions
This project uses cmake, and can be built out-of-source:
$ mkdir bld
$ cd bld
$ cmake ../src
$ make
$ sudo make install

src/        has the source for the main algorithm
src/solvers has vd-vertex solver code
src/py      has python wrapping code
src/common  has common classes not specific to voronoi diagrams

Other voronoi-diagram codes

CGAL
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Voronoi_diagram_2/Chapter_main.html

LEDA
http://www.algorithmic-solutions.info/leda_guide/geo_algs/voronoi.html

Boost/Sweepline. This was a Google Summer of Code 2010 project, meant for inclusion in Boost.Polygon.
Integer input coordinates. Exact geometric predicates through geometric filtering. 
Uses Fortune's sweepline algorithm.
https://svn.boost.org/svn/boost/sandbox/SOC/2010/sweepline
or perhaps https://svn.boost.org/svn/boost/sandbox/gtl/

Boostcon video:
"Sweep-Line Algorithm for Voronoi Diagrams of Points, Line Segments and Medial Axis of Polygons in the Plane"
http://blip.tv/boostcon/sweep-line-algorithm-for-voronoi-diagrams-of-points-line-segments-and-medial-axis-of-polygons-in-the-plane-5368229

VRONI/Martin Held. This code is commercial and not available, as far as
we know. 
http://www.cosy.sbg.ac.at/~held/projects/vroni/vroni.html
Patel (see References) seems to have independently implemented the
same algorithm, we don't know where this code is or under what license it is.

References

Sugihara and Iri, (1992) "construction of the voronoi diagram for one 
million generators in single-precision arithmetic" 
http://dx.doi.org/10.1109/5.163412

Imai (1996) "A Topology-Oriented Algorithm for the Voronoi Diagram 
of Polygons" http://www.cccg.ca/proceedings/1996/cccg1996_0019.pdf

Sugihara, Iri, Inagaki, Imai, (2000) "topology oriented implementation 
- an approach to robust geometric algorithms" 
http://dx.doi.org/10.1007/s004530010002

Held, (1991) "On the Computational Geometry of Pocket Machining"
Lecture notes in computer science, vol 500
http://www.amazon.com/Computational-Geometry-Machining-Lecture-Computer/dp/3540541039/

Held, (2001) "VRONI: an engineering approach to the reliable and 
efficient computation of Voronoi diagrams of points and line 
segments" http://dx.doi.org/10.1016/S0925-7721(01)00003-7

Martin Held, Stefan Huber, (2009) "Topology-oriented incremental 
computation of Voronoi diagrams of circular arcs and straight-line 
segments", Computer-Aided Design, Volume 41, Issue 5, May 2009, Pages 327-338
http://dx.doi.org/10.1016/j.cad.2008.08.004

A smooth spiral tool path for high speed machining of 2D pockets  
Computer-Aided Design, Volume 41, Issue 7, July 2009, Pages 539-550
Martin Held, Christian Spielberger
http://dx.doi.org/10.1016/j.cad.2009.04.002

Nirav B. Patel, "Voronoi diagrams, robust and efficient implementation", Binghamton
University, State University of New York, 2005, MSc thesis. (this thesis is not
accompanied by code, or much implementation detail)

todo: Burnikel-papers?