Voronoi Benchmark Boost , ,
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.
построение диаграммы Вороноя / Делаунай триангуляции набора случайных точек, равномерно распределенных по 32-битной целочисленной сеткеvoronoi_benchmark_points.cpp построение диаграммы Вороноя / Делаунай триангуляции множества случайных непересекающихся сегментов, равномерно распределенных по 32-битной целочисленной сетке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
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.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
http://www.boost.org/LICENSE_1_0.txt )
Статья Voronoi Benchmark раздела
Материалы статей собраны из открытых источников, владелец сайта не претендует на авторство. Там где авторство установить не удалось, материал подаётся без имени автора. В случае если Вы считаете, что Ваши права нарушены, пожалуйста, свяжитесь с владельцем сайта.
:: Главная ::
