aewallin / openvoronoi

OpenVoronoi **Updates:** 2018-07 (change to LGLP), 2015-02-12. 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 and line-segment sites work. Arc-sites are being worked on. The incremental topology-oriented (Sugihara-Iri and/or Held) algorithm is used (see References). The core algorithm is in C++ with python bindings using Boost Python. There are many python examples that use VTK for visualization. As of 2018 VTK 6 is used for visualizations. Some tests use a random polygon generator (randompolygon) and a font-geometry generator based on FreeType (truetype-tracer). OpenVoronoi is written by Anders Wallin (anders.e.e.wallin "at" gmail.com) and initially released under GPLv3. In July 2018, license was changed to LGPL2.1 (see COPYING) with permission and cooperation of all contributors (Issue #35). In February 2015 Rogach published a Java port called jopenvoronoi. Voronoi diagrams are used for many purposes in computational geometry, but the motivation for OpenVoronoi has mainly been 2D offset-generation (see offset.hpp) for cnc mill toolpath calcuations. An experimental approximate medial-axis filter (medial_axis.hpp) has been added. Links • **Project repository:** https://github.com/aewallin/openvoronoi • **Mailing list:** https://groups.google.com/forum/?hl=en#!forum/opencamlib Dependencies Required Dependencies • **cmake** - Build system • **libqd-dev** - Quad-double precision arithmetic library (http://crd.lbl.gov/~dhbailey/mpdist/) • **Boost graph library** - Graph algorithms • **graphviz** - Visualization for graph algorithms Optional Dependencies • **git** - Required only for the version-string • **python** - If python bindings are built/used • **Boost python** - If python bindings are built • **doxygen** - For building documentation • **asymptote** - To build white-paper figures • **lyx** - To build white-paper • **libvtk** - Many python-scripts use VTK for visualization • **python-vtk** - VTK python bindings • **truetype-tracer** - Some tests • **randompolygon** - Some tests Build/Install Instructions From Source Documentation Doxygen documentation can be built with . A white-paper on the algorithm and solvers in LyX format is located in . It has its own CMakeLists.txt file which builds a PDF file. Tests Both C++ and Python tests are found in . These are run with CTest. In the build-directory either or will run all tests. You can run only tests that have e.g. "ttt" in the test-name with: Currently the tests do not produce any output (png or svg output could be an option?) Organization • **doc/** - Documentation in lyx format, with figures in asymptote format. Build a PDF with the CMakeLists.txt in this directory. • **cpp_examples/** - C++ examples (more needed) • **python_examples/** - Python examples. Many use VTK and VTK's python bindings for visualization. • **src/** - Source for the main algorithm • **src/solvers** - VD-vertex solver code • **src/py** - Python wrapping code • **src/common** - Common classes not specific to voronoi diagrams • **src/utility** - Input and output from OpenVoronoi to/from various formats Contributing See the TODO file. Fork the github repo, create a feature branch, commit your changes, test. Make a short description of your changes and create a pull request. Follow the coding-style of the existing code. One fix/feature per pull request. Contributed code must comply with the LGPL. Provide short doxygen-formatted documentation in the code. 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.Polygon.Voronoi** - http://www.boost.org/doc/libs/1_52_0/libs/polygon/doc/voronoi_main.htm • **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 • **Voro++** - BSD-licensed code for 3D voronoi cell computation. May not be useful for 2D toolpath generation? http://math.lbl.gov/voro++/ • **Triangle** - http://www.cs.cmu.edu/~quake/triangle.html Really a mesh-generator for e.g. finite-element analysis. A constrained Delaunay triangulation could be used to generate a Voronoi diagram for point and line inputs. Boost.Polygon.Voronoi Notes Boost.Polygon.Voronoi was a Google Summer of Code project in 2010. Integer input coordinates. Exact geometric predicates through geometric filtering. Uses Fortune's sweepline algorithm. **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 Patel (see References) seems to have independently implemented the VRONI/Held algorithm, but we don't know where this code is or under what license it is. References Core Algorithm 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 comp…