|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r83803 - in trunk/libs/polygon/doc: . images
From: sydorchuk.andriy_at_[hidden]
Date: 2013-04-07 19:09:32
Author: asydorchuk
Date: 2013-04-07 19:09:31 EDT (Sun, 07 Apr 2013)
New Revision: 83803
URL: http://svn.boost.org/trac/boost/changeset/83803
Log:
Polygon: Improving documentation. Updated Voronoi Main/Builder/Diagram pages.
Added:
trunk/libs/polygon/doc/images/voronoi1.png (contents, props changed)
Text files modified:
trunk/libs/polygon/doc/voronoi_builder.htm | 388 ++++++-------
trunk/libs/polygon/doc/voronoi_diagram.htm | 1101 ++++++++++++++++++++-------------------
trunk/libs/polygon/doc/voronoi_main.htm | 295 +++++-----
trunk/libs/polygon/doc/voronoi_robust_fpt.htm | 159 ++--
4 files changed, 969 insertions(+), 974 deletions(-)
Added: trunk/libs/polygon/doc/images/voronoi1.png
==============================================================================
Binary file. No diff available.
Modified: trunk/libs/polygon/doc/voronoi_builder.htm
Modified: trunk/libs/polygon/doc/voronoi_diagram.htm
Modified: trunk/libs/polygon/doc/voronoi_main.htm
Modified: trunk/libs/polygon/doc/voronoi_robust_fpt.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
==============================================================================
--- trunk/libs/polygon/doc/voronoi_builder.htm (original)
+++ trunk/libs/polygon/doc/voronoi_builder.htm 2013-04-07 19:09:31 EDT (Sun, 07 Apr 2013)
@@ -1,28 +1,22 @@
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
-<html><head>
-
-
-
-
-
-
-
-
-
-
-
-
-
+<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></head><body>
-<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
-
+ <meta http-equiv="Content-Type"
+ content="text/html; charset=windows-1252">
+ <title>Voronoi Builder</title>
+</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>
+ <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>
@@ -33,7 +27,6 @@
<li>Interval Concept</li>
<li>Point Concept</li>
<li>Segment Concept</li>
-
<li>Rectangle Concept</li>
<li>Polygon 90 Concept</li>
<li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
@@ -58,17 +51,12 @@
<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<br>
- </li>
+ <li>Voronoi Main Page </li>
+ <li>Voronoi Benchmark </li>
<li>Voronoi Builder</li>
- <li><a href="voronoi_diagram.htm">Voronoi Diagram<br>
- </a></li>
+ <li>Voronoi Diagram </li>
<li>Voronoi Predicates</li>
- <li>Voronoi Robust FPT<br>
- </li>
-
+ <li>Voronoi Robust FPT </li>
</ul>
<h3 class="navbar">Other Resources</h3>
<ul>
@@ -84,152 +72,154 @@
</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>
+ <div style="padding: 5px;" align="center"> <img
+ src="images/intlogo.gif" border="0" height="51" width="127"><a
+ title="www.adobe.com home page" tabindex="2"
+ style="border: medium none ;" href="http://www.adobe.com/"> </a></div>
</td>
- <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"><!-- End Header --> <br>
- <h1>Voronoi Builder<br>
- </h1>
-
-Voronoi builder is the event generator structure. It implements the <a href="http://www.ams.org/samplings/feature-column/fcarc-voronoi">sweepline
-algorithm</a>
-that scans a 2D space and generates two types of events:
-site events and circle events (we won't go into details what those are
-exactly). Each event is reported to the output data structure builder.
-The structure shares Voronoi name as the events generated by it
-correspond to the Voronoi diagram edges and vertices, thus giving
+ <td
+ style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
+ valign="top" width="100%"><!-- End Header --> <br>
+ <h1>Voronoi Builder </h1>
+The Voronoi builder is the event generator structure, that implements
+the <a href="http://en.wikipedia.org/wiki/Sweep_line_algorithm">sweepline
+algorithm</a>,
+scanning 2D space and spawning the two types of events: <a
+ href="http://www.ams.org/samplings/feature-column/fcarc-voronoi">site
+events and circle events</a>. Each event is reported to the output data
+structure builder.
+The structure shares Voronoi name, as the events generated by it
+provide
enough information to construct the Voronoi diagram of a set of points
-and linear segments. The requirements for the input/output
-coordinate type of
-the builder geometries are not the same as for the rest of the
-Boost.Polygon library. The main differences are in the following:<br>
+and linear segments. The requirements for the coordinate type of
+the input/output geometries, configured through the coordinate type
+traits template argument, are the following:<br>
<ul>
- <li>The input coordinate type is not required to be integral (while it
+ <li>The input coordinate type (for input points and enpoints of
+the input segments) is not required to be integral
+(while it
still should be an integer type)</li>
<li>The output coordinate type (for
Voronoi vertices) is required to be IEEE-754 floating point type</li>
</ul>
<h2>Important</h2>
-
-
-We encourage users to use default static methods defined in the voronoi.hpp
-header to construct Voronoi diagram, however it's always possible to
+The users are encouraged to use the default static methods defined in
+the voronoi.hpp
+header for the Voronoi diagram construction. However it's also possible
+to
use Voronoi builder explicitly, especially if the user wants to drop
-the external dependencies such as MPL (metaprogramming library). So the
-following include set woudn't depend on any heavy external headers (except STL and boost/cstdint.hpp), even
-Boost.Polygon itself:<br>
-
+the external dependencies such as MPL (metaprogramming library). The
+following include set doesn't depend on any external headers
+(except STL and boost/cstdint.hpp), even
+the Boost.Polygon library:<br>
<br>
-
- <span style="font-family: Courier New,Courier,monospace;">#include <voronoi_builder.hpp></span><br style="font-family: Courier New,Courier,monospace;">
-
- <span style="font-family: Courier New,Courier,monospace;">#include <voronoi_diagram.hpp></span><span style="font-family: Courier New,Courier,monospace;"><br>
+ <span style="font-family: Courier New,Courier,monospace;">#include
+<voronoi_builder.hpp></span><br
+ style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">#include
+<voronoi_diagram.hpp></span><br>
+ <h2>Declaration</h2>
+Header: boost/polygon/voronoi_builder.hpp<br>
<br>
- </span>This
-also gives a way to build Voronoi construction API on top of the
-Voronoi builder data structure for the other Boost libraries.<br>
- <h2>Declaration<br>
- </h2>
-
-
-
-
- <font face="Courier New"> <span style="font-family: 'Courier New',Courier,monospace;">template
-<typename T,</span><br style="font-family: 'Courier New',Courier,monospace;">
+ <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;">
+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;">
+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 the 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 type traits used by Voronoi predicates (VP).<br>
-
- <font face="Courier New"> <span style="font-family: 'Courier New',Courier,monospace;">VP</span></font>
-- predicate kernel, that provides builder with robust and
+ <font face="Courier New"> <span
+ style="font-family: 'Courier New',Courier,monospace;">CTT</span></font>
+- defines the input/output coordinate type traits used by the Voronoi
+predicates (VP).<br>
+ <font face="Courier New"> <span
+ style="font-family: 'Courier New',Courier,monospace;">VP</span></font>
+- the predicate kernel, that contains robust and
efficient predicates and functors.<br>
-
The Voronoi builder data structure is ready to use from the box with
32-bit signed integer input coordinate type. The user may extend the
input coordinate range to the other integer types (e.g. 64-bit
-integer), however this will also require manual set up of the
-coordinate type traits. Default voronoi_predicates<<font face="Courier New"><span style="font-family: 'Courier New',Courier,monospace;">CTT</span></font>>
-structure provides correct and efficient predicates as soon as types defined by <font face="Courier New"> <span style="font-family: 'Courier New',Courier,monospace;">CTT</span></font>
-satisfy the requirements explained at the end of this page. In case those
-requirements are not satisfied for the user provided coordinate type traits,<font face="Courier New"><span style="font-family: 'Courier New',Courier,monospace;"></span></font>
-the proper predicates kernel
-implementation is required.<span style="font-family: Courier New,Courier,monospace;"></span><br>
-<h2>Member Functions</h2>
- <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+integer), however this will also require manual setup of the
+coordinate type traits. Default predicate kernel provides correct and
+efficient predicates as long as types
+defined by the coordinate type traits satisfy the requirements
+explained at the end of this page. In case
+those
+requirements are not satisfied,<font face="Courier New"><span
+ style="font-family: 'Courier New',Courier,monospace;"></span></font>
+the proper predicate kernel
+implementation is required.<span
+ style="font-family: Courier New,Courier,monospace;"></span><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;"><span style="font-weight: bold;">
-voronoi_builder</span>()</td>
+ <td style="font-family: 'Courier New',Courier,monospace;"><span
+ style="font-weight: bold;">voronoi_builder</span>()</td>
<td width="693">Default
constructor.</td>
</tr>
<tr>
- <td><span style="font-family: Courier New,Courier,monospace;">size_t <span style="font-weight: bold;">insert_point</span>(const int_type& x,<br>
+ <td><span
+ style="font-family: Courier New,Courier,monospace;">size_t <span
+ style="font-weight: bold;">insert_point</span>(const int_type& x,<br>
-const int_type& y)</span><br>
- </td>
+const int_type& y)</span> </td>
<td>Inserts a point object with
the specified coordinates into the Voronoi builder.<br>
-Returns index number of the inserted site.<br>
-
- </td>
+Returns index of the inserted point. </td>
</tr>
-
-
<tr>
- <td><span style="font-family: Courier New,Courier,monospace;">size_t <span style="font-weight: bold;">insert_segment</span>(const int_type& x1,<br>
-const int_type& y1,<br>
+ <td><span
+ style="font-family: Courier New,Courier,monospace;">size_t <span
+ style="font-weight: bold;">insert_segment</span>(const int_type&
+x1,<br>
+
+const int_type& y1,<br>
+
const int_type& x2,<br>
-const int_type& y2)</span><br>
- </td>
+const int_type& y2)</span> </td>
<td>Inserts a segment object
with the specified coordinates into the Voronoi builder.<br>
-Returns index number of the inserted site.<br>
-
- </td>
+Returns index of the inserted segment. </td>
</tr>
-
-
-
-
- <tr>
- <td style="font-family: 'Courier New',Courier,monospace;">
-template <typename OUTPUT><br>
-void <span style="font-weight: bold;">construct</span>(OUTPUT* output)<br>
- </td>
- <td 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 data structure to process them.<br>
+ <tr>
+ <td style="font-family: 'Courier New',Courier,monospace;">template
+<typename OUTPUT><br>
+void <span style="font-weight: bold;">construct</span>(OUTPUT* output)
</td>
+ <td width="693">Runs the sweepline
+algorithm over the set of inserted geometries and generates site and
+circle events to the OUTPUT data structure. It's the responsibility of
+the
+output data structure to process them. </td>
</tr>
<tr>
- <td style="font-family: 'Courier New',Courier,monospace;">
-void <span style="font-weight: bold;">clear</span>()<br>
- </td>
+ <td style="font-family: 'Courier New',Courier,monospace;">void
+ <span style="font-weight: bold;">clear</span>() </td>
<td width="693">Clears the
-list of the inserted geometries. Sets index counter to zero.<br>
- </td>
+list of the inserted geometries. Sets the input geometry index to
+zero. </td>
</tr>
</tbody>
</table>
<h1>Voronoi Coordinate Type Traits</h1>
-
-
- <p>The library provides the default coordinate type traits specialization for the
+ <p>The library provides the default coordinate type traits
+specialization for the
32-bit signed integer type:</p>
-
- <font style="font-family: 'Courier New',Courier,monospace;" face="Courier New">
+ <font style="font-family: 'Courier New',Courier,monospace;"
+ face="Courier New">
<p>template <typename T><br>
struct voronoi_ctype_traits;<br>
<br>
@@ -246,136 +236,135 @@
typedef type_converter_fpt to_fpt_converter_type;<br>
typedef type_converter_efpt to_efpt_converter_type;<br>
};</p>
- </font>
- One
+ </font> 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
-fpt_type has the better precision of the output geometries will be. In
+machine epsilons). That means, the more mantissa bits the user provided
+fpt_type has, the better precision of the output geometries will be. In
order for the user defined traits to be consistent with the default
-Voronoi builder predicates user should define following set of
-coordinate types (the assumption is made that input geometries have
+Voronoi builder predicate kernel user should define the following set
+of traits (the assumption is made that input geometries have
X-bit signed integer coordinate type):<br>
<br>
-<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <table style="text-align: left; width: 100%;" border="1"
+ cellpadding="2" cellspacing="2">
<tbody>
<tr>
- <td style="font-family: 'Courier New',Courier,monospace; font-weight: bold;">int_type<br>
+ <td
+ style="font-family: 'Courier New',Courier,monospace; font-weight: bold;">int_type
</td>
<td style="vertical-align: top;">At least X-bit signed
-integer type. <br>
- </td>
+integer type. </td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">
-int_x2_type<br>
+ <td
+ style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">int_x2_type
</td>
<td style="vertical-align: top;">At least 2X-bit signed
-integer type.<br>
- </td>
+integer type. </td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">
-uint_x2_type<br>
+ <td
+ style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">uint_x2_type
</td>
<td style="vertical-align: top;">At least 2X-bit unsigned
-integer type.<br>
- </td>
+integer type. </td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">
-big_int_type<br>
+ <td
+ style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">big_int_type
</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>
+integer type if input dataset contains only points.<br>
+At least 64X-bit signed integer type if input dataset contains
+segments. </td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">
-fpt_type<br>
+ <td
+ style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">fpt_type
</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>
+32X-bit unsigned integer type. </td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">
-efpt_type<br>
+ <td
+ style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">efpt_type
</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>
+64X-bit unsigned integer type. </td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">
-ulp_cmp_type<br>
+ <td
+ style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">ulp_cmp_type
</td>
- <td style="vertical-align: top;">Ulp comparison structure
+ <td style="vertical-align: top;">Ulp comparison structure,
that checks if two fpt_type values are within the given ulp range
-(relative error range).<br>
- </td>
+(relative error range). </td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">
-to_fpt_converter_type<br>
+ <td
+ style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">to_fpt_converter_type
</td>
- <td style="vertical-align: top;">Type converter structure
+ <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>
+fpt_type using operator(). </td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">
-to_efpt_converter_type<br>
+ <td
+ style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">to_efpt_converter_type
</td>
- <td style="vertical-align: top;">Type converter structure
+ <td style="vertical-align: top;">Type converter structure,
that converts any of the integer types above to the efpt_type using
-operator().<br>
- </td>
+operator(). </td>
</tr>
</tbody>
</table>
- <p>Notes:<br></p>
+ <p>Notes:</p>
<ul>
- <li>
-Four different integer types are used (instead of a single
+ <li>Four different integer types are used (instead of a single
big_int_type) to slightly improve algorithm performance and memory
usage.</li>
- <li>As the maximum required size of the big_int_type is known in advance
-(based on the size of the integer type), library provided
-implementation of a fixed integer could be used (it is much faster than
-heap-allocated big integers).</li>
- <li>
-Two separate floating-point types are defined because for the input
+ <li>As the maximum required size of the big_int_type is known
+in advance, it's possible to use fixed, stack allocated, multiprecision
+integer type.</li>
+ <li>Two separate floating-point types are defined, because for
+the input geometries
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
+32-bit signed integer coordinates, double type won't be able to handle
+2048-bit (64 chunks of 32 bits each) 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.</li>
- <li>efpt_type and to_efpt_converter_type are not used to construct Voronoi diagram of points (mocks will work fine).</li>
- <li>
-For an example of the user defined coordinate type traits
-see advanced Voronoi tutorial.</li>
+types, however this is not supported by the MSVC compiler.</li>
+ <li>efpt_type and to_efpt_converter_type are not used to
+construct the Voronoi diagram of a set of points (mock implementation
+will work).</li>
+ <li>For an example of the user defined coordinate type traits
+check the <a href="voronoi_advanced_tutorial.htm">advanced Voronoi
+tutorial</a>.</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%">
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1"> </td>
+ <td
+ style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
+ valign="top" width="100%">
<table class="docinfo" id="table2" frame="void" rules="none">
- <colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> <tbody valign="top">
+ <colgroup> <col class="docinfo-name"><col
+ class="docinfo-content"> </colgroup> <tbody valign="top">
<tr>
<th class="docinfo-name">Copyright:</th>
- <td>Copyright © Andrii Sydorchuk 2010-2012.</td>
+ <td>Copyright © Andrii Sydorchuk 2010-2013.</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">
+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>
@@ -384,6 +373,5 @@
</tr>
</tbody>
</table>
-
-
-</body></html>
+</body>
+</html>
==============================================================================
--- trunk/libs/polygon/doc/voronoi_diagram.htm (original)
+++ trunk/libs/polygon/doc/voronoi_diagram.htm 2013-04-07 19:09:31 EDT (Sun, 07 Apr 2013)
@@ -1,36 +1,24 @@
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
-<html><head>
-
-
-
-
-
-
-
-
-
-
-
-
-
+<html>
+<head>
<meta http-equiv="Content-Language" content="en-us">
-
-
- <meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Voronoi Diagram</title>
-
-
-
-
+ <meta http-equiv="Content-Type"
+ content="text/html; charset=windows-1252">
+ <title>Voronoi Diagram</title>
<meta http-equiv="content-type" content="text/html; charset=utf-8">
-
-
- <meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body>
-<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
-
+ <meta http-equiv="content-type" content="text/html; charset=utf-8">
+</head>
+<body>
+<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0"
+ cellpadding="0" cellspacing="0">
<tbody>
<tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
- <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>
+ <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>
@@ -41,7 +29,6 @@
<li>Interval Concept</li>
<li>Point Concept</li>
<li>Segment Concept</li>
-
<li>Rectangle Concept</li>
<li>Polygon 90 Concept</li>
<li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
@@ -66,16 +53,12 @@
<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 Main Page </li>
<li>Voronoi Benchmark</li>
- <li>Voronoi Builder<br>
- </li>
+ <li>Voronoi Builder </li>
<li>Voronoi Diagram</li>
<li>Voronoi Predicates</li>
- <li>Voronoi Robust FPT<br>
- </li>
-
+ <li>Voronoi Robust FPT </li>
</ul>
<h3 class="navbar">Other Resources</h3>
<ul>
@@ -91,468 +74,488 @@
</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>
+ <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>
-
+ <td
+ style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
+ valign="top" width="100%"><!-- End Header --> <br>
<h1>Voronoi Diagram</h1>
-Voronoi
+A Voronoi
diagram is the computational geometry concept that represents partition
-of the given space onto regions, with bounds determined by distances to a
-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>. The Boost.Polygon library provides implementation of
-the Voronoi diagram data structure in 2D space. The internal representation
+of the given space onto regions, with bounds determined by distances to
+a
+specified family of objects. The application area of this concept
+varies <a
+ href="http://www.ics.uci.edu/%7Eeppstein/gina/scot.drysdale.html">from
+Archaeology to Zoology</a>. The Boost.Polygon Voronoi extension
+provides
+implementation of
+the Voronoi diagram data structure in the 2D space. The internal
+representation
consists of the three arrays, that respectively contain: Voronoi cells
-(represent the area around the input sites bounded by the Voronoi edges), Voronoi vertices
+(represent the area around the input sites bounded by the Voronoi
+edges), Voronoi vertices
(points where three or more Voronoi edges intersect), Voronoi edges
-(the one dimensional curves containing points equidistant from the two
+(one dimensional curves containing points equidistant from the two
closest input sites). Each of the primitives (cell, vertex, edge)
contains pointers to the other linked primitives, so that it's always
-possible to efficiently traverse Voronoi graph. The picture below shows
+possible to efficiently traverse the Voronoi graph. The picture below
+shows
the Voronoi vertices in red, Voronoi edges in black, input sites that
-correspond to the Voronoi cells in blue. It is considered that each
+correspond to the Voronoi cells in blue. It is considered, that each
input segment consists of the three sites: segment itself and its
-endpoints. As the result two additional
-Voronoi edges are constructed per each input segment. This is made to
-simplify the representation of the Voronoi diagram.<br>
- <br>
-
-
- <img style="border: 1px solid ; width: 300px; height: 300px;" alt="" src="images/voronoi2.png"><br>
- <h2>Important</h2>All
+endpoints. As the result, two additional Voronoi edges are constructed
+per each input segment. This is made to
+simplify the representation of the Voronoi diagram and Voronoi edges in
+particular.<br>
+ <br>
+ <img src="images/voronoi2.png" alt=""
+ style="width: 600px; height: 600px;"><br>
+ <h2>Important</h2>
+All
the Voronoi primitive data structures (edge, vertex, cell) contain
mutable color member. Color type is equivalent to the std::size_t type,
except that the upper five bits are reserved for the internal usage.
-That would mean that the maximum supported value by color member is 32
+That means, that the maximum supported value by the color member is 32
times less than the one supported by std::size_t.<br>
- <h2>Declaration<br>
- </h2>
-
-
-
-
-
+ <h2>Declaration</h2>
+Header: boost/polygon/voronoi_diagram.hpp<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;">
+<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><font face="Courier New"><span style="font-family: 'Courier New',Courier,monospace;">T</span></font>
-- specifies the coordinate type of the Voronoi vertices.<br>
- <span style="font-family: Courier New,Courier,monospace;">TRAITS</span><font face="Courier New"><span style="font-family: 'Courier New',Courier,monospace;"></span></font>
-- Voronoi diagram traits (explained in the end of this chapter).<br>
+ </span><font face="Courier New"><span
+ style="font-family: 'Courier New',Courier,monospace;"><br>
+T</span></font>
+- the coordinate type of the Voronoi vertices.<br>
+ <span style="font-family: Courier New,Courier,monospace;">TRAITS</span><font
+ face="Courier New"><span
+ style="font-family: 'Courier New',Courier,monospace;"></span></font>
+- the Voronoi diagram traits.<br>
<h2>Member Functions</h2>
-
- <span style="font-family: Courier New,Courier,monospace;">
-
- </span>
- <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <span style="font-family: Courier New,Courier,monospace;"> </span>
+ <table style="text-align: left; width: 100%;" border="1"
+ cellpadding="2" cellspacing="2">
<tbody>
<tr>
- <td style="font-family: Courier New,Courier,monospace;"><span style="font-weight: bold;">voronoi_diagram</span>()<br>
- </td>
- <td>Default constructor.<br>
- </td>
+ <td style="font-family: Courier New,Courier,monospace;"><span
+ style="font-weight: bold;">voronoi_diagram</span>() </td>
+ <td>Default constructor. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">void
- <span style="font-weight: bold;">clear</span>()<br>
- </td>
- <td>Clears diagram.<br>
- </td>
+ <span style="font-weight: bold;">clear</span>() </td>
+ <td>Removes all primitives from the Voronoi diagram. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">const
-cell_container_type& <span style="font-weight: bold;">cells</span>() const<br>
- </td>
+cell_container_type& <span style="font-weight: bold;">cells</span>()
+const </td>
<td>Returns the const
-reference to the cell container.<br>
- </td>
+reference to the cell container. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">const
-vertex_container_type& <span style="font-weight: bold;">vertices</span>() const<br>
- </td>
+vertex_container_type& <span style="font-weight: bold;">vertices</span>()
+const </td>
<td>Returns the const
-reference to the vertex container.<br>
- </td>
+reference to the vertex container. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">const
-edge_container_type& <span style="font-weight: bold;">edges</span>() const<br>
- </td>
+edge_container_type& <span style="font-weight: bold;">edges</span>()
+const </td>
<td>Returns the const
-reference to the edge container.<br>
- </td>
+reference to the edge container. </td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">size_t <span style="font-weight: bold;">num_cells</span>() const<br>
- </td>
- <td>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>
+ <td style="font-family: Courier New,Courier,monospace;">size_t
+ <span style="font-weight: bold;">num_cells</span>() const </td>
+ <td>Returns the number of the Voronoi
+cells in the Voronoi diagram. </td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">size_t <span style="font-weight: bold;">num_edges</span>() const<br>
- </td>
+ <td style="font-family: Courier New,Courier,monospace;">size_t
+ <span style="font-weight: bold;">num_edges</span>() const </td>
<td>Returns the number of the
-edges (half-edges) in the Voronoi diagram.<br>This value should be the same as the size of the edge container.<br>
- </td>
+Voronoi edges (half-edges) in the Voronoi diagram. </td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">size_t <span style="font-weight: bold;">num_vertices</span>() const<br>
- </td>
+ <td style="font-family: Courier New,Courier,monospace;">size_t
+ <span style="font-weight: bold;">num_vertices</span>()
+const </td>
<td>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>
+Voronoi vertices in the Voronoi diagram. </td>
</tr>
</tbody>
</table>
-
<h2>Member Types</h2>
- <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <table style="text-align: left; width: 100%;" border="1"
+ cellpadding="2" cellspacing="2">
<tbody>
<tr>
- <td style="font-weight: bold;">coordinate_type<br>
- </td>
- <td>Coordinate type.<br>
- </td>
+ <td style="font-weight: bold;">coordinate_type </td>
+ <td>Coordinate type. </td>
</tr>
-
<tr>
- <td style="font-weight: bold;">cell_type<br>
- </td>
- <td>Voronoi cell.<br>
- </td>
+ <td style="font-weight: bold;">cell_type </td>
+ <td>Voronoi cell. </td>
</tr>
<tr>
- <td style="font-weight: bold;">vertex_type<br>
- </td>
- <td>Voronoi vertex.<br>
- </td>
+ <td style="font-weight: bold;">vertex_type </td>
+ <td>Voronoi vertex. </td>
</tr>
<tr>
- <td style="font-weight: bold;">edge_type<br>
- </td>
- <td>Voronoi edge.<br>
- </td>
+ <td style="font-weight: bold;">edge_type </td>
+ <td>Voronoi edge. </td>
</tr>
<tr>
- <td style="font-weight: bold;">cell_container_type<br>
- </td>
- <td>Container of Voronoi cells.<br>
- </td>
+ <td style="font-weight: bold;">cell_container_type </td>
+ <td>Container of the Voronoi cells. </td>
</tr>
-
<tr>
- <td style="font-weight: bold;">const_cell_iterator<br>
- </td>
- <td>Const cell container iterator.<br>
- </td>
+ <td style="font-weight: bold;">const_cell_iterator </td>
+ <td>Const cell container iterator. </td>
</tr>
<tr>
- <td style="font-weight: bold;">vertex_container_type<br>
- </td>
- <td>Container of Voronoi vertices.<br>
- </td>
+ <td style="font-weight: bold;">vertex_container_type </td>
+ <td>Container of the Voronoi vertices. </td>
</tr>
-
<tr>
- <td style="font-weight: bold;">const_vertex_iterator<br>
- </td>
- <td>Const vertex container iterator.<br>
- </td>
+ <td style="font-weight: bold;">const_vertex_iterator </td>
+ <td>Const vertex container iterator. </td>
</tr>
<tr>
- <td style="font-weight: bold;">edge_container_type<br>
- </td>
- <td>Container of Voronoi edges.<br>
- </td>
+ <td style="font-weight: bold;">edge_container_type </td>
+ <td>Container of the Voronoi edges. </td>
</tr>
-
<tr>
- <td style="font-weight: bold;">const_edge_iterator<br>
- </td>
- <td>Const edge container iterator.<br>
- </td>
+ <td style="font-weight: bold;">const_edge_iterator </td>
+ <td>Const edge container iterator. </td>
</tr>
</tbody>
</table>
-
-
-
- <h1>Voronoi Geometry Type<br>
- </h1>
- <h2>GeometryCategory<br>
- </h2>
-Defines geometry type of the input objects.<br>
- <br>
- <span style="font-family: Courier New,Courier,monospace;">enum GeometryCategory {</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> GEOMETRY_CATEGORY_POINT = 0x0,</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> GEOMETRY_CATEGORY_SEGMENT = 0x1</span><br style="font-family: Courier New,Courier,monospace;">
+ <h1>Voronoi Geometry Type</h1>
+The Voronoi
+diagram data structure doesn't embed coordinates of the input
+geometries.
+Instead it links with those via source index and source category
+methods
+of the Voronoi cell primitive. Source index is incrementally given
+(starting from zero) to each input site inserted into the <a
+ href="voronoi_builder.htm">Voronoi
+builder</a>.
+Considering the fact, that each input segment is splitted onto three
+separate sites with the same index, we distinguish between those using
+source category. For more examples check the <a
+ href="voronoi_basic_tutorial.htm">Voronoi basic tutorial</a>.<br>
+ <h2>GeometryCategory </h2>
+Defines geometric category of the input object.<br>
+Header: boost/polygon/<a
+ href="../../../boost/polygon/voronoi_geometry_type.hpp">voronoi_geometry_type.hpp</a><br>
+ <br>
+ <span style="font-family: Courier New,Courier,monospace;">enum
+GeometryCategory {</span><br
+ style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+GEOMETRY_CATEGORY_POINT = 0x0,</span><br
+ style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+GEOMETRY_CATEGORY_SEGMENT = 0x1</span><br
+ style="font-family: Courier New,Courier,monospace;">
<span style="font-family: Courier New,Courier,monospace;">};</span><br>
<h2>SourceCategory</h2>
-
-Defines category of the input site that forms Voronoi cell.<br>
- <br>
- <span style="font-family: Courier New,Courier,monospace;">enum SourceCategory {</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> // Point subtypes.</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> SOURCE_CATEGORY_SINGLE_POINT = 0x0,</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> SOURCE_CATEGORY_SEGMENT_START_POINT = 0x1,</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> SOURCE_CATEGORY_SEGMENT_END_POINT = 0x2,</span><br style="font-family: Courier New,Courier,monospace;">
+Defines semantic category of the input site.<br>
+Header: boost/polygon/<a
+ href="../../../boost/polygon/voronoi_geometry_type.hpp">voronoi_geometry_type.hpp</a><br>
+ <br>
+ <span style="font-family: Courier New,Courier,monospace;">enum
+SourceCategory {</span><br
+ style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+// Point subtypes.</span><br
+ style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+SOURCE_CATEGORY_SINGLE_POINT = 0x0,</span><br
+ style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+SOURCE_CATEGORY_SEGMENT_START_POINT = 0x1,</span><br
+ style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+SOURCE_CATEGORY_SEGMENT_END_POINT = 0x2,</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;"> // Segment subtypes.</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> SOURCE_CATEGORY_INITIAL_SEGMENT = 0x8,</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> SOURCE_CATEGORY_REVERSE_SEGMENT = 0x9,</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+// Segment subtypes.</span><br
+ style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+SOURCE_CATEGORY_INITIAL_SEGMENT = 0x8,</span><br
+ style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+SOURCE_CATEGORY_REVERSE_SEGMENT = 0x9,</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;"> SOURCE_CATEGORY_GEOMETRY_SHIFT = 0x3,</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> SOURCE_CATEGORY_BITMASK = 0x1F</span><br style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+SOURCE_CATEGORY_GEOMETRY_SHIFT = 0x3,</span><br
+ style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+SOURCE_CATEGORY_BITMASK = 0x1F</span><br
+ style="font-family: Courier New,Courier,monospace;">
<span style="font-family: Courier New,Courier,monospace;">};</span><br>
- <br>
-Voronoi
-diagram data structure doesn't store coordinates of the input
-geometries.
-Instead it links with those via source index and source category method
-of the Voronoi cell primitive. Source index is incrementally given
-(starting from zero) to each input site inserted into Voronoi builder.
-Considering the fact that each input segment is splitted onto three
-separate sites with the same index, we distinguish between them using
-SourceCategory. For the example see Voronoi basic tutorial.<br>
<h2>Member Functions</h2>
- <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <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;">bool <span style="font-weight: bold;">belongs</span>(</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> SourceCategory source_category,</span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;"> GeometryCategory geometry_category)</span><br>
- </td>
- <td style="vertical-align: middle;">Returns true if source category belongs to the given geometry category.<br>
-Returns false else.<br>
- </td>
+ <td style="vertical-align: top;"><span
+ style="font-family: Courier New,Courier,monospace;">bool <span
+ style="font-weight: bold;">belongs</span>(</span><br
+ style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+ SourceCategory source_category,</span><br
+ style="font-family: Courier New,Courier,monospace;">
+ <span style="font-family: Courier New,Courier,monospace;">
+GeometryCategory geometry_category)</span> </td>
+ <td style="vertical-align: middle;">Returns true if the
+given source
+category belongs to the given geometry category.<br>
+Returns false otherwise. </td>
</tr>
</tbody>
</table>
<h1>Voronoi Edge</h1>
-
-
-Voronoi edge is represented as enhanced classical half-edge
-data structure.<br>
+A Voronoi edge is a one-dimenstion curve, that contains points
+equidistant from the two closest input geometries. The Voronoi edge
+data structure is implemented as the enhanced classical <a
+ href="http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml">half-edge</a>
+data structure. On the image below, the Voronoi edges are drawn as
+directed linear (e.g. AE) or curved (e.g. DE) dashed lines of either
+green (e.g. AE) or black (e.g DE) color. The green edges are considered
+to be secondary, as they are generated by an input segment and its
+endpoint (e.g. edge EA, made by segment MN and its endpoint M). All the
+other edges are considered to be primary (e.g. curved edge CD, made by
+segment KL and point N). Apart from that, each edge can be finite (e.g.
+ED) or infinite (e.g. edge starting at point B and going in the east
+direction).<br>
+ <img src="images/voronoi1.png" alt=""
+ style="width: 600px; height: 600px;"><br>
+Each Voronoi edge (consider directed edge BA) provides efficient access
+to the following primitives:<br>
+ <ul>
+ <li>Cell the edge belongs to (Voronoi cell P, with source
+segment MN)</li>
+ <li>Start point of the edge (Voronoi vertex B, that is
+equidistant from the following input sites: O, L, MN)</li>
+ <li>End point of the edge (Voronoi vertex A, that is
+equidistant from the following input sites: O, M, MN)</li>
+ <li>Twin edge (Voronoi edge AB)</li>
+ <li>CCW next edge inside the Voronoi cell, that the edge
+belongs to (green Voronoi edge AE)</li>
+ <li>CCW previous edge inside the Voronoi cell, that the edge
+belongs to (Voronoi edge CB)</li>
+ <li>CCW rotated next edge around the start point of the edge
+(Voronoi edge BC)</li>
+ <li>CCW rotated previous edge around the start point of the
+edge (infinite Voronoi edge starting at the Voronoi vertex B and going
+in the east direction) </li>
+ </ul>
<h2>Declaration</h2>
-
-
-
+Header: boost/polygon/voronoi_diagram.hpp<br>
+ <br>
<span style="font-family: Courier New,Courier,monospace;">template
-<typename T></span><br style="font-family: Courier New,Courier,monospace;">
+<typename T></span><br
+ style="font-family: Courier New,Courier,monospace;">
<span style="font-family: Courier New,Courier,monospace;">class
voronoi_edge;<br>
<br>
T</span> - coordinate type.<br>
<h2>Member Functions</h2>
-
- <span style="font-family: Courier New,Courier,monospace;">
-
- </span>
- <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <span style="font-family: Courier New,Courier,monospace;"> </span>
+ <table style="text-align: left; width: 100%;" border="1"
+ cellpadding="2" cellspacing="2">
<tbody>
-
<tr>
- <td><span style="font-family: Courier New,Courier,monospace;"><span style="font-weight: bold;">voronoi_edge</span>(bool is_linear, bool is_primary)</span><br>
- </td>
- <td>Voronoi edge constructor.<br>
- </td>
+ <td><span
+ style="font-family: Courier New,Courier,monospace;"><span
+ style="font-weight: bold;">voronoi_edge</span>(bool is_linear, bool
+is_primary)</span> </td>
+ <td>Voronoi edge constructor. </td>
</tr>
-<tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_cell_type* <span style="font-weight: bold;">cell</span>()<br>
- </td>
+ <tr>
+ <td style="font-family: Courier New,Courier,monospace;">voronoi_cell_type*
+ <span style="font-weight: bold;">cell</span>() </td>
<td>Returns the pointer to the
Voronoi <span style="font-family: Courier New,Courier,monospace;"></span>cell
-that edge belongs to.<br>
- </td>
+that the edge belongs to. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">const
-voronoi_cell_type* <span style="font-weight: bold;">cell</span>() const<br>
- </td>
+voronoi_cell_type* <span style="font-weight: bold;">cell</span>()
+const </td>
<td>Returns the const pointer
-to the Voronoi cell that edge belongs to.<br>
- </td>
+to the Voronoi cell that the edge belongs to. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">void
- <span style="font-weight: bold;">cell</span>(voronoi_cell_type* c)<br>
- </td>
+ <span style="font-weight: bold;">cell</span>(voronoi_cell_type*
+c) </td>
<td>Sets the Voronoi cell
-pointer for the cell current edge belongs to.<br>
- </td>
+pointer to the cell the current edge belongs to. </td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_vertex_type* <span style="font-weight: bold;">vertex0</span>()<br>
- </td>
+ <td style="font-family: Courier New,Courier,monospace;">voronoi_vertex_type*
+ <span style="font-weight: bold;">vertex0</span>() </td>
<td>Returns the pointer to the
start point of the edge.<br>
-If the edge is infinite in that direction returns NULL.<br>
- </td>
+If the edge is infinite in that direction returns NULL. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">const
-voronoi_vertex_type* <span style="font-weight: bold;">vertex0</span>() const<br>
- </td>
+voronoi_vertex_type* <span style="font-weight: bold;">vertex0</span>()
+const </td>
<td>Returns the const pointer
-to the point vertex of the edge.<br>
-If the edge is infinite in that direction returns NULL.<br>
- </td>
+to the start point vertex of the edge.<br>
+If the edge is infinite in that direction returns NULL. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">void
- <span style="font-weight: bold;">vertex0</span>(voronoi_vertex_type* v)<br>
- </td>
+ <span style="font-weight: bold;">vertex0</span>(voronoi_vertex_type*
+v) </td>
<td>Sets the start point
-pointer of the edge.<br>
- </td>
+pointer of the edge. </td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_vertex_type* <span style="font-weight: bold;">vertex1</span>()<br>
- </td>
+ <td style="font-family: Courier New,Courier,monospace;">voronoi_vertex_type*
+ <span style="font-weight: bold;">vertex1</span>() </td>
<td>Returns the pointer to the
end point of the edge.<br>
-If the edge is infinite in that direction returns NULL.<br>
- </td>
+If the edge is infinite in that direction returns NULL. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">const
-voronoi_vertex_type* <span style="font-weight: bold;">vertex1</span>() const<br>
- </td>
+voronoi_vertex_type* <span style="font-weight: bold;">vertex1</span>()
+const </td>
<td>Returns the const pointer
to the end point of the edge.<br>
-If the edge is infinite in that direction returns NULL.<br>
- </td>
+If the edge is infinite in that direction returns NULL. </td>
</tr>
-
<tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* <span style="font-weight: bold;">twin</span>()<br>
- </td>
+ <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
+ <span style="font-weight: bold;">twin</span>() </td>
<td>Returns the pointer to the
-twin edge.<br>
- </td>
+twin edge. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">const
-voronoi_edge_type* <span style="font-weight: bold;">twin</span>() const<br>
- </td>
+voronoi_edge_type* <span style="font-weight: bold;">twin</span>()
+const </td>
<td>Returns the const pointer
-to the twin edge.<br>
- </td>
+to the twin edge. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">void
- <span style="font-weight: bold;">twin</span>(voronoi_edge_type* e)<br>
- </td>
+ <span style="font-weight: bold;">twin</span>(voronoi_edge_type*
+e) </td>
<td>Sets the twin edge pointer
-of the edge.<br>
- </td>
+of the edge. </td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* <span style="font-weight: bold;">next</span>()<br>
- </td>
+ <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
+ <span style="font-weight: bold;">next</span>() </td>
<td>Returns the pointer to the
CCW next edge within the corresponding Voronoi cell.<br>
-Edges not necessarily share a common vertex (e.g. infinite edges).<br>
- </td>
+Edges not necessarily share a common vertex (e.g. infinite edges). </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">const
-voronoi_edge_type* <span style="font-weight: bold;">next</span>() const<br>
- </td>
+voronoi_edge_type* <span style="font-weight: bold;">next</span>()
+const </td>
<td>Returns the const pointer
to the CCW next edge within the corresponding Voronoi cell.<br>
-Edges not necessarily share a common vertex (e.g. infinite edges).<br>
- </td>
+Edges not necessarily share a common vertex (e.g. infinite edges). </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">void
- <span style="font-weight: bold;">next</span>(voronoi_edge_type* e)<br>
- </td>
+ <span style="font-weight: bold;">next</span>(voronoi_edge_type*
+e) </td>
<td>Sets the CCW next edge
-pointer of the edge.<br>
- </td>
+pointer of the edge. </td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* <span style="font-weight: bold;">prev</span>()<br>
- </td>
+ <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
+ <span style="font-weight: bold;">prev</span>() </td>
<td>Returns the pointer to the
CCW prev edge within the corresponding Voronoi cell.<br>
-Edges not necessarily share a common vertex (e.g. infinite edges).<br>
- </td>
+Edges not necessarily share a common vertex (e.g. infinite edges). </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">const
-voronoi_edge_type* <span style="font-weight: bold;">prev</span>() const<br>
- </td>
+voronoi_edge_type* <span style="font-weight: bold;">prev</span>()
+const </td>
<td>Returns the const pointer
to the CCW prev edge within the corresponding Voronoi cell.<br>
-Edges not necessarily share a common vertex (e.g. infinite edges).<br>
- </td>
+Edges not necessarily share a common vertex (e.g. infinite edges). </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">void
- <span style="font-weight: bold;">prev</span>(voronoi_edge_type* e)<br>
- </td>
+ <span style="font-weight: bold;">prev</span>(voronoi_edge_type*
+e) </td>
<td>Sets the CCW prev edge
-pointer of the edge.<br>
- </td>
+pointer of the edge. </td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">color_type <span style="font-weight: bold;">color</span>() const<br>
- </td>
- <td>Returns the color value.<br>
- </td>
+ <td style="font-family: Courier New,Courier,monospace;">color_type
+ <span style="font-weight: bold;">color</span>() const </td>
+ <td>Returns the color value. </td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">void <span style="font-weight: bold;">color</span>(color_type color) const<br>
- </td>
+ <td style="font-family: Courier New,Courier,monospace;">void
+ <span style="font-weight: bold;">color</span>(color_type
+color) const </td>
<td>Sets the color of
the edge.<br>
-Allows to execute graph algorithms and associate data.<br>
- </td>
+Allows to associate the user provided data with the primitive. </td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* <span style="font-weight: bold;">rot_next</span>()<br>
- </td>
+ <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
+ <span style="font-weight: bold;">rot_next</span>() </td>
<td>Returns the pointer to the
-CCW next edge rotated around the edge start point.<br>Works for infinite
- edges as well.<br>
- </td>
+CCW next edge rotated around the edge start point.<br>
+Works for infinite edges as well. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">const
-voronoi_edge_type* <span style="font-weight: bold;">rot_next</span>() const<br>
- </td>
+voronoi_edge_type* <span style="font-weight: bold;">rot_next</span>()
+const </td>
<td>Returns the const pointer
-to the CCW next edge rotated around the edge start point.<br>Works for infinite edges as well.</td>
+to the CCW next edge rotated around the edge start point.<br>
+Works for infinite edges as well.</td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* <span style="font-weight: bold;">rot_prev</span>()<br>
- </td>
+ <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
+ <span style="font-weight: bold;">rot_prev</span>() </td>
<td>Returns the pointer to the
-CCW prev edge rotated around the edge start point.<br>Works for infinite edges as well.<br>
- </td>
+CCW prev edge rotated around the edge start point.<br>
+Works for infinite edges as well. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">const
-voronoi_edge_type* <span style="font-weight: bold;">rot_prev</span>() const<br>
- </td>
+voronoi_edge_type* <span style="font-weight: bold;">rot_prev</span>()
+const </td>
<td>Returns the const pointer
-to the CCW prev edge rotated around the edge start point.<br>Works for infinite edges as well.</td>
+to the CCW prev edge rotated around the edge start point.<br>
+Works for infinite edges as well.</td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">bool
- <span style="font-weight: bold;">is_finite</span>() const<br>
- </td>
+ <span style="font-weight: bold;">is_finite</span>() const </td>
<td>Returns true if the both
-end points of the edge are finite, else false.<br>
- </td>
+end points of the edge are finite, else false. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">bool
@@ -560,427 +563,436 @@
<td>Returns true if one of the
end points of the edge is infinite, else false.</td>
</tr>
-<tr>
+ <tr>
<td style="font-family: Courier New,Courier,monospace;">bool
- <span style="font-weight: bold;">is_linear</span>() const<br>
- </td>
+ <span style="font-weight: bold;">is_linear</span>() const </td>
<td>Returns true if the edge
-is linear (segment, ray, line), else false.<br>
- </td>
+is linear (segment, ray, line), else false. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">bool
- <span style="font-weight: bold;">is_curved</span>() const<br>
- </td>
+ <span style="font-weight: bold;">is_curved</span>() const </td>
<td>Returns true if the edge
-is curved (parabolic arc), else false.<br>
- </td>
+is curved (parabolic arc), else false. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">bool
- <span style="font-weight: bold;">is_primary</span>() const<br>
- </td>
+ <span style="font-weight: bold;">is_primary</span>() const </td>
<td>Returns false if the edge
-goes through the endpoint of the segment site, else true.<br>
- </td>
- </tr><tr>
+goes through the endpoint of the segment site, else true. </td>
+ </tr>
+ <tr>
<td style="font-family: Courier New,Courier,monospace;">bool
<span style="font-weight: bold;">is_secondary</span>() const</td>
<td>Returns true if the edge
goes through the endpoint of the segment site, else false.</td>
</tr>
-
</tbody>
</table>
- <span style="font-family: Courier New,Courier,monospace;"><br>
- </span>All
+ <span style="font-family: Courier New,Courier,monospace;"> </span>All
the above methods have O(1) complexity. The size of
-the Voronoi edge structure is equal to: 5 * sizeof(void *) + sizeof(size_t).<span style="font-family: Courier New,Courier,monospace;"></span><br>
+the Voronoi edge structure is equal to: 5 * sizeof(void *) +
+sizeof(size_t).<span style="font-family: Courier New,Courier,monospace;"></span><br>
<h2>Member Types</h2>
-
- <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <table style="text-align: left; width: 100%;" border="1"
+ cellpadding="2" cellspacing="2">
<tbody>
<tr>
- <td style="font-weight: bold;">coordinate_type<br>
- </td>
- <td>Coordinate type.<br>
- </td>
+ <td style="font-weight: bold;">coordinate_type </td>
+ <td>Coordinate type. </td>
</tr>
<tr>
- <td style="font-weight: bold;">voronoi_cell_type<br>
- </td>
- <td>Voronoi cell type.<br>
- </td>
+ <td style="font-weight: bold;">voronoi_cell_type </td>
+ <td>Voronoi cell type. </td>
</tr>
<tr>
- <td style="font-weight: bold;">voronoi_vertex_type<br>
- </td>
- <td>Voronoi vertex type.<br>
- </td>
+ <td style="font-weight: bold;">voronoi_vertex_type </td>
+ <td>Voronoi vertex type. </td>
</tr>
<tr>
- <td style="font-weight: bold;">voronoi_edge_type<br>
- </td>
- <td>Voronoi edge type.<br>
- </td>
- </tr><tr>
- <td style="vertical-align: top; font-weight: bold;">color_type<br>
- </td>
- <td style="vertical-align: top;">Color type (check the Important section).<br>
+ <td style="font-weight: bold;">voronoi_edge_type </td>
+ <td>Voronoi edge type. </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-weight: bold;">color_type
</td>
+ <td style="vertical-align: top;">Color type (check the
+Important section). </td>
</tr>
-
</tbody>
</table>
<h1>Voronoi Cell</h1>
-
-Voronoi cell is represented by a site the cell contains and a pointer
-to the incident edge.<br>
+A Voronoi cell represents a region of the Voronoi diagram bounded by
+the Voronoi edges. On the image below, there are 7 such regions: P, Q,
+R, S, T, U, V. Each Voronoi cell can contain a point (e.g. cells Q, S,
+T, U, V with corresponding input sources N, K, L, O, M respectively) or
+a segment
+(e.g. cells P and R with corresponding input sources MN and KL
+respectively) as its
+source. The Voronoi cell primitive doesn't contain coordinates of the
+source geometry, instead it stores the index and category of the source
+geometry. Source index corresponds to the unique id, issued to each
+input geometry (e.g. incremental counter, used by the Voronoi builder).
+Such an index uniquely identifies any input point (e.g. O), however
+doesn't make any distinction between segment (e.g. MN) and both its end
+points (e.g. M, N). In order to resolve possible ambiguity, the source
+category is used, that specifies the semantic topology of the input
+object (e.g. segment's startpoint, segment's endpoint or segment
+itself). The Voronoi cell data structure also provides access to a
+random Voronoi edge, located on the boundary of the cell (e.g. edge AE
+for
+the cell P).<br>
+ <img style="width: 600px; height: 600px;" alt=""
+ src="images/voronoi1.png"><br>
<h2>Declaration</h2>
-
-
-
+Header: boost/polygon/voronoi_diagram.hpp<br>
+ <br>
<span style="font-family: Courier New,Courier,monospace;">template
<typename T><br>
class voronoi_cell;<br>
<br>
-</span><span style="font-family: Courier New,Courier,monospace;">T</span> - coordinate type.<br>
+ </span><span style="font-family: Courier New,Courier,monospace;">T</span>
+- coordinate type.<br>
<h2>Member Functions</h2>
-
- <span style="font-family: Courier New,Courier,monospace;">
-
- </span>
- <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <span style="font-family: Courier New,Courier,monospace;"> </span>
+ <table style="text-align: left; width: 100%;" border="1"
+ cellpadding="2" cellspacing="2">
<tbody>
-
-
<tr>
- <td><span style="font-family: Courier New,Courier,monospace;"><span style="font-weight: bold;">voronoi_cell</span>(source_index_type source_index,</span><span style="font-family: Courier New,Courier,monospace;"><br>
- source_category_type source_category)</span><br>
- </td>
- <td>Voronoi cell constructor.<br>
- </td>
+ <td><span
+ style="font-family: Courier New,Courier,monospace;"><span
+ style="font-weight: bold;">voronoi_cell</span>(source_index_type
+source_index,</span><span
+ style="font-family: Courier New,Courier,monospace;"><br>
+
+source_category_type source_category)</span> </td>
+ <td>Voronoi cell constructor. </td>
</tr>
-<tr>
- <td style="font-family: Courier New,Courier,monospace;">source_index_type <span style="font-weight: bold;">source_index</span>() const<br>
- </td>
+ <tr>
+ <td style="font-family: Courier New,Courier,monospace;">source_index_type
+ <span style="font-weight: bold;">source_index</span>()
+const </td>
<td>Returns input site index among the other sites.<br>
-Both segment endpoints and segment itself will have the same index.<br>
- </td>
+Both segment and its end points will have the same index. </td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">source_category_type <span style="font-weight: bold;">source_category</span>() const<br>
- </td>
+ <td style="font-family: Courier New,Courier,monospace;">source_category_type
+ <span style="font-weight: bold;">source_category</span>()
+const </td>
<td>Returns input site category among the other sites.<br>
-Allows to distinguish between segment site and its endpoints.<br>
-
- </td>
+Allows to distinguish between segment site and its endpoints. </td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* <span style="font-weight: bold;">incident_edge</span>()<br>
- </td>
+ <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
+ <span style="font-weight: bold;">incident_edge</span>() </td>
<td>Returns the pointer to the
-one of the boundary edges.<br>
- </td>
+one of the boundary edges. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">const
-voronoi_edge_type* <span style="font-weight: bold;">incident_edge</span>() const<br>
- </td>
+voronoi_edge_type* <span style="font-weight: bold;">incident_edge</span>()
+const </td>
<td>Returns the const pointer
-to the one of the boundary edges.<br>
- </td>
+to the one of the boundary edges. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">void
- <span style="font-weight: bold;">incident_edge</span>(voronoi_edge_type* e)<br>
- </td>
+ <span style="font-weight: bold;">incident_edge</span>(voronoi_edge_type*
+e) </td>
<td>Sets the incident boundary
-edge pointer of the cell.<br>
- </td>
+edge pointer of the cell. </td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">color_type <span style="font-weight: bold;">color</span>() const<br>
- </td>
+ <td style="font-family: Courier New,Courier,monospace;">color_type
+ <span style="font-weight: bold;">color</span>() const </td>
<td>Returns the color associated with the cell.</td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">void <span style="font-weight: bold;">color</span>(color_type color) const<br>
- </td>
+ <td style="font-family: Courier New,Courier,monospace;">void
+ <span style="font-weight: bold;">color</span>(color_type
+color) const </td>
<td>Sets the color of
the cell.<br>
-
-Allows to execute graph algorithms and associate data.<br>
-</td>
+Allows to associate the user provided data with the primitive. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">bool
- <span style="font-weight: bold;">contains_point</span>() const</td>
+ <span style="font-weight: bold;">contains_point</span>()
+const</td>
<td>Returns true if the cell
contains a point site, else false.</td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">bool
- <span style="font-weight: bold;">contains_segment</span>() const</td>
+ <span style="font-weight: bold;">contains_segment</span>()
+const</td>
<td>Returns true if the cell
contains a segment site, else false.</td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">bool
- <span style="font-weight: bold;">is_degenerate</span>() const </td>
+ <span style="font-weight: bold;">is_degenerate</span>()
+const </td>
<td>Returns true if the cell
doesn't have an incident edge.<br>
-Could happen if a few input segments share a common endpoint.</td>
+Can happen if a few input segments share a common endpoint.</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 cell structure is equal to: sizeof(void *) + 2 * sizeof(size_t).<span style="font-family: Courier New,Courier,monospace;"></span>
+ <span style="font-family: Courier New,Courier,monospace;"> </span>All
+the above methods have O(1) complexity. The size of
+the Voronoi cell structure is equal to: sizeof(void *) + 2 *
+sizeof(size_t).<span style="font-family: Courier New,Courier,monospace;"></span>
<h2>Member Types</h2>
-
-
-
- <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <table style="text-align: left; width: 100%;" border="1"
+ cellpadding="2" cellspacing="2">
<tbody>
<tr>
- <td style="font-weight: bold;">coordinate_type<br>
- </td>
- <td>Coordinate type.<br>
- </td>
+ <td style="font-weight: bold;">coordinate_type </td>
+ <td>Coordinate type. </td>
</tr>
<tr>
<td style="font-weight: bold;">source_index_type</td>
- <td>Source index type.<br>
- </td>
+ <td>Source index type. </td>
</tr>
<tr>
- <td style="vertical-align: top; font-weight: bold;">source_category_type<br>
- </td>
- <td style="vertical-align: top;">Source category type.<br>
+ <td style="vertical-align: top; font-weight: bold;">source_category_type
</td>
+ <td style="vertical-align: top;">Source category type. </td>
</tr>
-<tr>
+ <tr>
<td style="vertical-align: top; font-weight: bold;">voronoi_edge_type
</td>
- <td style="vertical-align: top;">Voronoi edge type.
- </td>
+ <td style="vertical-align: top;">Voronoi edge type. </td>
</tr>
-<tr>
- <td style="font-weight: bold;">color_type
- </td>
- <td>Color type (check the Important section).
- </td>
+ <tr>
+ <td style="font-weight: bold;">color_type </td>
+ <td>Color type (check the Important section). </td>
</tr>
</tbody>
</table>
<h2>Miscellaneous</h2>
-
-The following code snippet effectively traverses the Voronoi edges around the
+The following code snippet effectively traverses the 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;">do {</span><br style="font-family: Courier New,Courier,monospace;">
+ <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;">
+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;">
+// 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.<br>
+A Voronoi vertex represents a point, that is equidistant from the three
+or more input geometries. As a consequence, it corresponds to the point
+of the intersection of the three or more Voronoi edges. On the image
+below, there are 5 such vertices: A, B, C, D, E. The Voronoi vertex
+data structure embeds the coordinates of the underlying point and
+provides access to a random Voronoi edge originating from the vertex
+(e.g. edge
+BC for the vertex B).<br>
+ <img style="width: 600px; height: 600px;" alt=""
+ src="images/voronoi1.png"><br>
<h2>Declaration</h2>
-
-
-
+Header: boost/polygon/voronoi_diagram.hpp<br>
+ <br>
<span style="font-family: Courier New,Courier,monospace;">template
-<typename T></span><br style="font-family: Courier New,Courier,monospace;">
+<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><span style="font-family: Courier New,Courier,monospace;">T</span> - coordinate type.<br>
+ </span><span style="font-family: Courier New,Courier,monospace;">T</span>
+- coordinate type.<br>
<h2>Member Functions</h2>
-
- <span style="font-family: Courier New,Courier,monospace;">
-
- </span>
- <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <span style="font-family: Courier New,Courier,monospace;"> </span>
+ <table style="text-align: left; width: 100%;" border="1"
+ cellpadding="2" cellspacing="2">
<tbody>
-
<tr>
- <td><span style="font-family: Courier New,Courier,monospace;"><span style="font-weight: bold;">voronoi_vertex</span>(const coordinate_type& x,<br>
- const coordinate_type& y)</span><span style="font-family: Courier New,Courier,monospace;"></span><br>
- </td>
- <td>Voronoi vertex constructor.<br>
- </td>
+ <td><span
+ style="font-family: Courier New,Courier,monospace;"><span
+ style="font-weight: bold;">voronoi_vertex</span>(const
+coordinate_type& x,<br>
+
+const coordinate_type& y)</span><span
+ style="font-family: Courier New,Courier,monospace;"></span> </td>
+ <td>Voronoi vertex constructor. </td>
</tr>
-<tr>
+ <tr>
<td style="font-family: Courier New,Courier,monospace;">const
-point_type& <span style="font-weight: bold;">x</span>() const<br>
- </td>
- <td>Returns the x-coordinate of the point that represents the vertex.<br>
- </td>
+point_type& <span style="font-weight: bold;">x</span>() const </td>
+ <td>Returns the x-coordinate of the point that represents
+the vertex. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">const
point_type& <span style="font-weight: bold;">y</span>() const</td>
- <td>Returns the y-coordinate of the point that represents the vertex.<br>
- </td>
+ <td>Returns the y-coordinate of the point that represents
+the vertex. </td>
</tr>
-<tr>
- <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type* <span style="font-weight: bold;">incident_edge</span>()<br>
- </td>
+ <tr>
+ <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
+ <span style="font-weight: bold;">incident_edge</span>() </td>
<td>Returns the incident edge
-pointer.<br>
- </td>
+pointer. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">const
-voronoi_edge_type* <span style="font-weight: bold;">incident_edge</span>() const<br>
- </td>
+voronoi_edge_type* <span style="font-weight: bold;">incident_edge</span>()
+const </td>
<td>Returns the const pointer
-to the incident edge.<br>
- </td>
+to the incident edge. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">void
- <span style="font-weight: bold;">incident_edge</span>(voronoi_edge_type* e)<br>
- </td>
+ <span style="font-weight: bold;">incident_edge</span>(voronoi_edge_type*
+e) </td>
<td>Sets the incident edge
-pointer.<br>
- </td>
+pointer. </td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">color_type <span style="font-weight: bold;">color</span>() const<br>
- </td>
+ <td style="font-family: Courier New,Courier,monospace;">color_type
+ <span style="font-weight: bold;">color</span>() const </td>
<td>Returns the color associated with the vertex.</td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace;">void <span style="font-weight: bold;">color</span>(color_type color) const<br>
- </td>
+ <td style="font-family: Courier New,Courier,monospace;">void
+ <span style="font-weight: bold;">color</span>(color_type
+color) const </td>
<td>Sets the color of
the vertex.<br>
-Allows to executegraph algorithms and associate data.</td>
+Allows to associate the user provided data with the primitive.</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: sizeof(void *) + sizeof(size_t) + 2 *
-sizeof(coordinate_type).<span style="font-family: Courier New,Courier,monospace;"></span>
+ <span style="font-family: Courier New,Courier,monospace;"> </span>All
+the above methods have O(1) complexity. The size of
+the Voronoi vertex structure is equal to: sizeof(void *) +
+sizeof(size_t) + 2 *
+sizeof(coordinate_type).<span
+ style="font-family: Courier New,Courier,monospace;"></span>
<h2>Member Types</h2>
- <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <table style="text-align: left; width: 100%;" border="1"
+ cellpadding="2" cellspacing="2">
<tbody>
<tr>
- <td style="font-weight: bold;">coordinate_type<br>
- </td>
- <td>Coordainte type.<br>
- </td>
+ <td style="font-weight: bold;">coordinate_type </td>
+ <td>Coordainte type. </td>
</tr>
-
<tr>
- <td style="vertical-align: top; font-weight: bold;">voronoi_edge_type<br>
- </td>
- <td style="vertical-align: top;">Voronoi edge type.<br>
+ <td style="vertical-align: top; font-weight: bold;">voronoi_edge_type
</td>
+ <td style="vertical-align: top;">Voronoi edge type. </td>
</tr>
-<tr>
- <td style="font-weight: bold;">color_type
- </td>
- <td>Color type (check the Important section).
- </td>
+ <tr>
+ <td style="font-weight: bold;">color_type </td>
+ <td>Color type (check the Important section). </td>
</tr>
</tbody>
</table>
-
- <h2>Miscellaneous</h2>The following code snippet effectively traverses the Voronoi edges around the
+ <h2>Miscellaneous</h2>
+The following code snippet effectively traverses the 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;">do {</span><br style="font-family: Courier New,Courier,monospace;">
+ <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;">
+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;">
+// 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());<br>
-</span>
- <h1>Voronoi Diagram Traits<br>
- </h1>
-Voronoi diagram traits are used to configure Voronoi diagram data
+(edge != vertex->incident_edge()); </span>
+ <h1>Voronoi Diagram Traits </h1>
+The Voronoi diagram traits are used to configure the Voronoi primitive
+types and predicates, used by the Voronoi diagram
+data
structure.<br>
+The implementation includes default traits specialization for the
+double output coordinate type.<br>
<h2>Declaration</h2>
-
-
-
+Header: boost/polygon/voronoi_diagram.hpp<br>
+ <br>
<span style="font-family: Courier New,Courier,monospace;">template
-<typename T></span><br style="font-family: Courier New,Courier,monospace;">
+<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><span style="font-family: Courier New,Courier,monospace;">T</span> - coordinate type.<br>
+ </span><span style="font-family: Courier New,Courier,monospace;">T</span>
+- coordinate type.<br>
<h2>Member Types</h2>
-
- <span style="font-family: Courier New,Courier,monospace;">
-
- </span>
- <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <span style="font-family: Courier New,Courier,monospace;"> </span>
+ <table style="text-align: left; width: 100%;" border="1"
+ cellpadding="2" cellspacing="2">
<tbody>
<tr>
- <td style="font-family: Courier New,Courier,monospace; font-weight: bold;">coordinate_type<br>
- </td>
- <td>The main coordinate type
-of the Voronoi diagram primitives.<br>
+ <td
+ style="font-family: Courier New,Courier,monospace; font-weight: bold;">coordinate_type
</td>
+ <td>Coordinate type
+of the Voronoi diagram primitives. </td>
</tr>
-
-
<tr>
- <td style="font-family: Courier New,Courier,monospace; font-weight: bold;">cell_type<br>
- </td>
- <td>Voronoi cell type.<br>
+ <td
+ style="font-family: Courier New,Courier,monospace; font-weight: bold;">cell_type
</td>
+ <td>Voronoi cell type. </td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace; font-weight: bold;">vertex_type<br>
- </td>
- <td>Voronoi vertex_type.<br>
+ <td
+ style="font-family: Courier New,Courier,monospace; font-weight: bold;">vertex_type
</td>
+ <td>Voronoi vertex type. </td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace; font-weight: bold;">edge_type<br>
- </td>
- <td>Voronoi edge_type.<br>
+ <td
+ style="font-family: Courier New,Courier,monospace; font-weight: bold;">edge_type
</td>
+ <td>Voronoi edge type. </td>
</tr>
<tr>
- <td style="font-family: Courier New,Courier,monospace; font-weight: bold;">vertex_equality_predicate_type<br>
+ <td
+ style="font-family: Courier New,Courier,monospace; font-weight: bold;">vertex_equality_predicate_type
</td>
<td>Predicate that returns
-true if two points are considered to be equal.<br>
-This is used to unite nearby Voronoi vertices.<br>
- </td>
+true if the two points are considered to be equal.<br>
+False otherwise. It is used to unite nearby Voronoi vertices. </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%">
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1"> </td>
+ <td
+ style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
+ valign="top" width="100%">
<table class="docinfo" id="table2" frame="void" rules="none">
- <colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> <tbody valign="top">
+ <colgroup> <col class="docinfo-name"><col
+ class="docinfo-content"> </colgroup> <tbody valign="top">
<tr>
<th class="docinfo-name">Copyright:</th>
- <td>Copyright © Andrii Sydorchuk 2010-2012.</td>
+ <td>Copyright © Andrii Sydorchuk 2010-2013.</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">
+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>
@@ -989,6 +1001,5 @@
</tr>
</tbody>
</table>
-
-
-</body></html>
\ No newline at end of file
+</body>
+</html>
==============================================================================
--- trunk/libs/polygon/doc/voronoi_main.htm (original)
+++ trunk/libs/polygon/doc/voronoi_main.htm 2013-04-07 19:09:31 EDT (Sun, 07 Apr 2013)
@@ -55,15 +55,12 @@
<li>Property Merge 90</li>
<li>Property Merge 45</li>
<li>Property Merge</li>
- <li>Voronoi Main Page<br>
- </li>
+ <li>Voronoi Main Page </li>
<li>Voronoi Benchmark</li>
- <li>Voronoi Builder<br>
- </li>
+ <li>Voronoi Builder </li>
<li>Voronoi Diagram</li>
<li>Voronoi Predicates</li>
- <li>Voronoi Robust FPT<br>
- </li>
+ <li>Voronoi Robust FPT </li>
</ul>
<h3 class="navbar">Other Resources</h3>
<ul>
@@ -87,96 +84,112 @@
<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>
+ <h1>THE BOOST.POLYGON VORONOI LIBRARY </h1>
<img style="width: 900px; height: 300px;" alt=""
src="images/voronoi3.png"><br>
-The Boost.Polygon Voronoi library provides functionality to construct
-the Voronoi diagram
+The Voronoi extension of the Boost.Polygon library provides
+functionality to construct a <a href="voronoi_diagram.htm">Voronoi
+diagram</a>
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
+input segments
should be of the integer type;</li>
<li>input segments should not overlap
except their endpoints.</li>
</ul>
While the first restriction is permanent (it
allows to give the exact warranties about the output precision and
-algorithm execution),
-the second one may be resolved using the Boost.Polygon functionality (<a
- href="gtl_segment_concept.htm">segment utils</a>).
+algorithm execution flow),
+the second one may be resolved using the Boost.Polygon <a
+ href="gtl_segment_concept.htm">segment utils</a>.
The strong sides of the
library and main benefits comparing to the other implementations are
discussed in the following paragraphs.<span style="font-weight: bold;"></span><br>
+ <h2>Fully Functional with Segments</h2>
+There are just a few implementations of the Voronoi diagram
+construction
+algorithm that can
+handle input data sets that contain linear segment, even considering
+the commercial
+libraries.
+Support of the
+segments allows to discretize any input geometry (sampled
+floating-point coordinates can be scaled and snapped to the integer
+grid): circle, ellipse,
+parabola. This functionality allows to compute
+the medial axis transform of the arbitrary set of input geometries,
+with direct applications in the computer vision
+projects.
<h2>Robustness and Efficiency</h2>
-Robustness issues can be divided onto two main categories: memory
+Robustness issues can be divided onto the two main categories: memory
management
-issues and numeric stability issues. Our implementation avoids the
-first type of issues using pure STL data structures, thus there is no
+issues and numeric stability issues. The implementation avoids the
+first type of the issues using pure STL data structures, thus there is
+no
presence of the new operator in the code. The second category of
-problems is
-resolved using multiprecision <a href="voronoi_predicates.htm">geometric
-predicates</a>.
-Even for commercial implementations, usage of such predicates usually
-results in a vast performance slowdown. Boost.Polygon
-Voronoi implementation overcomes this by avoiding multiprecision
-computations in 95% of the cases and
-uses efficient, floating-point based predicates. Such preciates don't
-produce the correct result always, however the library embeds <a
+the problems is
+resolved using the multiprecision geometric
+predicates.
+Even for the commercial libraries, usage of such predicates
+results in a vast performance slowdown. The Voronoi implementation
+overcomes this by avoiding the multiprecision
+computations in the 95% of the cases and
+uses the efficient, floating-point based predicates. Such preciates
+don't
+produce the correct result always, however the library embeds the <a
href="voronoi_robust_fpt.htm">relative
error arithmetic apparatus</a> to identify such situations and switch
to the
higher precision predicates when appropriate. As the result, the
implementation has a solid performance comparing to the other known
libraries (more details in the benchmarks).<br>
- <h2>Precision of the Output Structures<br>
- </h2>
-Voronoi implementation guaranties, that the relative error of the
+ <h2>Precision of the Output Structures </h2>
+The Voronoi implementation guaranties, that the relative error of the
coordinates of the output
geometries is at most 64 machine epsilons (6
bits of mantissa, for the IEEE-754 floating-point type), while on
-average it's slightly lower. This means, that precision of the output
-geometries can be increased simply by using floating-point type with
+average it's slightly lower. This means, that the precision of the
+output
+geometries can be increased simply by using a floating-point type with
the larger mantissa. The practical point of this statements is
explained in the following table:<br>
<table style="text-align: left; width: 100%;" border="1"
cellpadding="2" cellspacing="2">
<tbody>
<tr>
- <td style="vertical-align: top;">Output Coordinate Type<br>
- </td>
- <td style="vertical-align: top;">Output Coordinate Value<br>
- </td>
- <td style="vertical-align: top;">Max Absolute Error<br>
- </td>
- <td style="vertical-align: top;">Precise Value Range<br>
- </td>
+ <td style="vertical-align: top;">Output Coordinate Type </td>
+ <td style="vertical-align: top;">Output Coordinate Value </td>
+ <td style="vertical-align: top;">Max Absolute Error </td>
+ <td style="vertical-align: top;">Precise Value Range </td>
</tr>
<tr>
- <td style="vertical-align: top;">double (53 bit mantissa)<br>
- </td>
- <td style="vertical-align: top;">1<br>
- </td>
+ <td style="vertical-align: top;">double (53 bit mantissa) </td>
+ <td style="vertical-align: top;">1 </td>
<td style="vertical-align: top;">2<sup>-53</sup> * 2<sup>6</sup>
= 2<sup>-47</sup></td>
<td style="vertical-align: top;">1 ± 2<sup>-47</sup></td>
</tr>
<tr>
- <td style="vertical-align: top;">double (53 bit mantissa)<br>
- </td>
- <td style="vertical-align: top;">2<sup>31</sup><br>
- </td>
+ <td style="vertical-align: top;">double (53 bit mantissa) </td>
+ <td style="vertical-align: top;">2<sup>31</sup> </td>
<td style="vertical-align: top;">2<sup>-53</sup> * 2<sup>31</sup>
* 2<sup>6</sup> = 2<sup>-16</sup></td>
<td style="vertical-align: top;">2<sup>31</sup> ± 2<sup>-16</sup></td>
</tr>
<tr>
<td style="vertical-align: top;">long double (64 bit
-mantissa)<br>
- </td>
+mantissa)</td>
+ <td style="vertical-align: top;">1 </td>
+ <td style="vertical-align: top;">2<sup>-64</sup> * 2<sup>6</sup>
+= 2<sup>-58</sup></td>
+ <td style="vertical-align: top;">1 ± 2<sup>-58</sup></td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">long double (64 bit
+mantissa) </td>
<td style="vertical-align: top;">2<sup>31</sup></td>
<td style="vertical-align: top;">2<sup>-64</sup> * 2<sup>31</sup>
* 2<sup>6</sup> = 2<sup>-27</sup></td>
@@ -190,40 +203,27 @@
Every Computer Scientist Should Know About Floating-Point Arithmetic"</a><a
href="http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html"></a>.<br>
<br>
-During the finalization step the implementation unites Voronoi vertices
+During the finalization step the implementation unites the Voronoi
+vertices
whose both
coordinates are situated within the relative error range equal to 128
machine epsilons and removes any Voronoi edges between those. This is
the only case, that might cause differences between the algorithm
output
-topology and theoretically precise one and practically means the
+topology and theoretically precise one, and practically means the
following: for the Voronoi diagram of a set of solid bodies inside the
Solar System (radius 2<sup>42</sup> metres) and the long double (64 bit
mantissa) output coordinate type the maximum absolute error within the
Solar System rectangle will be equal to 2<sup>-64</sup> * 2<sup>42</sup>
* 2<sup>6</sup> = 2<sup>-18</sup> metres; as the result, vertices with
both coordinates that are within 2<sup>-18</sup> metres (8
-micrometres or the size of the bacteria) are going to be considered
-equal.<br>
- <h2>Fully Functional with Segments</h2>
-There are just a few implementations of the Voronoi diagram
-construction
-algorithm that can
-handle linear segment inputs, even considering the commercial
-libraries.
-Support of the
-segments allows to discretize any input geometry (sampled
-floating-point coordinates can be scaled and snapped to the integer
-grid): circle, ellipse,
-parabola. This functionality allows to compute
-the medial axis transform of the arbitrary set of input geometries,
-with direct applications in pattern recognition and computer vision
-projects.<br>
- <h2>Simple Interface<br>
- </h2>
-The main library header <span
- style="font-family: Courier New,Courier,monospace;">voronoi.hpp</span>
-defines the following static functions to integrate the Voronoi library
+micrometres or the size of a bacteria) will be considered
+equal and united.<br>
+ <h2>Simple Interface </h2>
+The boost/polygon/<a
+ href="../../../boost/polygon/voronoi.hpp">voronoi.hpp</a>
+library header defines the following static functions to integrate the
+Voronoi library
functionality with the Boost.Polygon interfaces:<br>
<br>
<table style="text-align: left; width: 100%;" border="1"
@@ -233,12 +233,10 @@
<td style="font-family: Courier New,Courier,monospace;">template
<typename Point, typename VB><br>
size_t <span style="font-weight: bold;">insert</span>(const Point
-&point, VB *vb)<br>
- </td>
+&point, VB *vb) </td>
<td>Inserts a point into the Voronoi builder data structure.<br>
Point type should model the point concept.<br>
-Returns index number of the inserted site.<br>
- </td>
+Returns index of the inserted site. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">template
@@ -248,24 +246,20 @@
PointIterator last,<br>
VB
-*vb)<br>
- </td>
+*vb) </td>
<td>Inserts an iterator range of points into the Voronoi
builder data structure.<br>
-Corresponding point type should model the point concept.<br>
- </td>
+Corresponding point type should model the point concept. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">template
<typename Segment, typename VB><br>
size_t <span style="font-weight: bold;">insert</span>(const Segment
-&segment, VB *vb)<br>
- </td>
+&segment, VB *vb) </td>
<td>Inserts a segment into the Voronoi builder data
structure.<br>
Segment type should model the segment concept.<br>
-Returns index number of the inserted site.<br>
- </td>
+Returns index of the inserted site. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">template
@@ -275,12 +269,10 @@
SegmentIterator last,<br>
VB
-*vb)<br>
- </td>
+*vb) </td>
<td>Inserts an iterator range of segments into the Voronoi
builder data structure.<br>
-Corresponding segment type should model the segment concept.<br>
- </td>
+Corresponding segment type should model the segment concept. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">template
@@ -290,11 +282,9 @@
PointIterator last,<br>
-VD *vd)<br>
- </td>
- <td>Constructs Voronoi diagram of a set of points.<br>
-Corresponding point type should model the point concept.<br>
- </td>
+VD *vd) </td>
+ <td>Constructs the Voronoi diagram of a set of points.<br>
+Corresponding point type should model the point concept. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">template
@@ -304,11 +294,9 @@
SegmentIterator last,<br>
-VD *vd)<br>
- </td>
- <td>Constructs Voronoi diagram of a set of segments.<br>
-Corresponding segment type should model the segment concept.<br>
- </td>
+VD *vd) </td>
+ <td>Constructs the Voronoi diagram of a set of segments.<br>
+Corresponding segment type should model the segment concept. </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">template
@@ -325,89 +313,92 @@
SegmentIterator s_last,<br>
-VD *vd)<br>
- </td>
- <td>Constructs Voronoi
+VD *vd) </td>
+ <td>Constructs the Voronoi
diagram of a set of points and segments.<br>
Corresponding point type should model the point concept.<br>
-Corresponding segment type should model the segment concept.<br>
- </td>
+Corresponding segment type should model the segment concept. </td>
</tr>
</tbody>
</table>
<br>
The
-following two lines of code construct Voronoi diagram of points (as
-long as corresponding input geometry type satisfies the Boost.Polygon <a
- href="gtl_design_overview.htm">concept model</a>):<br>
+following two lines of code construct the Voronoi diagram of a set of
+points (as
+long as the corresponding input geometry type satisfies the
+Boost.Polygon concept model):<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.begin(),
points.end(), &vd);</span><br>
<br>
-The library also provides the clear interfaces to <a
- href="voronoi_basic_tutorial.htm">associate user data</a> with the
-output geometries and efficiently <a href="voronoi_diagram.htm">traverse
-Voronoi graph</a>.
+The library provides the clear interfaces to associate the user data
+with the
+output geometries and efficiently traverse
+the
+Voronoi graph.
More details on those topics are covered in the <a
href="voronoi_basic_tutorial.htm">basic Voronoi tutorial</a>. 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>.
The library allows users to implement their own Voronoi diagram /
-Delaunay triangulation construction structures based on the <a
+Delaunay triangulation construction routines based on the <a
href="voronoi_builder.htm">Voronoi builder API</a>.<br>
- <h2>No Third Party Dependencies<br>
- </h2>
-The Boost.Polygon Voronoi library doesn't depend on any 3rd party code
+ <h2>No Third Party Dependencies </h2>
+The Voronoi extension of the Boost.Polygon library doesn't depend on
+any 3rd party code
and contains single dependency on the Boost libraries:
boost/cstdint.hpp.
All the required multiprecision types and related functionality are
encapsulated as
part of the implementation. The library is fast to compile (3 public
-and 4 private heades), has strong cohesion between it's components and
+and 4 private heades), has strong cohesion between its components and
is clearly modularized from the rest of the Boost.Polygon library, with
-the optional integration via the <a
+the optional integration through the <a
href="../../../boost/polygon/voronoi.hpp">voronoi.hpp</a> header.<br>
<h2>Extensible for the User Provided Coordinate Types</h2>
-The implementation is coordinate type agnostic. As soon
-as user provided types satisfy the set of restrictions of the <a
- href="voronoi_builder.htm">Voronoi builder</a> coordinate type traits
-and implement methods required by the library, no additional changes
-are required
+The implementation is coordinate type agnostic. As long
+as the user provided types satisfy the set of the requirements of the <a
+ href="voronoi_builder.htm">Voronoi builder</a> coordinate type traits,
+no additional
+changes
+are needed
neither to the algorithm, nor to the implementation of the predicates.
-Thus it's
+For example, it's
possible to
-construct Voronoi diagram for the 256-bit integer input coordinate type
+construct the Voronoi diagram with the 256-bit integer input coordinate
+type
and
512-bit output floating-point type without making any changes to the
-internal code.<br>
- <h2>Future Development<br>
- </h2>
+library.<br>
+ <h2>Future Development </h2>
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
+The high-priority tasks that already have the approximate
+implementation plan
are the following (some of those may be proposed as future GSoC
projects):<br>
<ul>
- <li>Implement Delaunay triangulation data structure.<br>
+ <li>Implement the Delaunay triangulation data structure.<br>
Note: only data structure needs to be implemented that properly
processes events provided by the Voronoi builder.</li>
- <li>Implement medial axis transform data structure.<br>
+ <li>Implement the medial axis transform data structure.<br>
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
-of this data structure is to automatically filter Voronoi edges that
+of this data structure is to automatically filter the Voronoi edges
+that
belong to those areas.</li>
- <li>Voronoi
-diagram data structure could be used to find K nearest neighbors of N
+ <li>The Voronoi
+diagram data structure can be used to find the K nearest neighbors of
+the N
sites in O(N*K*log(K) + N*log(N)) time. The return value would be a
-list of the k nearest neighbors for each site.<br>
- </li>
- <li>Using the r-tree data structure built on top of the
+list of the k nearest neighbors for each site. </li>
+ <li>Use the r-tree data structure built on top of the
bounding rectangles around the Voronoi cells to answer the nearest
neighbor queries in log(N) time, where N is the number of the Voronoi
cells.<br>
@@ -419,48 +410,48 @@
is
constructed.</li>
<li>Provide serialization utilities for the Voronoi diagram
-data structure.<br>
- </li>
+data structure. </li>
</ul>
High-priority tasks to be considered:<br>
<ul>
<li>Drop the restriction on the non-intersecting input
geometries.</li>
- <li>Integrate of the Voronoi diagram data structure with the
+ <li>Integrate the Voronoi diagram data structure with the
BGL (Boost
Graph Library).</li>
- <li>Support of the other types of distance metrics.</li>
+ <li>Support the other types of distance metrics.</li>
<li>Construction of the constrained Delaunay triangulation.</li>
<li>Support of the circular input geometries.</li>
</ul>
Based on the community suggestions priorities may be changed.<br>
- <h2>Theoretical Research<br>
- </h2>
-Voronoi
+ <h2>Theoretical Research </h2>
+The Voronoi library
was developed as part of the Google Summer of Code 2010. The
library was actively maintained for the last three years and involved
+the
strong mathematical research in the field of algorithms, data
structures,
relative error arithmetic and numerical robustness. Nowadays one can
-often read a scientific article that contains non-practical theoretical
+often read a scientific paper, that contains non-practical
+theoretical
results or implementation with
benchmarks nobody else can reproduce. The opposite story is with
-the Boost.Polygon Voronoi library. We provide pure implementation and
+the Voronoi library, that contains complete
+implementation of
+the Voronoi diagram construction algorithm 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 implementation.
+his/her PC. Upon the community request, more documentation on the
+theoretical aspects of the implementation will be published.
The
authors would like to acknowledge the 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>
+for Voronoi diagrams</a>", that covers fundamental ideas of the
+current implementation. </td>
</tr>
<tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1"
- valign="top"> </td>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1"> </td>
<td
style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
valign="top" width="100%">
@@ -469,7 +460,7 @@
class="docinfo-content"> </colgroup> <tbody valign="top">
<tr>
<th class="docinfo-name">Copyright:</th>
- <td>Copyright © Andrii Sydorchuk 2010-2012.</td>
+ <td>Copyright © Andrii Sydorchuk 2010-2013.</td>
</tr>
<tr class="field">
<th class="docinfo-name">License:</th>
==============================================================================
--- trunk/libs/polygon/doc/voronoi_robust_fpt.htm (original)
+++ trunk/libs/polygon/doc/voronoi_robust_fpt.htm 2013-04-07 19:09:31 EDT (Sun, 07 Apr 2013)
@@ -1,21 +1,22 @@
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
-<html><head>
-
-
-
-
-
-
+<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></head><body>
-<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
-
+ <meta http-equiv="Content-Type"
+ content="text/html; charset=windows-1252">
+ <title>Voronoi Robust FPT</title>
+</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>
+ <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>
@@ -26,7 +27,6 @@
<li>Interval Concept</li>
<li>Point Concept</li>
<li>Segment Concept</li>
-
<li>Rectangle Concept</li>
<li>Polygon 90 Concept</li>
<li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
@@ -51,16 +51,12 @@
<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 Main Page </li>
<li>Voronoi Benchmark</li>
- <li>Voronoi Builder<br>
- </li>
+ <li>Voronoi Builder </li>
<li>Voronoi Diagram</li>
<li>Voronoi Predicates</li>
- <li>Voronoi Robust FPT<br>
- </li>
-
+ <li>Voronoi Robust FPT </li>
</ul>
<h3 class="navbar">Other Resources</h3>
<ul>
@@ -76,130 +72,139 @@
</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>
+ <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>
-
+ <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
+robust floating-point types are the set of hidden 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 used to implement robust and efficient
-arithmetic predicates or functors that compute values within known
+assumed, that the other Boost libraries may find this unit
+functionality useful, as it can be used 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
+fpt type (robust floating-point type) 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
-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>
+error. Let's consider two values A and B, C - rounding error, re(X)
+- relative error of the X expression, then the 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;">
+<= 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;">
+<= (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;">
+<= 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;">
+<= 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
-difference type -
-represents expression wrapper that holds the positive and negative
+difference type 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.
+sums of the expression as separate values, in order to avoid
+any 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>
+-, *, / (division operator is not overloaded for the case were divisor
+has robust difference type).<br>
Looking at the relative error formulas above one may notice a few facts:<br>
1) all of the formulas evaluate upper bound of the relative error, the
-actual value could be a lot smaller;<br>
+actual value can be a lot smaller;<br>
2) relative error estimate for the expression depends on the order
operations are evaluated;<br>
-3) relative error of the difference of two positive numbers may
+3) relative error of the difference of the 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
+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>
+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>
+= 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 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>
+= re(C-B+A) = max(re(C-B), re(A)) = max(re(A), re(B)).<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
+the relative error), of course the second one is preferable. The robust
+difference type 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
-the relative error is always known for the expression result.<br>
+difference only when the result is required.<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
+the expression, that contains square roots, within known 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>
+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>
+Evaluating this expression directly may apply huge cancellation error,
+however it may be transformed to the next equivalent form:<br>
<span style="font-family: Courier New,Courier,monospace;"><br>
-(A * A * a - B * B * b) / (A * sqrt(a) + B * sqrt(b));</span><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>
+The numerator and denominator of this expression can be computed
+directly, as those won't lead to any 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>
+sum(A[i] * sqrt(a[i]), i = 1 .. N), N <= 4.</span> </td>
</tr>
<tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
- <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1"> </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">
+ <colgroup> <col class="docinfo-name"><col
+ class="docinfo-content"> </colgroup> <tbody valign="top">
<tr>
<th class="docinfo-name">Copyright:</th>
- <td>Copyright © Andrii Sydorchuk 2010-2012</td>
+ <td>Copyright © Andrii Sydorchuk 2010-2013</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">
+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>
@@ -208,5 +213,5 @@
</tr>
</tbody>
</table>
-
-</body></html>
\ No newline at end of file
+</body>
+</html>