|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r77703 - sandbox/gtl/doc
From: sydorchuk.andriy_at_[hidden]
Date: 2012-04-01 17:49:47
Author: asydorchuk
Date: 2012-04-01 17:49:46 EDT (Sun, 01 Apr 2012)
New Revision: 77703
URL: http://svn.boost.org/trac/boost/changeset/77703
Log:
Updating docs. Adding the last documentation page template.
Added:
sandbox/gtl/doc/voronoi_benchmark.htm (contents, props changed)
Text files modified:
sandbox/gtl/doc/index.htm | 5 ++-
sandbox/gtl/doc/voronoi_basic_tutorial.htm | 3 +
sandbox/gtl/doc/voronoi_builder.htm | 7 +++--
sandbox/gtl/doc/voronoi_main.htm | 43 ++++++++++++++++++++++++++++-----------
sandbox/gtl/doc/voronoi_predicates.htm | 16 +++++++++++---
sandbox/gtl/doc/voronoi_robust_fpt.htm | 12 ++++++++--
6 files changed, 61 insertions(+), 25 deletions(-)
Modified: sandbox/gtl/doc/index.htm
==============================================================================
--- sandbox/gtl/doc/index.htm (original)
+++ sandbox/gtl/doc/index.htm 2012-04-01 17:49:46 EDT (Sun, 01 Apr 2012)
@@ -1,5 +1,6 @@
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
-<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"><head><!--
+<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"><head>
+<!--
Copyright 2009-2010 Intel Corporation
license banner
--><title>Boost Polygon Library: Main Page</title>
@@ -240,7 +241,7 @@
to construct, traverse, visualize, associate data with Voronoi diagrams without digging into library details.</li>
<li>Voronoi Advanced Tutorial
Learn how to configure Voronoi builder and Voronoi diagram
- datastructures to suit your requirements. </li>
+ datastructure with user provided coordinate types. </li>
</ul>
</li></ul>
Modified: sandbox/gtl/doc/voronoi_basic_tutorial.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_basic_tutorial.htm (original)
+++ sandbox/gtl/doc/voronoi_basic_tutorial.htm 2012-04-01 17:49:46 EDT (Sun, 01 Apr 2012)
@@ -7,6 +7,7 @@
+
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Polygon Usage</title></head><body>
<h1>Voronoi Basic Tutorial<br>
@@ -255,7 +256,7 @@
to notice that construction of the Voronoi diagram takes only two lines
of code, everything else is about initializing input data structures,
traversing Voronoi graph, associating data with diagram primitives and
-using Voronoi utililities. In
+using Voronoi utilities. In
default mode Voronoi diagram operates with signed int (32 bit) input
coordinate type and double (64 bit) output coordinate type. In Voronoi Advanced Tutorial we explain why this is enough in 95% of problems and how to configure algorithm coordinate types for the other 5%.<br>
<span style="font-family: Courier New,Courier,monospace;"></span><br>
Added: sandbox/gtl/doc/voronoi_benchmark.htm
Modified: sandbox/gtl/doc/voronoi_builder.htm
Modified: sandbox/gtl/doc/voronoi_main.htm
Modified: sandbox/gtl/doc/voronoi_predicates.htm
Modified: sandbox/gtl/doc/voronoi_robust_fpt.htm
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
==============================================================================
--- (empty file)
+++ sandbox/gtl/doc/voronoi_benchmark.htm 2012-04-01 17:49:46 EDT (Sun, 01 Apr 2012)
@@ -0,0 +1,121 @@
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head>
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+<meta http-equiv="Content-Language" content="en-us">
+<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title></head><body>
+
+<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
+ <tbody><tr>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ <div style="padding: 5px;" align="center">
+ <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/">
+ </a></div>
+ <div style="margin: 5px;">
+ <h3 class="navbar">Contents</h3>
+ <ul>
+ <li>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
+ <li>Isotropy</li>
+ <li>Coordinate Concept</li>
+ <li>Interval Concept</li>
+ <li>Point Concept</li>
+ <li>Rectangle Concept</li>
+ <li>Polygon 90 Concept</li>
+ <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
+ With Holes Concept</a></li>
+ <li>Polygon 45 Concept</li>
+ <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
+ With Holes Concept</a></li>
+ <li>Polygon Concept</li>
+ <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
+ Holes Concept</a></li>
+ <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
+ Concept</a></li>
+ <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
+ Concept</a></li>
+ <li>Polygon Set Concept</li>
+ <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
+ Extraction 90</a></li>
+ <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
+ Extraction 45</a></li>
+ <li><a href="gtl_connectivity_extraction.htm">Connectivity
+ Extraction</a></li>
+ <li>Property Merge 90</li>
+ <li>Property Merge 45</li>
+ <li>Property Merge</li>
+ <li><a href="voronoi_main.htm">Voronoi Main Page<br>
+</a></li>
+ <li>Voronoi Benchmark<br>
+ </li>
+ <li>Voronoi Builder</li>
+ <li><a href="voronoi_diagram.htm">Voronoi Diagram<br>
+</a></li>
+ <li>Voronoi Predicates</li>
+ <li>Voronoi Robust FPT<br>
+ </li>
+ <li>Voronoi Utils</li>
+</ul>
+ <h3 class="navbar">Other Resources</h3>
+ <ul>
+ <li>GTL Boostcon 2009 Paper</li>
+ <li><a href="GTL_boostcon_draft03.htm">GTL Boostcon 2009
+ Presentation</a></li>
+ <li>Performance Analysis</li>
+ <li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
+ <li>Voronoi Basic Tutorial</li>
+ <li><a href="voronoi_diagram_advanced_tutorial.htm">Voronoi
+ Diagram Advanced Tutorial</a></li>
+ </ul>
+ </div>
+ <h3 class="navbar">Polygon Sponsor</h3>
+ <div style="padding: 5px;" align="center">
+ <img src="images/intlogo.gif" border="0" height="51" width="127"><a title="www.adobe.com home page" tabindex="2" style="border: medium none ;" href="http://www.adobe.com/">
+ </a></div>
+ </td>
+ <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"><!-- End Header -->
+ <br>
+ <p></p>
+ <h1>Voronoi Benchmark<br>
+ </h1></td>
+ </tr>
+ <tr>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
+ <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
+ <table class="docinfo" id="table2" frame="void" rules="none">
+ <colgroup>
+ <col class="docinfo-name"><col class="docinfo-content">
+ </colgroup>
+ <tbody valign="top">
+ <tr>
+ <th class="docinfo-name">Copyright:</th>
+ <td>Copyright © Intel Corporation 2008-2010.</td>
+ </tr>
+ <tr class="field">
+ <th class="docinfo-name">License:</th>
+ <td class="field-body">Distributed under the Boost Software
+ License, Version 1.0. (See accompanying file
+ <tt class="literal"><span class="pre">LICENSE_1_0.txt</span></tt>
+ or copy at
+ <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
+ http://www.boost.org/LICENSE_1_0.txt>)</td>
+ </tr>
+ </tbody></table>
+ </td>
+ </tr>
+</tbody></table>
+
+</body></html>
\ No newline at end of file
==============================================================================
--- sandbox/gtl/doc/voronoi_builder.htm (original)
+++ sandbox/gtl/doc/voronoi_builder.htm 2012-04-01 17:49:46 EDT (Sun, 01 Apr 2012)
@@ -12,6 +12,8 @@
+
+
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title></head><body>
@@ -260,7 +262,7 @@
</td>
</tr>
</tbody></table>
- <h1>Coordinate Type Traits</h1>
+ <h1>Voronoi Coordinate Type Traits</h1>
<p>The library provides default builder coordinate type traits for the
32-bit signed integer type:</p>
<font style="font-family: 'Courier New',Courier,monospace;" face="Courier New">
@@ -381,8 +383,7 @@
4) efpt_type and to_efpt_converter_type are not used to construct
Voronoi of points (mocks will work fine).<br>
5) for an example of the user defined builder coordinate type traits see
- <a href="voronoi_diagram_advanced_tutorial.htm">Voronoi Diagram Advanced
- Tutorial</a>.</p></td>
+ advanced Voronoi tutorial.</p></td>
</tr>
<tr>
<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
==============================================================================
--- sandbox/gtl/doc/voronoi_main.htm (original)
+++ sandbox/gtl/doc/voronoi_main.htm 2012-04-01 17:49:46 EDT (Sun, 01 Apr 2012)
@@ -28,6 +28,8 @@
+
+
<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>
@@ -121,7 +123,9 @@
the second one may be waved in the future releases. 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>
- <h1>Robustness and Efficiency</h1>
+
+ <h2>Robustness and Efficiency</h2>
+
Lets explain a bit those terms. The efficiency is simply measured by
the time it takes the algorithm to execute. The robustness is a bit
@@ -144,8 +148,11 @@
Voronoi: we avoid multiprecision computations in 95% of cases using
extremely fast floating-point predicates. Yes, those are not always
exact, but we developed relative error arithmetic apparatus to identify them and switch to higher precision predicates when required.<br>
- <h1>Precision of Output Structures<br>
- </h1>
+
+ <h2>Precision of Output Structures<br>
+
+ </h2>
+
One of the extremely important results of using two types of predicates
is that library efficiently computes relatively precise coordinates of
output geometries. Here we will explain a bit what exactly
@@ -183,7 +190,9 @@
consider vertices with both coordinates that are within 2^-17 meters (8
micrometers) distance to be equal. Come on that distance is equal to
the size of bacteria. Can you even see those?<br>
- <h1>Fully Functional with Segment Inputs</h1>
+
+ <h2>Fully Functional with Segment Inputs</h2>
+
There are not many implementations of Voronoi diagrams that could
handle segment inputs, even considering commercial ones. Support of
segments allows to discretize any input geometry (circle, elipse,
@@ -193,7 +202,9 @@
medial axis transform of the arbitrary input geometry. So one may start
using it for the next generation pattern recognition or computer vision
project.<br>
- <h1>Basic and Advanced Usage Cases</h1>The main library header <span style="font-family: Courier New,Courier,monospace;">voronoi.hpp</span> defines following static functions:<br>
+
+ <h2>Basic and Advanced Usage Cases</h2>
+The main library header <span style="font-family: Courier New,Courier,monospace;">voronoi.hpp</span> defines following static functions:<br>
<br>
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
<tbody>
@@ -237,17 +248,22 @@
<span style="font-family: Courier New,Courier,monospace;">voronoi_diagram<double> vd;</span><br style="font-family: Courier New,Courier,monospace;">
<span style="font-family: Courier New,Courier,monospace;">construct_voronoi(points, segments, &vd);</span><br>
<br>
-Isn't that simple? The library also provides clear interfaces to associate user data with output geometries, efficiently traverse Voronoi graph and utilities to visualize output primitives (e.g. discretization of parabolic edges, clipping of linear edges). More details on those is covered in the basic Voronoi tutorial. Advanced usage of the library with configuration of the coordinate types is explained in the advanced Voronoi tutorial.<br>
+Isn't that simple? The library also provides clear interfaces to associate user data with output geometries, efficiently traverse Voronoi graph and utilities to visualize output primitives (e.g. discretization of parabolic edges, clipping of linear edges). More details on those is covered in the basic Voronoi tutorial. Advanced usage of the library with configuration of the coordinate types is explained in the advanced Voronoi tutorial.<br>
- <h1>Extendable for User Provided Coordinate Types</h1>
-Voronoi implementation is coordinate type agnostic. That means that as soon as user provided types satisfy set of Voronoi builder coordinate type traits restrictions
+
+ <h2>Extendable for User Provided Coordinate Types</h2>
+
+Voronoi implementation is coordinate type agnostic. That means that as soon as user provided types satisfy set of Voronoi builder coordinate type traits restrictions
and implement library required methods no changes are requied neither
from algorithm, nor from predicates implementation. So it's possible to
construct Voronoi diagram for 256 bit integer input coordinate type and
512 bit output floating-pont type without changing any internal code.<br>
- <h1>Bright Future<br>
- </h1>
+
+ <h2>Bright Future<br>
+
+ </h2>
+
Below one may find list of main directions for the future development of the library.<br>
<br>
High-priority tasks that already have approximate implementation plan (some of those may be proposed as future GSoC projects):<br>
@@ -278,8 +294,11 @@
<li>Support of circle input geometries.</li>
</ul>
Based on the community suggestions priorities may be changed.<br>
- <h1>Theoretical Research<br>
- </h1>
+
+ <h2>Theoretical Research<br>
+
+ </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,
==============================================================================
--- sandbox/gtl/doc/voronoi_predicates.htm (original)
+++ sandbox/gtl/doc/voronoi_predicates.htm 2012-04-01 17:49:46 EDT (Sun, 01 Apr 2012)
@@ -12,6 +12,8 @@
+
+
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title></head><body>
@@ -54,7 +56,8 @@
<li>Property Merge 90</li>
<li>Property Merge 45</li>
<li>Property Merge</li>
- <li>Voronoi Main</li>
+ <li><a href="voronoi_main.htm">Voronoi Main Page<br>
+</a></li>
<li>Voronoi Benchmark</li>
<li>Voronoi Builder<br>
@@ -104,7 +107,9 @@
geometries you'll get. This
is a very handy functionality as it allows to improve output precision
simply providing 3rd party IEEE-754 like floating-point types.<br>
- <h1>Geometric Predicates</h1>
+
+ <h2>Geometric Predicates</h2>
+
The main issues with implementation of any complex geometric
algorithm arise when dealing with robustness of geometric predicates.
Usually this
@@ -138,7 +143,9 @@
arithmetic and multiple
precision computations.<br>
- <h1>Lazy Arithmetic</h1>Lazy
+
+ <h2>Lazy Arithmetic</h2>
+Lazy
arithmetic is based on usage of IEEE-754 floating-point types to evaluate an expression. While this approach has a good speed
performance it doesn't produce reliable results all the time (as in the
example above). The way to solve the issue is apart from computing
@@ -147,7 +154,8 @@
come up with two decisions: 1) output the value; 2) recompute the
expression using multi precision type. The way relative errors are
evaluated is explained in the Voronoi Robust FPT section.<br>
-<h1>Multiple Precision Arithmetic</h1>In the vast majority of cases
+ <h2>Multiple Precision Arithmetic</h2>
+In the vast majority of cases
lazy arithmetic approach produces correct result thus furhter
processing is not required. In other cases Voronoi defined or user
provided multiple precision types are used to produce correct result.
==============================================================================
--- sandbox/gtl/doc/voronoi_robust_fpt.htm (original)
+++ sandbox/gtl/doc/voronoi_robust_fpt.htm 2012-04-01 17:49:46 EDT (Sun, 01 Apr 2012)
@@ -12,6 +12,7 @@
+
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title></head><body>
@@ -102,7 +103,9 @@
arithmetic predicates or functors that compute values with known
relative error.<br>
- <h1>Robust Fpt Type</h1>
+
+ <h2>Robust Fpt Type</h2>
+
Robust
fpt (robust floating-point type)
- represents IEEE-754 floating-point type wrapper that also contains
@@ -123,7 +126,9 @@
floating-point implementation should be equal to 1 machine epsilon. <br>
- <h1>Robust Difference Type</h1>Robust
+
+ <h2>Robust Difference Type</h2>
+Robust
difference type -
represents expression wrapper that holds positive and negative partial
sums of the expression in a separate values in order to avoid
@@ -155,7 +160,8 @@
diference only when the result is required. And did I mention that
positive and negative values might be of robust fpt type, that's why
relative error is always known for the expression result.<br>
-<h1>Robust Sqrt Expression Structure</h1>
+ <h2>Robust Sqrt Expression Structure</h2>
+
Robust square root expression structure allows to compute results of
expression that contains square roots with predefined relative error.
As an example consider following expression:<br>