forked from aewallin/openvoronoi
-
Notifications
You must be signed in to change notification settings - Fork 0
/
README
130 lines (102 loc) · 5.22 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
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
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/
Build/Install instructions
From PPA (works on Ubuntu 11.10 oneiric)
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
Working Platforms
- Ubuntu 11.10 oneiric (gcc 4.6.1 with Boost 1.46.1)
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
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
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
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
todo: Burnikel-papers?