Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r77792 - in sandbox/gtl: doc libs/polygon/benchmark
From: sydorchuk.andriy_at_[hidden]
Date: 2012-04-06 17:06:42


Author: asydorchuk
Date: 2012-04-06 17:06:39 EDT (Fri, 06 Apr 2012)
New Revision: 77792
URL: http://svn.boost.org/trac/boost/changeset/77792

Log:
Running benchmarks on Linux. Updating documentation.

Text files modified:
   sandbox/gtl/doc/voronoi_main.htm | 25 +++++++++++++++----------
   sandbox/gtl/libs/polygon/benchmark/Jamfile.v2 | 35 ++++++++++++++++++++++-------------
   sandbox/gtl/libs/polygon/benchmark/benchmark_points.txt | 21 +++++++++++++++++++++
   sandbox/gtl/libs/polygon/benchmark/benchmark_segments.txt | 21 +++++++++++++++++++++
   4 files changed, 79 insertions(+), 23 deletions(-)

Modified: sandbox/gtl/doc/voronoi_main.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_main.htm (original)
+++ sandbox/gtl/doc/voronoi_main.htm 2012-04-06 17:06:39 EDT (Fri, 06 Apr 2012)
@@ -30,8 +30,10 @@
 
 
 
+
+
 <meta http-equiv="Content-Language" content="en-us">
-<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title><meta http-equiv="content-type" content="text/html; charset=utf-8"><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body>
+<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title><meta http-equiv="content-type" content="text/html; charset=utf-8"><meta http-equiv="content-type" content="text/html; charset=utf-8"><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body>
 
 <table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
         <tbody><tr>
@@ -101,7 +103,7 @@
                                 <li>Layout Versus Schematic Tutorial</li>
                                 <li>Minkowski Sum Tutorial</li>
                                 <li>Voronoi Basic Tutorial</li>
- <li>Voronoi Advanced Tutorial</li>
+ <li>Voronoi Advanced Tutorial</li>
                         </ul>
                 </div>
                 <h3 class="navbar">Polygon Sponsor</h3>
@@ -120,7 +122,8 @@
 should be of integer type; 2) input segments should not intersect
 except their endpoints. While the first restriction is permanent (it
 allows to give waranties for algorithm output precision and execution),
-the second one may be waved in the future releases. Strong sides of the
+the second one may be resolved using Boost.Polygon functionality.
+Strong sides of the
 library and main benefits comparing to other implementations are
 discussed in the following paragraphs.<span style="font-weight: bold;"></span><br>
       
@@ -278,11 +281,11 @@
 belong to those areas.</li>
         <li>Implementing data structure built on top of Voronoi diagram that allows to execute nearest neighbour queries in O(log N) time.<br>
 Note: this would be sort of kd-tree data structure built on top of bounding rectangles around Voronoi cells.</li>
+
         <li>Providing interface to retrieve convex hull of a set of
 points and segments from Voronoi builder one's the Voronoi diagram is
-constructed in O(N) time.</li>
- <li>Dropping restriction on non-intersecting input geometries.<br>
-Note: this means that library will also compute segment intersections if such exist.</li>
+constructed in O(N) time.<br>
+</li>
         <li>Closer integration with interfaces and functionality of Boost Polygon Library.<br>
         </li>
       </ul>
@@ -292,14 +295,15 @@
         <li>Support of other types of distance metrics.</li>
         <li>Construction of constrained Delaunay triangulation.</li>
         <li>Support of circle input geometries.</li>
+ <li>Dropping restriction on non-intersecting input geometries.</li>
+
       </ul>
 Based on the community suggestions priorities may be changed.<br>
       
       <h2>Theoretical Research<br>
 
- </h2>
-
-Voronoi was developed as part of Google Summer of Code 2010. The
+ </h2>Voronoi
+was developed as part of Google Summer of Code 2010. The
 library was actively maintained for the last two years and involved
 strong math research in the field of algorithms, data structures,
 relative error arithmetic and numerical robustness. Nowadays one can
@@ -308,7 +312,8 @@
 benchmarks nobody else can reproduce. The opposite story is with
 Voronoi. We provide pure implementation and benchmarks one may run on
 his PC. In case community finds it useful we will incrementally
-add more documentation on the theoretical side of our realization.<br>
+add more documentation on the theoretical side of our realization. The
+authors would like to acknowledge Steven Fortune's article <span style="font-family: Arial,Helvetica,sans-serif;"><span style="font-weight: bold;"></span></span>"A Sweepline algorithm for Voronoi diagrams", that contains fundamental ideas of the current implementation.<br>
 
 
 

Modified: sandbox/gtl/libs/polygon/benchmark/Jamfile.v2
==============================================================================
--- sandbox/gtl/libs/polygon/benchmark/Jamfile.v2 (original)
+++ sandbox/gtl/libs/polygon/benchmark/Jamfile.v2 2012-04-06 17:06:39 EDT (Fri, 06 Apr 2012)
@@ -5,23 +5,32 @@
 
 import testing ;
 
