HTTPS clone URL
Subversion checkout URL
2D voronoi diagram for point and line-segment sites using incremental topology-oriented algorithm. C++ with python bindings. GPLv3.
C++ Python CMake Shell
Fetching latest commit...
Cannot retrieve the latest commit at this time.
|Failed to load latest commit information.|
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). OpenVoronoi is written by Anders Wallin (anders.e.e.wallin "at" gmail.com) and released under GPLv3 (see COPYING). 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. 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 There is a gallery of voronoi diagrams produced with OpenVoronoi at https://picasaweb.google.com/106188605401091280402/OpenVoronoiExamples Dependencies python 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/ most python-examples use VTK and the VTK python bindings to visualize the input geometry and the voronoi diagram. On ubuntu these are available in the packages - libvtk (Ubuntu 11.10 has libvtk5.6) - python-vtk many examples use truetype-tracer (python module "ttt") for generating input data. https://github.com/aewallin/truetype-tracer some examples and tests use the 2-opt random polygon generator from CGAL. There is a boost-python module "rpg" which is used by these scripts. https://github.com/aewallin/CGAL_RPG Build/Install instructions From PPA sudo add-apt-repository ppa:anders-e-e-wallin/cam sudo apt-get update sudo apt-get install openvoronoi From source $ git clone git://github.com/aewallin/openvoronoi.git $ cd openvoronoi $ mkdir bld $ cd bld $ cmake ../src $ make $ sudo make install Tests There are a few python-scrits in src/test/ that can be run with CTest. In the build-directory either "make test" or "ctest" will run all tests. You can run only tests that have e.g. "ttt" in the test-name with "ctest -R ttt" Currently the tests do not produce any output (png or svg output could be an option?) Organization doc/ has documentation in lyx format, with figures in asymptote format. Build a PDF with the CMakeLists.txt in this directory. cpp_examples/ has c++ examples (more needed) python_examples/ has Python examples. Many use VTK and VTK's python bindingd for visualization. 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 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 yor 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 GPL. 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, Voronoi Diagram algorithms 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 Nirav B. Patel (2005), "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) Kim D-S, (1998), "Polygon offsetting using a Voronoi diagram and two stacks" Computer Aided Design, Vol. 30, No. 14, pp 1069-1076 http://dx.doi.org/10.1016/S0010-4485(98)00063-3 Chen, Fu "An optimal approach to multiple tool selection and their numerical control path generation for aggressive rough machining of pockets with free-form boundaries" Computer Aided Design 43 (2011) 651-663 http://dx.doi.org/10.1016/j.cad.2011.01.020 todo: Burnikel-papers? References, HSM or Trochoidal paths: Martin Held, Christian Spielberger (2009). "A smooth spiral tool path for high speed machining of 2D pockets", Computer-Aided Design, Volume 41, Issue 7, July 2009, Pages 539-550 http://dx.doi.org/10.1016/j.cad.2009.04.002 See also www.cosy.sbg.ac.at/~cspiel/projects/hsm/isvd08.pdf and www.cosy.sbg.ac.at/~held/teaching/seminar/seminar_2010-11/hsm.pdf Gershon Elber, Elaine Cohen, Sam Drake, "MATHSM: medial axis trasform toward high speed machining of pockets", Computer Aided Design 37 (2004) 241-250 http://dx.doi.org/10.1016/j.cad.2004.05.008 Rauch et al. (2009) "Improving trochoidal tool paths generation and implementation using process constraints modelling" http://dx.doi.org/10.1016/j.ijmachtools.2008.12.006 This paper has formulas for maximum depth of cut for circular and trochoidal clearing paths Ibaraki (2010) "On the removal of critical cutting regions by trochoidal grooving" http://dx.doi.org/10.1016/j.precisioneng.2010.01.007