|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r77090 - sandbox/gtl/doc
From: sydorchuk.andriy_at_[hidden]
Date: 2012-02-21 18:35:40
Author: asydorchuk
Date: 2012-02-21 18:35:39 EST (Tue, 21 Feb 2012)
New Revision: 77090
URL: http://svn.boost.org/trac/boost/changeset/77090
Log:
Updating docs.
Text files modified:
sandbox/gtl/doc/index.htm | 111 ++++++++++++++++++++-------------------
sandbox/gtl/doc/voronoi_ctype_traits.htm | 66 +++++------------------
2 files changed, 72 insertions(+), 105 deletions(-)
Modified: sandbox/gtl/doc/index.htm
Modified: sandbox/gtl/doc/voronoi_ctype_traits.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
==============================================================================
--- sandbox/gtl/doc/index.htm (original)
+++ sandbox/gtl/doc/index.htm 2012-02-21 18:35:39 EST (Tue, 21 Feb 2012)
@@ -1,15 +1,14 @@
<!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>
- <meta http-equiv="content-type" content="text/html;charset=ISO-8859-1">
- <!-- <link type="text/css" rel="stylesheet" href="adobe_source.css"> -->
-<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0"><tbody><tr>
+--><title>Boost Polygon Library: Main Page</title>
+
+ <meta http-equiv="content-type" content="text/html;charset=ISO-8859-1" /><!-- <link type="text/css" rel="stylesheet" href="adobe_source.css"> --></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 border="0" src="images/boost.png" width="277" height="86"><a title="www.boost.org home page" href="http://www.boost.org/" tabindex="2" style="border: medium none ;">
+ <img src="images/boost.png" border="0" height="86" width="277" /><a title="www.boost.org home page" href="http://www.boost.org/" tabindex="2" style="border: medium none ;">
</a>
</div>
<div style="margin: 5px;">
@@ -62,7 +61,7 @@
</div>
<h3 class="navbar">Polygon Sponsor</h3>
<div style="padding: 5px;" align="center">
- <img border="0" src="images/intlogo.gif" width="127" height="51"><a title="www.adobe.com home page" href="http://www.adobe.com/" tabindex="2" style="border: medium none ;">
+ <img src="images/intlogo.gif" border="0" height="51" width="127" /><a title="www.adobe.com home page" href="http://www.adobe.com/" tabindex="2" style="border: medium none ;">
</a>
</div>
</td>
@@ -70,7 +69,7 @@
<!-- End Header -->
-<br>
+<br />
<p>
</p><h1>THE BOOST.POLYGON LIBRARY</h1>
<p>The Boost.Polygon library provides algorithms focused on manipulating planar
@@ -85,20 +84,22 @@
Boost.Polygon library is not intended to cover all of computational
geometry in its scope, and provides a set of capabilities for working with
coordinates, points, intervals and rectangles that are needed to support
-implementing and interacting with polygon data structures and algorithms. </p><img border="0" src="images/hand.png" width="837" height="277"><p>
-One of the important features of the library is implementation of generic
-sweepline algorithm to build Voronoi diagrams in 2D (developed as part of GSoC
-2010 program). Voronoi diagram datastructure has applications in image
-segmentation, optical character recognition, nearest neighbor queries execution,
-etc. It is closely related with other computational geometry concepts: delaunay
-triangulation, medial axis, straight skeleton, largest empty circle.
-Boost.Polygon library provides interface to construct Voronoi diagrams of points
-figure a and line segments figure b (the last could be used to discretize any
-two-dimensional curve). Figure c contains example of medial axis of a non-convex
-polygon. The implementation outperforms most of the known commercial and
-non-commercial libraries in both efficiency and numerical robustness aspects.
+implementing and interacting with polygon data structures and algorithms. </p><img src="images/hand.png" border="0" height="277" width="837" /><p>
+One of the important features of the library is implementation of
+generic sweepline algorithm to build Voronoi diagrams in 2D (developed
+as part of GSoC 2010 program). Voronoi diagram datastructure has
+applications in image segmentation, optical character recognition,
+nearest neighbor queries execution. It is closely related with other
+computational geometry concepts: delaunay triangulation, medial axis,
+straight skeleton, largest empty circle. Boost.Polygon library
+provides interface to construct Voronoi diagrams of points figure a and
+line segments figure b (the last could be used to discretize any
+two-dimensional curve). Figure c contains example of medial axis of a
+non-convex polygon. The implementation outperforms most of the known
+commercial and non-commercial libraries in both efficiency and
+numerical robustness aspects.
</p>
-<p><img border="0" src="images/voronoi.png" width="900" height="300"></p>
+<p><img src="images/voronoi.png" border="0" height="300" width="900" /></p>
<p>
The coordinate data type is a template parameter of all data types and
algorithms provided by the library, and is expected to be integral (this is
@@ -124,40 +125,39 @@
intended to demonstrate what could be achieved with ease by a C++-concepts based
library interface, but is implemented based on current language features. This API makes
the following code snippet that operates on non-library geometry types possible:</p>
-<p:colorscheme
- colors="#ffffff,#000000,#808080,#000000,#bbe0e3,#333399,#009999,#99cc00"/>
+<p:colorscheme colors="#ffffff,#000000,#808080,#000000,#bbe0e3,#333399,#009999,#99cc00">
-<div v:shape="_x0000_s1026" class="O">
- <div style="text-align:justify;mso-char-wrap:1;mso-kinsoku-overflow:1">
+</p:colorscheme><div v:shape="_x0000_s1026" class="O">
+ <div style="text-align: justify;">
<nobr>
- <span style="font-family: Courier New; mso-ascii-font-family: Courier New; mso-bidi-font-family: Arial; mso-hansi-font-family: Courier New">
- void foo(list<CPolygon>& result, const list<CPolygon>& a, </span></nobr><br>
- <span style="font-family: Courier New">
+ <span style="font-family: Courier New;">
+ void foo(list<CPolygon>& result, const list<CPolygon>& a, </span></nobr><br />
+ <span style="font-family: Courier New;">
</span><nobr>
- <span style="font-family: Courier New; mso-ascii-font-family: Courier New; mso-bidi-font-family: Arial; mso-hansi-font-family: Courier New">
+ <span style="font-family: Courier New;">
const list<CPolygon>&
b, int deflateValue) { </span></nobr></div>
- <div style="text-align:justify;mso-char-wrap:1;mso-kinsoku-overflow:1">
+ <div style="text-align: justify;">
<nobr>
-<span style="font-family: Courier New; mso-ascii-font-family: Courier New; mso-bidi-font-family: Arial; mso-hansi-font-family: Courier New">
+<span style="font-family: Courier New;">
CBoundingBox domainExtent; </span></nobr></div>
- <div style="text-align:justify;mso-char-wrap:1;mso-kinsoku-overflow:1">
+ <div style="text-align: justify;">
<nobr>
- <span style="font-family: Courier New; mso-ascii-font-family: Courier New; mso-bidi-font-family: Arial; mso-hansi-font-family: Courier New">
- <span style="mso-spacerun:yes"> </span> using namespace boost::polygon::operators; </span></nobr></div>
- <div style="text-align:justify;mso-char-wrap:1;mso-kinsoku-overflow:1">
+ <span style="font-family: Courier New;">
+ <span style=""> </span> using namespace boost::polygon::operators; </span></nobr></div>
+ <div style="text-align: justify;">
<nobr>
- <span style="font-family: Courier New; mso-ascii-font-family: Courier New; mso-bidi-font-family: Arial; mso-hansi-font-family: Courier New">
- <span style="mso-spacerun:yes"> </span>
+ <span style="font-family: Courier New;">
+ <span style=""> </span>
boost::polygon::extents(domainExtent, a); </span></nobr></div>
- <div style="text-align:justify;mso-char-wrap:1;mso-kinsoku-overflow:1">
+ <div style="text-align: justify;">
<nobr>
- <span style="font-family: Courier New; mso-ascii-font-family: Courier New; mso-bidi-font-family: Arial; mso-hansi-font-family: Courier New">
- <span style="mso-spacerun:yes"> </span>result += (b &
+ <span style="font-family: Courier New;">
+ <span style=""> </span>result += (b &
domainExtent) ^ (a - deflateValue); </span></nobr></div>
- <div style="text-align:justify;mso-char-wrap:1;mso-kinsoku-overflow:1">
+ <div style="text-align: justify;">
<nobr>
- <span style="font-family: Courier New; mso-ascii-font-family: Courier New; mso-bidi-font-family: Arial; mso-hansi-font-family: Courier New">
+ <span style="font-family: Courier New;">
}</span></nobr></div>
</div>
<p>In the code snippet above the hypothetical polygon type CPolygon has been
@@ -168,10 +168,11 @@
It is considerably more typing to describe this usage of the API than to code
it, and the description is not much clearer than the code itself.
A picture is worth a thousand words.</p>
-<p><img border="0" src="images/foo.PNG" width="432" height="371"></p>
-<p>In Boost.Polygon operations such as those shown above are free functions named for what they do, or are overloads of C++ operators that make it
-easy to infer from reading the code what to expect. Operators are
-contained in the namespace <font face="Courier New">boost::polygon::operators</font>
+<p><img src="images/foo.PNG" border="0" height="371" width="432" /></p>
+<p>In Boost.Polygon operations such as those shown above are free
+functions named for what they do, or are overloads of C++ operators
+that make it easy to infer from reading the code what to expect.
+Operators are contained in the namespace <font face="Courier New">boost::polygon::operators</font>
so that they can be used outside the <font face="Courier New">boost::polygon</font>
namespace without bringing in the entire <font face="Courier New">boost::polygon</font>
namespace. Following the
@@ -212,7 +213,7 @@
Using the n-layer map-overlay algorithm on polygon data</li>
</ul>
-<li>Tutorials:
+</li><li>Tutorials:
<ul>
<li>Layout Versus Schematic Learn how to
apply Boost.Polygon capabilities to implement a simplified circuit
@@ -226,7 +227,7 @@
datastructure to suit your requirements. </li>
</ul>
-</ul>
+</li></ul>
<p>We would like to thank: Thomas Klimpel, Frank Mori Hess, Barend Gehrels,
@@ -240,17 +241,17 @@
process and Fernando Cacciola for graciously serving as review manager.</p>
- <tr>
+ </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" rules="none" frame="void" id="table2">
+<table class="docinfo" id="table2" frame="void" rules="none">
<colgroup>
- <col class="docinfo-name"><col class="docinfo-content">
+ <col class="docinfo-name" /><col class="docinfo-content" />
</colgroup>
- <tbody vAlign="top">
+ <tbody valign="top">
<tr>
<th class="docinfo-name">Copyright:</th>
<td>Copyright © Intel Corporation 2008-2010.</td>
@@ -263,6 +264,6 @@
<a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
http://www.boost.org/LICENSE_1_0.txt>)</td>
</tr>
-</table>
+</tbody></table>
-</html>
\ No newline at end of file
+</td></tr></tbody></table></body></html>
\ No newline at end of file
==============================================================================
--- sandbox/gtl/doc/voronoi_ctype_traits.htm (original)
+++ sandbox/gtl/doc/voronoi_ctype_traits.htm 2012-02-21 18:35:39 EST (Tue, 21 Feb 2012)
@@ -1,7 +1,7 @@
<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 border="0" src="images/boost.png" width="277" height="86"><a title="www.boost.org home page" href="http://www.boost.org/" tabindex="2" style="border: medium none ;">
+ <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" href="http://www.boost.org/" tabindex="2" style="border: medium none ;">
</a>
</div>
<div style="margin: 5px;">
@@ -29,14 +29,13 @@
<li>Connectivity Extraction</li>
<li>Property Merge 90</li>
<li>Property Merge 45</li>
- <li>Property Merge</li>
- <li>Voronoi CTypes Traits</li>
+ <li>Property Merge</li><li>Voronoi Main Page<br></li>
+ <li>Voronoi Builder Datastructure<br></li>
<li><a href="voronoi_diagram_datastructure.htm">Voronoi Diagram
Datastructure</a></li>
<li><a href="voronoi_lazy_arithmetic_concept.htm">Voronoi Lazy
Arithmetic Concept</a></li>
- <li><a href="voronoi_sweepline_algorithm.htm">Voronoi Sweepline
- Algorithm</a></li>
+
</ul>
<h3 class="navbar">Other Resources</h3>
<ul>
@@ -54,70 +53,36 @@
</div>
<h3 class="navbar">Polygon Sponsor</h3>
<div style="padding: 5px;" align="center">
- <img border="0" src="images/intlogo.gif" width="127" height="51"><a title="www.adobe.com home page" href="http://www.adobe.com/" tabindex="2" style="border: medium none ;">
+ <img src="images/intlogo.gif" border="0" height="51" width="127"><a title="www.adobe.com home page" href="http://www.adobe.com/" tabindex="2" style="border: medium none ;">
</a>
</div>
</td>
-<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
-
-<!-- End Header -->
+<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"><!-- End Header -->
<br>
-<h1>Voronoi Coordinate Types Requirements</h1>
-<p>The requirements for the coordinate type of all input and output data types
-supported by the Voronoi unit are weaker than for the rest of the Boost.Polygon
-library. The main differences are in the following: 1) The input coordinate type
-is not required to be integral (while it still should be integer type); 2) The
-output coordinate type could be integer or floating-point non built-in type.
-This additional functionality is achieved using Voronoi coordinate type traits,
-that are described in details below. Separate paragraph is dedicated to
-the default Voronoi coordinate types, that enable user to use Voronoi unit
-functionality ignoring underlying coordinate types metaprogramming.</p>
-<h1>Default Voronoi Coordinate Types</h1>
-<p>By default Voronoi unit operates with 32-bit signed integer coordinate type
-for the input objects and double coordinate type for the output geometries. This
-set up is ready to use from the box and doesn't require any additional
-configuration steps to be done. The simplest code that builds voronoi diagram
-with default coordinate types looks like this:</p>
- <div style="text-align:justify;mso-char-wrap:1;mso-kinsoku-overflow:1">
- <span style="font-family: Courier New">#include "boost/polygon/voronoi.hpp"</span><p>
- <span style="font-family: Courier New">int main() {<br>
- /* Read input points and segments.<br>
- Input coordinates should be 32-bit signed integers! */<br>
- voronoi_diagram<double> vd;<br>
- construct_voronoi(points, segments, &vd);<br>
- /* Having some fun with the output. */<br>
- }</span></p>
- <p>As you might see two lines of code do all the complex computational
- geometry procedure for you.</div>
-<h1>Voronoi Builder CType Traits</h1>
-<p>As was mentioned above Voronoi input & output coordinate types are not
-required to be built-in. To provide functionality that supports user defined
-coordinate types special technique called runtime-variable traits is used. Let's
-have a closer look at the voronoi_builder structure definition:</p>
<p>
-<font face="Courier New">template <typename T,<br>
+</p><h1>Voronoi Builder Datastructure<br></h1>Voronoi Builder datastructure provides interface to construct Voronoi diagrams. It implements sweepline algorithm that scans 2D space and constructs output geometries (voronoi edges and voronoi vertices) which are processed by Voronoi Diagram datastructure. The requirements for the input / output coordinate types of the Builder geometries are not the same as for the rest of the Boost.Polygon library. The main differences are in the following: 1) The input coordinate type
+is not required to be integral (while it still should be integer type); 2) The
+output coordinate type (for voronoi vertices) is required to be IEEE-754 floating point type. Let's have a closer look at the voronoi_builder definition:<br><br><font face="Courier New">template <typename T,<br>
typename CTT =
detail::voronoi_ctype_traits<T>,<br>
typename VP =
detail::voronoi_predicates<CTT> ><br>
-class voronoi_builder { ... };</font></p>
-<h1>Voronoi Diagram Traits</h1>
-<p>
- </p>
+class voronoi_builder { /* Implementation. */ };<br><br></font><font face="Courier New">T</font> - specifies coordinate type of the input geometries (points and segments).<br><font face="Courier New">CTT</font> - defines input / output coordinate types used by VP.<br><font face="Courier New">VP</font> - predicates kernel, that provides builder with robust and efficient predicates.<br>The Voronoi Builder datastructure is ready to use from the box with 32bit signed integer input coordinate type. The user may extend input coordinate range to other integer types (e.g. 64-bit integer), however this will also require manual set up of coordinate type traits. Default voronoi_predicates<CTT> implementaiton provides correct predicates as soon as CTT types satisfy requirements explained below. In case those requirements are not satisfied for the user provided CTT, proper VP implementation is required. The default VP implementation is highly optimized and efficient that's why it's always better to come up with a
proper CTT structure.<br><font face="Courier New"></font><h1>Member Functions<br></h1><h1>Voronoi Builder CType Traits</h1><p>The library provides default Builder coordinate type traits for the 32 bit signed integer type:</p><p>template <typename T><br>struct voronoi_ctype_traits;<br><br>template <><br>struct voronoi_ctype_traits<int32> {<br> typedef int32 int_type;<br> typedef uint32 uint_type;<br> typedef int64 int_x2_type;<br> typedef uint64 uint_x2_type;<br> typedef extended_int<128> big_int_type;<br> typedef fpt64 fpt_type;<br> typedef extended_exponent_fpt<fpt_type> efpt_type;<br> typedef ulp_comparison<fpt_type> ulp_cmp_type;<br> typedef type_converter_fpt to_fpt_converter_type;<br> typedef type_converter_efpt to_efpt_converter_type;<br> enum { ULPS = 64 };<br>};</p>
+<p>In order for the user defined traits to be consistent with default Voronoi Builder predicates implementation user should provide following set of coordinate types (assumption is made that input geometries have X-bit signed integer coordinate type):<br></p><table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2"><tbody><tr><td>int_type<br></td><td style="vertical-align: top;">At least X-bit signed integer type.<br></td></tr><tr><td style="vertical-align: top;">uint_type<br></td><td style="vertical-align: top;">At least X-bit unsigned integer type.<br></td></tr><tr><td style="vertical-align: top;">int_x2_type<br></td><td style="vertical-align: top;">At least 2X-bit signed integer type.<br></td></tr><tr><td style="vertical-align: top;">uint_x2_type<br></td><td style="vertical-align: top;">At least 2X-bit unsigned integer type.<br></td></tr><tr><td style="vertical-align: top;">big_int_type<br></td><td style="vertical-align: top;">At least 8X-bit signed integer type for voronoi
of points.<br>At least 128X-bit signed integer type for voronoi of segments.<br></td></tr><tr><td style="vertical-align: top;">fpt_type<br></td><td style="vertical-align: top;">IEEE-754 floating point type, with mantissa at least (X+20) bits and exponent able to handle 32X-bit unsigned integer type.<br></td></tr><tr><td style="vertical-align: top;">efpt_type<br></td><td style="vertical-align: top;">IEEE-754 floating point type, with mantissa at least (X+20) bits and exponent able to handle 128X-bit unsigned integer type.<br></td></tr><tr><td style="vertical-align: top;">ulp_cmp_type<br></td><td style="vertical-align: top;">Ulp comarison structure that checks if two fpt_type values are withing given ulp range (relative error range).<br></td></tr><tr><td style="vertical-align: top;">to_fpt_converter_type<br></td><td style="vertical-align: top;">Type converter structure that converts any of the integer types above plus efpt_type to the fpt_type using operator().<br></td></tr><tr><td style="vertical-align: top;
">to_efpt_converter_type<br></td><td style="vertical-align: top;">Type converter structure that converts any of the integer types above to the efpt_type using operator().<br></td></tr><tr><td style="vertical-align: top;">ULPS<br></td><td style="vertical-align: top;">Relative precision of the output geometries (approximation of relative error).<br></td></tr></tbody></table><p><br>Notes:<br>1) 5 different integer types are used (instead of a single big_int_type for everything) to slightly improve algorithm performance and memory usage.<br>2) As maximum required size of the big_int_type is known in advance library provided implementation of fixed integers could be used, which is much faster than heap-allocated big integers.<br>3) two separate floating-point types are defined because for input with 32 bit signed integer coordinates double won't be able to handle 4096 bit (128 * 32) integers as they will overflow its' exponent. On the gcc compiler it's possible to use 80-bit long doubles for both fpt types, howev
er this is not supported by msvc compiler.<br>4) efpt_type and to_efpt_converter_type are not used by voronoi of points (mocks will work fine).<br>5) for an example of the user defined voronoi coordinate type traits see Voronoi Diagram Advanced Tutorial.</p>
- <tr>
+ </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" rules="none" frame="void" id="table2">
+<table class="docinfo" id="table2" frame="void" rules="none">
<colgroup>
<col class="docinfo-name"><col class="docinfo-content">
</colgroup>
- <tbody vAlign="top">
+ <tbody valign="top">
<tr>
<th class="docinfo-name">Copyright:</th>
<td>Copyright © Intel Corporation 2008-2010.</td>
@@ -130,5 +95,6 @@
<a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
http://www.boost.org/LICENSE_1_0.txt>)</td>
</tr>
-</table>
+</tbody></table>
+</td></tr></tbody></table>
\ No newline at end of file