|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r77092 - sandbox/gtl/doc
From: sydorchuk.andriy_at_[hidden]
Date: 2012-02-22 16:01:07
Author: asydorchuk
Date: 2012-02-22 16:01:06 EST (Wed, 22 Feb 2012)
New Revision: 77092
URL: http://svn.boost.org/trac/boost/changeset/77092
Log:
Updating docs.
Text files modified:
sandbox/gtl/doc/voronoi_ctype_traits.htm | 371 +++++++++++++++++++++++++++++----------
1 files changed, 272 insertions(+), 99 deletions(-)
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/voronoi_ctype_traits.htm (original)
+++ sandbox/gtl/doc/voronoi_ctype_traits.htm 2012-02-22 16:01:06 EST (Wed, 22 Feb 2012)
@@ -1,100 +1,273 @@
-<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" href="http://www.boost.org/" tabindex="2" style="border: medium none ;">
- </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>Polygon 90 With Holes Concept</li>
- <li>Polygon 45 Concept</li>
- <li>Polygon 45 With Holes Concept</li>
- <li>Polygon Concept</li>
- <li>Polygon With Holes Concept</li>
- <li>Polygon 90 Set Concept</li>
- <li>Polygon 45 Set Concept</li>
- <li>Polygon Set Concept</li>
- <li>Connectivity Extraction 90</li>
- <li>Connectivity Extraction 45</li>
- <li>Connectivity Extraction</li>
- <li>Property Merge 90</li>
- <li>Property Merge 45</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>
-
- </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><a href="voronoi_diagram_basic_tutorial.htm">Voronoi Diagram
- Basic Tutorial</a></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" 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 -->
-<br>
-<p>
-</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 { /* 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>
-
-
- </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>
\ No newline at end of file
+<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" href="http://www.boost.org/" tabindex="2" style="border: medium none ;"> </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>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>
+ </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><a href="voronoi_diagram_basic_tutorial.htm">Voronoi
+Diagram Basic Tutorial</a></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" 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 --> <br>
+ <p> </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"><span style="font-family: Courier New,Courier,monospace;">template
+<typename T,</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+typename CTT =
+detail::voronoi_ctype_traits<T>,</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+typename VP =
+detail::voronoi_predicates<CTT> ></span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">class
+voronoi_builder { /* Implementation. */ };</span><br>
+ <br>
+ </font><font face="Courier New"><span style="font-family: Courier New,Courier,monospace;">T</span></font> -
+specifies coordinate
+type of the input geometries (points and segments).<br>
+ <font face="Courier New"><span style="font-family: Courier New,Courier,monospace;">CTT</span></font>
+- defines input / output
+coordinate types used by VP.<br>
+ <font face="Courier New"><span style="font-family: Courier New,Courier,monospace;">VP</span></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<<font face="Courier New"><span style="font-family: Courier New,Courier,monospace;">CTT</span></font>>
+implementaiton provides correct
+predicates as soon as <font face="Courier New"><span style="font-family: Courier New,Courier,monospace;">CTT</span></font>
+types satisfy requirements explained below.
+In case those requirements are not satisfied for the user provided <font face="Courier New"><span style="font-family: Courier New,Courier,monospace;">CTT</span></font>,
+proper <font face="Courier New"><span style="font-family: Courier New,Courier,monospace;">VP</span></font>
+implementation is required. The default <font face="Courier New"><span style="font-family: Courier New,Courier,monospace;">VP</span></font>
+implementation is
+highly optimized and efficient that's why it's always better to come up
+with a proper <font face="Courier New"><span style="font-family: Courier New,Courier,monospace;">CTT</span></font>
+structure.<br>
+ <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>
+ <font style="font-family: Courier New,Courier,monospace;" face="Courier New">
+ <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>
+ </font>
+ <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 style="font-family: Courier New,Courier,monospace;">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; font-family: Courier New,Courier,monospace;">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; font-family: Courier New,Courier,monospace;">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; font-family: Courier New,Courier,monospace;">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; font-family: Courier New,Courier,monospace;">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; font-family: Courier New,Courier,monospace;">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; font-family: Courier New,Courier,monospace;">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; font-family: Courier New,Courier,monospace;">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; font-family: Courier New,Courier,monospace;">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; font-family: Courier New,Courier,monospace;">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; font-family: Courier New,Courier,monospace;">ULPS<br>
+ </td>
+ <td style="vertical-align: top;">Relative precision
+threshold that triggers multi-precision predicates.<br>
+ </td>
+ </tr>
+ </tbody>
+ </table>
+ <p>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,
+however this is not supported by msvc compiler.<br>
+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 voronoi coordinate type traits
+see <a href="voronoi_diagram_advanced_tutorial.htm">Voronoi Diagram
+Advanced Tutorial</a>.</p>
+ </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>