|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r77923 - in sandbox/gtl: doc libs/polygon/example
From: sydorchuk.andriy_at_[hidden]
Date: 2012-04-11 16:33:05
Author: asydorchuk
Date: 2012-04-11 16:33:04 EDT (Wed, 11 Apr 2012)
New Revision: 77923
URL: http://svn.boost.org/trac/boost/changeset/77923
Log:
Updating documentation.
Text files modified:
sandbox/gtl/doc/voronoi_basic_tutorial.htm | 86 ++++++++++++++++++---------------------
sandbox/gtl/doc/voronoi_builder.htm | 22 ++++++---
sandbox/gtl/doc/voronoi_main.htm | 10 ++-
sandbox/gtl/libs/polygon/example/voronoi_basic_tutorial.cpp | 44 +++++++------------
4 files changed, 77 insertions(+), 85 deletions(-)
Modified: sandbox/gtl/doc/voronoi_basic_tutorial.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_basic_tutorial.htm (original)
+++ sandbox/gtl/doc/voronoi_basic_tutorial.htm 2012-04-11 16:33:04 EDT (Wed, 11 Apr 2012)
@@ -1,11 +1,9 @@
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head>
-
- <meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
- <title>Voronoi Basic Tutorial</title>
+
-</head><body>
+ <meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Voronoi Basic Tutorial</title></head><body>
<h1>Voronoi Basic Tutorial<br>
</h1>
@@ -49,41 +47,29 @@
#include "boost/polygon/voronoi.hpp"<br>
using boost::polygon;<br>
</span>
-<h2>Preparing Input Geometries</h2>
+<h2>Important</h2>
+<span style="font-family: Courier New,Courier,monospace;"></span>Voronoi diagram construction methods defined in the voronoi.hpp header
+could be used in case the following 4 requirements are satisfied:<br>
-Before executing the algorithm lets see how the user provided types for
-the input geometries might look like:<br>
+<ul>
+<li>User provided point type conforms x() and y() access methods to retrieve its coordinates;</li><li>User provided segment type conforms low() and high() access methods to retrieve its endpoints;</li><li>User provided container of points / segments supports forward iterator using the increment operator++;</li><li>User doesn't need to configure default coordinate types used by the library.</li>
+</ul>
-<br>
+For all the other case you should explicitly use Voronoi builder data structure to construct Voronoi diagram.<br>
-<span style="font-family: Courier New,Courier,monospace;">class Point {<br>
-public:<br>
- Point() {}<br>
- Point(int x, int y) { x_ = x; y_ = y; }<br>
-<br>
- // Those accessors are required!<br>
- int x() const { return x_; }<br>
- int y() const { return y_; }<br>
+<h2>Preparing Input Geometries</h2>Below is the example of how the user provided point and segment classes might look like:<br>
+<br><span style="font-family: Courier New,Courier,monospace;">struct Point {<br> int a;<br>
+ int b;<br>
<br>
-private:<br>
- // Should be castable to the signed int32 type!<br>
- int x_;<br>
- int y_;<br>
+ Point (int x, int y) : a(x), b(y) {}<br>
+
};</span><span style="font-family: Courier New,Courier,monospace;"><br>
+<br>struct Segment {<br>
+ Point p0;<br>
+ Point p1;<br>
<br>
-class Segment {<br>
-public:<br>
- Segment() {}<br>
- Segment(int x1, int y1, int x2, int y2) : p0_(x1, y1), p1_(x2,
-y2) {}<br>
-<br>
- // Those accessors are required!<br>
- Point low() const { return p0_; }<br>
- Point high() const { return p1_; }<br>
-</span><span style="font-family: Courier New,Courier,monospace;"><br>
-private:<br>
- Point p0_;<br>
- Point p1_;</span><br>
+ Segment (int x1, int y1, int x2, int y2) : p0(x1, y1), p1(x2, y2) {}<br>
+</span><span style="font-family: Courier New,Courier,monospace;"></span>
<span style="font-family: Courier New,Courier,monospace;">};<br>
<br>
@@ -100,16 +86,27 @@
segments.push_back(Segment(3, -11, 13, -1));</span><span style="font-family: Courier New,Courier,monospace;"><br>
</span>
<h2>Construction of the Voronoi Diagram<br>
-</h2>
-
-Now let's construct the Voronoi diagram of the input set of points and
-segments:<br>
-
+</h2>As one may notice the user provided Point and Segment class
+doesn't conform to the interfaces supported by the static methods in
+the voronoi.hpp header, that's why we are going to use Voronoi builder
+data structure:<br>
<br>
+<span style="font-family: Courier New,Courier,monospace;">voronoi_builder<int> vb;</span><br>
<span style="font-family: Courier New,Courier,monospace;">voronoi_diagram<double>
vd;<br>
+for (</span><span style="font-family: Courier New,Courier,monospace;">std::vector<Point>::iterator it = points.begin(); it != points.end(); ++it)<br>
+ vb.insert_point(it->a, it->b);<br>
+for (std::vector<Segment>::iterator it = segments.begin(); it != segments.end(); ++it)<br>
+ vb.insert_segment(it->p0.a, it->p0.b, it->p1.a, it->p1.b);<br>
+</span><span style="font-family: Courier New,Courier,monospace;">vb.construct(&vd);<br>
+<br>
+</span>In case all the requirements of the <span style="font-weight: bold;">Important</span> section are satisfied the code would look like:<br>
+<br>
+<span style="font-family: Courier New,Courier,monospace;">voronoi_diagram<double>
+vd;<br>
construct_voronoi(points, segments, &vd);<br>
+</span><span style="font-family: Courier New,Courier,monospace;">
<br>
</span>So brief, isn't that awesome!<br>
@@ -267,14 +264,11 @@
plus some offset.<br>
<span style="font-family: Courier New,Courier,monospace;"><br>
-bounding_rectangle<double> bbox;<br>
-for (std::vector<Point>::iterator it = points.begin(); it !=
-points.end(); ++it)<br>
- bbox.update(it->x(), it->y());<br>
-for (std::vector<Segment>::iterator it = segments.begin(); it !=
-segments.end(); ++it) {<br>
- bbox.update(it->low().x(), it->low().y());<br>
- bbox.update(it->high().x(), it->high().y());<br>
+bounding_rectangle<double> bbox;<br>for (std::vector<Point>::iterator it = points.begin(); it != points.end(); ++it)<br>
+ bbox.update(it->a, it->b);<br>
+for (std::vector<Segment>::iterator it = segments.begin(); it != segments.end(); ++it) {<br>
+ bbox.update(it->p0.a, it->p0.b);<br>
+ bbox.update(it->p1.a, it->p1.b);<br>
}<br>
// Add 10% offset to the bounding rectangle.<br>
bbox = voronoi_utils<double>::scale(bbox, 1.1);</span><span style="font-family: Courier New,Courier,monospace;"><br>
Modified: sandbox/gtl/doc/voronoi_builder.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_builder.htm (original)
+++ sandbox/gtl/doc/voronoi_builder.htm 2012-04-11 16:33:04 EDT (Wed, 11 Apr 2012)
@@ -1,19 +1,16 @@
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head>
-
- <meta http-equiv="Content-Language" content="en-us">
- <meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
- <title>Voronoi Builder</title>
+ <meta http-equiv="Content-Language" content="en-us">
-</head><body>
+ <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">
+ <td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1">
<div style="padding: 5px;" align="center"> <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/"> </a></div>
<div style="margin: 5px;">
<h3 class="navbar">Contents</h3>
@@ -80,7 +77,7 @@
<h1>Voronoi Builder<br>
</h1>
-Voronoi builder is event generator structure. It implements <a href="http://www.ams.org/samplings/feature-column/fcarc-voronoi">sweepline
+Voronoi builder is the event generator structure. It implements the <a href="http://www.ams.org/samplings/feature-column/fcarc-voronoi">sweepline
algorithm</a> that scans 2D space and generates two types of events:
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.
@@ -125,6 +122,15 @@
implementation is highly optimized and efficient that's why it's always
better to come up with a proper <font face="Courier New"> <span style="font-family: 'Courier New',Courier,monospace;">CTT</span></font>
structure.<br>
+ <h2>Important</h2>
+We encourage users to use default static methods defined in the voronoi.hpp header to construct Voronoi diagram. However in the following cases Voronoi builder data structure should be used explicitly:<br>
+ <ul>
+ <li>User provided point type doesn't conform x() and y() access methods to retrieve its coordinates;</li>
+ <li>User provided segment type doesn't conforms low() and high() access methods to retrieve its endpoints;</li>
+ <li>User provided container of points / segments doesn't support forward iterator using the increment operator++;</li>
+ <li>User needs to configure coordinate type domain or predicates the library operates with.</li>
+ </ul>
+
<h2>Member Functions</h2>
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
<tbody>
@@ -392,7 +398,7 @@
</td>
</tr>
<tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
+ <td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1"> </td>
<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
<table class="docinfo" id="table2" frame="void" rules="none">
<colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> <tbody valign="top">
Modified: sandbox/gtl/doc/voronoi_main.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_main.htm (original)
+++ sandbox/gtl/doc/voronoi_main.htm 2012-04-11 16:33:04 EDT (Wed, 11 Apr 2012)
@@ -1,6 +1,8 @@
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head>
+
+
<meta http-equiv="Content-Language" content="en-us">
@@ -21,7 +23,7 @@
<tbody>
<tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ <td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1">
<div style="padding: 5px;" align="center"> <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/"> </a></div>
<div style="margin: 5px;">
<h3 class="navbar">Contents</h3>
@@ -194,7 +196,7 @@
project.<br>
<h2>Basic and Advanced Usage Cases</h2>
The main library header <span style="font-family: Courier New,Courier,monospace;">voronoi.hpp</span>
-defines following static functions:<br>
+defines the following static functions:<br>
<br>
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
<tbody>
@@ -245,7 +247,7 @@
For the users that don't want to go into the details of the library
this
means that it's possible to construct the Voronoi diagram with the
-following two lines of code:<br>
+following two lines of code (if this doesn't work for you read Voronoi builder documentation page):<br>
<br>
<span style="font-family: Courier New,Courier,monospace;">voronoi_diagram<double>
vd;</span><br style="font-family: Courier New,Courier,monospace;">
@@ -346,7 +348,7 @@
</td>
</tr>
<tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
+ <td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1"> </td>
<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
<table class="docinfo" id="table2" frame="void" rules="none">
<colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> <tbody valign="top">
Modified: sandbox/gtl/libs/polygon/example/voronoi_basic_tutorial.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/example/voronoi_basic_tutorial.cpp (original)
+++ sandbox/gtl/libs/polygon/example/voronoi_basic_tutorial.cpp 2012-04-11 16:33:04 EDT (Wed, 11 Apr 2012)
@@ -14,33 +14,18 @@
#include "boost/polygon/voronoi_utils.hpp"
using namespace boost::polygon;
-class Point {
-public:
- Point() {}
- Point(int x, int y) { x_ = x; y_ = y; }
-
- // Those accessors are required!
- int x() const { return x_; }
- int y() const { return y_; }
-
-private:
- // Should be castable to the signed int32 type!
- int x_;
- int y_;
-};
+struct Point {
+ int a;
+ int b;
-class Segment {
-public:
- Segment() {}
- Segment(int x1, int y1, int x2, int y2) : p0(x1, y1), p1(x2, y2) {}
-
- // Those accessors are required!
- Point low() const { return p0; }
- Point high() const { return p1; }
+ Point (int x, int y) : a(x), b(y) {}
+};
-private:
+struct Segment {
Point p0;
Point p1;
+
+ Segment (int x1, int y1, int x2, int y2) : p0(x1, y1), p1(x2, y2) {}
};
// Traversing Voronoi edges using edge iterator.
@@ -130,8 +115,13 @@
segments.push_back(Segment(3, -11, 13, -1));
// Construction of the Voronoi Diagram.
+ voronoi_builder<int> vb;
voronoi_diagram<double> vd;
- construct_voronoi(points, segments, &vd);
+ for (std::vector<Point>::iterator it = points.begin(); it != points.end(); ++it)
+ vb.insert_point(it->a, it->b);
+ for (std::vector<Segment>::iterator it = segments.begin(); it != segments.end(); ++it)
+ vb.insert_segment(it->p0.a, it->p0.b, it->p1.a, it->p1.b);
+ vb.construct(&vd);
// Traversing Voronoi Graph.
{
@@ -176,10 +166,10 @@
// Construct clipping bounding rectangle.
bounding_rectangle<double> bbox;
for (std::vector<Point>::iterator it = points.begin(); it != points.end(); ++it)
- bbox.update(it->x(), it->y());
+ bbox.update(it->a, it->b);
for (std::vector<Segment>::iterator it = segments.begin(); it != segments.end(); ++it) {
- bbox.update(it->low().x(), it->low().y());
- bbox.update(it->high().x(), it->high().y());
+ bbox.update(it->p0.a, it->p0.b);
+ bbox.update(it->p1.a, it->p1.b);
}
// Add 10% offset to the bounding rectangle.
bbox = voronoi_utils<double>::scale(bbox, 1.1);
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