|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r77865 - sandbox/gtl/doc
From: sydorchuk.andriy_at_[hidden]
Date: 2012-04-09 18:16:22
Author: asydorchuk
Date: 2012-04-09 18:16:19 EDT (Mon, 09 Apr 2012)
New Revision: 77865
URL: http://svn.boost.org/trac/boost/changeset/77865
Log:
Fixing documentation titles.
Text files modified:
sandbox/gtl/doc/voronoi_advanced_tutorial.htm | 459 ++++++++++++++++++--------
sandbox/gtl/doc/voronoi_basic_tutorial.htm | 236 +++++++++----
sandbox/gtl/doc/voronoi_benchmark.htm | 320 +++++++++---------
sandbox/gtl/doc/voronoi_builder.htm | 684 ++++++++++++++++++++--------------------
sandbox/gtl/doc/voronoi_diagram.htm | 673 ++++++++++++++++++++++----------------
sandbox/gtl/doc/voronoi_main.htm | 401 +++++++++++-----------
sandbox/gtl/doc/voronoi_predicates.htm | 264 +++++++--------
sandbox/gtl/doc/voronoi_robust_fpt.htm | 313 +++++++++---------
sandbox/gtl/doc/voronoi_utils.htm | 395 ++++++++++++----------
9 files changed, 2047 insertions(+), 1698 deletions(-)
Modified: sandbox/gtl/doc/voronoi_advanced_tutorial.htm
Modified: sandbox/gtl/doc/voronoi_basic_tutorial.htm
Modified: sandbox/gtl/doc/voronoi_benchmark.htm
Modified: sandbox/gtl/doc/voronoi_builder.htm
Modified: sandbox/gtl/doc/voronoi_diagram.htm
Modified: sandbox/gtl/doc/voronoi_main.htm
Modified: sandbox/gtl/doc/voronoi_predicates.htm
Modified: sandbox/gtl/doc/voronoi_robust_fpt.htm
Modified: sandbox/gtl/doc/voronoi_utils.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_advanced_tutorial.htm (original)
+++ sandbox/gtl/doc/voronoi_advanced_tutorial.htm 2012-04-09 18:16:19 EDT (Mon, 09 Apr 2012)
@@ -1,24 +1,18 @@
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head>
+
+ <meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
+ <title>Voronoi Advanced Tutorial</title>
-
-
-
-
-
-
-
-
-
-
-
-
-<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Polygon Usage</title></head><body>
-
+
+</head><body>
<h1>Voronoi Advanced Tutorial<br>
-</h1>This tutorial consists of two parts. The first one provides two
+</h1>
+
+This tutorial consists of two parts. The first one provides two
examples of a real world problems that default configuration of Voronoi
-library is capable to solve. By default configuration we mean the one that accepts
+library is capable to solve. By default configuration we mean the one
+that accepts
signed 32-bit integer and outputs floating-point (64-bit
double) coordinates. We provide those examples to convince even the
most skeptical users that they probably don't need to configure library
@@ -26,12 +20,11 @@
posed problem really requires those, fully featured configuration of
both input and output coordinate types is provided in the second part
of this tutorial.<br>
-<h2>Red Planet</h2>
+<h2>Red Planet</h2>
<h3>Problem Statement</h3>
-
<img style="width: 665px; height: 369px;" alt="" src="images/rover.jpg"><br>
<br>
@@ -48,64 +41,66 @@
<h3>Application of Voronoi diagram</h3>
-
The problem above could be solved using Voronoi diagram. The first
stage would be to discretize obstacles (rocks and wells) with
polylines. Afterwards we will compute Voronoi diagram of the input set
of segments. As each Voronoi edge is equidistant from the two closest
sites we are able to filter edges the robot won't be able to pass due
-to it's dimensions. The last step would be to run a bit optimized A* algorithm to find
+to it's dimensions. The last step would be to run a bit optimized A*
+algorithm to find
the shortest or at least suboptimal path and we are done.<br>
<h3>Discretization of input geometries</h3>
-
-To show how good is the default input coordinate type provided by the Voronoi library
+To show how good is the default input coordinate type provided by the
+Voronoi library
we will discretize the whole area of Mars. That will be approximately
1.44 * 10^8 square kilometres that is equal to 1.44 *
10^18 square centimetres, which could be snapped to the integer
-grid with a side of 1.2 * 10^9 centimetres. To make the Voronoi graph
+grid with a side of 1.2 * 10^9 centimetres. To make the Voronoi
+graph
precise on the boundaries of that grid we will replicate input map 9
times (3x3), thus Voronoi diagram within a central piece will
provide us with a correct connectivity graph. This step will increase
the size of our grid to 3.6 * 10^9 centimetres that is less than 2^32.
-So we are able to discretize the Red Planet's surface within a 1 centimetre
-precision using the default input coordinate type (signed 32-bit integer). That would imply maximum absolute error to be
-equal up to 0.5 centimetres per coordinate. Considering the radius of our robot to be
+So we are able to discretize the Red Planet's surface within a 1
+centimetre
+precision using the default input coordinate type (signed 32-bit
+integer). That would imply maximum absolute error to be
+equal up to 0.5 centimetres per coordinate. Considering the radius of
+our robot to be
0.3 metres and for security reasons avoiding any large enough obstacles
that are within 1 metre distance from it that error would be irrelevant.<br>
-
-
-
- <span style="color: rgb(0, 0, 0); font-family: sans-serif; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 13px; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; background-color: rgb(249, 249, 249); display: inline ! important; float: none;"></span>
+<span style="color: rgb(0, 0, 0); font-family: sans-serif; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: 13px; orphans: 2; text-align: left; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; background-color: rgb(249, 249, 249); display: inline ! important; float: none;"></span>
<h3>Output analysis</h3>
-
-Estimates of the resulting Voronoi diagram precision were already explained here.
+Estimates of the resulting Voronoi diagram precision were already
+explained here.
So to avoid those computations again we will simply state that the
maximum absolute error of the output geometries will be on the grid
boundaries and will be equal to 2^-16 centimetres, which is
approximately equal to 150 nanometres and is 100 times larger than
-a radius of a complex molecule.
-
-We would like to notice that the absolute error of the discretization step is much higher than the one
-produced by the Voronoi diagram construction algorithm. <h2>VLSI Design</h2>
-
+a radius of a complex molecule. We would like to notice that the
+absolute error of the discretization step is much higher than the one
+produced by the Voronoi diagram construction algorithm.
+<h2>VLSI Design</h2>
<h3>Problem Statement</h3>
-
<img style="width: 400px; height: 283px;" alt="" src="images/vlsi.jpg"><br>
<br>
-Very-large-scale integration (VLSI) is the process of creating
+
+Very-large-scale integration (VLSI) is the
+process of creating
integrated circuits by combining thousands of transistors into a single
chip. Considering the fact that it may take weeks or months to get an
integrated circuit manufactured, designers often spend large amounts of
time analyzing their layouts to avoid costly mistakes. One of the
common static analysis checks is minimum distance requirement between
-the components of an integrated circuit (distance should be not less than
+the components of an integrated circuit (distance should be not less
+than
specified value).<br>
<h3>Application of Voronoi diagram</h3>
@@ -113,12 +108,13 @@
It appears that the minimum distance between components of the input
set of points and segments corresponds to the one of the Voronoi
diagram edges. This means that we can iterate through each edge of
-the Voronoi graph, extract the pair of input geometries that form it and find
-the distance between those. As the total amount of such edges is O(N) value
+the Voronoi graph, extract the pair of input geometries that form it
+and find
+the distance between those. As the total amount of such edges is O(N)
+value
(N - is the number of input geometries) the minimum distance could be
efficiently find in a linear time once we construct the diagram.<br>
-
<h3>Discretization of input geometries</h3>
The average size of the modern CPUs is around 2.5 x 2.5 centimetres.
@@ -132,192 +128,357 @@
The maximum absolute error of the output geometries will be 2.5 / 2^47
centimetres or 0.2 femtometres that is 10 times smaller value than
the radius of an electron. However in this particular case we are not
-interested in the precision of the output, rather in its topology. As it was noticed on
+interested in the precision of the output, rather in its topology. As
+it was noticed on
the Voronoi main page very small edges
are removed from the Voronoi diagram. However user should not worry
because the edge that correspond to the minimal distance won't be among
those. That means that we would be able to 100% correctly identify a
pair of closest objects within the discretization precision.<br>
+<h2>Conclusions</h2>
-
-
-
-
-
-<h2>Conclusions</h2>The above two examples show usage of the default Voronoi coordinate types
+The above two examples show usage of the default Voronoi coordinate
+types
in the macro and micro world. The main point of those was to give user
-understanding of a scale the default coordinate types provides. There are
+understanding of a scale the default coordinate types provides. There
+are
two main points we didn't mention before, but that would be relevant to
the most real world problems:<br>
+
<ul>
- <li>The absolute error of the coordinates of the output Voronoi diagram
+
+ <li>The absolute error of the coordinates of the output Voronoi
+diagram
inside the 32-bit integer discretization grid is slightly smaller than
-the absolute error of discretization itself, thus could be neglected at all.</li>
+the absolute error of discretization itself, thus could be neglected at
+all.</li>
<li>In both problems above we didn't consider error of measurement.
-For example: is it possible to construct a map of the Mars within the 0.5
+For example: is it possible to construct a map of the Mars within the
+0.5
centimetres precision, or to get coordinates of the circuit parts
withing the subatomic precision? I guess the answer for both questions
-would be "No". And that actually means that the error of the discretization
-step could be neglected comparing to the error produced by the measuring
+would be "No". And that actually means that the error of the
+discretization
+step could be neglected comparing to the error produced by the
+measuring
devices.<br>
</li>
</ul>
+
The second statement means that there is actually no point to provide
implementation that operates with floating-point input coordinates,
because those always could be snapped to the integer grid. In case you
are not satisfied with the precision that the 32-bit integer grid
-provides or would like to retrieve coordinates of the output geometries within a smaller
+provides or would like to retrieve coordinates of the output geometries
+within a smaller
relative error, follow the next paragraph.<br>
+<h2>Voronoi Coordinate Types Configuration</h2>
-
-
-<h2>Voronoi Coordinate Types Configuration</h2>In the following chapter we are going to extend input coordinate type to the 48-bit signed
-integer and output coordinate type to the 80-bit IEEE floating-point type
+In the following chapter we are going to extend input coordinate type
+to the 48-bit signed
+integer and output coordinate type to the 80-bit IEEE floating-point
+type
(long double). The code for this chapter is available in voroni_advanced_tutorial.cpp.
-While it won't be possible to compile it using the MSVC compiler (it doesn't
+While it won't be possible to compile it using the MSVC compiler (it
+doesn't
support 80-bit long double type; ieee754.h header is required), it
should give a clear understanding of how the library supports the user
provided coordinate types.<br>
+
<br>
-So the main step would be to declare the voronoi coordinate type traits that satisfy set of restrictions explained here:<br>
+
+So the main step would be to declare the voronoi coordinate type traits
+that satisfy set of restrictions explained here:<br>
+
<br>
-<span style="font-family: Courier New,Courier,monospace;">struct my_voronoi_ctype_traits {</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> typedef boost::int64_t int_type;</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> typedef detail::extended_int<3> int_x2_type;</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> typedef detail::extended_int<3> uint_x2_type;</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> typedef detail::extended_int<128> big_int_type;</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> typedef fpt80 fpt_type;</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> typedef fpt80 efpt_type;</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> typedef my_ulp_comparison ulp_cmp_type;</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> typedef my_fpt_converter to_fpt_converter_type;</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> typedef my_fpt_converter to_efpt_converter_type;</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">struct
+my_voronoi_ctype_traits {</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+typedef boost::int64_t int_type;</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+typedef detail::extended_int<3> int_x2_type;</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+typedef detail::extended_int<3> uint_x2_type;</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+typedef detail::extended_int<128> big_int_type;</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+typedef fpt80 fpt_type;</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+typedef fpt80 efpt_type;</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+typedef my_ulp_comparison ulp_cmp_type;</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+typedef my_fpt_converter to_fpt_converter_type;</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+typedef my_fpt_converter to_efpt_converter_type;</span><br style="font-family: Courier New,Courier,monospace;">
+
<span style="font-family: Courier New,Courier,monospace;">};<br>
<br>
</span>It is always better to use C++ built-in types wherever it's
-possible. That's why we use the 64-bit signed integer type to handle our
-input coordinates. <span style="font-family: Courier New,Courier,monospace;">int_x2_type</span> and <span style="font-family: Courier New,Courier,monospace;">uint_x2_type</span>
+possible. That's why we use the 64-bit signed integer type to handle
+our
+input coordinates. <span style="font-family: Courier New,Courier,monospace;">int_x2_type</span>
+and <span style="font-family: Courier New,Courier,monospace;">uint_x2_type</span>
is required to handle 96-bit signed/unsigned integers. As there is no
-such built-in type we use library provided efficient fixed integer type.
-The big integer type should be capable to handle 48 * 64 bit integers, that is
-less than 32 * 128, and so far we are good with <span style="font-family: Courier New,Courier,monospace;">extended_int<128></span> type. We use the same floating point type for both <span style="font-family: Courier New,Courier,monospace;">fpt_type</span> and <span style="font-family: Courier New,Courier,monospace;">efpt_type</span>
+such built-in type we use library provided efficient fixed integer
+type.
+The big integer type should be capable to handle 48 * 64 bit integers,
+that is
+less than 32 * 128, and so far we are good with <span style="font-family: Courier New,Courier,monospace;">extended_int<128></span>
+type. We use the same floating point type for both <span style="font-family: Courier New,Courier,monospace;">fpt_type</span>
+and <span style="font-family: Courier New,Courier,monospace;">efpt_type</span>
as it has enough exponent bits to represent both 48 * 32 bit and 48 *
64 bit integers (that is also the reason we don't need two
floating-point converter structures). The <span style="font-family: Courier New,Courier,monospace;">ulp_cmp_type</span>
structure checks weather two IEEE floating-point values are within the
given signed integer ulp range (we won't analyze corresponding code
-here as it requires deep understanding of the floating-point architecture and its usage to compare floating-point values), but just to mention the declaration is following:<br>
+here as it requires deep understanding of the <a href="http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html">floating-point
+architecture</a> and its <a href="../boost/polygon/detail/voronoi_ctypes.hpp">usage to compare
+floating-point values</a>), but just to mention the declaration is
+following:<br>
+
<span style="font-family: Courier New,Courier,monospace;"></span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;">struct my_ulp_comparison {</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> enum Result {</span><span style="font-family: Courier New,Courier,monospace;"><br>
+
+<span style="font-family: Courier New,Courier,monospace;">struct
+my_ulp_comparison {</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;"> enum
+Result {</span><span style="font-family: Courier New,Courier,monospace;"><br>
LESS = -1,</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> EQUAL = 0,</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> MORE = 1</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+EQUAL = 0,</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+MORE = 1</span><br style="font-family: Courier New,Courier,monospace;">
+
<span style="font-family: Courier New,Courier,monospace;"> };</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> Result operator()(fpt80 a, fpt80 b, unsigned int maxUlps) const;</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;"> Result
+operator()(fpt80 a, fpt80 b, unsigned int maxUlps) const;</span><br style="font-family: Courier New,Courier,monospace;">
+
<span style="font-family: Courier New,Courier,monospace;">};<br>
<br>
-</span>The last step would be to declare the <span style="font-family: Courier New,Courier,monospace;">my_fpt_converter</span> structure (converts the integer types to the floating-point type):<br>
+</span>The last step would be to declare the <span style="font-family: Courier New,Courier,monospace;">my_fpt_converter</span>
+structure (converts the integer types to the floating-point type):<br>
+
<br>
-<span style="font-family: Courier New,Courier,monospace;">struct my_fpt_converter {</span><br style="font-family: Courier New,Courier,monospace;">
-<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;"> fpt80 operator()(const T& that) const {</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> return static_cast<fpt80>(that);</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">struct
+my_fpt_converter {</span><br style="font-family: Courier New,Courier,monospace;">
+
+<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;"> fpt80
+operator()(const T& that) const {</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+return static_cast<fpt80>(that);</span><br style="font-family: Courier New,Courier,monospace;">
+
<span style="font-family: Courier New,Courier,monospace;"> }</span><br style="font-family: Courier New,Courier,monospace;">
+
<br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> template <size_t N></span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> fpt80 operator()(const typename detail::extended_int<N> &that) const {</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> fpt80 result = 0.0;</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> for (size_t i = 1; i <= (std::min)((size_t)3, that.size()); ++i) {</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> if (i != 1)</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> result *= static_cast<fpt80>(0x100000000ULL);</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> result += that.chunks()[that.size() - i];</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> }</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> return (that.count() < 0) ? -result : result;</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+template <size_t N></span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;"> fpt80
+operator()(const typename detail::extended_int<N> &that)
+const {</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+fpt80 result = 0.0;</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+for (size_t i = 1; i <= (std::min)((size_t)3, that.size()); ++i) {</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+if (i != 1)</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+result *= static_cast<fpt80>(0x100000000ULL);</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+result += that.chunks()[that.size() - i];</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+}</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+return (that.count() < 0) ? -result : result;</span><br style="font-family: Courier New,Courier,monospace;">
+
<span style="font-family: Courier New,Courier,monospace;"> }</span><br style="font-family: Courier New,Courier,monospace;">
+
<span style="font-family: Courier New,Courier,monospace;">};<br>
<br>
</span>At this point we are done with declaration of the Voronoi
coordinate type traits. The next step is to declare the Voronoi diagram
traits:<br>
+
<br>
-<span style="font-family: Courier New,Courier,monospace;">struct my_voronoi_diagram_traits {</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> typedef fpt80 coordinate_type;</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> typedef struct {</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> template <typename CT></span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> fpt80 operator()(const CT& that) const {</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> return static_cast<fpt80>(that);</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> }</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> } ctype_converter_type;</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> typedef detail::point_2d<coordinate_type> point_type;</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> typedef voronoi_cell<coordinate_type> cell_type;</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> typedef voronoi_vertex<coordinate_type> vertex_type;</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> typedef voronoi_edge<coordinate_type> edge_type;</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> typedef struct {</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">struct
+my_voronoi_diagram_traits {</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+typedef fpt80 coordinate_type;</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+typedef struct {</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+template <typename CT></span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+fpt80 operator()(const CT& that) const {</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+return static_cast<fpt80>(that);</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+}</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;"> }
+ctype_converter_type;</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+typedef detail::point_2d<coordinate_type> point_type;</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+typedef voronoi_cell<coordinate_type> cell_type;</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+typedef voronoi_vertex<coordinate_type> vertex_type;</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+typedef voronoi_edge<coordinate_type> edge_type;</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+typedef struct {</span><br style="font-family: Courier New,Courier,monospace;">
+
<span style="font-family: Courier New,Courier,monospace;"> public:</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> enum { ULPS = 128 };</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> bool operator()(const point_type &v1, const point_type &v2) const {</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> return (ulp_cmp(v1.x(), v2.x(), ULPS) == my_ulp_comparison::EQUAL &&</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+enum { ULPS = 128 };</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+bool operator()(const point_type &v1, const point_type &v2)
+const {</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+return (ulp_cmp(v1.x(), v2.x(), ULPS) == my_ulp_comparison::EQUAL
+&&</span><br style="font-family: Courier New,Courier,monospace;">
+
<span style="font-family: Courier New,Courier,monospace;">
ulp_cmp(v1.y(), v2.y(), ULPS) == my_ulp_comparison::EQUAL);</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> }</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> private:</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> my_ulp_comparison ulp_cmp;</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> } vertex_equality_predicate_type;</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+}</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+private:</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+my_ulp_comparison ulp_cmp;</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;"> }
+vertex_equality_predicate_type;</span><br style="font-family: Courier New,Courier,monospace;">
+
<span style="font-family: Courier New,Courier,monospace;">};</span><br>
-<span style="font-family: Courier New,Courier,monospace;"></span><br>Above we simply declared the Voronoi primitive types, type converter and vertex
+<span style="font-family: Courier New,Courier,monospace;"></span><br>
+
+Above we simply declared the Voronoi primitive types, type converter
+and vertex
equality predicate using the new coordinate type and corresponding ulp
-comparison structure. As we are done with the declaration of the coordinate
+comparison structure. As we are done with the declaration of the
+coordinate
type specific structures we are ready to proceed to the construction
step itself. The first step would be to initialize voronoi_builder
structure with a set of random points:<br>
+
<br>
-<span style="font-family: Courier New,Courier,monospace;">// Random generator and distribution. MAX is equal to 2^48.</span><br>
-<span style="font-family: Courier New,Courier,monospace;">boost::mt19937_64 gen(std::time(0));</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;">boost::random::uniform_int_distribution<boost::int64_t> distr(-MAX, MAX-1);</span><span style="font-family: Courier New,Courier,monospace;"><br>
-// Declaring and configuring Voronoi builder with the new coordinate type traits.<br>
+
+<span style="font-family: Courier New,Courier,monospace;">// Random
+generator and distribution. MAX is equal to 2^48.</span><br>
+
+<span style="font-family: Courier New,Courier,monospace;">boost::mt19937_64
+gen(std::time(0));</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">boost::random::uniform_int_distribution<boost::int64_t>
+distr(-MAX, MAX-1);</span><span style="font-family: Courier New,Courier,monospace;"><br>
+// Declaring and configuring Voronoi builder with the new coordinate
+type traits.<br>
voronoi_builder<boost::int64_t, my_voronoi_ctype_traits> vb;</span><span style="font-family: Courier New,Courier,monospace;"></span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;">// Voronoi builder initialization step.<br>
+
+<span style="font-family: Courier New,Courier,monospace;">// Voronoi
+builder initialization step.<br>
for (size_t i = 0; i < GENERATED_POINTS; ++i) {</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> boost::int64_t x = distr(gen);</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> boost::int64_t y = distr(gen);</span><br style="font-family: Courier New,Courier,monospace;">
-<span style="font-family: Courier New,Courier,monospace;"> vb.insert_point(x, y);</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+boost::int64_t x = distr(gen);</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+boost::int64_t y = distr(gen);</span><br style="font-family: Courier New,Courier,monospace;">
+
+<span style="font-family: Courier New,Courier,monospace;">
+vb.insert_point(x, y);</span><br style="font-family: Courier New,Courier,monospace;">
+
<span style="font-family: Courier New,Courier,monospace;">}<br>
<br>
-</span>The second step would be to generate the Voronoi diagram and this is done as before with the two lines of code:<br>
+</span>The second step would be to generate the Voronoi diagram and
+this is done as before with the two lines of code:<br>
+
<br>
-<span style="font-family: Courier New,Courier,monospace;">// Declaring and configuring Voronoi diagram structure with the new coordinate type traits.<br>
+
+<span style="font-family: Courier New,Courier,monospace;">// Declaring
+and configuring Voronoi diagram structure with the new coordinate type
+traits.<br>
voronoi_diagram<fpt80, my_voronoi_diagram_traits> vd;</span><br>
+
<span style="font-family: Courier New,Courier,monospace;">vb.construct(&vd);<br>
<br>
-</span>From this point the user can operate with the Voronoi diagram data structure
+</span>From this point the user can operate with the Voronoi diagram
+data structure
and in our tutorial we output some simple stats of the resulting
Voronoi graph. Probably the hardest part of this tutorial is
the declaration of the ulp comparison structure. The library provides
efficient well-commented cross-platform implementation for 64-bit
floating-point type (double). So the best advice would be to follow
-that implementation, but before doing that really consider if the default
+that implementation, but before doing that really consider if the
+default
coordinate types are not capable to solve your problem.<br>
+
<br>
+
<table class="docinfo" id="table1" 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>
+
+ <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>
</body></html>
\ No newline at end of file
==============================================================================
--- sandbox/gtl/doc/voronoi_basic_tutorial.htm (original)
+++ sandbox/gtl/doc/voronoi_basic_tutorial.htm 2012-04-09 18:16:19 EDT (Mon, 09 Apr 2012)
@@ -1,22 +1,21 @@
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head>
+
+ <meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
+ <title>Voronoi Basic Tutorial</title>
-
-
-
-
-
-
-
-
-<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Polygon Usage</title></head><body>
-
+
+</head><body>
<h1>Voronoi Basic Tutorial<br>
-</h1>
+</h1>
+
<p>In this tutorial we will cover the basic usage of the Boost.Polygon
-Voronoi library that should be enough for 95% of cases. Below we will discuss the following topics:<br>
+Voronoi library that should be enough for 95% of cases. Below we will
+discuss the following topics:<br>
</p>
+
<ul>
+
<li>preparing input geometries;<br>
</li>
<li>construction of the Voronoi diagram;</li>
@@ -24,17 +23,25 @@
</li>
<li>associating the user data with the Voronoi primitives;</li>
<li>Voronoi diagram discretization and rendering.</li>
-</ul>In the example that goes through this tutorial (voronoi_basic_tutorial.cpp)
+</ul>
+
+In the example that goes through this tutorial (voronoi_basic_tutorial.cpp)
we
-are going to construct the Voronoi diagram of a few points and segments.
-On the image below one may see the corresponding rendered Voronoi graph. Primary Voronoi edges
+are going to construct the Voronoi diagram of a few points and
+segments.
+On the image below one may see the corresponding rendered Voronoi
+graph. Primary Voronoi edges
are marked with
-the black color, non-primary with green, input geometries have blue color. In
+the black color, non-primary with green, input geometries have blue
+color. In
case you forgot, we split each input segment onto three sites (segment
itself and both endpoints), edges that go between those sites are
considered to be non-primary.<br>
+
<br>
+
<img style="border: 2px solid ; width: 300px; height: 300px;" alt="" src="images/voronoi4.png"><br>
+
<br>
And before you proceed don't forget to:<span style="font-family: Courier New,Courier,monospace;"><br>
@@ -43,9 +50,12 @@
using boost::polygon;<br>
</span>
<h2>Preparing Input Geometries</h2>
+
Before executing the algorithm lets see how the user provided types for
the input geometries might look like:<br>
+
<br>
+
<span style="font-family: Courier New,Courier,monospace;">class Point {<br>
public:<br>
Point() {}<br>
@@ -64,7 +74,8 @@
class Segment {<br>
public:<br>
Segment() {}<br>
- Segment(int x1, int y1, int x2, int y2) : p0_(x1, y1), p1_(x2, y2) {}<br>
+ Segment(int x1, int y1, int x2, int y2) : p0_(x1, y1), p1_(x2,
+y2) {}<br>
<br>
// Those accessors are required!<br>
Point low() const { return p0_; }<br>
@@ -73,11 +84,15 @@
private:<br>
Point p0_;<br>
Point p1_;</span><br>
+
<span style="font-family: Courier New,Courier,monospace;">};<br>
<br>
</span>Once those are declared we can create the sample input:<br>
+
<br>
-<span style="font-family: Courier New,Courier,monospace;">std::vector<Point> points;<br>
+
+<span style="font-family: Courier New,Courier,monospace;">std::vector<Point>
+points;<br>
points.push_back(Point(0, 0));<br>
points.push_back(Point(1, 6));<br>
std::vector<Segment> segments;<br>
@@ -85,25 +100,34 @@
segments.push_back(Segment(3, -11, 13, -1));</span><span style="font-family: Courier New,Courier,monospace;"><br>
</span>
<h2>Construction of the Voronoi Diagram<br>
-
</h2>
+Now let's construct the Voronoi diagram of the input set of points and
+segments:<br>
-
-Now let's construct the Voronoi diagram of the input set of points and segments:<br>
<br>
-<span style="font-family: Courier New,Courier,monospace;">voronoi_diagram<double> vd;<br>
+
+<span style="font-family: Courier New,Courier,monospace;">voronoi_diagram<double>
+vd;<br>
construct_voronoi(points, segments, &vd);<br>
<br>
</span>So brief, isn't that awesome!<br>
-<h2>Traversing Voronoi Graph</h2>Voronoi graph traversal is the basic
+
+<h2>Traversing Voronoi Graph</h2>
+
+Voronoi graph traversal is the basic
operation one would like to do once the Voronoi diagram is constructed.
There are three ways to do that and we are going to cover all of them:<br>
+
<ul>
+
<li>simply iterating over the Voronoi edges (counts each edge twice):<br>
- <span style="font-family: Courier New,Courier,monospace;"><br>int iterate_primary_edges1(const voronoi_diagram<double> &vd) {<br>
+ <span style="font-family: Courier New,Courier,monospace;"><br>
+int iterate_primary_edges1(const voronoi_diagram<double> &vd)
+{<br>
int result = 0;<br>
- for (voronoi_diagram<double>::const_edge_iterator it = vd.edges().begin();<br>
+ for (voronoi_diagram<double>::const_edge_iterator it =
+vd.edges().begin();<br>
it != vd.edges().end(); ++it) {<br>
if (it->is_primary())<br>
++result;<br>
@@ -112,15 +136,21 @@
}</span><br>
<span style="font-family: Courier New,Courier,monospace;"> </span><br>
</li>
- <li>iterating over the Voronoi cells and then traversing edges around each cell (counts each edge twice):<br>
+ <li>iterating over the Voronoi cells and then traversing edges around
+each cell (counts each edge twice):<br>
<br>
- <span style="font-family: Courier New,Courier,monospace;">int iterate_primary_edges2(const voronoi_diagram<double> &vd) {<br>
+ <span style="font-family: Courier New,Courier,monospace;">int
+iterate_primary_edges2(const voronoi_diagram<double> &vd) {<br>
int result = 0;<br>
- for (voronoi_diagram<double>::const_cell_iterator it = vd.cells().begin();<br>
+ for (voronoi_diagram<double>::const_cell_iterator it =
+vd.cells().begin();<br>
it != vd.cells().end(); ++it) {<br>
- const voronoi_diagram<double>::cell_type &cell = *it;<br>
- const voronoi_diagram<double>::edge_type *edge = cell.incident_edge();<br>
- // This is convenient way to iterate edges around Voronoi cell.<br>
+ const voronoi_diagram<double>::cell_type
+&cell = *it;<br>
+ const voronoi_diagram<double>::edge_type *edge
+= cell.incident_edge();<br>
+ // This is convenient way to iterate edges around
+Voronoi cell.<br>
do {<br>
if (edge->is_primary())<br>
++result;<br>
@@ -131,18 +161,22 @@
}</span><br>
<br>
</li>
-
<li>iterating over the Voronoi
vertices and then traversing edges around each vertex (number of
iterations through each edge is equal to the number of finite endpoints
of the edge):<span style="font-family: Courier New,Courier,monospace;"></span><br>
- <span style="font-family: Courier New,Courier,monospace;">int iterate_primary_edges3(const voronoi_diagram<double> &vd) {<br>
+ <span style="font-family: Courier New,Courier,monospace;">int
+iterate_primary_edges3(const voronoi_diagram<double> &vd) {<br>
int result = 0;<br>
- for (voronoi_diagram<double>::const_vertex_iterator it = vd.vertices().begin();<br>
+ for (voronoi_diagram<double>::const_vertex_iterator it =
+vd.vertices().begin();<br>
it != vd.vertices().end(); ++it) {<br>
- const voronoi_diagram<double>::vertex_type &vertex = *it;<br>
- const voronoi_diagram<double>::edge_type *edge = vertex.incident_edge();<br>
- // This is convenient way to iterate edges around Voronoi vertex.<br>
+ const voronoi_diagram<double>::vertex_type
+&vertex = *it;<br>
+ const voronoi_diagram<double>::edge_type *edge
+= vertex.incident_edge();<br>
+ // This is convenient way to iterate edges around
+Voronoi vertex.<br>
do {<br>
if (edge->is_primary())<br>
++result;<br>
@@ -151,30 +185,48 @@
}<br>
return result;<br>
}</span></li>
+</ul>
-</ul>This should give a very nice idea on how to traverse Voronoi
+This should give a very nice idea on how to traverse Voronoi
diagram. Notice that while the output from the first two methods should
be the same, it wouldn't for the third one. The reason is that in the
last case we will iterate only once through the edges with a single
finite endpoint and will skip all the edges with no finite endpoints.<br>
+
<h2>Associating User Data with Voronoi Primitives</h2>
-A few simple cases of associating user data with Voronoi primitives are following:<br>
+A few simple cases of associating user data with Voronoi primitives are
+following:<br>
+
<ul>
+
<li>associating number of incident edges with each cell, vertex;</li>
<li>associating color with each edge;</li>
- <li>using DFS or BFS on the Voronoi graph requires to mark visited edges/vertices/cells.</li>
+ <li>using DFS or BFS on the Voronoi graph requires to mark visited
+edges/vertices/cells.</li>
</ul>
-We will consider the first example and will associate the total number of incident edges with each cell.<br>
-Note: Each Voronoi primitive contains mutable pointer to void* type, that allows to associate any type of data with it.<br>
+
+We will consider the first example and will associate the total number
+of incident edges with each cell.<br>
+
+Note: Each Voronoi primitive contains mutable pointer to void* type,
+that allows to associate any type of data with it.<br>
+
<br>
-<span style="font-family: Courier New,Courier,monospace;">std::vector<int> counts;</span><br>
-<span style="font-family: Courier New,Courier,monospace;">// This is required as reallocation of underlying vector will invalidate all the pointers.<br>
+
+<span style="font-family: Courier New,Courier,monospace;">std::vector<int>
+counts;</span><br>
+
+<span style="font-family: Courier New,Courier,monospace;">// This is
+required as reallocation of underlying vector will invalidate all the
+pointers.<br>
counts.reserve(vd.num_cells());<br>
-for (voronoi_diagram<double>::const_cell_iterator it = vd.cells().begin();<br>
+for (voronoi_diagram<double>::const_cell_iterator it =
+vd.cells().begin();<br>
it != vd.cells().end(); ++it) {<br>
const voronoi_diagram<double>::cell_type &cell = *it;<br>
- const voronoi_diagram<double>::edge_type *edge = cell.incident_edge();<br>
+ const voronoi_diagram<double>::edge_type *edge =
+cell.incident_edge();<br>
int count = 0;<br>
do {<br>
++count;<br>
@@ -184,46 +236,67 @@
cell.data(&counts.back());<br>
}</span><span style="font-family: Courier New,Courier,monospace;"><br>
</span><br>
+
Note: In the example above we could not use count variable
without a vector, because pointer to it will become invalid as soon as
we leave the scope of the enclosing for-loop.<br>
+
<h2>Rendering Voronoi Diagram</h2>
There are two main issues that don't allow to strictly render resulting
Voronoi diagram using such rendering tools as OpenGL or DirectX.
Those are:<br>
+
<ul>
+
<li>Some of the Voronoi edges are infinite, so should be clipped;</li>
- <li>Some of the Voronoi edge are parabolic arcs, so should be discretized.</li>
-</ul>Note: This would be the issues not only for rendering tools.
+ <li>Some of the Voronoi edge are parabolic arcs, so should be
+discretized.</li>
+</ul>
+
+Note: This would be the issues not only for rendering tools.
Basically every task that requires diagram to be represented as a set
of finite segments will fall into this category.<br>
-<br>All the above functionality is already implemented in the Voronoi
+
+<br>
+
+All the above functionality is already implemented in the Voronoi
utils.
Before clipping an edge we are going to define the clipping rectangle.
It is practical to choose it so that it wraps all the input geometries
plus some offset.<br>
+
<span style="font-family: Courier New,Courier,monospace;"><br>
bounding_rectangle<double> bbox;<br>
-for (std::vector<Point>::iterator it = points.begin(); it != points.end(); ++it)<br>
+for (std::vector<Point>::iterator it = points.begin(); it !=
+points.end(); ++it)<br>
bbox.update(it->x(), it->y());<br>
-for (std::vector<Segment>::iterator it = segments.begin(); it != segments.end(); ++it) {<br>
+for (std::vector<Segment>::iterator it = segments.begin(); it !=
+segments.end(); ++it) {<br>
bbox.update(it->low().x(), it->low().y());<br>
bbox.update(it->high().x(), it->high().y());<br>
}<br>
// Add 10% offset to the bounding rectangle.<br>
bbox = voronoi_utils<double>::scale(bbox, 1.1);</span><span style="font-family: Courier New,Courier,monospace;"><br>
-</span><br>Now lets consider that we have the 3rd party library function that draws segments using the following prototype:<span style="font-family: Courier New,Courier,monospace;"><br>
+</span><br>
+
+Now lets consider that we have the 3rd party library function that
+draws segments using the following prototype:<span style="font-family: Courier New,Courier,monospace;"><br>
<br>
void draw_segment(double x1, double y1, double x2, double y2);<br>
<br>
-</span>Then the function that renders our diagram edges will have the following implementation:<br>
+</span>Then the function that renders our diagram edges will have the
+following implementation:<br>
+
<br>
-<span style="font-family: Courier New,Courier,monospace;">void render_diagram(const voronoi_diagram<double> &vd,<br>
+
+<span style="font-family: Courier New,Courier,monospace;">void
+render_diagram(const voronoi_diagram<double> &vd,<br>
const voronoi_utils<double>::brect_type &bbox) {<br>
int visited = 1;<br>
- for (voronoi_diagram<double>::const_edge_iterator it = vd.edges().begin();<br>
+ for (voronoi_diagram<double>::const_edge_iterator it =
+vd.edges().begin();<br>
it != vd.edges().end(); ++it) {<br>
// We use data pointer to mark visited edges.<br>
it->data(&visited);<br>
@@ -231,13 +304,17 @@
if (it->twin()->data()) continue;<br>
voronoi_utils<double>::point_set_type polyline;<br>
if (it->is_linear())<br>
- voronoi_utils<double>::clip(*it, bbox, polyline);<br>
+ voronoi_utils<double>::clip(*it,
+bbox, polyline);<br>
else<br>
// Parabolic edges are always finite.<br>
- voronoi_utils<double>::discretize(*it, 1E-1, polyline);<br>
- // Note: discretized edge segments may also lie outside of the bbox.<br>
+
+voronoi_utils<double>::discretize(*it, 1E-1, polyline);<br>
+ // Note: discretized edge segments may also lie
+outside of the bbox.<br>
for (int i = 1; i < polyline.size(); ++i)<br>
- draw_segment(polyline[i-1].x(), polyline[i-1].y(),<br>
+ draw_segment(polyline[i-1].x(),
+polyline[i-1].y(),<br>
polyline[i].x(), polyline[i].y());<br>
}<br>
@@ -249,31 +326,34 @@
drawings under ./libs/polygon/example directory.<span style="text-decoration: underline;"><br>
</span><span style="font-family: Courier New,Courier,monospace;">
<br>
-</span>I hope the reader managed to get to this point and found the basic tutorial to be useful (in the end it's not so basic). Worth
+</span>I hope the reader managed to get to this point and found the
+basic tutorial to be useful (in the end it's not so basic). Worth
to notice that construction of the Voronoi diagram takes only two lines
of code, everything else is about initializing input data structures,
traversing Voronoi graph, associating data with diagram primitives and
using Voronoi utilities. In
default mode Voronoi diagram operates with signed int (32-bit) input
-coordinate type and double (64-bit) output coordinate type. In Voronoi Advanced Tutorial we explain why this is enough for 95% of problems and how to expand the algorithm coordinate types for the other 5% of cases.<br>
+coordinate type and double (64-bit) output coordinate type. In Voronoi Advanced Tutorial we
+explain why this is enough for 95% of problems and how to expand the
+algorithm coordinate types for the other 5% of cases.<br>
+
<span style="font-family: Courier New,Courier,monospace;"></span><br>
+
<table class="docinfo" id="table1" 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>
+
+ <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>
</body></html>
\ No newline at end of file
==============================================================================
--- sandbox/gtl/doc/voronoi_benchmark.htm (original)
+++ sandbox/gtl/doc/voronoi_benchmark.htm 2012-04-09 18:16:19 EDT (Mon, 09 Apr 2012)
@@ -1,134 +1,129 @@
<!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 Benchmark</title>
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-<meta http-equiv="Content-Language" content="en-us">
-<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title></head><body>
-
+
+</head><body>
<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
- <tbody><tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
- <div style="padding: 5px;" align="center">
- <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/">
- </a></div>
- <div style="margin: 5px;">
- <h3 class="navbar">Contents</h3>
- <ul>
- <li>Boost.Polygon Main Page</li>
- <li>Design Overview</li>
- <li>Isotropy</li>
- <li>Coordinate Concept</li>
- <li>Interval Concept</li>
- <li>Point Concept</li>
- <li>Rectangle Concept</li>
- <li>Polygon 90 Concept</li>
- <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
- With Holes Concept</a></li>
- <li>Polygon 45 Concept</li>
- <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
- With Holes Concept</a></li>
- <li>Polygon Concept</li>
- <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
- Holes Concept</a></li>
- <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
- Concept</a></li>
- <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
- Concept</a></li>
- <li>Polygon Set Concept</li>
- <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
- Extraction 90</a></li>
- <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
- Extraction 45</a></li>
- <li><a href="gtl_connectivity_extraction.htm">Connectivity
- Extraction</a></li>
- <li>Property Merge 90</li>
- <li>Property Merge 45</li>
- <li>Property Merge</li>
+
+ <tbody>
+ <tr>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ <div style="padding: 5px;" align="center"> <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/"> </a></div>
+ <div style="margin: 5px;">
+ <h3 class="navbar">Contents</h3>
+ <ul>
+ <li>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
+ <li>Isotropy</li>
+ <li>Coordinate Concept</li>
+ <li>Interval Concept</li>
+ <li>Point Concept</li>
+ <li>Rectangle Concept</li>
+ <li>Polygon 90 Concept</li>
+ <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
+With Holes Concept</a></li>
+ <li>Polygon 45 Concept</li>
+ <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
+With Holes Concept</a></li>
+ <li>Polygon Concept</li>
+ <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
+Holes Concept</a></li>
+ <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
+Concept</a></li>
+ <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
+Concept</a></li>
+ <li>Polygon Set Concept</li>
+ <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
+Extraction 90</a></li>
+ <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
+Extraction 45</a></li>
+ <li><a href="gtl_connectivity_extraction.htm">Connectivity
+Extraction</a></li>
+ <li>Property Merge 90</li>
+ <li>Property Merge 45</li>
+ <li>Property Merge</li>
<li><a href="voronoi_main.htm">Voronoi Main Page<br>
-</a></li>
+ </a></li>
<li>Voronoi Benchmark<br>
</li>
<li>Voronoi Builder</li>
<li><a href="voronoi_diagram.htm">Voronoi Diagram<br>
-</a></li>
+ </a></li>
<li>Voronoi Predicates</li>
<li>Voronoi Robust FPT<br>
</li>
<li>Voronoi Utils</li>
-</ul>
- <h3 class="navbar">Other Resources</h3>
- <ul>
- <li>GTL Boostcon 2009 Paper</li>
- <li><a href="GTL_boostcon_draft03.htm">GTL Boostcon 2009
- Presentation</a></li>
- <li>Performance Analysis</li>
- <li>Layout Versus Schematic Tutorial</li>
- <li>Minkowski Sum Tutorial</li>
- <li>Voronoi Basic Tutorial</li>
- <li>Voronoi Advanced Tutorial</li>
- </ul>
- </div>
- <h3 class="navbar">Polygon Sponsor</h3>
- <div style="padding: 5px;" align="center">
- <img src="images/intlogo.gif" border="0" height="51" width="127"><a title="www.adobe.com home page" tabindex="2" style="border: medium none ;" href="http://www.adobe.com/">
- </a></div>
- </td>
- <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"><!-- End Header -->
- <br>
- <p></p>
- <h1>Voronoi Benchmark</h1>There are not many known Voronoi libraries that are capable to satisfy following set of conditions:<br>
+ </ul>
+ <h3 class="navbar">Other Resources</h3>
+ <ul>
+ <li>GTL Boostcon 2009 Paper</li>
+ <li><a href="GTL_boostcon_draft03.htm">GTL Boostcon 2009
+Presentation</a></li>
+ <li>Performance Analysis</li>
+ <li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
+ <li>Voronoi Basic Tutorial</li>
+ <li><a href="voronoi_advanced_tutorial.htm">Voronoi 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>
+
+ <h1>Voronoi Benchmark</h1>
+There are not many known Voronoi libraries that are capable to satisfy
+following set of conditions:<br>
<ul>
<li>could handle both point and segment input geometries;</li>
- <li>give exact warranties about the algorithm robustness and output topology;<br>
+ <li>give exact warranties about the algorithm robustness and
+output topology;<br>
</li>
- <li>compute output geometries within precision of the output coordinate type.</li>
+ <li>compute output geometries within precision of the output
+coordinate type.</li>
</ul>
-Apart from Boost.Polygon Voronoi we managed to find just one library that meets at least two of those requirements: CGAL
+Apart from Boost.Polygon Voronoi we managed to find just one library
+that meets at least two of those requirements: CGAL
(it is clearly defined in CGAL documentation that it's capable to
handle the first two items, however there are no warranties on the
output geometries precision). Taking into account that CGAL is
well-known in the
computational geometry area it should be clear why it is the main
-target of this benchmark comparison. Other libraries (OpenVoronoi, QHull, Triangle), that at least
+target of this benchmark comparison. Other libraries (OpenVoronoi, QHull, Triangle),
+that at least
partially satisfy above requirements would be added to this benchmark
incrementally (we are open for suggestions).<br>
<h2>Important<br>
</h2>
While results of this benchmark show complete dominance of
-the Boost.Polygon Voronoi over the CGAL Delaunay Graph implementation, we would like to make it clear
+the Boost.Polygon Voronoi over the CGAL Delaunay Graph implementation,
+we would like to make it clear
that both libraries use different approach to construct Voronoi
diagram. Thus there are problems were CGAL incremental approach would
-be still more vital than sweepline approach (e.g. input sites are inserted as a live stream
+be still more vital than sweepline approach (e.g. input sites are
+inserted as a live stream
data).<br>
-
<h2>Voronoi Benchmark Details<br>
-
</h2>
-
-The benchmark consists of the two parts. The first one constructs the Voronoi diagram of a set of random points (voronoi_benchmark_points.cpp), the second one constructs the Voronoi diagram of a set of random segments (voronoi_benchmark_segments.cpp).
+The benchmark consists of the two parts. The first one constructs the
+Voronoi diagram of a set of random points (voronoi_benchmark_points.cpp),
+the second one constructs the Voronoi diagram of a set of random
+segments (voronoi_benchmark_segments.cpp).
Below we list important details about the benchmark, Boost and CGAL
-implementation that should be considered while reviewing benchmark results:<br>
+implementation that should be considered while reviewing benchmark
+results:<br>
<ul>
- <li>We ensure that input data sets are the same for both libraries by initializing random generator with the same seed;</li>
- <li>We ensure that input data sets that consist of segments don't contain intersections using Boost.Polygon functionality;<br>
+ <li>We ensure that input data sets are the same for both
+libraries by initializing random generator with the same seed;</li>
+ <li>We ensure that input data sets that consist of segments
+don't contain intersections using Boost.Polygon functionality;<br>
</li>
<li>There is no Voronoi diagram data structure in CGAL at the
moment. That's why we use Segment Delaunay Graph which is topologically
@@ -140,14 +135,14 @@
storage required for those in our benchmarks. Thus one may expect
Boost.Polygon Voronoi to be even more faster in comparison with CGAL.<br>
</li>
-
- <li>The Boost and CGAL implementation process each input segment
+ <li>The Boost and CGAL implementation process each input
+segment
as 3 input objects (segment itself and its endpoints), thus the running
-time and memory usage for Voronoi of segments would be approximately at least 3 times
+time and memory usage for Voronoi of segments would be approximately at
+least 3 times
slower than for Voronoi of points;<br>
</li>
</ul>
-
<br>
The benchmark was executed on the following two system configurations:<br>
<br>
@@ -156,37 +151,38 @@
Libraries: Boost 1.48.0, CGAL-4.0.<br>
<br>
Hardware: Intel i5-7600 2.8 GHz, 4GiB RAM.<br>
-
OS: Ubuntu 11.10 64-bit.<br>
-
-Libraries: Boost 1.48.0, CGAL-4.0, GMP 5.0.4, MPFR 3.1.0 + cumulative patch.<br>
-
+Libraries: Boost 1.48.0, CGAL-4.0, GMP 5.0.4, MPFR 3.1.0 + cumulative
+patch.<br>
<h2>Voronoi Benchmark Results</h2>
-
-
-
<h3>Random Points Benchmark</h3>
-
<table style="text-align: left; width: 100%; margin-left: auto; margin-right: auto;" border="1" cellpadding="2" cellspacing="2">
<tbody>
<tr>
<td colspan="2" rowspan="1" style="vertical-align: top; text-align: center;">Test specification<br>
</td>
- <td colspan="4" rowspan="1" style="vertical-align: top; text-align: center;">Average construction time (in secs)<br>
+ <td colspan="4" rowspan="1" style="vertical-align: top; text-align: center;">Average construction
+time (in secs)<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; text-align: center;">Number of Points<br>
+ <td style="vertical-align: top; text-align: center;">Number
+of Points<br>
</td>
- <td style="vertical-align: top; text-align: center;">Number of Runs<br>
+ <td style="vertical-align: top; text-align: center;">Number
+of Runs<br>
</td>
- <td style="vertical-align: top; text-align: center;">Boost Win-32<br>
+ <td style="vertical-align: top; text-align: center;">Boost
+Win-32<br>
</td>
- <td style="vertical-align: top; text-align: center;">CGAL Win-32<br>
+ <td style="vertical-align: top; text-align: center;">CGAL
+Win-32<br>
</td>
- <td style="vertical-align: top; text-align: center;">Boost Linux-64<br>
+ <td style="vertical-align: top; text-align: center;">Boost
+Linux-64<br>
</td>
- <td style="vertical-align: top; text-align: center;">CGAL Linux-64<br>
+ <td style="vertical-align: top; text-align: center;">CGAL
+Linux-64<br>
</td>
</tr>
<tr>
@@ -289,38 +285,42 @@
<tr>
<td style="vertical-align: top;"><img style="width: 500px; height: 300px;" alt="" src="../libs/polygon/benchmark/benchmark_results/plots/benchmark_points_100000.png"></td>
<td style="vertical-align: top;"><img style="width: 500px; height: 300px;" alt="" src="../libs/polygon/benchmark/benchmark_results/plots/benchmark_points_1000000.png"></td>
- </tr><tr>
+ </tr>
+ <tr>
<td style="vertical-align: top;"><img style="width: 500px; height: 300px;" alt="" src="../libs/polygon/benchmark/benchmark_results/plots/benchmark_points_memory.png"><br>
</td>
<td style="vertical-align: top;"><img style="width: 500px; height: 300px;" alt="" src="../libs/polygon/benchmark/benchmark_results/plots/benchmark_points_all.png"><br>
</td>
</tr>
-
</tbody>
</table>
-
-
<h3>Random Segments Benchmark</h3>
-
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
<tbody>
<tr>
<td colspan="2" rowspan="1" style="vertical-align: top; text-align: center;">Test specification<br>
</td>
- <td colspan="4" rowspan="1" style="vertical-align: top; text-align: center;">Average construction time (in secs)</td>
+ <td colspan="4" rowspan="1" style="vertical-align: top; text-align: center;">Average construction
+time (in secs)</td>
</tr>
<tr>
- <td style="vertical-align: top; text-align: center;">Number of Segments<br>
+ <td style="vertical-align: top; text-align: center;">Number
+of Segments<br>
</td>
- <td style="vertical-align: top; text-align: center;">Number of Runs<br>
+ <td style="vertical-align: top; text-align: center;">Number
+of Runs<br>
</td>
- <td style="vertical-align: top; text-align: center;">Boost Win-32<br>
+ <td style="vertical-align: top; text-align: center;">Boost
+Win-32<br>
</td>
- <td style="vertical-align: top; text-align: center;">CGAL Win-32<br>
+ <td style="vertical-align: top; text-align: center;">CGAL
+Win-32<br>
</td>
- <td style="vertical-align: top; text-align: center;">Boost Linux-64<br>
+ <td style="vertical-align: top; text-align: center;">Boost
+Linux-64<br>
</td>
- <td style="vertical-align: top; text-align: center;">CGAL Linux-64<br>
+ <td style="vertical-align: top; text-align: center;">CGAL
+Linux-64<br>
</td>
</tr>
<tr>
@@ -423,19 +423,19 @@
<tr>
<td style="vertical-align: top;"><img style="width: 500px; height: 300px;" alt="" src="../libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_100000.png"></td>
<td style="vertical-align: top;"><img style="width: 500px; height: 300px;" alt="" src="../libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_1000000.png"></td>
- </tr><tr>
+ </tr>
+ <tr>
<td style="vertical-align: top;"><img style="width: 500px; height: 300px;" alt="" src="../libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_memory.png"><br>
</td>
<td style="vertical-align: top;"><img style="width: 500px; height: 300px;" alt="" src="../libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_all.png"><br>
</td>
</tr>
-
</tbody>
</table>
-<span style="font-weight: bold;"></span>
- <h2>Voronoi Benchmark Conclusions</h2>The main conclusions for the benchmark results above are following:<br>
-<ul>
-
+ <span style="font-weight: bold;"></span>
+ <h2>Voronoi Benchmark Conclusions</h2>
+The main conclusions for the benchmark results above are following:<br>
+ <ul>
<li>There is no input size range were CGAL would outperform
Boost.Polygon Voronoi. Even considering the fact that we didn't include
time it would take CGAL to compute coordinates of the Voronoi vertices.</li>
@@ -443,12 +443,10 @@
has clear N*log(N) complexity, while this doesn't seem to be true for
CGAL (at least for large input data sets).<br>
</li>
-
<li>Boost.Polygon Voronoi computes coordinates of the output
Voronoi vertices within 64 machine epsilon precision. There are no such
warranties for the CGAL library.<br>
</li>
-
<li>Boost.Polygon Voronoi of points is 4 times faster for small
input data sets (10 points) and this factor grows up to 100 for large
input data sets (1000000 points).</li>
@@ -458,32 +456,30 @@
<li>Boost.Polygon
Voronoi is capable to construct Voronoi of 10000 points or 1000
segments in 0.02 seconds. This allows to produce real time frame rate
-for those quantities.</li></ul></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>
+for those quantities.</li>
+ </ul>
+ </td>
+ </tr>
+ <tr>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
+ <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
+ <table class="docinfo" id="table2" frame="void" rules="none">
+ <colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> <tbody valign="top">
+ <tr>
+ <th class="docinfo-name">Copyright:</th>
+ <td>Copyright © Intel Corporation 2008-2010.</td>
+ </tr>
+ <tr class="field">
+ <th class="docinfo-name">License:</th>
+ <td class="field-body">Distributed under the Boost Software
+License, Version 1.0. (See accompanying file <tt class="literal"><span class="pre">LICENSE_1_0.txt</span></tt> or copy at <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
+http://www.boost.org/LICENSE_1_0.txt>)</td>
+ </tr>
+ </tbody>
+ </table>
+ </td>
+ </tr>
+ </tbody>
+</table>
</body></html>
\ No newline at end of file
==============================================================================
--- sandbox/gtl/doc/voronoi_builder.htm (original)
+++ sandbox/gtl/doc/voronoi_builder.htm 2012-04-09 18:16:19 EDT (Mon, 09 Apr 2012)
@@ -1,287 +1,286 @@
<!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 Builder</title>
-
-
-
-
-
-
-
-
-
-
-
-
-
-<meta http-equiv="Content-Language" content="en-us">
-<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title></head><body>
-
+
+</head><body>
<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
- <tbody><tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
- <div style="padding: 5px;" align="center">
- <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/">
- </a></div>
- <div style="margin: 5px;">
- <h3 class="navbar">Contents</h3>
- <ul>
- <li>Boost.Polygon Main Page</li>
- <li>Design Overview</li>
- <li>Isotropy</li>
- <li>Coordinate Concept</li>
- <li>Interval Concept</li>
- <li>Point Concept</li>
- <li>Rectangle Concept</li>
- <li>Polygon 90 Concept</li>
- <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
- With Holes Concept</a></li>
- <li>Polygon 45 Concept</li>
- <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
- With Holes Concept</a></li>
- <li>Polygon Concept</li>
- <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
- Holes Concept</a></li>
- <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
- Concept</a></li>
- <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
- Concept</a></li>
- <li>Polygon Set Concept</li>
- <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
- Extraction 90</a></li>
- <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
- Extraction 45</a></li>
- <li><a href="gtl_connectivity_extraction.htm">Connectivity
- Extraction</a></li>
- <li>Property Merge 90</li>
- <li>Property Merge 45</li>
- <li>Property Merge</li>
+
+ <tbody>
+ <tr>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ <div style="padding: 5px;" align="center"> <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/"> </a></div>
+ <div style="margin: 5px;">
+ <h3 class="navbar">Contents</h3>
+ <ul>
+ <li>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
+ <li>Isotropy</li>
+ <li>Coordinate Concept</li>
+ <li>Interval Concept</li>
+ <li>Point Concept</li>
+ <li>Rectangle Concept</li>
+ <li>Polygon 90 Concept</li>
+ <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
+With Holes Concept</a></li>
+ <li>Polygon 45 Concept</li>
+ <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
+With Holes Concept</a></li>
+ <li>Polygon Concept</li>
+ <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
+Holes Concept</a></li>
+ <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
+Concept</a></li>
+ <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
+Concept</a></li>
+ <li>Polygon Set Concept</li>
+ <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
+Extraction 90</a></li>
+ <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
+Extraction 45</a></li>
+ <li><a href="gtl_connectivity_extraction.htm">Connectivity
+Extraction</a></li>
+ <li>Property Merge 90</li>
+ <li>Property Merge 45</li>
+ <li>Property Merge</li>
<li><a href="voronoi_main.htm">Voronoi Main Page<br>
-</a></li>
+ </a></li>
<li>Voronoi Benchmark<br>
</li>
<li>Voronoi Builder</li>
<li><a href="voronoi_diagram.htm">Voronoi Diagram<br>
-</a></li>
+ </a></li>
<li>Voronoi Predicates</li>
<li>Voronoi Robust FPT<br>
</li>
<li>Voronoi Utils</li>
-</ul>
- <h3 class="navbar">Other Resources</h3>
- <ul>
- <li>GTL Boostcon 2009 Paper</li>
- <li><a href="GTL_boostcon_draft03.htm">GTL Boostcon 2009
- Presentation</a></li>
- <li>Performance Analysis</li>
- <li>Layout Versus Schematic Tutorial</li>
- <li>Minkowski Sum Tutorial</li>
- <li>Voronoi Basic Tutorial</li>
- <li>Voronoi Advanced Tutorial</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 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 data structure builder. The structure
- shares Voronoi name as the events generated by it correspond to the
- Voronoi diagram edges and vertices, thus giving enough information to
- construct the 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 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;">
- 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><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 the robust and efficient
- predicates.<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 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>
-
+ </ul>
+ <h3 class="navbar">Other Resources</h3>
+ <ul>
+ <li>GTL Boostcon 2009 Paper</li>
+ <li><a href="GTL_boostcon_draft03.htm">GTL Boostcon 2009
+Presentation</a></li>
+ <li>Performance Analysis</li>
+ <li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
+ <li>Voronoi Basic Tutorial</li>
+ <li><a href="voronoi_advanced_tutorial.htm">Voronoi 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>
+
+ <h1>Voronoi Builder<br>
+ </h1>
+Voronoi builder is event generator structure. It implements <a href="http://www.ams.org/samplings/feature-column/fcarc-voronoi">sweepline
+algorithm</a> 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 data structure builder.
+The structure shares Voronoi name as the events generated by it
+correspond to the Voronoi diagram edges and vertices, thus giving
+enough information to construct the 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 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;">
+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><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 the robust and
+efficient predicates.<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
+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>
<h2>Member Functions</h2>
-
- <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>
- </tr>
- <tr>
+ <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>
+ </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>
- <td style="vertical-align: top;">Inserts point object with the specified coordinates into the Voronoi builder. <br>
+ <td style="vertical-align: top;">Inserts point object with
+the specified coordinates into the 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 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 the Voronoi builder.<br>
-
- Point object should support x() and y() methods to retrieve its coordinates.<br>
+ <td style="vertical-align: top;">Inserts point object into
+the 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(<br>
+ <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>
- </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>
- </td>
- </tr>
- <tr>
- <td style="vertical-align: top;"><span style="font-family: Courier New,Courier,monospace;">void insert_segment(<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>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;"><span style="font-family: Courier New,Courier,monospace;">void
+insert_segment(<br>
const int_type& x1,<br>
const int_type& y1,<br>
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 segment object
+with the specified coordinates into the 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>
+ <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(<br>
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>
-Endpoint object should support x() and y() methods to retrieve its coordinates.<br>
+ <td style="vertical-align: top;">Inserts segment object
+with the specified endpoints into the Voronoi builder.<br>
+Endpoint object should support x() and y() methods to retrieve its
+coordinates.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template <typename SegmentType><br>
+ <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;">Inserts 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>
- </td>
- </tr>
-<tr>
- <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace;">
- template <typename SegmentIterator><br>
- void insert_segments(SegmentIterator first_segment, SegmentIterator last_segment)<br>
- </td>
- <td style="vertical-align: top;" width="693">Inserts segment
- objects 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>
- </td>
- </tr>
- <tr>
- <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace;">
- template <typename PointIterator, typename SegmentIterator><br>
+ <td style="vertical-align: top;">Inserts 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>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace;">
+template <typename SegmentIterator><br>
+void insert_segments(SegmentIterator first_segment, SegmentIterator
+last_segment)<br>
+ </td>
+ <td style="vertical-align: top;" width="693">Inserts
+segment objects 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>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace;">
+template <typename PointIterator, typename SegmentIterator><br>
void insert_sites(<br>
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 object 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 data structure. It's
- responsibility of the output structure builder object to process them. For
- example both Voronoi diagram and Delaunay triangulation could be
- constructed from the Voronoi builder events, however internally
- they are different data structures, so it's up to them to process
- properly events produced by the builder object.<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>
- </tbody></table>
- <h1>Voronoi Coordinate Type Traits</h1>
- <p>The library provides 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>
- <br>
- template <><br>
- struct voronoi_ctype_traits<int32> {<br>
+ </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>
+ </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 data structure. It's responsibility of the
+output structure builder object to process them. For example both
+Voronoi diagram and Delaunay triangulation could be constructed from
+the Voronoi builder events, however internally they are different data
+structures, so it's up to them to process properly events produced by
+the builder object.<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>
+ </tbody>
+ </table>
+ <h1>Voronoi Coordinate Type Traits</h1>
+ <p>The library provides 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>
+ <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 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>
- };</p>
- </font>
- <p>One
+};</p>
+ </font>
+ <p>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
@@ -290,127 +289,128 @@
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">
- <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;">
- 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 64X-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+16) 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+16) bits and exponent able to handle 64X-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 comparison structure that
- checks if two fpt_type values are withing the 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>
-
- </tbody></table>
- <p>Notes:<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;">
+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 64X-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+16) 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+16) bits and exponent able to handle
+64X-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 comparison structure
+that checks if two fpt_type values are withing the 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>
+ </tbody>
+ </table>
+ <p>Notes:<br>
1) 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
- (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 with
+2) 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
+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></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>
+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>
+ </td>
+ </tr>
+ <tr>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
+ <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
+ <table class="docinfo" id="table2" frame="void" rules="none">
+ <colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> <tbody valign="top">
+ <tr>
+ <th class="docinfo-name">Copyright:</th>
+ <td>Copyright © Intel Corporation 2008-2010.</td>
+ </tr>
+ <tr class="field">
+ <th class="docinfo-name">License:</th>
+ <td class="field-body">Distributed under the Boost Software
+License, Version 1.0. (See accompanying file <tt class="literal"><span class="pre">LICENSE_1_0.txt</span></tt> or copy at <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
+http://www.boost.org/LICENSE_1_0.txt>)</td>
+ </tr>
+ </tbody>
+ </table>
+ </td>
+ </tr>
+ </tbody>
+</table>
</body></html>
\ No newline at end of file
==============================================================================
--- sandbox/gtl/doc/voronoi_diagram.htm (original)
+++ sandbox/gtl/doc/voronoi_diagram.htm 2012-04-09 18:16:19 EDT (Mon, 09 Apr 2012)
@@ -1,116 +1,95 @@
<!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=utf-8">
+
+ <meta http-equiv="content-type" content="text/html; charset=utf-8">
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-<meta http-equiv="Content-Language" content="en-us">
-<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title><meta http-equiv="content-type" content="text/html; charset=utf-8"><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body>
-
+</head><body>
<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
- <tbody><tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
- <div style="padding: 5px;" align="center">
- <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/">
- </a></div>
- <div style="margin: 5px;">
- <h3 class="navbar">Contents</h3>
- <ul>
- <li>Boost.Polygon Main Page</li>
- <li>Design Overview</li>
- <li>Isotropy</li>
- <li>Coordinate Concept</li>
- <li>Interval Concept</li>
- <li>Point Concept</li>
- <li>Rectangle Concept</li>
- <li>Polygon 90 Concept</li>
- <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
- With Holes Concept</a></li>
- <li>Polygon 45 Concept</li>
- <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
- With Holes Concept</a></li>
- <li>Polygon Concept</li>
- <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
- Holes Concept</a></li>
- <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
- Concept</a></li>
- <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
- Concept</a></li>
- <li>Polygon Set Concept</li>
- <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
- Extraction 90</a></li>
- <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
- Extraction 45</a></li>
- <li><a href="gtl_connectivity_extraction.htm">Connectivity
- Extraction</a></li>
- <li>Property Merge 90</li>
- <li>Property Merge 45</li>
- <li>Property Merge</li>
- <li><a href="voronoi_main.htm">Voronoi Main Page<br>
-</a></li>
- <li>Voronoi Benchmark</li>
- <li>Voronoi Builder<br>
- </li>
- <li>Voronoi Diagram</li>
+ <tbody>
+ <tr>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ <div style="padding: 5px;" align="center"> <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/"> </a></div>
+ <div style="margin: 5px;">
+ <h3 class="navbar">Contents</h3>
+ <ul>
+ <li>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
+ <li>Isotropy</li>
+ <li>Coordinate Concept</li>
+ <li>Interval Concept</li>
+ <li>Point Concept</li>
+ <li>Rectangle Concept</li>
+ <li>Polygon 90 Concept</li>
+ <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
+With Holes Concept</a></li>
+ <li>Polygon 45 Concept</li>
+ <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
+With Holes Concept</a></li>
+ <li>Polygon Concept</li>
+ <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
+Holes Concept</a></li>
+ <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
+Concept</a></li>
+ <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
+Concept</a></li>
+ <li>Polygon Set Concept</li>
+ <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
+Extraction 90</a></li>
+ <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
+Extraction 45</a></li>
+ <li><a href="gtl_connectivity_extraction.htm">Connectivity
+Extraction</a></li>
+ <li>Property Merge 90</li>
+ <li>Property Merge 45</li>
+ <li>Property Merge</li>
+ <li><a href="voronoi_main.htm">Voronoi Main Page<br>
+ </a></li>
+ <li>Voronoi Benchmark</li>
+ <li>Voronoi Builder<br>
+ </li>
+ <li>Voronoi Diagram</li>
<li>Voronoi Predicates</li>
-
<li>Voronoi Robust FPT<br>
</li>
-
-
-
<li>Voronoi Utils<br>
</li>
-
-
- </ul>
- <h3 class="navbar">Other Resources</h3>
- <ul>
- <li>GTL Boostcon 2009 Paper</li>
- <li><a href="GTL_boostcon_draft03.htm">GTL Boostcon 2009
- Presentation</a></li>
- <li>Performance Analysis</li>
- <li>Layout Versus Schematic Tutorial</li>
- <li>Minkowski Sum Tutorial</li>
- <li>Voronoi Basic Tutorial</li>
- <li>Voronoi Advanced Tutorial</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>
+ </ul>
+ <h3 class="navbar">Other Resources</h3>
+ <ul>
+ <li>GTL Boostcon 2009 Paper</li>
+ <li><a href="GTL_boostcon_draft03.htm">GTL Boostcon 2009
+Presentation</a></li>
+ <li>Performance Analysis</li>
+ <li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
+ <li>Voronoi Basic Tutorial</li>
+ <li><a href="voronoi_advanced_tutorial.htm">Voronoi 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>
- <h1>Voronoi Diagram</h1>Voronoi
+ <h1>Voronoi Diagram</h1>
+Voronoi
diagram is a computational geometry concept that represents partition
of a given space onto regions, with bounds determined by distances to a
-specified family of objects. The application area of this concept vary from Archaeology to Zoology. Boost.Polygon provides implementation of
+specified family of objects. The application area of this concept vary <a href="http://www.ics.uci.edu/%7Eeppstein/gina/scot.drysdale.html">from
+Archaeology to Zoology</a>. Boost.Polygon provides implementation of
the Voronoi diagram data structure in 2D space. Internal representation
consists of a three arrays, that respectively contain: Voronoi cells
(area around input sites bounded by Voronoi edges), Voronoi vertices
@@ -128,10 +107,13 @@
<br>
<img style="border: 1px solid ; width: 300px; height: 300px;" alt="" src="images/voronoi2.png"><br>
<br>
-Voronoi diagram declaration and list of the member functions is following:<br>
+Voronoi diagram declaration and list of the member functions is
+following:<br>
<br>
- <span style="font-family: Courier New,Courier,monospace;">template <typename T, typename TRAITS = voronoi_diagram_traits<T> ></span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">class voronoi_diagram;<br>
+ <span style="font-family: Courier New,Courier,monospace;">template
+<typename T, typename TRAITS = voronoi_diagram_traits<T> ></span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">class
+voronoi_diagram;<br>
<br>
</span>
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
@@ -143,58 +125,75 @@
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void clear()<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void
+clear()<br>
</td>
<td style="vertical-align: top;">Clears diagram.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const cell_container_type &cells() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const
+cell_container_type &cells() const<br>
</td>
- <td style="vertical-align: top;">Returns the const reference to the cell container.<br>
+ <td style="vertical-align: top;">Returns the const
+reference to the cell container.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const vertex_container_type &vertices() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const
+vertex_container_type &vertices() const<br>
</td>
- <td style="vertical-align: top;">Returns the const reference to the vertex container.<br>
+ <td style="vertical-align: top;">Returns the const
+reference to the vertex container.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const edge_container_type &edges() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const
+edge_container_type &edges() const<br>
</td>
- <td style="vertical-align: top;">Returns the const reference to the edge container.<br>
+ <td style="vertical-align: top;">Returns the const
+reference to the edge container.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">unsigned int num_cells() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">unsigned
+int num_cells() const<br>
</td>
- <td style="vertical-align: top;">Returns the number of the cells in the Voronoi diagram.<br>
+ <td style="vertical-align: top;">Returns the number of the
+cells in the Voronoi diagram.<br>
This value should be the same as the size of the cell container.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">unsigned int num_edges() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">unsigned
+int num_edges() const<br>
</td>
- <td style="vertical-align: top;">Returns the number of the edges in the Voronoi diagram.<br>
+ <td style="vertical-align: top;">Returns the number of the
+edges in the Voronoi diagram.<br>
This value should be twice smaller than the size of the edge container.<br>
The reason is that two half-edges are present for each Voronoi edge.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">unsigned int num_vertices() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">unsigned
+int num_vertices() const<br>
</td>
- <td style="vertical-align: top;">Returns the number of the vertices in the Voronoi diagram.<br>
+ <td style="vertical-align: top;">Returns the number of the
+vertices in the Voronoi diagram.<br>
This value should be the same as the size of the vertex container.<br>
</td>
</tr>
</tbody>
</table>
<h1>Voronoi Edge</h1>
-Voronoi edge is represented as a bit improved classical half-edge data structure. The declaration and list of the member functions is following:<br>
+Voronoi edge is represented as a bit improved classical half-edge
+data structure. The declaration and list of the member functions is
+following:<br>
<br>
- <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;">class voronoi_edge;<br>
+ <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;">class
+voronoi_edge;<br>
<br>
</span>
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
@@ -206,276 +205,357 @@
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_cell_type *cell()<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_cell_type
+*cell()<br>
</td>
- <td style="vertical-align: top;">Returns the pointer to the Voronoi <span style="font-family: Courier New,Courier,monospace;"></span>cell that edge belongs to.<br>
+ <td style="vertical-align: top;">Returns the pointer to the
+Voronoi <span style="font-family: Courier New,Courier,monospace;"></span>cell
+that edge belongs to.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_cell_type *cell() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const
+voronoi_cell_type *cell() const<br>
</td>
- <td style="vertical-align: top;">Returns the const pointer to the Voronoi cell that edge belongs to.<br>
+ <td style="vertical-align: top;">Returns the const pointer
+to the Voronoi cell that edge belongs to.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void cell(voronoi_cell_type *c)<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void
+cell(voronoi_cell_type *c)<br>
</td>
- <td style="vertical-align: top;">Sets the Voronoi cell pointer for the cell current edge belongs to.<br>
+ <td style="vertical-align: top;">Sets the Voronoi cell
+pointer for the cell current edge belongs to.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_vertex_type *vertex0()<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_vertex_type
+*vertex0()<br>
</td>
- <td style="vertical-align: top;">Returns the pointer to the start point of the edge.<br>
+ <td style="vertical-align: top;">Returns the pointer to the
+start point of the edge.<br>
If edge is infinite in that direction returns NULL.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_vertex_type *vertex0() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const
+voronoi_vertex_type *vertex0() const<br>
</td>
- <td style="vertical-align: top;">Returns the const pointer to the start point of the edge.<br>
+ <td style="vertical-align: top;">Returns the const pointer
+to the start point of the edge.<br>
If edge is infinite in that direction returns NULL.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void vertex0(voronoi_vertex_type *v)<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void
+vertex0(voronoi_vertex_type *v)<br>
</td>
- <td style="vertical-align: top;">Sets the start point pointer of the edge.<br>
+ <td style="vertical-align: top;">Sets the start point
+pointer of the edge.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_vertex_type *vertex1()<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_vertex_type
+*vertex1()<br>
</td>
- <td style="vertical-align: top;">Returns the pointer to the end point of the edge.<br>
+ <td style="vertical-align: top;">Returns the pointer to the
+end point of the edge.<br>
If the edge is infinite in that direction returns NULL.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_vertex_type *vertex1() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const
+voronoi_vertex_type *vertex1() const<br>
</td>
- <td style="vertical-align: top;">Returns the const pointer to the end point of the edge.<br>
+ <td style="vertical-align: top;">Returns the const pointer
+to the end point of the edge.<br>
If the edge is infinite in that direction returns NULL.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void vertex1(voronoi_vertex_type *v)<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void
+vertex1(voronoi_vertex_type *v)<br>
</td>
- <td style="vertical-align: top;">Sets the endpoint pointer of the edge.<br>
+ <td style="vertical-align: top;">Sets the endpoint pointer
+of the edge.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type *twin()<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type
+*twin()<br>
</td>
- <td style="vertical-align: top;">Returns the pointer to the twin edge.<br>
+ <td style="vertical-align: top;">Returns the pointer to the
+twin edge.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_edge_type *twin() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const
+voronoi_edge_type *twin() const<br>
</td>
- <td style="vertical-align: top;">Returns the const pointer to the twin edge.<br>
+ <td style="vertical-align: top;">Returns the const pointer
+to the twin edge.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void twin(voronoi_edge_type *e)<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void
+twin(voronoi_edge_type *e)<br>
</td>
- <td style="vertical-align: top;">Sets the twin edge pointer of the edge.<br>
+ <td style="vertical-align: top;">Sets the twin edge pointer
+of the edge.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type *next()<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type
+*next()<br>
</td>
- <td style="vertical-align: top;">Returns the pointer to the CCW next edge within the corresponding Voronoi cell.<br>
+ <td style="vertical-align: top;">Returns the pointer to the
+CCW next edge within the corresponding Voronoi cell.<br>
Edges not necessarily share a common vertex.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_edge_type *next() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const
+voronoi_edge_type *next() const<br>
</td>
- <td style="vertical-align: top;">Returns the const pointer to the CCW next edge within the corresponding Voronoi cell.<br>
+ <td style="vertical-align: top;">Returns the const pointer
+to the CCW next edge within the corresponding Voronoi cell.<br>
Edges not necessarily share a common vertex.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void next(voronoi_edge_type *e)<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void
+next(voronoi_edge_type *e)<br>
</td>
- <td style="vertical-align: top;">Sets the CCW next edge pointer of the edge.<br>
+ <td style="vertical-align: top;">Sets the CCW next edge
+pointer of the edge.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type *prev()<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type
+*prev()<br>
</td>
- <td style="vertical-align: top;">Returns the pointer to the CCW prev edge within the corresponding Voronoi cell.<br>
+ <td style="vertical-align: top;">Returns the pointer to the
+CCW prev edge within the corresponding Voronoi cell.<br>
Edges not necessarily share a common vertex.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_edge_type *prev() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const
+voronoi_edge_type *prev() const<br>
</td>
- <td style="vertical-align: top;">Returns the const pointer to the CCW prev edge within the corresponding Voronoi cell.<br>
+ <td style="vertical-align: top;">Returns the const pointer
+to the CCW prev edge within the corresponding Voronoi cell.<br>
Edges not necessarily share a common vertex.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void prev(voronoi_edge_type *e)<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void
+prev(voronoi_edge_type *e)<br>
</td>
- <td style="vertical-align: top;">Sets the CCW prev edge pointer of the edge.<br>
+ <td style="vertical-align: top;">Sets the CCW prev edge
+pointer of the edge.<br>
</td>
</tr>
-
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void *data() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void
+*data() const<br>
</td>
- <td style="vertical-align: top;">Returns the pointer to the data associated with the edge.<br>
+ <td style="vertical-align: top;">Returns the pointer to the
+data associated with the edge.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void data(void *d) const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void
+data(void *d) const<br>
</td>
- <td style="vertical-align: top;">Sets the data pointer of the edge.<br>
+ <td style="vertical-align: top;">Sets the data pointer of
+the edge.<br>
This allows the user to associate any data type with the edge.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type *rot_next()<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type
+*rot_next()<br>
</td>
- <td style="vertical-align: top;">Returns the pointer to the CCW next edge rotated around the edge start point.<br>
+ <td style="vertical-align: top;">Returns the pointer to the
+CCW next edge rotated around the edge start point.<br>
If the edge is infinite in that direction returns NULL.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_edge_type *rot_next() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const
+voronoi_edge_type *rot_next() const<br>
</td>
- <td style="vertical-align: top;">Returns the const pointer to the CCW next edge rotated around the edge start point.<br>
-
+ <td style="vertical-align: top;">Returns the const pointer
+to the CCW next edge rotated around the edge start point.<br>
If the edge is infinite in that direction returns NULL.</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type *rot_prev()<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type
+*rot_prev()<br>
</td>
- <td style="vertical-align: top;">Returns the pointer to the CCW prev edge rotated around the edge start point.<br>
+ <td style="vertical-align: top;">Returns the pointer to the
+CCW prev edge rotated around the edge start point.<br>
If the edge is infinite in that direction returns NULL.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_edge_type *rot_prev() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const
+voronoi_edge_type *rot_prev() const<br>
</td>
- <td style="vertical-align: top;">Returns the const pointer to the CCW prev edge rotated around the edge start point.<br>
-
-
+ <td style="vertical-align: top;">Returns the const pointer
+to the CCW prev edge rotated around the edge start point.<br>
If the edge is infinite in that direction returns NULL.</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool is_finite() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool
+is_finite() const<br>
</td>
- <td style="vertical-align: top;">Returns true if the both endpoints of the edge are finite, else false.<br>
+ <td style="vertical-align: top;">Returns true if the both
+endpoints of the edge are finite, else false.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool is_linear() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool
+is_linear() const<br>
</td>
- <td style="vertical-align: top;">Returns true if the edge is linear (segment, ray, line), else false.<br>
+ <td style="vertical-align: top;">Returns true if the edge
+is linear (segment, ray, line), else false.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool is_curved() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool
+is_curved() const<br>
</td>
- <td style="vertical-align: top;">Returns true if the edge is curved (parabolic arc), else false.<br>
+ <td style="vertical-align: top;">Returns true if the edge
+is curved (parabolic arc), else false.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool is_primary() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool
+is_primary() const<br>
</td>
- <td style="vertical-align: top;">Returns false if the edge goes through the endpoint of the segment, else true.<br>
+ <td style="vertical-align: top;">Returns false if the edge
+goes through the endpoint of the segment, else true.<br>
</td>
</tr>
</tbody>
</table>
<span style="font-family: Courier New,Courier,monospace;"><br>
- </span>All the above methods have O(1) complexity. The size of the Voronoi edge structure is equal to: 6 * sizeof(void *).<br>
+ </span>All the above methods have O(1) complexity. The size of
+the Voronoi edge structure is equal to: 6 * sizeof(void *).<br>
<h1>Voronoi Cell</h1>
-
Voronoi cell is represented by a site the cell contains and a pointer
-to the incident edge. The declaration and list of the member functions is
+to the incident edge. The declaration and list of the member functions
+is
following:<br>
<br>
- <span style="font-family: Courier New,Courier,monospace;">template <typename T><br>
+ <span style="font-family: Courier New,Courier,monospace;">template
+<typename T><br>
class voronoi_cell;<br>
<br>
</span>
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
<tbody>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_cell(const point_type &p1,<br>
- voronoi_edge_type *edge)<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_cell(const
+point_type &p1,<br>
+
+voronoi_edge_type *edge)<br>
</td>
- <td style="vertical-align: top;">Constructs the Voronoi cell from the given point site and pointer to the one of the boundary edges.<br>
+ <td style="vertical-align: top;">Constructs the Voronoi
+cell from the given point site and pointer to the one of the boundary
+edges.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_cell(const point_type &p1,<br>
- const point_type &p2,<br>
- voronoi_edge_type *edge)<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_cell(const
+point_type &p1,<br>
+
+const point_type &p2,<br>
+
+voronoi_edge_type *edge)<br>
</td>
- <td style="vertical-align: top;">Constructs the Voronoi cell from the given segment site and pointer to the one of the boundary edges.<br>
+ <td style="vertical-align: top;">Constructs the Voronoi
+cell from the given segment site and pointer to the one of the boundary
+edges.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const point_type &point0() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const
+point_type &point0() const<br>
</td>
- <td style="vertical-align: top;">If the cell contains point site returns it.<br>
+ <td style="vertical-align: top;">If the cell contains point
+site returns it.<br>
If the cell contains segment site returns its first endpoint.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const point_type &point1() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const
+point_type &point1() const<br>
</td>
- <td style="vertical-align: top;">If the cell contains point site returns it.<br>
+ <td style="vertical-align: top;">If the cell contains point
+site returns it.<br>
If the cell contains segment site returns its second endpoint.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type *incident_edge()<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type
+*incident_edge()<br>
</td>
- <td style="vertical-align: top;">Returns the pointer to the one of the boundary edges.<br>
+ <td style="vertical-align: top;">Returns the pointer to the
+one of the boundary edges.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_edge_type *incident_edge() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const
+voronoi_edge_type *incident_edge() const<br>
</td>
- <td style="vertical-align: top;">Returns the const pointer to the one of the boundary edges.<br>
+ <td style="vertical-align: top;">Returns the const pointer
+to the one of the boundary edges.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void incident_edge(voronoi_edge_type *e)<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void
+incident_edge(voronoi_edge_type *e)<br>
</td>
- <td style="vertical-align: top;">Sets the incident boundary edge pointer of the cell.<br>
+ <td style="vertical-align: top;">Sets the incident boundary
+edge pointer of the cell.<br>
</td>
</tr>
-
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void *data() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void
+*data() const<br>
</td>
- <td style="vertical-align: top;">Returns the pointer to the data associated with the cell.</td>
+ <td style="vertical-align: top;">Returns the pointer to the
+data associated with the cell.</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void data(void *d) const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void
+data(void *d) const<br>
</td>
- <td style="vertical-align: top;">Sets the data pointer of the cell.<br>
-
+ <td style="vertical-align: top;">Sets the data pointer of
+the cell.<br>
This allows the user to associate any data type with the cell.</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool contains_point() const</td>
- <td style="vertical-align: top;">Returns true if the cell contains a point site, else false.</td>
- </tr>
- <tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool contains_segment() const</td>
- <td style="vertical-align: top;">Returns true if the cell contains a segment site, else false.</td>
- </tr>
- <tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool is_degenerate() const </td>
- <td style="vertical-align: top;">Returns true if the cell doesn't have an incident edge.<br>
-
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool
+contains_point() const</td>
+ <td style="vertical-align: top;">Returns true if the cell
+contains a point site, else false.</td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool
+contains_segment() const</td>
+ <td style="vertical-align: top;">Returns true if the cell
+contains a segment site, else false.</td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool
+is_degenerate() const </td>
+ <td style="vertical-align: top;">Returns true if the cell
+doesn't have an incident edge.<br>
Could happen if a few input segments share a common endpoint.</td>
</tr>
</tbody>
@@ -485,94 +565,116 @@
the Voronoi cell structure is equal to: 2 * sizeof(void *) + 4 *
sizeof(coordinate_type).<br>
<br>
-Following code snippet effectively traverses Voronoi edges around the Voronoi cell:<br>
+Following code snippet effectively traverses Voronoi edges around the
+Voronoi cell:<br>
<br>
- <span style="font-family: Courier New,Courier,monospace;">const voronoi_edge<double> *edge = cell->incident_edge();</span><br>
+ <span style="font-family: Courier New,Courier,monospace;">const
+voronoi_edge<double> *edge = cell->incident_edge();</span><br>
<span style="font-family: Courier New,Courier,monospace;">do {</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> edge = edge->next();</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> // Do smth. with edge.</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">} while (edge != cell->incident_edge());</span><br>
+ <span style="font-family: Courier New,Courier,monospace;">
+edge = edge->next();</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+// Do smth. with edge.</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">} while
+(edge != cell->incident_edge());</span><br>
<h1>Voronoi Vertex</h1>
Voronoi vertex is represented by a point that corresponds to the vertex
-and a pointer to the incident edge. The declaration and list of the member
+and a pointer to the incident edge. The declaration and list of the
+member
functions is following:<br>
<br>
- <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;">class voronoi_vertex;<br>
+ <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;">class
+voronoi_vertex;<br>
<br>
</span>
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
<tbody>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_vertex(const point_type &vertex, voronoi_edge_type *edge)<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_vertex(const
+point_type &vertex, voronoi_edge_type *edge)<br>
</td>
- <td style="vertical-align: top;">Constructs the Voronoi vertex that corresponds to the give point and incident edge.<br>
+ <td style="vertical-align: top;">Constructs the Voronoi
+vertex that corresponds to the give point and incident edge.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const point_type &vertex() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const
+point_type &vertex() const<br>
</td>
- <td style="vertical-align: top;">Returns the point that represents vertex.<br>
+ <td style="vertical-align: top;">Returns the point that
+represents vertex.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type *incident_edge()<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">voronoi_edge_type
+*incident_edge()<br>
</td>
- <td style="vertical-align: top;">Returns the incident edge pointer.<br>
+ <td style="vertical-align: top;">Returns the incident edge
+pointer.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const voronoi_edge_type *incident_edge() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">const
+voronoi_edge_type *incident_edge() const<br>
</td>
- <td style="vertical-align: top;">Returns the const pointer to the incident edge.<br>
+ <td style="vertical-align: top;">Returns the const pointer
+to the incident edge.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void incident_edge(voronoi_edge_type *e)<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void
+incident_edge(voronoi_edge_type *e)<br>
</td>
- <td style="vertical-align: top;">Sets the incident edge pointer.<br>
+ <td style="vertical-align: top;">Sets the incident edge
+pointer.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void *data() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void
+*data() const<br>
</td>
- <td style="vertical-align: top;">Returns the pointer to the data associated with the vertex.</td>
+ <td style="vertical-align: top;">Returns the pointer to the
+data associated with the vertex.</td>
</tr>
-
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void data(void *d) const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void
+data(void *d) const<br>
</td>
- <td style="vertical-align: top;">Sets the data pointer of the cell.<br>
-
-
+ <td style="vertical-align: top;">Sets the data pointer of
+the cell.<br>
This allows the user to associate any data type with the vertex.</td>
</tr>
</tbody>
</table>
<span style="font-family: Courier New,Courier,monospace;"><br>
- </span>All the above methods have O(1) complexity. The size of the Voronoi vertex structure is equal to: 2 * sizeof(void *) + 2 *
+ </span>All the above methods have O(1) complexity. The size of
+the Voronoi vertex structure is equal to: 2 * sizeof(void *) + 2 *
sizeof(coordinate_type).<br>
<br>
-Following code snipped effectively traverses Voronoi edges around the Voronoi vertex:<br>
+Following code snipped effectively traverses Voronoi edges around the
+Voronoi vertex:<br>
<br>
- <span style="font-family: Courier New,Courier,monospace;">const voronoi_edge<double> *edge = vertex->incident_edge();</span><br>
-
+ <span style="font-family: Courier New,Courier,monospace;">const
+voronoi_edge<double> *edge = vertex->incident_edge();</span><br>
<span style="font-family: Courier New,Courier,monospace;">do {</span><br style="font-family: Courier New,Courier,monospace;">
-
- <span style="font-family: Courier New,Courier,monospace;"> edge = edge->next();</span><br style="font-family: Courier New,Courier,monospace;">
-
- <span style="font-family: Courier New,Courier,monospace;"> // Do smth. with edge.</span><br style="font-family: Courier New,Courier,monospace;">
-
- <span style="font-family: Courier New,Courier,monospace;">} while (edge != vertex->incident_edge());</span><br>
+ <span style="font-family: Courier New,Courier,monospace;">
+edge = edge->next();</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+// Do smth. with edge.</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">} while
+(edge != vertex->incident_edge());</span><br>
<h1>Voronoi Diagram Traits<br>
</h1>
-
Voronoi diagram traits are used to configure the Voronoi diagram data
structure. The declaration and list of the required type definitions is
following:<br>
<br>
- <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;">struct voronoi_diagram_traits;<br>
+ <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;">struct
+voronoi_diagram_traits;<br>
<br>
</span>
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
@@ -580,14 +682,17 @@
<tr>
<td style="vertical-align: top; font-family: Courier New,Courier,monospace;">coordinate_type<br>
</td>
- <td style="vertical-align: top;">The main coordinate type of the Voronoi diagram internal structures.<br>
+ <td style="vertical-align: top;">The main coordinate type
+of the Voronoi diagram internal structures.<br>
</td>
</tr>
<tr>
<td style="vertical-align: top; font-family: Courier New,Courier,monospace;">ctype_converter_type<br>
</td>
- <td style="vertical-align: top;">Coordinate type converter structure.<br>
-Converts the coordinates provided by the Voronoi builder to the internal coordinate type.<br>
+ <td style="vertical-align: top;">Coordinate type converter
+structure.<br>
+Converts the coordinates provided by the Voronoi builder to the
+internal coordinate type.<br>
</td>
</tr>
<tr>
@@ -617,43 +722,35 @@
<tr>
<td style="vertical-align: top; font-family: Courier New,Courier,monospace;">vertex_equality_predicate_type<br>
</td>
- <td style="vertical-align: top;">Predicate that returns true if two points are considered to be equal.<br>
+ <td style="vertical-align: top;">Predicate that returns
+true if two points are considered to be equal.<br>
This is used to unite nearby Voronoi vertices.<br>
</td>
</tr>
</tbody>
</table>
-
-
-
-
-
-</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>
+ </td>
+ </tr>
+ <tr>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
+ <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
+ <table class="docinfo" id="table2" frame="void" rules="none">
+ <colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> <tbody valign="top">
+ <tr>
+ <th class="docinfo-name">Copyright:</th>
+ <td>Copyright © Intel Corporation 2008-2010.</td>
+ </tr>
+ <tr class="field">
+ <th class="docinfo-name">License:</th>
+ <td class="field-body">Distributed under the Boost Software
+License, Version 1.0. (See accompanying file <tt class="literal"><span class="pre">LICENSE_1_0.txt</span></tt> or copy at <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
+http://www.boost.org/LICENSE_1_0.txt>)</td>
+ </tr>
+ </tbody>
+ </table>
+ </td>
+ </tr>
+ </tbody>
+</table>
</body></html>
\ No newline at end of file
==============================================================================
--- sandbox/gtl/doc/voronoi_main.htm (original)
+++ sandbox/gtl/doc/voronoi_main.htm 2012-04-09 18:16:19 EDT (Mon, 09 Apr 2012)
@@ -1,144 +1,114 @@
<!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 Main</title>
+
+
+ <meta http-equiv="content-type" content="text/html; charset=utf-8">
+
+ <meta http-equiv="content-type" content="text/html; charset=utf-8">
+
+ <meta http-equiv="content-type" content="text/html; charset=utf-8">
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-<meta http-equiv="Content-Language" content="en-us">
-<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title><meta http-equiv="content-type" content="text/html; charset=utf-8"><meta http-equiv="content-type" content="text/html; charset=utf-8"><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body>
-
+</head><body>
<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
- <tbody><tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
- <div style="padding: 5px;" align="center">
- <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/">
- </a></div>
- <div style="margin: 5px;">
- <h3 class="navbar">Contents</h3>
- <ul>
- <li>Boost.Polygon Main Page</li>
- <li>Design Overview</li>
- <li>Isotropy</li>
- <li>Coordinate Concept</li>
- <li>Interval Concept</li>
- <li>Point Concept</li>
- <li>Rectangle Concept</li>
- <li>Polygon 90 Concept</li>
- <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
- With Holes Concept</a></li>
- <li>Polygon 45 Concept</li>
- <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
- With Holes Concept</a></li>
- <li>Polygon Concept</li>
- <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
- Holes Concept</a></li>
- <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
- Concept</a></li>
- <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
- Concept</a></li>
- <li>Polygon Set Concept</li>
- <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
- Extraction 90</a></li>
- <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
- Extraction 45</a></li>
- <li><a href="gtl_connectivity_extraction.htm">Connectivity
- Extraction</a></li>
- <li>Property Merge 90</li>
- <li>Property Merge 45</li>
- <li>Property Merge</li>
- <li>Voronoi Main Page<br>
-</li>
+ <tbody>
+ <tr>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ <div style="padding: 5px;" align="center"> <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/"> </a></div>
+ <div style="margin: 5px;">
+ <h3 class="navbar">Contents</h3>
+ <ul>
+ <li>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
+ <li>Isotropy</li>
+ <li>Coordinate Concept</li>
+ <li>Interval Concept</li>
+ <li>Point Concept</li>
+ <li>Rectangle Concept</li>
+ <li>Polygon 90 Concept</li>
+ <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
+With Holes Concept</a></li>
+ <li>Polygon 45 Concept</li>
+ <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
+With Holes Concept</a></li>
+ <li>Polygon Concept</li>
+ <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
+Holes Concept</a></li>
+ <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
+Concept</a></li>
+ <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
+Concept</a></li>
+ <li>Polygon Set Concept</li>
+ <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
+Extraction 90</a></li>
+ <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
+Extraction 45</a></li>
+ <li><a href="gtl_connectivity_extraction.htm">Connectivity
+Extraction</a></li>
+ <li>Property Merge 90</li>
+ <li>Property Merge 45</li>
+ <li>Property Merge</li>
+ <li>Voronoi Main Page<br>
+ </li>
<li>Voronoi Benchmark</li>
-
- <li>Voronoi Builder<br>
- </li>
- <li>Voronoi Diagram</li>
+ <li>Voronoi Builder<br>
+ </li>
+ <li>Voronoi Diagram</li>
<li>Voronoi Predicates</li>
-
<li>Voronoi Robust FPT<br>
</li>
-
-
-
<li>Voronoi Utils<br>
</li>
-
-
- </ul>
- <h3 class="navbar">Other Resources</h3>
- <ul>
- <li>GTL Boostcon 2009 Paper</li>
- <li><a href="GTL_boostcon_draft03.htm">GTL Boostcon 2009
- Presentation</a></li>
- <li>Performance Analysis</li>
- <li>Layout Versus Schematic Tutorial</li>
- <li>Minkowski Sum Tutorial</li>
- <li>Voronoi Basic Tutorial</li>
- <li>Voronoi Advanced Tutorial</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>
+ </ul>
+ <h3 class="navbar">Other Resources</h3>
+ <ul>
+ <li>GTL Boostcon 2009 Paper</li>
+ <li><a href="GTL_boostcon_draft03.htm">GTL Boostcon 2009
+Presentation</a></li>
+ <li>Performance Analysis</li>
+ <li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
+ <li>Voronoi Basic Tutorial</li>
+ <li><a href="voronoi_advanced_tutorial.htm">Voronoi 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>
+
<h1>THE BOOST.POLYGON VORONOI LIBRARY<br>
-</h1><img style="width: 900px; height: 300px;" alt="" src="images/voronoi3.png"><br>
+ </h1>
+ <img style="width: 900px; height: 300px;" alt="" src="images/voronoi3.png"><br>
The Boost.Polygon Voronoi library provides functionality to construct Voronoi diagrams
-of a set of points and linear segments in 2D space with the following set of
+of a set of points and linear segments in 2D space with the following
+set of
limitations:<br>
<ul>
- <li>coordinates of the input points and endpoints of the segments
+ <li>coordinates of the input points and endpoints of the
+segments
should be of integer type;</li>
<li>input segments should not intersect
except their endpoints.</li>
</ul>
While the first restriction is permanent (it
-allows to give warranties for algorithm output precision and execution),
+allows to give warranties for algorithm output precision and
+execution),
the second one may be resolved using Boost.Polygon functionality.
Strong sides of the
library and main benefits comparing to other implementations are
discussed in the following paragraphs.<span style="font-weight: bold;"></span><br>
-
<h2>Robustness and Efficiency</h2>
-
-
Lets explain a bit those terms. The efficiency is simply measured by
the time it takes the algorithm to execute. The robustness is a bit
more harder to explain. But those of you who had experience with
@@ -147,31 +117,34 @@
degeneracies for some inputs, the algorithm produces wrong output for
some inputs (e.g. point is considered to be outside of the polygon,
while should be inside). In other words robust implementation doesn't
-fail and produces expected output in 100% of cases, thus user can rely on
+fail and produces expected output in 100% of cases, thus user can rely
+on
it. Robustness is the weak place of the most non-commercial
implementations of any complex geometric algorithm. The main issues of
that could be divided onto two main categories: memory management
issues, numeric stability issues. Our implementation avoids the
first type of issues using pure STL data structure, thus you won't find
any operator new in the code. The second category of problems is
-resolved using multiprecision geometric predicates.
+resolved using multiprecision <a href="voronoi_predicates.htm">geometric
+predicates</a>.
Even for commercial implementations usage of such predicates usually
-results in huge performance slowdown. Here is another strong side of the Boost.Polygon
-Voronoi library: we avoid multiprecision computations in 95% of cases using
+results in huge performance slowdown. Here is another strong side of
+the Boost.Polygon
+Voronoi library: we avoid multiprecision computations in 95% of cases
+using
extremely fast floating-point predicates. Yes, those are not always
-exact, but we developed relative error arithmetic apparatus to identify them and switch to the higher precision predicates when required.<br>
-
+exact, but we developed <a href="voronoi_robust_fpt.htm">relative
+error arithmetic apparatus</a> to identify them and switch to the
+higher precision predicates when required.<br>
<h2>Precision of the Output Structures<br>
-
</h2>
-
One of the extremely important results of using two types of predicates
is that library efficiently computes relatively precise coordinates of
the output geometries. Here we will explain a bit what exactly
"relatively precise" means and how the received output may differ from
the theoretically correct one (here and after we assume that output
coordinate type is IEEE-754 floating-point type).<br>
-<br>
+ <br>
Voronoi implementation guaranties that the relative error of the
coordinates of the output
geometries is always not higher then 64 machine epsilons (6
@@ -192,7 +165,7 @@
x-coordinate
lies in the range [2^31-2^-27, 2^31+2^-27]. If you'd like to become
master of absolute and relative errors try this article.<br>
-<br>
+ <br>
During finalization step library unites Voronoi vertices whose both
coordinates are situated within relative error range equal to 128
machine epsilons and removes any Voronoi edges between them. That is
@@ -208,66 +181,87 @@
consider vertices with both coordinates that are within 2^-17 meters (8
micrometers) distance to be equal. Come on that distance is equal to
the size of bacteria. Can you even see those?<br>
-
<h2>Fully Functional with Segment Inputs</h2>
-
-There are not many implementations of the Voronoi diagram construction algorithm that could
-handle segment inputs, even considering the commercial libraries. Support of the
+There are not many implementations of the Voronoi diagram construction
+algorithm that could
+handle segment inputs, even considering the commercial libraries.
+Support of the
segments allows to discretize any input geometry (circle, ellipse,
parabola). Of course as the result those might have floating-point
coordinates, but that is resolved using scaling and snapping to the
integer grid. This functionality is very handy as allows to compute
-the medial axis transform of the arbitrary set of input geometries. So one may start
+the medial axis transform of the arbitrary set of input geometries. So
+one may start
using it for the next generation pattern recognition or computer vision
project.<br>
-
<h2>Basic and Advanced Usage Cases</h2>
-The main library header <span style="font-family: Courier New,Courier,monospace;">voronoi.hpp</span> defines following static functions:<br>
+The main library header <span style="font-family: Courier New,Courier,monospace;">voronoi.hpp</span>
+defines following static functions:<br>
<br>
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
<tbody>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template <typename PC, typename VD><br>
+ <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>
</td>
- <td style="vertical-align: top;">Constructs the Voronoi diagram of a set of points into the output data structure.<br>
-Coordinates of the input geometries should belong to the [-2^31, 2^31-1] integer range.<br>
+ <td style="vertical-align: top;">Constructs the Voronoi
+diagram of a set of points into the output data structure.<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>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template <typename SC, typename VD><br>
+ <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>
</td>
- <td style="vertical-align: top;">Constructs the Voronoi diagram of a set of segments into the output data structure.<br>
-Coordinates of the input geometries should belong to the [-2^31, 2^31-1] integer range.<br>
+ <td style="vertical-align: top;">Constructs the Voronoi
+diagram of a set of segments into the output data structure.<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>
+Segment object should provide low(), high() public methods to retrieve
+endpoints of a segment.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template <typename PC, typename SC, typename VD><br>
+ <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 *output)<br>
+ const PC &points, const SC &segments, VD
+*output)<br>
</td>
- <td style="vertical-align: top;">Constructs the Voronoi diagram of a set of points and segments into the output data structure.<br>
-Coordinates of the input geometries should belong to the [-2^31, 2^31-1] integer range.<br>
+ <td style="vertical-align: top;">Constructs the Voronoi
+diagram of a set of points and segments into the output data structure.<br>
+Coordinates of the input geometries should belong to the [-2^31,
+2^31-1] integer range.<br>
</td>
</tr>
</tbody>
</table>
<br>
-For the users that don't want to go into the details of the library this
+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
following two lines of code:<br>
<br>
- <span style="font-family: Courier New,Courier,monospace;">voronoi_diagram<double> vd;</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">construct_voronoi(points, segments, &vd);</span><br>
+ <span style="font-family: Courier New,Courier,monospace;">voronoi_diagram<double>
+vd;</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">construct_voronoi(points,
+segments, &vd);</span><br>
<br>
Isn't that simple? The library also provides the clear interfaces to
-associate user data with the output geometries, efficiently traverse Voronoi graph and utilities to visualize output primitives (e.g. discretization of the parabolic edges, clipping of the linear edges). More details on those is covered in the basic Voronoi tutorial. Advanced usage of the library with the configuration of the coordinate types is explained in the advanced Voronoi tutorial.<br>
+associate user data with the output geometries, efficiently traverse Voronoi graph and utilities to
+ visualize output primitives (e.g.
+discretization of the parabolic edges, clipping of the linear edges).
+More details on those is covered in the basic Voronoi tutorial.
+Advanced usage of the library with the configuration of the coordinate
+types is explained in the <a href="voronoi_advanced_tutorial.htm">advanced
+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
@@ -276,99 +270,98 @@
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>
-
-
<h2>Extensible for User Provided Coordinate Types</h2>
Our implementation is coordinate type agnostic. That means that as soon
as the user provided types satisfy set of restrictions of the Voronoi builder coordinate type traits
-and implement the library required methods no changes are required neither
-from algorithm, nor from the implementation of the predicates. So it's possible to
-construct Voronoi diagram for the 256-bit integer input coordinate type and
-512-bit output floating-point type without making any changes to the internal code.<br>
-
-
+and implement the library required methods no changes are required
+neither
+from algorithm, nor from the implementation of the predicates. So it's
+possible to
+construct Voronoi diagram for the 256-bit integer input coordinate type
+and
+512-bit output floating-point type without making any changes to the
+internal code.<br>
<h2>Bright Future<br>
-
</h2>
-
-Below one may find the list of the main directions for the future development of the library.<br>
+Below one may find the list of the main directions for the future
+development of the library.<br>
High-priority tasks that already have approximate implementation plan
are following (some of those may be proposed as future GSoC projects):<br>
<ul>
<li>Implementing Delaunay triangulation data structure.<br>
-Note: only data structure needs to be implemented that properly processes events provided by the Voronoi builder.</li>
+Note: only data structure needs to be implemented that properly
+processes events provided by the Voronoi builder.</li>
<li>Implementing medial axis transform data structure.<br>
-Note: in general case the Voronoi diagram has completely the same geometry
+Note: in general case the Voronoi diagram has completely the same
+geometry
as the medial axis (they are 100% equal), however for many applications
-user is not interested in the Voronoi edges inside the hole regions. The main point
+user is not interested in the Voronoi edges inside the hole regions.
+The main point
of this data structure is to automatically filter Voronoi edges that
belong to those areas.</li>
- <li>Implementing data structure built on top of Voronoi diagram that allows to execute nearest neighbor queries in O(log N) time.<br>
-Note: there should be r-tree data structure available soon as part of the Boost libraries.</li>
-
+ <li>Implementing data structure built on top of Voronoi diagram
+that allows to execute nearest neighbor queries in O(log N) time.<br>
+Note: there should be r-tree data structure available soon as part of
+the Boost libraries.</li>
<li>Providing interface to retrieve convex hull of a set of
points and segments from Voronoi builder once the Voronoi diagram is
constructed in O(N) time.<br>
-</li>
- <li>Closer integration with the interfaces and functionality of Boost Polygon Library.<br>
+ </li>
+ <li>Closer integration with the interfaces and functionality of
+Boost Polygon Library.<br>
</li>
</ul>
High-priority tasks to be considered:<br>
<ul>
- <li>Dropping restriction on the non-intersecting input geometries.</li>
- <li>Integration of Voronoi diagram structure with BGL (Boost Graph Library).</li>
-
+ <li>Dropping restriction on the non-intersecting input
+geometries.</li>
+ <li>Integration of Voronoi diagram structure with BGL (Boost
+Graph Library).</li>
<li>Support of the other types of distance metrics.</li>
<li>Construction of the constrained Delaunay triangulation.</li>
<li>Support of the circle input geometries.</li>
-
-
</ul>
Based on the community suggestions priorities may be changed.<br>
-
<h2>Theoretical Research<br>
-
- </h2>Voronoi
+ </h2>
+Voronoi
was developed as part of the Google Summer of Code 2010. The
library was actively maintained for the last two years and involved
-the strong mathematical research in the field of algorithms, data structures,
+the strong mathematical research in the field of algorithms, data
+structures,
relative error arithmetic and numerical robustness. Nowadays one can
often read scientific article that contains non-practical theoretical
results or implementation with
benchmarks nobody else can reproduce. The opposite story is with
-the Boolst.Polygon Voronoi library. We provide pure implementation and benchmarks one may run on
+the Boolst.Polygon Voronoi library. We provide pure implementation and
+benchmarks one may run on
his PC. In case community finds it useful we will incrementally
add more documentation on the theoretical side of our realization. The
-authors would like to acknowledge Steven Fortune's article <span style="font-family: Arial,Helvetica,sans-serif;"><span style="font-weight: bold;"></span></span>"A Sweepline algorithm for Voronoi diagrams", that contains the fundamental ideas of the current implementation.<br>
-
-
-
-</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>
+authors would like to acknowledge Steven Fortune's article <span style="font-family: Arial,Helvetica,sans-serif;"><span style="font-weight: bold;"></span></span>"<a href="http://dl.acm.org/citation.cfm?id=10549">A Sweepline algorithm
+for Voronoi diagrams</a>", that contains the fundamental ideas of the
+current implementation.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
+ <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
+ <table class="docinfo" id="table2" frame="void" rules="none">
+ <colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> <tbody valign="top">
+ <tr>
+ <th class="docinfo-name">Copyright:</th>
+ <td>Copyright © Intel Corporation 2008-2010.</td>
+ </tr>
+ <tr class="field">
+ <th class="docinfo-name">License:</th>
+ <td class="field-body">Distributed under the Boost Software
+License, Version 1.0. (See accompanying file <tt class="literal"><span class="pre">LICENSE_1_0.txt</span></tt> or copy at <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
+http://www.boost.org/LICENSE_1_0.txt>)</td>
+ </tr>
+ </tbody>
+ </table>
+ </td>
+ </tr>
+ </tbody>
+</table>
</body></html>
\ No newline at end of file
==============================================================================
--- sandbox/gtl/doc/voronoi_predicates.htm (original)
+++ sandbox/gtl/doc/voronoi_predicates.htm 2012-04-09 18:16:19 EDT (Mon, 09 Apr 2012)
@@ -1,131 +1,121 @@
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head>
+
+ <meta http-equiv="Content-Language" content="en-us">
+
+ <meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
+ <title>Voronoi Predicates</title>
-
-
-
-
-
-
-
-
-
-
-
-
-
-<meta http-equiv="Content-Language" content="en-us">
-<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title></head><body>
-
+
+</head><body>
<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
- <tbody><tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
- <div style="padding: 5px;" align="center">
- <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/">
- </a></div>
- <div style="margin: 5px;">
- <h3 class="navbar">Contents</h3>
- <ul>
- <li>Boost.Polygon Main Page</li>
- <li>Design Overview</li>
- <li>Isotropy</li>
- <li>Coordinate Concept</li>
- <li>Interval Concept</li>
- <li>Point Concept</li>
- <li>Rectangle Concept</li>
- <li>Polygon 90 Concept</li>
- <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
- With Holes Concept</a></li>
- <li>Polygon 45 Concept</li>
- <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
- With Holes Concept</a></li>
- <li>Polygon Concept</li>
- <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
- Holes Concept</a></li>
- <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
- Concept</a></li>
- <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
- Concept</a></li>
- <li>Polygon Set Concept</li>
- <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
- Extraction 90</a></li>
- <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
- Extraction 45</a></li>
- <li><a href="gtl_connectivity_extraction.htm">Connectivity
- Extraction</a></li>
- <li>Property Merge 90</li>
- <li>Property Merge 45</li>
- <li>Property Merge</li>
- <li><a href="voronoi_main.htm">Voronoi Main Page<br>
-</a></li>
- <li>Voronoi Benchmark</li>
- <li>Voronoi Builder<br>
- </li>
- <li>Voronoi Diagram</li>
+ <tbody>
+ <tr>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ <div style="padding: 5px;" align="center"> <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/"> </a></div>
+ <div style="margin: 5px;">
+ <h3 class="navbar">Contents</h3>
+ <ul>
+ <li>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
+ <li>Isotropy</li>
+ <li>Coordinate Concept</li>
+ <li>Interval Concept</li>
+ <li>Point Concept</li>
+ <li>Rectangle Concept</li>
+ <li>Polygon 90 Concept</li>
+ <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
+With Holes Concept</a></li>
+ <li>Polygon 45 Concept</li>
+ <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
+With Holes Concept</a></li>
+ <li>Polygon Concept</li>
+ <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
+Holes Concept</a></li>
+ <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
+Concept</a></li>
+ <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
+Concept</a></li>
+ <li>Polygon Set Concept</li>
+ <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
+Extraction 90</a></li>
+ <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
+Extraction 45</a></li>
+ <li><a href="gtl_connectivity_extraction.htm">Connectivity
+Extraction</a></li>
+ <li>Property Merge 90</li>
+ <li>Property Merge 45</li>
+ <li>Property Merge</li>
+ <li><a href="voronoi_main.htm">Voronoi Main Page<br>
+ </a></li>
+ <li>Voronoi Benchmark</li>
+ <li>Voronoi Builder<br>
+ </li>
+ <li>Voronoi Diagram</li>
<li>Voronoi Predicates</li>
-
<li>Voronoi Robust FPT<br>
</li>
-
-
-
<li>Voronoi Utils<br>
</li>
-
-
- </ul>
- <h3 class="navbar">Other Resources</h3>
- <ul>
- <li>GTL Boostcon 2009 Paper</li>
- <li><a href="GTL_boostcon_draft03.htm">GTL Boostcon 2009
- Presentation</a></li>
- <li>Performance Analysis</li>
- <li>Layout Versus Schematic Tutorial</li>
- <li>Minkowski Sum Tutorial</li>
- <li>Voronoi Basic Tutorial</li>
- <li>Voronoi Advanced Tutorial</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 Predicates<br>
-</h1>In mathematical theory predicate is an operator which returns true
-or false (e.g. it may answer a question: "is it sunny today?").<br>The Voronoi predicates contain implementation of a set of the geometric
-predicates used by the Voronoi builder. Except of those it also provides
-functors that allow to compute the coordinates of the centers of the inscribed
+ </ul>
+ <h3 class="navbar">Other Resources</h3>
+ <ul>
+ <li>GTL Boostcon 2009 Paper</li>
+ <li><a href="GTL_boostcon_draft03.htm">GTL Boostcon 2009
+Presentation</a></li>
+ <li>Performance Analysis</li>
+ <li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
+ <li>Voronoi Basic Tutorial</li>
+ <li><a href="voronoi_advanced_tutorial.htm">Voronoi 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>
+
+ <h1>Voronoi Predicates<br>
+ </h1>
+In mathematical theory predicate is an operator which returns true
+or false (e.g. it may answer a question: "is it sunny today?").<br>
+The Voronoi predicates contain implementation of a set of the geometric
+predicates used by the Voronoi builder.
+Except of those it also provides
+functors that allow to compute the coordinates of the centers of the
+inscribed
circles (those correspond to the Voronoi vertices) within the given
-relative error precision range (64 machine epsilons). This means that the more mantissa bits
+relative error precision range (64 machine epsilons). This means that
+the more mantissa bits
your floating point type has the better precision of the output
geometries you'll get. This
is a very handy functionality as it allows to improve output precision
simply providing 3rd party IEEE-754 like floating-point types.<br>
-
<h2>Geometric Predicates</h2>
-
The main issues with the implementation of any complex geometric
-algorithm arise when dealing with the robustness of the geometric predicates.
+algorithm arise when dealing with the robustness of the geometric
+predicates.
Usually this
is also the point where the commercial projects stand strong against
noncommercial implementations (it's not the case with our
implementation).
-For the short example let's consider the following code snippet, that could
+For the short example let's consider the following code snippet, that
+could
be used to compute orientation of the three points:<br>
<br>
- <span style="font-family: Courier New,Courier,monospace;">double cross_product(double dx1, double dy1, double dx2, double dy2) {</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> return dx1 * dy2 - dx2 * dy1;</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">double
+cross_product(double dx1, double dy1, double dx2, double dy2) {</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+return dx1 * dy2 - dx2 * dy1;</span><br style="font-family: Courier New,Courier,monospace;">
<span style="font-family: Courier New,Courier,monospace;">}<br>
<br>
int main() {<br>
int v = 1 << 30; // 2 ^ 30<br>
- double result = </span><span style="font-family: Courier New,Courier,monospace;">cross_product</span><span style="font-family: Courier New,Courier,monospace;">(v, v - 1, v + 1, v);<br>
+ double result = </span><span style="font-family: Courier New,Courier,monospace;">cross_product</span><span style="font-family: Courier New,Courier,monospace;">(v, v - 1, v + 1,
+v);<br>
printf("%.3f", result);<br>
return 0;<br>
}<br>
@@ -142,8 +132,6 @@
efficient the approach that combines two known techniques (lazy
arithmetic and multiple
precision computations) is used.<br>
-
-
<h2>Lazy Arithmetic</h2>
Lazy
arithmetic is based on the usage of IEEE-754 floating-point types to
@@ -157,43 +145,37 @@
on that we can
come up with two decisions: 1) output the value; 2) recompute the
expression using multiprecision type. The way relative errors are
-evaluated is explained in the Voronoi Robust FPT section.<br>
+evaluated is explained in the <a href="voronoi_robust_fpt.htm">Voronoi
+Robust FPT</a> section.<br>
<h2>Multiple Precision Arithmetic</h2>
In the vast majority of cases
the lazy arithmetic approach produces correct result thus further
-processing is not required. In other cases the Voronoi library defined or user
+processing is not required. In other cases the Voronoi library defined
+or user
provided multiple precision types are used to produce correct result.
However even that doesn't solve all the cases. Multiprecision geometric
-predicates could be divided onto two categories:<br><br>
-1) mathematical transformation of the predicate exists that evaluates exact result:<span style="font-family: Courier New,Courier,monospace;"><br>
-
+predicates could be divided onto two categories:<br>
+ <br>
+1) mathematical transformation of the predicate exists that evaluates
+exact result:<span style="font-family: Courier New,Courier,monospace;"><br>
<br>
-
Predicate: A/B + C/D ?< 0;<br>
-
After math. transform: (A*D + B*C) / (B * D) ?< 0;<br>
-
<br>
-
Predicate: sqrt(A) ?< 1.2;<br>
-
After math. transform: A ?< 1.44;<br>
-
<br>
-
</span>2) the correct result could be produced only by increasing
precision of the multiprecision type and with defined relative error
for the output type:<br>
<br>
- <span style="font-family: Courier New,Courier,monospace;">Predicate: sqrt(A) + sqrt(B) + sqrt(C) + sqrt(D) + sqrt(E) ?< 1.2;<br>
-
+ <span style="font-family: Courier New,Courier,monospace;">Predicate:
+sqrt(A) + sqrt(B) + sqrt(C) + sqrt(D) + sqrt(E) ?< 1.2;<br>
Imagine that value of the expression to the left is very close to 1.2;<br>
-
</span><br>
- <span style="font-family: Courier New,Courier,monospace;">Predicate: sin(x) ?< 0.57;<br>
-
+ <span style="font-family: Courier New,Courier,monospace;">Predicate:
+sin(x) ?< 0.57;<br>
Relative error of sin function should be known;<br>
-
<br>
</span>The Voronoi of points could be completely
implemented using predicates of the first type, however the Voronoi of
@@ -209,23 +191,29 @@
situated Voronoi vertices are considered to be the same in the output
data structure (this won't influence main targets algorithm is used
for).<span style="font-family: Courier New,Courier,monospace;"><br>
- </span>
-</td></tr><tr><td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"><br>
-</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"><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>
+ </span></td>
+ </tr>
+ <tr>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"><br>
+ </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">
+ <tbody valign="top">
+ <tr>
+ <th class="docinfo-name">Copyright:</th>
+ <td>Copyright © Intel Corporation 2008-2010.</td>
+ </tr>
+ <tr class="field">
+ <th class="docinfo-name">License:</th>
+ <td class="field-body">Distributed under the Boost Software
+License, Version 1.0. (See accompanying file <tt class="literal"><span class="pre">LICENSE_1_0.txt</span></tt> or copy at <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
+http://www.boost.org/LICENSE_1_0.txt>)</td>
+ </tr>
+ </tbody>
+ </table>
+ </td>
+ </tr>
+ </tbody>
+</table>
</body></html>
\ No newline at end of file
==============================================================================
--- sandbox/gtl/doc/voronoi_robust_fpt.htm (original)
+++ sandbox/gtl/doc/voronoi_robust_fpt.htm 2012-04-09 18:16:19 EDT (Mon, 09 Apr 2012)
@@ -1,208 +1,211 @@
<!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 Robust FPT</title>
-
-
-
-
-
-
-
-
-
-
-
-
-<meta http-equiv="Content-Language" content="en-us">
-<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title></head><body>
-
+
+</head><body>
<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
- <tbody><tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
- <div style="padding: 5px;" align="center">
- <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/">
- </a></div>
- <div style="margin: 5px;">
- <h3 class="navbar">Contents</h3>
- <ul>
- <li>Boost.Polygon Main Page</li>
- <li>Design Overview</li>
- <li>Isotropy</li>
- <li>Coordinate Concept</li>
- <li>Interval Concept</li>
- <li>Point Concept</li>
- <li>Rectangle Concept</li>
- <li>Polygon 90 Concept</li>
- <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
- With Holes Concept</a></li>
- <li>Polygon 45 Concept</li>
- <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
- With Holes Concept</a></li>
- <li>Polygon Concept</li>
- <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
- Holes Concept</a></li>
- <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
- Concept</a></li>
- <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
- Concept</a></li>
- <li>Polygon Set Concept</li>
- <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
- Extraction 90</a></li>
- <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
- Extraction 45</a></li>
- <li><a href="gtl_connectivity_extraction.htm">Connectivity
- Extraction</a></li>
- <li>Property Merge 90</li>
- <li>Property Merge 45</li>
- <li>Property Merge</li>
- <li><a href="voronoi_main.htm">Voronoi Main Page<br>
-</a></li>
- <li>Voronoi Benchmark</li>
- <li>Voronoi Builder<br>
- </li>
- <li>Voronoi Diagram</li>
+ <tbody>
+ <tr>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ <div style="padding: 5px;" align="center"> <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/"> </a></div>
+ <div style="margin: 5px;">
+ <h3 class="navbar">Contents</h3>
+ <ul>
+ <li>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
+ <li>Isotropy</li>
+ <li>Coordinate Concept</li>
+ <li>Interval Concept</li>
+ <li>Point Concept</li>
+ <li>Rectangle Concept</li>
+ <li>Polygon 90 Concept</li>
+ <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
+With Holes Concept</a></li>
+ <li>Polygon 45 Concept</li>
+ <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
+With Holes Concept</a></li>
+ <li>Polygon Concept</li>
+ <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
+Holes Concept</a></li>
+ <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
+Concept</a></li>
+ <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
+Concept</a></li>
+ <li>Polygon Set Concept</li>
+ <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
+Extraction 90</a></li>
+ <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
+Extraction 45</a></li>
+ <li><a href="gtl_connectivity_extraction.htm">Connectivity
+Extraction</a></li>
+ <li>Property Merge 90</li>
+ <li>Property Merge 45</li>
+ <li>Property Merge</li>
+ <li><a href="voronoi_main.htm">Voronoi Main Page<br>
+ </a></li>
+ <li>Voronoi Benchmark</li>
+ <li>Voronoi Builder<br>
+ </li>
+ <li>Voronoi Diagram</li>
<li>Voronoi Predicates</li>
-
<li>Voronoi Robust FPT<br>
</li>
-
-
-
<li>Voronoi Utils<br>
</li>
-
-
- </ul>
- <h3 class="navbar">Other Resources</h3>
- <ul>
- <li>GTL Boostcon 2009 Paper</li>
- <li><a href="GTL_boostcon_draft03.htm">GTL Boostcon 2009
- Presentation</a></li>
- <li>Performance Analysis</li>
- <li>Layout Versus Schematic Tutorial</li>
- <li>Minkowski Sum Tutorial</li>
- <li>Voronoi Basic Tutorial</li>
- <li>Voronoi Advanced Tutorial</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 Robust FPT</h1>The Voronoi
+ </ul>
+ <h3 class="navbar">Other Resources</h3>
+ <ul>
+ <li>GTL Boostcon 2009 Paper</li>
+ <li><a href="GTL_boostcon_draft03.htm">GTL Boostcon 2009
+Presentation</a></li>
+ <li>Performance Analysis</li>
+ <li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
+ <li>Voronoi Basic Tutorial</li>
+ <li><a href="voronoi_advanced_tutorial.htm">Voronoi 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>
+
+ <h1>Voronoi Robust FPT</h1>
+The Voronoi
robust floating-point types are the set of classes and tools that
allow to estimate relative error of the arithmetic expressions. It is
assumed that the other Boost libraries may find this unit functionality
extremely useful, as it can be use d to implement robust and efficient
arithmetic predicates or functors that compute values within known
relative error.<br>
-
-
<h2>Robust Fpt Type</h2>
-
The robust
fpt type (robust floating-point type)
-- represents the IEEE-754 floating-point type wrapper that also contains
+- represents the IEEE-754 floating-point type wrapper that also
+contains
information about the relative error of the underlying value. The
implementation overloads 5 standard operations: +, -, *, /, sqrt and
-apart from the evaluating value of the expression also computes its relative
+apart from the evaluating value of the expression also computes its
+relative
error. Let's consider two values A and B; C - rounding error, re(X)
- relative error of the X expression, then following rules apply:<br>
<br>
- <span style="font-family: Courier New,Courier,monospace;">re(A+B) <= max(re(A), re(B)) + C, if A * B >= 0;</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">re(A-B) <= (B * re(A) + A * re(B)) / |A - B| + C, if A * B < 0;</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">re(A*B) <= re(A) + re(B) + C;</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">re(A/B) <= re(A) + re(B) + C;</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">re(sqrt(A)) <= re(A) * 0.5 + C;<br>
+ <span style="font-family: Courier New,Courier,monospace;">re(A+B)
+<= max(re(A), re(B)) + C, if A * B >= 0;</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">re(A-B)
+<= (B * re(A) + A * re(B)) / |A - B| + C, if A * B < 0;</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">re(A*B)
+<= re(A) + re(B) + C;</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">re(A/B)
+<= re(A) + re(B) + C;</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">re(sqrt(A))
+<= re(A) * 0.5 + C;<br>
<br>
</span>The constant C is equal to the rounding error,
which for the above set of arithmetic operations in the IEEE-754
floating-point implementation should be equal to 1 machine epsilon. <br>
-
-
-
- <h2>Robust Difference Type</h2>The robust
+ <h2>Robust Difference Type</h2>
+The robust
difference type -
-represents expression wrapper that holds the positive and negative partial
+represents expression wrapper that holds the positive and negative
+partial
sums of the expression in a separate values in order to avoid
-the cancellation errors before evaluating the final difference. Following
+the cancellation errors before evaluating the final difference.
+Following
arithmetic operators are overloaded for the robust difference type: +,
-, *, / (division operator is not overloaded for the case were both
arguments have robust difference type).<br>
-Looking at the relative error formulas above one may notice a few facts about them:<br>
-1) all of the formulas evaluate upper bound of the relative error, the actual value could be a lot smaller;<br>
-2) relative error estimate for the expression depends on the order operations are executed;<br>
-3) relative error of the difference of two positive numbers may be
-extremely large in case their values are close to each other (this is also known as the cancellation error).<br>
-To explain this a bit consider the following expression (~ - stands for almost equal, << - many times larger than):<br>
- <br>
- <span style="font-family: Courier New,Courier,monospace;">A - B + C, where A ~ B and C << B;</span><br>
- <br>
-Computing the relative error of this expression from left to right will produce extremely large relative error:<br>
+Looking at the relative error formulas above one may notice a few facts
+about them:<br>
+1) all of the formulas evaluate upper bound of the relative error, the
+actual value could be a lot smaller;<br>
+2) relative error estimate for the expression depends on the order
+operations are executed;<br>
+3) relative error of the difference of two positive numbers may
+be
+extremely large in case their values are close to each other (this is
+also known as the cancellation error).<br>
+To explain this a bit consider the following expression (~ - stands for
+almost equal, << - many times larger than):<br>
+ <br>
+ <span style="font-family: Courier New,Courier,monospace;">A - B +
+C, where A ~ B and C << B;</span><br>
+ <br>
+Computing the relative error of this expression from left to right will
+produce extremely large relative error:<br>
+ <br>
+ <span style="font-family: Courier New,Courier,monospace;">re(A-B+C)
+= max(re(A-B), re(C)) = re(A-B) = (B * re(A) + A * re(B)) / 0 = INF;<br>
<br>
- <span style="font-family: Courier New,Courier,monospace;">re(A-B+C) = max(re(A-B), re(C)) = re(A-B) = (B * re(A) + A * re(B)) / 0 = INF;<br>
+ </span>While doing this from right to left will keep the relative
+error value small:<br>
<br>
- </span>While doing this from right to left will keep the relative error value small:<br>
+ <span style="font-family: Courier New,Courier,monospace;">re(A-B+C)
+= re(C-B+A) = max(re(C-B), re(A)) = max(re(A), re(B));<br>
<br>
- <span style="font-family: Courier New,Courier,monospace;">re(A-B+C) = re(C-B+A) = max(re(C-B), re(A)) = max(re(A), re(B));<br>
- <br>
- </span>While both estimates are valid (they define upper bound of the relative error), of course the second one is preferable.<br>
+ </span>While both estimates are valid (they define upper bound of
+the relative error), of course the second one is preferable.<br>
Here is the place where robust difference type comes useful. Basically
-it splits expression onto positive and negative partial sums and evaluates the
+it splits expression onto positive and negative partial sums and
+evaluates the
difference only when the result is required. And did I mention that
-positive and negative values might be of the robust fpt type, that's why
+positive and negative values might be of the robust fpt type, that's
+why
the relative error is always known for the expression result.<br>
- <h2>Robust Sqrt Expression Structure</h2>The robust square root expression structure allows to compute the result of
-the expression that contains square roots within defined relative error.
+ <h2>Robust Sqrt Expression Structure</h2>
+The robust square root expression structure allows to compute the
+result of
+the expression that contains square roots within defined relative
+error.
As an example consider the following expression:<br>
<br>
- <span style="font-family: Courier New,Courier,monospace;">A * sqrt(a) - B * sqrt(b), A * B > 0, a >= 0, b >= 0;</span><br>
+ <span style="font-family: Courier New,Courier,monospace;">A *
+sqrt(a) - B * sqrt(b), A * B > 0, a >= 0, b >= 0;</span><br>
<br>
Computing this expressions directly may apply huge cancellation error,
however it may be transformed to the next equivalent expression:<br>
<span style="font-family: Courier New,Courier,monospace;"><br>
(A * A * a - B * B * b) / (A * sqrt(a) + B * sqrt(b));</span><br>
- <br>The numerator and denominator of this expression could be computed directly as those won't lead to the cancellation errors.<br><br>
-In general case the robust sqrt expression structure allows to evaluate the following set of expressions:<br>
+ <br>
+The numerator and denominator of this expression could be computed
+directly as those won't lead to the cancellation errors.<br>
+ <br>
+In general case the robust sqrt expression structure allows to evaluate
+the following set of expressions:<br>
<span style="font-family: Courier New,Courier,monospace;"><br>
sum(A[i] * sqrt(a[i]), i = 1 .. N), N <= 4;</span><br>
<br>
This appears to be enough for the Boost.Polygon Voronoi.<br>
-
-
-
-</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>
+ </td>
+ </tr>
+ <tr>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
+ <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
+ <table class="docinfo" id="table2" frame="void" rules="none">
+ <colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> <tbody valign="top">
+ <tr>
+ <th class="docinfo-name">Copyright:</th>
+ <td>Copyright © Intel Corporation 2008-2010.</td>
+ </tr>
+ <tr class="field">
+ <th class="docinfo-name">License:</th>
+ <td class="field-body">Distributed under the Boost Software
+License, Version 1.0. (See accompanying file <tt class="literal"><span class="pre">LICENSE_1_0.txt</span></tt> or copy at <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
+http://www.boost.org/LICENSE_1_0.txt>)</td>
+ </tr>
+ </tbody>
+ </table>
+ </td>
+ </tr>
+ </tbody>
+</table>
</body></html>
\ No newline at end of file
==============================================================================
--- sandbox/gtl/doc/voronoi_utils.htm (original)
+++ sandbox/gtl/doc/voronoi_utils.htm 2012-04-09 18:16:19 EDT (Mon, 09 Apr 2012)
@@ -1,186 +1,193 @@
<!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 Utils</title>
+
+
+ <meta http-equiv="content-type" content="text/html; charset=utf-8">
+
+ <meta http-equiv="content-type" content="text/html; charset=utf-8">
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-<meta http-equiv="Content-Language" content="en-us">
-<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title><meta http-equiv="content-type" content="text/html; charset=utf-8"><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body>
-
+</head><body>
<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
- <tbody><tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
- <div style="padding: 5px;" align="center">
- <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/">
- </a></div>
- <div style="margin: 5px;">
- <h3 class="navbar">Contents</h3>
- <ul>
- <li>Boost.Polygon Main Page</li>
- <li>Design Overview</li>
- <li>Isotropy</li>
- <li>Coordinate Concept</li>
- <li>Interval Concept</li>
- <li>Point Concept</li>
- <li>Rectangle Concept</li>
- <li>Polygon 90 Concept</li>
- <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
- With Holes Concept</a></li>
- <li>Polygon 45 Concept</li>
- <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
- With Holes Concept</a></li>
- <li>Polygon Concept</li>
- <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
- Holes Concept</a></li>
- <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
- Concept</a></li>
- <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
- Concept</a></li>
- <li>Polygon Set Concept</li>
- <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
- Extraction 90</a></li>
- <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
- Extraction 45</a></li>
- <li><a href="gtl_connectivity_extraction.htm">Connectivity
- Extraction</a></li>
- <li>Property Merge 90</li>
- <li>Property Merge 45</li>
- <li>Property Merge</li>
- <li><a href="voronoi_main.htm">Voronoi Main Page<br>
-</a></li>
- <li>Voronoi Benchmark</li>
- <li>Voronoi Builder<br>
- </li>
- <li>Voronoi Diagram</li>
+ <tbody>
+ <tr>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ <div style="padding: 5px;" align="center"> <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/"> </a></div>
+ <div style="margin: 5px;">
+ <h3 class="navbar">Contents</h3>
+ <ul>
+ <li>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
+ <li>Isotropy</li>
+ <li>Coordinate Concept</li>
+ <li>Interval Concept</li>
+ <li>Point Concept</li>
+ <li>Rectangle Concept</li>
+ <li>Polygon 90 Concept</li>
+ <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
+With Holes Concept</a></li>
+ <li>Polygon 45 Concept</li>
+ <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
+With Holes Concept</a></li>
+ <li>Polygon Concept</li>
+ <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
+Holes Concept</a></li>
+ <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
+Concept</a></li>
+ <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
+Concept</a></li>
+ <li>Polygon Set Concept</li>
+ <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
+Extraction 90</a></li>
+ <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
+Extraction 45</a></li>
+ <li><a href="gtl_connectivity_extraction.htm">Connectivity
+Extraction</a></li>
+ <li>Property Merge 90</li>
+ <li>Property Merge 45</li>
+ <li>Property Merge</li>
+ <li><a href="voronoi_main.htm">Voronoi Main Page<br>
+ </a></li>
+ <li>Voronoi Benchmark</li>
+ <li>Voronoi Builder<br>
+ </li>
+ <li>Voronoi Diagram</li>
<li>Voronoi Predicates</li>
-
<li>Voronoi Robust FPT<br>
</li>
-
-
-
<li>Voronoi Utils<br>
</li>
-
-
- </ul>
- <h3 class="navbar">Other Resources</h3>
- <ul>
- <li>GTL Boostcon 2009 Paper</li>
- <li><a href="GTL_boostcon_draft03.htm">GTL Boostcon 2009
- Presentation</a></li>
- <li>Performance Analysis</li>
- <li>Layout Versus Schematic Tutorial</li>
- <li>Minkowski Sum Tutorial</li>
- <li>Voronoi Basic Tutorial</li>
- <li>Voronoi Advanced Tutorial</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 Utils</h1>Voronoi
+ </ul>
+ <h3 class="navbar">Other Resources</h3>
+ <ul>
+ <li>GTL Boostcon 2009 Paper</li>
+ <li><a href="GTL_boostcon_draft03.htm">GTL Boostcon 2009
+Presentation</a></li>
+ <li>Performance Analysis</li>
+ <li>Layout Versus Schematic Tutorial</li>
+ <li>Minkowski Sum Tutorial</li>
+ <li>Voronoi Basic Tutorial</li>
+ <li><a href="voronoi_advanced_tutorial.htm">Voronoi 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>
+
+ <h1>Voronoi Utils</h1>
+Voronoi
utilities implements a set of tools that users may find useful
especially for
-the visualization of the Voronoi diagrams or discretization of the parabolic
+the visualization of the Voronoi diagrams or discretization of the
+parabolic
edges. Keep in mind that there are no warranties about precision of the
-output structures produces by the utilities class. This is mostly because input
+output structures produces by the utilities class. This is mostly
+because input
coordinate type utilities operate with
is double. Any degeneracies may be reported, however those are of low
priority to be fixed. The class
declaration is following:<br>
- <br><span style="font-family: Courier New,Courier,monospace;">
-template <typename T, typename TRAITS = voronoi_utils_traits<T> ></span><br style="font-family: Courier New,Courier,monospace;"><span style="font-family: Courier New,Courier,monospace;">
-class voronoi_utils;<br>
<br>
- </span><span style="font-family: Courier New,Courier,monospace;">T - </span>output coordinate type used by the utilities.<br>
- <span style="font-family: Courier New,Courier,monospace;">TRAITS - </span>output geometries type traits (see definition below).<br>
-
-<h2 style="color: rgb(0, 0, 0); font-family: 'Times New Roman'; font-style: normal; font-variant: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px;">Member Functions</h2>
-
+ <span style="font-family: Courier New,Courier,monospace;">template
+<typename T, typename TRAITS = voronoi_utils_traits<T> ></span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">class
+voronoi_utils;<br>
+ <br>
+ </span><span style="font-family: Courier New,Courier,monospace;">T
+- </span>output coordinate type used by the utilities.<br>
+ <span style="font-family: Courier New,Courier,monospace;">TRAITS
+- </span>output geometries type traits (see definition below).<br>
+ <h2 style="color: rgb(0, 0, 0); font-family: 'Times New Roman'; font-style: normal; font-variant: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px;">Member
+Functions</h2>
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
<tbody>
<tr>
- <td style="vertical-align: top;"><span style="font-family: Courier New,Courier,monospace;">template <typename CT></span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">static brect_type scale_bounding_rectangle(<br>
+ <td style="vertical-align: top;"><span style="font-family: Courier New,Courier,monospace;">template
+<typename CT></span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">static
+brect_type scale_bounding_rectangle(<br>
const bounding_rectangle<CT> &brect,<br>
fpt_type factor = 1.0)</span><br>
</td>
- <td style="vertical-align: top;">Returns the scaled bounding rectangle.<br>
-The center of the transformation corresponds to the center of the input rectangle.<br>
+ <td style="vertical-align: top;">Returns the scaled
+bounding rectangle.<br>
+The center of the transformation corresponds to the center of the input
+rectangle.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top;"><span style="font-family: Courier New,Courier,monospace;">template <typename CT><br>
+ <td style="vertical-align: top;"><span style="font-family: Courier New,Courier,monospace;">template
+<typename CT><br>
static void discretize_finite_edge(<br>
const voronoi_edge<CT> &edge,<br>
coordinate_type max_error,<br>
point_set_type &discretization)</span><span style="font-family: Courier New,Courier,monospace;"></span><span style="font-family: Courier New,Courier,monospace;"></span><br>
</td>
- <td style="vertical-align: top;">Provides the point discretization of the input voronoi edge.<br>
+ <td style="vertical-align: top;">Provides the point
+discretization of the input voronoi edge.<br>
If the edge is infinite (ray, line) doesn't fill output point set.<br>
Max error specifies the maximum absolute value of the approximation.<br>
-
</td>
</tr>
<tr>
- <td style="vertical-align: top;"><span style="font-family: Courier New,Courier,monospace;">template <typename CT><br>
+ <td style="vertical-align: top;"><span style="font-family: Courier New,Courier,monospace;">template
+<typename CT><br>
static void clip_linear_edge(<br>
const voronoi_edge<CT> &edge,<br>
const brect_type &brect,<br>
point_set_type &clipped_edge)</span><br>
</td>
- <td style="vertical-align: top;">Clips the input Voronoi edges with the specified rectangle.<br>
+ <td style="vertical-align: top;">Clips the input Voronoi
+edges with the specified rectangle.<br>
If the edge is a parabolic arc doesn't fill the output point set.<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;">static void clip_linear_edge(<br>
+ </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;">static
+void clip_linear_edge(<br>
const PointType &p1,<br>
const PointType &p2,<br>
const brect_type &brect,<br>
point_set_type &clipped_edge)</span><br>
</td>
- <td style="vertical-align: top;">Clips the input linear edge with the specified rectangle.<br>The edge is defined by its endpoints.<br>
+ <td style="vertical-align: top;">Clips the input linear
+edge with the specified rectangle.<br>
+The edge is defined by its endpoints.<br>
</td>
</tr>
-
</tbody>
- </table><h1>Bounding Rectangle</h1>The module provides implementation of a simple bounding rectangle structure with the following declaration:<br>
+ </table>
+ <h1>Bounding Rectangle</h1>
+The module provides implementation of a simple bounding rectangle
+structure with the following declaration:<br>
<br style="font-family: Courier New,Courier,monospace;">
- <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;">class bounding_rectangle;<br>
+ <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;">class
+bounding_rectangle;<br>
<br>
T - </span>coordinate type the rectangle operates with.<br>
- <h2 style="color: rgb(0, 0, 0); font-family: 'Times New Roman'; font-style: normal; font-variant: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px;">Member Functions</h2>
+ <h2 style="color: rgb(0, 0, 0); font-family: 'Times New Roman'; font-style: normal; font-variant: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px;">Member
+Functions</h2>
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
<tbody>
<tr>
<td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bounding_rectangle()<br>
</td>
- <td style="vertical-align: top;">Default constructor. Initializes the empty bounding rectangle.<br>
+ <td style="vertical-align: top;">Default constructor.
+Initializes the empty bounding rectangle.<br>
</td>
</tr>
<tr>
@@ -190,60 +197,79 @@
coordinate_type x2,<br>
coordinate_type y2)<br>
</td>
- <td style="vertical-align: top;">Constructs the bounding rectangle with the given coordinates.<br>
+ <td style="vertical-align: top;">Constructs the bounding
+rectangle with the given coordinates.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void update(<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void
+update(<br>
coordinate_type x,<br>
coordinate_type y)<br>
</td>
- <td style="vertical-align: top;">Extends the bounding rectangle with the specified point defined by its coordinates.<br>
-If the rectangle is not initialized, initialized it with the specifed point.<br>
+ <td style="vertical-align: top;">Extends the bounding
+rectangle with the specified point defined by its coordinates.<br>
+If the rectangle is not initialized, initialized it with the specifed
+point.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool is_empty() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool
+is_empty() const<br>
</td>
- <td style="vertical-align: top;">Returns true if the rectangle is empty (uninitialized), else false.<br>
+ <td style="vertical-align: top;">Returns true if the
+rectangle is empty (uninitialized), else false.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void clear()<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">void
+clear()<br>
</td>
- <td style="vertical-align: top;">Sets rectangle to an empty state.<br>
+ <td style="vertical-align: top;">Sets rectangle to an empty
+state.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool contains(<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">bool
+contains(<br>
coordinate_type x,<br>
coordinate_type y) const<br>
</td>
- <td style="vertical-align: top;">Returns true if the rectangle contains the given point defined by its coordinates, else false.<br>
+ <td style="vertical-align: top;">Returns true if the
+rectangle contains the given point defined by its coordinates, else
+false.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">coordinate_type x_min() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">coordinate_type
+x_min() const<br>
</td>
- <td style="vertical-align: top;">Returns the x coordinate of the bottom left corner of the rectangle.<br>
+ <td style="vertical-align: top;">Returns the x coordinate
+of the bottom left corner of the rectangle.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">coordinate_type y_min() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">coordinate_type
+y_min() const<br>
</td>
- <td style="vertical-align: top;">Returns the y coordinate of the bottom left corner of the rectangle.<br>
+ <td style="vertical-align: top;">Returns the y coordinate
+of the bottom left corner of the rectangle.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">coordinate_type x_max() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">coordinate_type
+x_max() const<br>
</td>
- <td style="vertical-align: top;">Returns the x coordinate of the top right corner of the rectangle.<br>
+ <td style="vertical-align: top;">Returns the x coordinate
+of the top right corner of the rectangle.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">coordinate_type y_max() const<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">coordinate_type
+y_max() const<br>
</td>
- <td style="vertical-align: top;">Returns the y coordinate of the top right corner of the rectangle.<br>
+ <td style="vertical-align: top;">Returns the y coordinate
+of the top right corner of the rectangle.<br>
</td>
</tr>
</tbody>
@@ -252,56 +278,61 @@
</h1>
Below is shown the default Voronoi utilities traits declaration:<br>
<br>
- <span style="font-family: Courier New,Courier,monospace;">template <typename fpt_></span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">struct voronoi_utils_traits;</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">template
+<typename fpt_></span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">struct
+voronoi_utils_traits;</span><br style="font-family: Courier New,Courier,monospace;">
<br style="font-family: Courier New,Courier,monospace;">
<span style="font-family: Courier New,Courier,monospace;">template<></span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">struct voronoi_utils_traits<double> {</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> typedef double fpt_type;</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> typedef detail::point_2d<fpt_type> point_type;</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> typedef std::vector<point_type> point_set_type;</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> typedef bounding_rectangle<fpt_type> brect_type;</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> typedef struct {</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> template <typename CT></span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> fpt_type operator()(const CT& value) const {</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> return static_cast<fpt_type>(value);</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> }</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> } ctype_converter_type;</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">struct
+voronoi_utils_traits<double> {</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+typedef double fpt_type;</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+typedef detail::point_2d<fpt_type> point_type;</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+typedef std::vector<point_type> point_set_type;</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+typedef bounding_rectangle<fpt_type> brect_type;</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+typedef struct {</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+template <typename CT></span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+fpt_type operator()(const CT& value) const {</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+return static_cast<fpt_type>(value);</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+}</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+} ctype_converter_type;</span><br style="font-family: Courier New,Courier,monospace;">
<span style="font-family: Courier New,Courier,monospace;">};<br>
<br>
</span>Most of the types define output geometries.
ctype_converter_type is used to cast the coordinate type of the input
primitives to the one used by the utililities internally.<br>
-
-
-
-
-</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>
+ </td>
+ </tr>
+ <tr>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
+ <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
+ <table class="docinfo" id="table2" frame="void" rules="none">
+ <colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> <tbody valign="top">
+ <tr>
+ <th class="docinfo-name">Copyright:</th>
+ <td>Copyright © Intel Corporation 2008-2010.</td>
+ </tr>
+ <tr class="field">
+ <th class="docinfo-name">License:</th>
+ <td class="field-body">Distributed under the Boost Software
+License, Version 1.0. (See accompanying file <tt class="literal"><span class="pre">LICENSE_1_0.txt</span></tt> or copy at <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
+http://www.boost.org/LICENSE_1_0.txt>)</td>
+ </tr>
+ </tbody>
+ </table>
+ </td>
+ </tr>
+ </tbody>
+</table>
</body></html>
\ No newline at end of file