-# It took five hours to configure CGAL.
-# If you want to run the benchmarks specify the following paths and
-# make sure that following libraries are compiled and do exist.
-# Good luck!
-path-constant CGAL_ROOT : "d:/Programming/CGAL-4.0" ;
-path-constant GMP_ROOT : "d:/Programming/CGAL-4.0/auxiliary/gmp" ;
+# Windows
+# It took five hours to configure CGAL on Windows. Good luck!
+#path-constant CGAL_ROOT : "d:/Programming/CGAL-4.0" ;
+#project polygon-test
+# :
+# requirements
+# <include>$(CGAL_ROOT)/include
+# <library>$(CGAL_ROOT)/lib/libCGAL-vc90-mt-4.0.lib
+# <library>$(CGAL_ROOT)/lib/libCGAL_Core-vc90-mt-4.0.lib
+# <include>$(GMP_ROOT)/auxiliary/gmp/include
+# <library>$(GMP_ROOT)/auxiliary/gmp/lib/libgmp-10.lib
+# <library>$(GMP_ROOT)/auxiliary/gmp/lib/libmpfr-4.lib
+# <library>$(BOOST_ROOT)/libs/thread/build//boost_thread
+# <library>$(BOOST_ROOT)/lib/libboost_thread-vc90-mt-1_48.lib
+# ;
+
+# Linux
+# If follow official documentation of CGAL it takes 30 mins to
+# set up properly CGAL and required libraries (GMP, MPFR).
+path-constant CGAL_ROOT : "/home/slevin/Workspace/Libraries/CGAL" ;
 project polygon-test
     :
     requirements
         <include>$(CGAL_ROOT)/include
- <include>$(GMP_ROOT)/include
- <library>$(BOOST_ROOT)/libs/thread/build//boost_thread
- <library>$(BOOST_ROOT)/lib/libboost_thread-vc90-mt-1_48.lib
- <library>$(GMP_ROOT)/lib/libgmp-10.lib
- <library>$(GMP_ROOT)/lib/libmpfr-4.lib
- <library>$(CGAL_ROOT)/lib/libCGAL-vc90-mt-4.0.lib
- <library>$(CGAL_ROOT)/lib/libCGAL_Core-vc90-mt-4.0.lib
+ <library>$(CGAL_ROOT)/lib/libCGAL.so
+ <library>$(CGAL_ROOT)/lib/libCGAL_Core.so
     ;
 
 alias "benchmark-points"

Modified: sandbox/gtl/libs/polygon/benchmark/benchmark_points.txt
==============================================================================
--- sandbox/gtl/libs/polygon/benchmark/benchmark_points.txt (original)
+++ sandbox/gtl/libs/polygon/benchmark/benchmark_points.txt 2012-04-06 17:06:39 EDT (Fri, 06 Apr 2012)
@@ -17,3 +17,24 @@
 | 10000 | 100 | 0.684090 |
 | 100000 | 10 | 16.904600 |
 | 1000000 | 1 | 566.056000 |
+
+System: CPU i5-7600 2.8 GHz, 4Gb RAM.
+OS: Ubuntu 11.10 64 bit.
+Compiler: gcc 4.6.1.
+
+Boost.Polygon Voronoi of Points:
+| 10 | 100000 | 0.000013 |
+| 100 | 10000 | 0.000192 |
+| 1000 | 1000 | 0.002130 |
+| 10000 | 100 | 0.022900 |
+| 100000 | 10 | 0.274000 |
+| 1000000 | 1 | 3.290000 |
+
+CGAL Triangulation of Points:
+| 10 | 100000 | 0.000052 |
+| 100 | 10000 | 0.001150 |
+| 1000 | 1000 | 0.016680 |
+| 10000 | 100 | 0.297900 |
+| 100000 | 10 | 8.047000 |
+| 1000000 | 1 | 315.740000 |
+

Modified: sandbox/gtl/libs/polygon/benchmark/benchmark_segments.txt
==============================================================================
--- sandbox/gtl/libs/polygon/benchmark/benchmark_segments.txt (original)
+++ sandbox/gtl/libs/polygon/benchmark/benchmark_segments.txt 2012-04-06 17:06:39 EDT (Fri, 06 Apr 2012)
@@ -17,3 +17,24 @@
 | 10000 | 100 | 2.561340 |
 | 100000 | 10 | 49.314600 |
 | 1000000 | 1 | 1640.830000 |
+
+System: CPU i5-7600 2.8 GHz, 4Gb RAM.
+OS: Ubuntu 11.10 64 bit.
+Compiler: gcc 4.6.1.
+
+Boost.Polygon Voronoi of Segments:
+| 10 | 100000 | 0.000167 |
+| 100 | 10000 | 0.002044 |
+| 1000 | 1000 | 0.020840 |
+| 10000 | 100 | 0.213500 |
+| 100000 | 10 | 2.257000 |
+| 1000000 | 1 | 22.600000 |
+
+CGAL Triangulation of Segments:
+| 10 | 100000 | 0.000485 |
+| 100 | 10000 | 0.007053 |
+| 1000 | 1000 | 0.084670 |
+| 10000 | 100 | 1.267500 |
+| 100000 | 10 | 25.703000 |
+| 1000000 | 1 | 951.250000 |
+


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk