Polygon Sponsor

Voronoi Benchmark

• could handle input data sets of points and segments
  
• give exact warranties about the algorithm robustness and output topology
  
• compute coordinates of the output geometries within the fixed relative precision
  

• Boost.Polygon Voronoi - satisfies all the conditions above, implements sweep-line algorithm.
  
• CGAL - satisfies the first two conditions, implements incremental algorithm. CGAL is a well-known library in the computational geometry area, especially for its robustness.
  
• S-Hull - doesn't satisfy any of the above conditions. S-Hull is a non-robust implementation of the sweep-hull algorithm used to construct Delaunay triangulation of a set of points.
  

Important

Voronoi Benchmark Details

• The first one constructs the Voronoi diagram of a set of random points (voronoi_benchmark_points.cpp)
• The second one constructs the Voronoi diagram of a set of random segments (voronoi_benchmark_segments.cpp)

• We ensure that input data sets are the same for all libraries by initializing random generator with the same seed
• We ensure that input data sets that consist of segments don't contain intersections using Boost.Polygon functionality
• S-Hull's implementation doesn't process duplicate points properly, thus those are eliminated before the algorithm execution explicitly (Boost.Polygon Voronoi and CGAL do that  implicitly)
  
• There is no Voronoi diagram data structure in CGAL/S-Hull. That's why we use the segment Delaunay graph which is topologically dual to the Voronoi diagram
• CGAL's and S-Hull's output Delaunay triangulation doesn't contain information about coordinates of the Voronoi vertices. We didn't include time to compute Voronoi vertices and memory storage required for those in this benchmark.
  
• Both Boost.Polygon Voronoi and CGAL process each input segment as 3 input objects (segment itself and its endpoints), thus the running time and memory usage for Voronoi of segments would be at least 3 times slower than for Voronoi of points

Voronoi Benchmark Results

Random Points Benchmark

Random Segments Benchmark

Voronoi Benchmark Summary

• There is no input size range were CGAL would outperform Boost.Polygon Voronoi. Even considering the fact that we didn't include time it would take CGAL to compute coordinates of the Voronoi vertices.
• The more interesting fact is that robust implementation of the Boost.Polygon Voronoi is faster than non-robust of S-Hull (except small input sets of around 100 points on Linux-64).
  
• Logarithmic execution time shows that Boost.Polygon Voronoi and S-Hull have clear N*log(N) complexity, while this doesn't seem to be true for CGAL (at least for large input data sets).
  
• Boost.Polygon Voronoi computes coordinates of the output Voronoi vertices within 64 machine epsilon precision. There are no such warranties for the CGAL library.
  
• Boost.Polygon Voronoi of points is 4 times faster for small input data sets (10 points) and this factor grows up to 100 for large input data sets (1000000 points).
• Boost.Polygon Voronoi of segments is 3 times faster for small input data sets (10 segments) and this factor grows up to 40 for large input data sets (1000000 segments).
• Boost.Polygon Voronoi is capable to construct Voronoi of 10000 points or 1000 segments in 0.02 seconds. This allows to produce real time frame rate for those quantities.