Voronoi Benchmark

### 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 GTL Boostcon 2009 Paper GTL Boostcon 2009 Presentation Performance Analysis Layout Versus Schematic Tutorial Minkowski Sum Tutorial Voronoi Basic Tutorial Voronoi Advanced Tutorial ### 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)