|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r77955 - in sandbox/gtl: boost/polygon doc
From: sydorchuk.andriy_at_[hidden]
Date: 2012-04-13 17:09:35
Author: asydorchuk
Date: 2012-04-13 17:09:34 EDT (Fri, 13 Apr 2012)
New Revision: 77955
URL: http://svn.boost.org/trac/boost/changeset/77955
Log:
Updating documentation.
Text files modified:
sandbox/gtl/boost/polygon/voronoi_builder.hpp | 9 +-
sandbox/gtl/doc/voronoi_builder.htm | 121 ++++++++++++++++++++++-----------------
sandbox/gtl/doc/voronoi_diagram.htm | 18 +++--
sandbox/gtl/doc/voronoi_main.htm | 34 +++++-----
4 files changed, 103 insertions(+), 79 deletions(-)
Modified: sandbox/gtl/boost/polygon/voronoi_builder.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi_builder.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi_builder.hpp 2012-04-13 17:09:34 EDT (Fri, 13 Apr 2012)
@@ -55,13 +55,13 @@
template <typename PointType>
void insert(const PointType& point,
- typename enable_if<typename gtl_if<typename is_point_concept<typename geometry_concept<PointType>::type>::type>::type>::type * = 0) {
+ typename enable_if<typename gtl_if<typename is_point_concept<typename geometry_concept<PointType>::type>::type>::type>::type * = 0) {
insert_point(x(point), y(point));
}
template <typename PointIterator>
void insert(PointIterator first_point, PointIterator last_point,
- typename enable_if<typename gtl_if<typename is_point_concept<typename geometry_concept<typename std::iterator_traits<PointIterator>::value_type>::type>::type>::type>::type * = 0) {
+ typename enable_if<typename gtl_if<typename is_point_concept<typename geometry_concept<typename std::iterator_traits<PointIterator>::value_type>::type>::type>::type>::type * = 0) {
// Create a site event from each input point.
for (PointIterator it = first_point; it != last_point; ++it) {
insert(*it);
@@ -86,8 +86,9 @@
}
template <typename PointType>
- void insert_segment(const PointType& point1, const PointType& point2) {
- insert_segment(point1.x(), point1.y(), point2.x(), point2.y());
+ void insert_segment(const PointType& point1, const PointType& point2,
+ typename enable_if<typename gtl_if<typename is_point_concept<typename geometry_concept<PointType>::type>::type>::type>::type * = 0) {
+ insert_segment(x(point1), y(point1), x(point2), y(point2));
}
template <typename SegmentType>
Modified: sandbox/gtl/doc/voronoi_builder.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_builder.htm (original)
+++ sandbox/gtl/doc/voronoi_builder.htm 2012-04-13 17:09:34 EDT (Fri, 13 Apr 2012)
@@ -1,6 +1,7 @@
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head>
+
<meta http-equiv="Content-Language" content="en-us">
@@ -74,11 +75,11 @@
<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>
-
<h1>Voronoi Builder<br>
</h1>
+
Voronoi builder is the event generator structure. It implements the <a href="http://www.ams.org/samplings/feature-column/fcarc-voronoi">sweepline
-algorithm</a> that scans 2D space and generates two types of events:
+algorithm</a> that scans a 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 data structure builder.
The structure shares Voronoi name as the events generated by it
@@ -91,7 +92,9 @@
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 declaration:<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;">
@@ -104,34 +107,36 @@
<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 the robust and
-efficient predicates.<br>
+- predicate kernel, that provides builder with the robust and
+efficient predicates and functors.<br>
+
The Voronoi builder data structure is ready to use from the box with
32-bit signed integer input coordinate type. The user may extend the
input coordinate range to the other integer types (e.g. 64-bit
integer), however this will also require manual set up of the
coordinate type traits. Default voronoi_predicates<<font face="Courier New"><span style="font-family: 'Courier New',Courier,monospace;">CTT</span></font>>
-structure provides correct predicates as soon as <font face="Courier New"> <span style="font-family: 'Courier New',Courier,monospace;">CTT</span></font>
-types satisfy the requirements explained below. In case those
+structure provides correct predicates as soon as types defined by <font face="Courier New"> <span style="font-family: 'Courier New',Courier,monospace;">CTT</span></font>
+satisfy the requirements explained in the end of this page. 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>
+implementation is required.<br>
<h2>Important</h2>
-We encourage users to use default static methods defined in the voronoi.hpp header to construct Voronoi diagram. However in the following cases Voronoi builder data structure should be used explicitly:<br>
+
+We encourage users to use default static methods defined in the voronoi.hpp
+header to construct Voronoi diagram, however it's always possible to
+use Voronoi builder explicitly. The geometry types inserted into the
+builder should model apropriate Boost.Polygon concepts (e.g. point concept, segment concept). If it's too complicated for the user to follow the concept principles there are two solutions:<br>
+
+
<ul>
- <li>User provided point type doesn't conform x() and y() access methods to retrieve its coordinates;</li>
- <li>User provided segment type doesn't conforms low() and high() access methods to retrieve its endpoints;</li>
- <li>User provided container of points / segments doesn't support forward iterator using the increment operator++;</li>
- <li>User needs to configure coordinate type domain or predicates the library operates with.</li>
+<li>use Voronoi builder insertion methods, that accept geometry coordinates</li><li>use Boost.Polygon native classes (e.g. point_data), that already model appropriate concepts</li>
</ul>
-
- <h2>Member Functions</h2>
+<h2>Member Functions</h2>
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
<tbody>
<tr>
@@ -141,37 +146,33 @@
constructor.</td>
</tr>
<tr>
- <td style="vertical-align: top;"><span style="font-family: Courier New,Courier,monospace;">void insert_point(<br>
- const int_type& x,<br>
- const int_type& y)</span><br>
+ <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
-the specified coordinates into the Voronoi builder. <br>
+ <td style="vertical-align: top;">Inserts a point object with
+the specified coordinates into the Voronoi builder.
</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>
+insert(const PointType& point)</span><br>
</td>
- <td style="vertical-align: top;">Inserts point object into
+ <td style="vertical-align: top;">Inserts a point object into
the Voronoi builder.<br>
-Point object should support x() and y() methods to retrieve its
-coordinates.<br>
+
+Point object should be a model of the point concept.
</td>
</tr>
<tr>
<td style="font-family: 'Courier New',Courier,monospace;">
template <typename PointIterator><br>
-void insert_points(<br>
- PointIterator first_point,<br>
- PointIterator last_point)<br>
+void insert(PointIterator first_point, PointIterator last_point)<br>
</td>
<td style="vertical-align: top;" width="693">Inserts point
objects into the Voronoi builder.<br>
-Point objects should support x() and y() methods to retrieve their
-coordinates.<br>
+
+Point object should be a model of the point concept.
</td>
</tr>
<tr>
@@ -182,8 +183,8 @@
const int_type& x2,<br>
const int_type& y2)</span><br>
</td>
- <td style="vertical-align: top;">Inserts segment object
-with the specified coordinates into the Voronoi builder.<br>
+ <td style="vertical-align: top;">Inserts a segment object
+with the specified coordinates into the Voronoi builder.
</td>
</tr>
<tr>
@@ -193,10 +194,10 @@
const PointType& point1,<br>
const PointType& point2)</span><br>
</td>
- <td style="vertical-align: top;">Inserts segment object
-with the specified endpoints into the Voronoi builder.<br>
+ <td style="vertical-align: top;">Inserts a segment object defined by its endpoints into the Voronoi builder.<br>
Endpoint object should support x() and y() methods to retrieve its
coordinates.<br>
+This method is depricated and will be replaced soon to support point concept.<br>
</td>
</tr>
<tr>
@@ -204,12 +205,13 @@
<typename SegmentType><br>
void insert_segment(const SegmentType& segment)<br>
</td>
- <td style="vertical-align: top;">Inserts segment object
+ <td style="vertical-align: top;">Inserts a segment object
into the Voronoi builder.<br>
Segment object should support low() and high() methods to retrieve its
endpoints.<br>
Endpoint object should support x() and y() methods to retrieve its
coordinates.<br>
+This method is depricated and will be replaced soon to support point/segment concept.<br>
</td>
</tr>
<tr>
@@ -224,6 +226,7 @@
endpoints.<br>
Endpoint object should support x() and y() methods to retrieve its
coordinates.<br>
+This method is depricated and will be replaced soon to support point/segment concept.<br>
</td>
</tr>
<tr>
@@ -237,7 +240,12 @@
</td>
<td style="vertical-align: top;" width="693">Inserts point
and segment objects into Voronoi builder.<br>
-Requirements for the point and segment object interface are given above.<br>
+
+Segment object should support low() and high() methods to retrieve its
+endpoints.<br>
+
+Endpoint object should support x() and y() methods to retrieve its
+coordinates.<br>This method is depricated and will be replaced soon to support point/segment concept.<br>
</td>
</tr>
<tr>
@@ -266,8 +274,11 @@
</tbody>
</table>
<h1>Voronoi Coordinate Type Traits</h1>
- <p>The library provides default coordinate type traits for the
+
+
+ <p>The library provides the default 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>
@@ -286,7 +297,7 @@
typedef type_converter_efpt to_efpt_converter_type;<br>
};</p>
</font>
- <p>One
+ One
of the most important features of the library is that Voronoi builder
output geometries are constructed within defined relative error (64
machine epsilons). That means the more mantissa bits the user provided
@@ -295,8 +306,8 @@
Voronoi builder predicates user should define following set of
coordinate types (the 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">
+ <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>
@@ -377,24 +388,30 @@
</tr>
</tbody>
</table>
- <p>Notes:<br>
-1) Four different integer types are used (instead of a single
+ <p>Notes:<br></p>
+ <ul>
+ <li>
+Four different integer types are used (instead of a single
big_int_type) to slightly improve algorithm performance and memory
-usage.<br>
-2) As the maximum required size of the big_int_type is known in advance
+usage.</li>
+ <li>As the maximum required size of the big_int_type is known in advance
(based on the size of the integer type), library provided
implementation of a fixed integer could be used (it is much faster than
-heap-allocated big integers).<br>
-3) Two separate floating-point types are defined because for the input
+heap-allocated big integers).</li>
+ <li>
+Two separate floating-point types are defined because for the input
with
32-bit signed integer coordinates double won't be able to handle
2048-bit (64 * 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 the
-Voronoi diagram of points (mocks will work fine).<br>
-5) For an example of the user defined builder coordinate type traits
-see advanced Voronoi tutorial.</p>
+types, however this is not supported by MSVC compiler.</li>
+ <li>efpt_type and to_efpt_converter_type are not used to construct the
+Voronoi diagram of points (mocks will work fine).</li>
+ <li>
+For an example of the user defined builder coordinate type traits
+see advanced Voronoi tutorial.</li>
+ </ul>
+
</td>
</tr>
<tr>
Modified: sandbox/gtl/doc/voronoi_diagram.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_diagram.htm (original)
+++ sandbox/gtl/doc/voronoi_diagram.htm 2012-04-13 17:09:34 EDT (Fri, 13 Apr 2012)
@@ -1,25 +1,24 @@
<!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>Voronoi Diagram</title>
+ <meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Voronoi Diagram</title>
+
<meta http-equiv="content-type" content="text/html; charset=utf-8">
- <meta http-equiv="content-type" content="text/html; charset=utf-8">
-
-</head><body>
+ <meta http-equiv="content-type" content="text/html; charset=utf-8"></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">
+ <td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1">
<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>
@@ -115,6 +114,11 @@
<span style="font-family: Courier New,Courier,monospace;">class
voronoi_diagram;<br>
<br>
+</span><font face="Courier New"><span style="font-family: 'Courier New',Courier,monospace;">T</span></font>
+- specifies coordinate type of the output geometries: input sites (points / segments), Voronoi vertices.<br>
+ <span style="font-family: Courier New,Courier,monospace;">TRAITS - </span>Voronoi diagram traits (explained in the end of this chapter).<br>
+ <span style="font-family: Courier New,Courier,monospace;">
+ <br>
</span>
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
<tbody>
@@ -732,7 +736,7 @@
</td>
</tr>
<tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
+ <td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1"> </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">
Modified: sandbox/gtl/doc/voronoi_main.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_main.htm (original)
+++ sandbox/gtl/doc/voronoi_main.htm 2012-04-13 17:09:34 EDT (Fri, 13 Apr 2012)
@@ -3,6 +3,8 @@
+
+
<meta http-equiv="Content-Language" content="en-us">
@@ -203,42 +205,45 @@
<tr>
<td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template
<typename PC, typename VD><br>
-static inline void construct_voronoi_points(<br>
- const PC &points, VD *output)<br>
+static inline void construct_voronoi(<br>
+ const PC &points, VD *output)<br>
</td>
- <td style="vertical-align: top;">Constructs Voronoi
-diagram of a set of points into the output data structure.<br>
+ <td style="vertical-align: top;">Constructs Voronoi diagram of a set of points.<br>
Coordinates of the input geometries should belong to the [-2^31,
2^31-1] integer range.<br>
-PC is a container of points that supports forward iterator.<br>
+PC is a container of points that model point concept.<br>
</td>
</tr>
<tr>
<td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template
<typename SC, typename VD><br>
static inline void construct_voronoi_segments(<br>
- const SC &segments, VD *output)<br>
+ const SC &segments, VD *output)<br>
</td>
- <td style="vertical-align: top;">Constructs Voronoi
-diagram of a set of segments into the output data structure.<br>
+ <td style="vertical-align: top;">Constructs Voronoi diagram of a set of segments.<br>
Coordinates of the input geometries should belong to the [-2^31,
2^31-1] integer range.<br>
SC is a container of segments that supports forward iterator.<br>
Segment object should provide low(), high() public methods to retrieve
endpoints of a segment.<br>
+This method is deprecated and will be changed to the concept model the first method conforms.<br>
</td>
</tr>
<tr>
<td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template
<typename PC, typename SC, typename VD><br>
static inline void construct_voronoi(<br>
- const PC &points, const SC &segments, VD
+ const PC &points, const SC &segments, VD
*output)<br>
</td>
<td style="vertical-align: top;">Constructs Voronoi
-diagram of a set of points and segments into the output data structure.<br>
+diagram of a set of points and segments.<br>
Coordinates of the input geometries should belong to the [-2^31,
2^31-1] integer range.<br>
+
+Segment object should provide low(), high() public methods to retrieve
+endpoints of a segment.<br>
+This method is depricated and will be changed to the concept model the first method conforms.<br>
</td>
</tr>
</tbody>
@@ -246,7 +251,7 @@
<br>
For the users that don't want to go into the details of the library
this
-means that it's possible to construct the Voronoi diagram with the
+means that it's possible to construct Voronoi diagram with the
following two lines of code (if this doesn't work for you read Voronoi builder documentation page):<br>
<br>
<span style="font-family: Courier New,Courier,monospace;">voronoi_diagram<double>
@@ -263,12 +268,9 @@
Voronoi tutorial</a>.<br>
<h2>No Third Party Dependencies<br>
</h2>
-Yes, the library doesn't depend on any 3rd party code. Even more than
-that there is only one dependency on the Boost libraries: boost/cstdint.hpp.
+Yes, the library doesn't depend on any 3rd party code. The code depends only on the Boost libraries and STL.
All the required multiprecision types functionality is implemented as
-part of the library and is not exposed to the user. Considering the
-fact that Voronoi implementation consists of just 8 headers (4 public
-and 4 private) it is easy to compile it within a minute after download.<br>
+part of the library and is not exposed to the user.<br>
<h2>Extensible for the User Provided Coordinate Types</h2>
Our implementation is coordinate type agnostic. That means that as soon
as user provides types that satisfy set of restrictions of the Voronoi builder coordinate type traits
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