Contents
- Boost.Polygon Main Page
- Design Overview
- Isotropy
- Coordinate Concept
- Interval Concept
- Point Concept
- Segment Concept
- Rectangle Concept
- Polygon 90 Concept
- Polygon 90 With Holes Concept
- Polygon 45 Concept
- Polygon 45 With Holes Concept
- Polygon Concept
- Polygon With Holes Concept
- Polygon 90 Set Concept
- Polygon 45 Set Concept
- Polygon Set Concept
- Connectivity Extraction 90
- Connectivity Extraction 45
- Connectivity Extraction
- Property Merge 90
- Property Merge 45
- Property Merge
- Voronoi Main Page
- Voronoi Benchmark
- Voronoi Builder
- Voronoi Diagram
Other Resources
Polygon Sponsor
Voronoi Benchmark
Benchmark Details
From the topological perspective Delaunay triangulation is a dual data structure to the Voronoi diagram, thus libraries that provide Delaunay triangulation construction routines were also included into the benchmark. However, from the computation perspective Voronoi diagram contains more information as it embeds information regarding the coordinates of the centers of the inscribed circles tangent to the three or more input geometries.The benchmark consists of the two parts:
- construction of the Voronoi diagram / Delaunay triangulation of a set of random points uniformly distributed over 32-bit integer grid (voronoi_benchmark_points.cpp)
- construction of the Voronoi diagram / Delaunay triangulation of a set of random non-intersecting segments uniformly distributed over 32-bit integer grid (voronoi_benchmark_segments.cpp).
Libraries
| Library |
Boost.Polygon |
CGAL |
SHull |
| Official page |
www.boost.org/libs/polygon |
http://www.cgal.org |
http://www.s-hull.org |
| Algorithm |
sweep-line |
incremental |
sweep-hull |
| Supported input geometries |
points and segments |
points and segments |
points |
| Output data structure |
Voronoi diagram |
Delaunay triangulation |
Delaunay triangulation |
| Complexity |
O(N log N) |
O(N log N) | O(N log N) |
| Memory usage |
O(N) |
O(N) |
O(N) |
| Robustness policies |
lazy arithmetic, exact predicates, topology analysis |
lazy arithmetic, exact predicates, topology analysis |
non-robust |
| Output coordinates precision |
128 machine epsilon |
no output coordinates |
no output coordinates |
| External dependencies |
No |
Boost, GMP, MPFR |
No |
The other known libraries (OpenVoronoi, Triangle, Vroni) will be considered for the inclusion into the benchmark in the future.
System Configuration
Hardware: Intel i5-7600 2.8 GHz, 16GiB RAM.OS: Ubuntu 13.04 64-bit.
Compiler: GCC 4.7.3.
Libraries and dependencies: Boost 1.54.0, CGAL-4.3-beta1, GMP 5.1.4, MPFR 3.1.2, S-Hull.
Benchmark Results
Random Points Benchmark
| Test specification |
Average construction
time (in secs) |
||||||
| Number
of Points |
Number
of Runs |
Boost
Linux-64 |
CGAL
Linux-64 |
S-Hull
Linux-64 |
|||
| 100 |
10000 |
0.000206 |
0.000073 |
0.000243 |
|||
| 1000 |
1000 |
0.002250 |
0.000753 |
0.002184 |
|||
| 10000 |
100 |
0.024100 |
0.007917 |
0.030552 |
|||
| 100000 |
10 |
0.292000 |
0.084336 |
0.451913 |
|||
| 1000000 |
1 |
3.470000 |
0.902300 |
6.603814 |
|||
Random Segments Benchmark
| Test specification |
Average construction time (in secs) | ||||
| Number
of Segments |
Number
of Runs |
Boost
Linux-64 |
CGAL
Linux-64 |
||
| 100 |
10000 |
0.002284 |
0.002985 |
||
| 1000 |
1000 |
0.023240 |
0.032180 |
||
| 10000 |
100 |
0.237700 |
0.337400 |
||
| 100000 |
10 |
2.488000 |
3.633000 |
||
| 1000000 |
1 |
25.00000 |
39.090000 |
||
| Copyright: | Copyright © Andrii Sydorchuk 2010-2012. |
|---|---|
| License: | Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |