Boost-Commit :

Date view	Thread view	Subject view	Author view

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

Next message: christophe.j.henry_at_[hidden]: "[Boost-commit] svn:boost r77793 - trunk/boost/msm/back"
Previous message: sydorchuk.andriy_at_[hidden]: "[Boost-commit] svn:boost r77791 - sandbox/gtl/libs/polygon/benchmark"

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 |
+

Next message: christophe.j.henry_at_[hidden]: "[Boost-commit] svn:boost r77793 - trunk/boost/msm/back"
Previous message: sydorchuk.andriy_at_[hidden]: "[Boost-commit] svn:boost r77791 - sandbox/gtl/libs/polygon/benchmark"

Date view	Thread view	Subject view	Author view

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