|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r77113 - sandbox/gtl/doc
From: sydorchuk.andriy_at_[hidden]
Date: 2012-02-24 18:32:35
Author: asydorchuk
Date: 2012-02-24 18:32:34 EST (Fri, 24 Feb 2012)
New Revision: 77113
URL: http://svn.boost.org/trac/boost/changeset/77113
Log:
Updating voronoi_builder docs.
Added:
sandbox/gtl/doc/voronoi_builder.htm
- copied, changed from r77102, /sandbox/gtl/doc/voronoi_builder_datastructure.htm
Removed:
sandbox/gtl/doc/voronoi_builder_datastructure.htm
Text files modified:
sandbox/gtl/doc/index.htm | 59 ++++-----
sandbox/gtl/doc/voronoi_builder.htm | 223 ++++++++++++++++++++++-----------------
2 files changed, 149 insertions(+), 133 deletions(-)
Modified: sandbox/gtl/doc/index.htm
==============================================================================
--- sandbox/gtl/doc/index.htm (original)
+++ sandbox/gtl/doc/index.htm 2012-02-24 18:32:34 EST (Fri, 24 Feb 2012)
@@ -1,10 +1,11 @@
<!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"> --></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">
@@ -15,35 +16,30 @@
<h3 class="navbar">Contents</h3>
<ul>
<li>Boost.Polygon Main Page</li>
- <li>Design Overview</li>
- <li>Isotropy</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 CType Traits</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>
+ <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 Builder</li>
+ <li>Voronoi Diagram Datastructure</li>
+ <li>Voronoi Lazy Arithmetic Concept</li>
</ul>
<h3 class="navbar">Other Resources</h3>
<ul>
@@ -102,10 +98,7 @@
<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
-different for Voronoi code, look at the <a href="voronoi_ctype_traits.htm">Voronoi
-CType Traits</a> page).
-Floating point coordinate data types are not supported by the algorithms
+algorithms provided by the library, and is expected to be integral. Floating point coordinate data types are not supported by the algorithms
implemented in the library due to the fact that the achieving floating point
robustness implies a different set of algorithms and generally platform specific
assumptions about floating point representations.
Copied: sandbox/gtl/doc/voronoi_builder.htm (from r77102, /sandbox/gtl/doc/voronoi_builder_datastructure.htm)
Deleted: sandbox/gtl/doc/voronoi_builder_datastructure.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_builder_datastructure.htm (original)
+++ sandbox/gtl/doc/voronoi_builder.htm 2012-02-24 18:32:34 EST (Fri, 24 Feb 2012)
@@ -1,20 +1,17 @@
-<html>
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html><head>
-<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>
+<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="width: 100%; margin: 0pt; padding: 0pt" border="0" cellpadding="0" cellspacing="0">
- <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/">
+<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">
+ <div style="margin: 5px;">
<h3 class="navbar">Contents</h3>
<ul>
<li>Boost.Polygon Main Page</li>
@@ -71,16 +68,16 @@
</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/">
+ <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 -->
+ <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"><!-- End Header -->
<br>
<p></p>
<h1>Voronoi Builder<br>
</h1>
- Voronoi builder is event generator datastructure. It implements
+ Voronoi builder is event generator structure. It implements
sweepline algorithm that scans 2D space and generates two types of
events: site events and circle events (we won't go into details what
those are exactly). Each event is reported to the output datastructure
@@ -97,102 +94,130 @@
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
+ <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>
- <span style="font-family: 'Courier New',Courier,monospace">T</span></font>
+ <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>
+ <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>
+ <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
32-bit 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>>
+ 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>
+ <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>,
+ <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>
+ <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>
+ <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>
+ <span style="font-family: 'Courier New',Courier,monospace;">CTT</span></font>
structure.<br>
<h1>Member Functions</h1>
- <table style="text-align: left; width: 100%" border="1" cellpadding="2" cellspacing="2">
- <tr>
- <td style="font-family: 'Courier New',Courier,monospace">
+ <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <tbody><tr>
+ <td style="font-family: 'Courier New',Courier,monospace;">
voronoi_builder()</td>
- <td style="vertical-align: top" width="693">Default constructor.</td>
+ <td style="vertical-align: top;" width="693">Default constructor.</td>
</tr>
<tr>
- <td style="font-family: 'Courier New',Courier,monospace">
+ <td style="vertical-align: top;"><span style="font-family: Courier New,Courier,monospace;">void insert_point(const int_type& x, const int_type& y)</span><br>
+ </td>
+ <td style="vertical-align: top;">Inserts point object with provided coordinates into Voronoi builder. <br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;"><span style="font-family: Courier New,Courier,monospace;">template <typename PointType></span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">void insert_point(const PointType& point)</span><br>
+ </td>
+ <td style="vertical-align: top;">Inserts point object into Voronoi builder.<br>
+
+ Point object should support x() and y() methods to retrieve its coordinates.<br>
+ </td>
+ </tr>
+<tr>
+ <td style="font-family: 'Courier New',Courier,monospace;">
template <typename PointIterator><br>
- void insert_points(PointIterator first_point,<br>
-
- PointIterator last_point)<br>
+ void insert_points(PointIterator first_point, PointIterator last_point)<br>
</td>
- <td style="vertical-align: top" width="693">Inserts point
+ <td style="vertical-align: top;" width="693">Inserts point
objects into Voronoi builder.<br>
- Point objects should support x() and y() methods that retrieve
+ Point objects should support x() and y() methods to retrieve
their coordinates.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace">
+ <td style="vertical-align: top;"><span style="font-family: Courier New,Courier,monospace;">void insert_segment(const int_type& x1, const int_type& y1, const int_type& x2, const int_type& y2)</span><br>
+ </td>
+ <td style="vertical-align: top;">Insert segment object with provided coordinates into Voronoi builder.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;"><span style="font-family: Courier New,Courier,monospace;">template <typename PointType></span><span style="font-family: Courier New,Courier,monospace;"><br>
+void insert_segment(const PointType& point1, const PointType& point2)</span><br>
+ </td>
+ <td style="vertical-align: top;">Insert segment object with provided endpoints into Voronoi builder.<br>
+Endpoint objects should support x() and y() methods to retrieve their coordinates.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template <typename SegmentType><br>
+void insert_segment(const SegmentType& segment)<br>
+ </td>
+ <td style="vertical-align: top;">Insert segment object into Voronoi builder.<br>
+Segment object should support low() and high() methods that retrieve segment endpoints.<br>
+Endpoint objects should support x() and y() methods to retrieve their coordinates.<br>
+ </td>
+ </tr>
+<tr>
+ <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace;">
template <typename SegmentIterator><br>
- void insert_segments(SegmentIterator first_segment,<br>
-
- SegmentIterator last_segment)<br>
+ void insert_segments(SegmentIterator first_segment, SegmentIterator last_segment)<br>
</td>
- <td style="vertical-align: top" width="693">Inserts segment
+ <td style="vertical-align: top;" width="693">Inserts segment
objects into Voronoi builder.<br>
- Segment objects should support low() and high() methods that
+ Segment objects should support low() and high() methods to
retrieve segment endpoints.<br>
- Endpoint objects should support x() and y() methods that
+ Endpoint objects should support x() and y() methods to
retrieve their coordinates.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace">
- template <typename PointIterator,<br>
- typename SegmentIterator><br>
- void insert_sites(PointIterator first_point,<br>
-
- PointIterator last_point,<br>
-
- SegmentIterator first_segment,<br>
-
- SegmentIterator last_segment)<br>
+ <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace;">
+ template <typename PointIterator, typename SegmentIterator><br>
+void insert_sites(PointIterator first_point, PointIterator last_point,
+SegmentIterator first_segment, SegmentIterator last_segment)<br>
</td>
- <td style="vertical-align: top" width="693">Inserts point and
+ <td style="vertical-align: top;" width="693">Inserts point and
segment objects into Voronoi builder.<br>
Requirements for the point and segment objects interface are
given above.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace">
+ <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace;">
template <typename OUTPUT><br>
void construct(OUTPUT *output)<br>
</td>
- <td style="vertical-align: top" width="693">Runs sweepline
+ <td style="vertical-align: top;" width="693">Runs sweepline
algorithm over the set of the inserted geometries, outputs site
and circle events to the OUTPUT datastructure. It's
responsibility of the output structure to process them. For
@@ -200,24 +225,24 @@
constructed from the Voronoi builder events, however internally
they are different datastructures, so it's up to them to process
properly events produced by the builder object. To make this
- possible OUTPUT type should provide a set of template methods
+ possible OUTPUT type should provide a set of generic methods
which are discussed in detail on <a href="voronoi_diagram.htm">
Voronoi Diagram</a> page.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace">
+ <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace;">
void clear()<br>
</td>
- <td style="vertical-align: top" width="693">Clears the list of
+ <td style="vertical-align: top;" width="693">Clears the list of
the inserted geometries.<br>
</td>
</tr>
- </table>
+ </tbody></table>
<h1>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">
+ <font style="font-family: 'Courier New',Courier,monospace;" face="Courier New">
<p>template <typename T><br>
struct voronoi_ctype_traits;<br>
<br>
@@ -243,93 +268,93 @@
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">
- <tr>
- <td style="font-family: 'Courier New',Courier,monospace">int_type<br>
+ <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
+ <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">
+ <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
+ <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">
+ <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
+ <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">
+ <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
+ <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">
+ <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,
+ <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">
+ <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,
+ <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">
+ <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
+ <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">
+ <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
+ <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">
+ <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
+ <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">
+ <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace;">
ULPS<br>
</td>
- <td style="vertical-align: top">Relative precision threshold
+ <td style="vertical-align: top;">Relative precision threshold
that triggers multi-precision predicates.<br>
</td>
</tr>
- </table>
+ </tbody></table>
<p>Notes:<br>
1) 4 different integer types are used (instead of a single big_int_type
for everything) to slightly improve algorithm performance and memory
@@ -344,13 +369,13 @@
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
+ 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>.</td>
+ 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%">
+ <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">
@@ -369,11 +394,9 @@
<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>
-</table>
-
-</body>
+</tbody></table>
-</html>
+</body></html>
\ No newline at end of file
==============================================================================
--- sandbox/gtl/doc/voronoi_builder_datastructure.htm 2012-02-24 18:32:34 EST (Fri, 24 Feb 2012)
+++ (empty file)
@@ -1,379 +0,0 @@
-<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="width: 100%; margin: 0pt; padding: 0pt" border="0" cellpadding="0" cellspacing="0">
- <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>Voronoi Main Page<br>
- </li>
- <li>Voronoi Builder<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" 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 Builder<br>
- </h1>
- Voronoi builder is event generator datastructure. It implements
- sweepline algorithm that scans 2D space and generates two types of
- events: site events and circle events (we won't go into details what
- those are exactly). Each event is reported to the output datastructure
- provided to the builder through the generic interface. The structure
- shares Voronoi name as the events generated by it correspond to the
- Voronoi diagram edges and vertices and give enought information to
- construct Voronoi diagram of a set of points and segments. 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>
- <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
- 32-bit 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</h1>
- <table style="text-align: left; width: 100%" border="1" cellpadding="2" cellspacing="2">
- <tr>
- <td style="font-family: 'Courier New',Courier,monospace">
- voronoi_builder()</td>
- <td style="vertical-align: top" width="693">Default constructor.</td>
- </tr>
- <tr>
- <td style="font-family: 'Courier New',Courier,monospace">
- template <typename PointIterator><br>
- void insert_points(PointIterator first_point,<br>
-
- PointIterator last_point)<br>
- </td>
- <td style="vertical-align: top" width="693">Inserts point
- objects into Voronoi builder.<br>
- Point objects should support x() and y() methods that retrieve
- their coordinates.<br>
- </td>
- </tr>
- <tr>
- <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace">
- template <typename SegmentIterator><br>
- void insert_segments(SegmentIterator first_segment,<br>
-
- SegmentIterator last_segment)<br>
- </td>
- <td style="vertical-align: top" width="693">Inserts segment
- objects into Voronoi builder.<br>
- Segment objects should support low() and high() methods that
- retrieve segment endpoints.<br>
- Endpoint objects should support x() and y() methods that
- retrieve their coordinates.<br>
- </td>
- </tr>
- <tr>
- <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace">
- template <typename PointIterator,<br>
- typename SegmentIterator><br>
- void insert_sites(PointIterator first_point,<br>
-
- PointIterator last_point,<br>
-
- SegmentIterator first_segment,<br>
-
- SegmentIterator last_segment)<br>
- </td>
- <td style="vertical-align: top" width="693">Inserts point and
- segment objects into Voronoi builder.<br>
- Requirements for the point and segment objects interface are
- given above.<br>
- </td>
- </tr>
- <tr>
- <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace">
- template <typename OUTPUT><br>
- void construct(OUTPUT *output)<br>
- </td>
- <td style="vertical-align: top" width="693">Runs sweepline
- algorithm over the set of the inserted geometries, outputs site
- and circle events to the OUTPUT datastructure. It's
- responsibility of the output structure to process them. For
- example both Voronoi diagram and Delaunay triangulation could be
- constructed from the Voronoi builder events, however internally
- they are different datastructures, so it's up to them to process
- properly events produced by the builder object. To make this
- possible OUTPUT type should provide a set of template methods
- which are discussed in detail on <a href="voronoi_diagram.htm">
- Voronoi Diagram</a> page.<br>
- </td>
- </tr>
- <tr>
- <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace">
- void clear()<br>
- </td>
- <td style="vertical-align: top" width="693">Clears the list of
- the inserted geometries.<br>
- </td>
- </tr>
- </table>
- <h1>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">
- <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 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>One of the most important features of the library is that Voronoi
- builder output geometries are constructed with defined relative error.
- That means the more mantissa bits the user provided fpt_type has the
- better precision of the output geometries will be. 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">
- <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">
- 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>
- </table>
- <p>Notes:<br>
- 1) 4 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>.</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>
- </table>
- </td>
- </tr>
-</table>
-
-</body>
-
-</html>