|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r77978 - in sandbox/gtl: boost/polygon doc libs/polygon/benchmark libs/polygon/example libs/polygon/test
From: sydorchuk.andriy_at_[hidden]
Date: 2012-04-14 16:37:31
Author: asydorchuk
Date: 2012-04-14 16:37:29 EDT (Sat, 14 Apr 2012)
New Revision: 77978
URL: http://svn.boost.org/trac/boost/changeset/77978
Log:
Moving all the MPL dependencies to the voronoi.hpp. Library is again self-contained. Hooray!!!
Text files modified:
sandbox/gtl/boost/polygon/voronoi.hpp | 56 +++++++++++---
sandbox/gtl/boost/polygon/voronoi_builder.hpp | 37 ---------
sandbox/gtl/doc/voronoi_basic_tutorial.htm | 77 ++++++++++---------
sandbox/gtl/doc/voronoi_builder.htm | 149 +++++++++++----------------------------
sandbox/gtl/doc/voronoi_main.htm | 123 +++++++++++++++++++-------------
sandbox/gtl/doc/voronoi_utils.htm | 7 +
sandbox/gtl/libs/polygon/benchmark/voronoi_benchmark_segments.cpp | 2
sandbox/gtl/libs/polygon/example/voronoi_advanced_tutorial.cpp | 2
sandbox/gtl/libs/polygon/example/voronoi_basic_tutorial.cpp | 40 ++++++++--
sandbox/gtl/libs/polygon/example/voronoi_visualizer.cpp | 3
sandbox/gtl/libs/polygon/test/voronoi_benchmark_test.cpp | 6
sandbox/gtl/libs/polygon/test/voronoi_builder_test.cpp | 48 ++++++------
12 files changed, 264 insertions(+), 286 deletions(-)
Modified: sandbox/gtl/boost/polygon/voronoi.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi.hpp 2012-04-14 16:37:29 EDT (Sat, 14 Apr 2012)
@@ -10,6 +10,7 @@
#ifndef BOOST_POLYGON_VORONOI
#define BOOST_POLYGON_VORONOI
+#include "polygon.hpp"
#include "voronoi_builder.hpp"
#include "voronoi_diagram.hpp"
@@ -28,27 +29,58 @@
namespace boost {
namespace polygon {
-template <typename PC, typename VD>
-static inline void construct_voronoi(const PC &points, VD *output,
- typename enable_if<typename gtl_if<typename is_point_concept<typename geometry_concept<typename PC::value_type>::type>::type>::type>::type * = 0) {
+template <typename Point, typename VB>
+static inline void insert(const Point &point, VB &vb,
+ typename enable_if<typename gtl_if<typename is_point_concept<typename geometry_concept<Point>::type>::type>::type>::type * = 0) {
+ vb.insert_point(x(point), y(point));
+}
+
+template <typename PointIterator, typename VB>
+static inline void insert(PointIterator first, const PointIterator last, VB &vb,
+ typename enable_if<typename gtl_if<typename is_point_concept<typename geometry_concept<typename std::iterator_traits<PointIterator>::value_type>::type>::type>::type>::type * = 0) {
+ for (PointIterator it = first; it != last; ++it) {
+ insert(*it, vb);
+ }
+}
+
+template <typename Segment, typename VB>
+static inline void insert(const Segment &segment, VB &vb,
+ typename enable_if<typename gtl_if<typename is_directed_line_segment_concept<typename geometry_concept<Segment>::type>::type>::type>::type * = 0) {
+ vb.insert_segment(x(low(segment)), y(low(segment)), x(high(segment)), y(high(segment)));
+}
+
+template <typename SegmentIterator, typename VB>
+static inline void insert(SegmentIterator first, SegmentIterator last, VB &vb,
+ typename enable_if<typename gtl_if<typename is_directed_line_segment_concept<typename geometry_concept<typename std::iterator_traits<SegmentIterator>::value_type>::type>::type>::type>::type * = 0) {
+ for (SegmentIterator it = first; it != last; ++it) {
+ insert(*it, vb);
+ }
+}
+
+template <typename PointIterator, typename VD>
+static inline void construct_voronoi(PointIterator first, PointIterator last, VD *output,
+ typename enable_if<typename gtl_if<typename is_point_concept<typename geometry_concept<typename std::iterator_traits<PointIterator>::value_type>::type>::type>::type>::type * = 0) {
default_voronoi_builder builder;
- builder.insert(points.begin(), points.end());
+ insert(first, last, builder);
builder.construct(output);
}
-template <typename SC, typename VD>
-static inline void construct_voronoi_segments(const SC &segments, VD *output) {
+template <typename SegmentIterator, typename VD>
+static inline void construct_voronoi(SegmentIterator first, SegmentIterator last, VD *output,
+ typename enable_if<typename gtl_if<typename is_directed_line_segment_concept<typename geometry_concept<typename std::iterator_traits<SegmentIterator>::value_type>::type>::type>::type>::type * = 0) {
default_voronoi_builder builder;
- builder.insert_segments(segments.begin(), segments.end());
+ insert(first, last, builder);
builder.construct(output);
}
-template <typename PC, typename SC, typename VD>
-static inline void construct_voronoi(const PC &points, const SC &segments, VD *output,
- typename enable_if<typename gtl_if<typename is_point_concept<typename geometry_concept<typename PC::value_type>::type>::type>::type>::type * = 0) {
+template <typename PointIterator, typename SegmentIterator, typename VD>
+static inline void construct_voronoi(
+ PointIterator p_first, PointIterator p_last, SegmentIterator s_first, SegmentIterator s_last, VD *output,
+ typename enable_if<typename gtl_if<typename is_point_concept<typename geometry_concept<typename std::iterator_traits<PointIterator>::value_type>::type>::type>::type>::type * = 0,
+ typename enable_if<typename gtl_if<typename is_directed_line_segment_concept<typename geometry_concept<typename std::iterator_traits<SegmentIterator>::value_type>::type>::type>::type>::type * = 0) {
default_voronoi_builder builder;
- builder.insert(points.begin(), points.end());
- builder.insert_segments(segments.begin(), segments.end());
+ insert(p_first, p_last, builder);
+ insert(s_first, s_last, builder);
builder.construct(output);
}
} // polygon
Modified: sandbox/gtl/boost/polygon/voronoi_builder.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi_builder.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi_builder.hpp 2012-04-14 16:37:29 EDT (Sat, 14 Apr 2012)
@@ -14,8 +14,6 @@
#include <map>
#include <vector>
-#include "isotropy.hpp"
-#include "point_concept.hpp"
#include "detail/voronoi_ctypes.hpp"
#include "detail/voronoi_predicates.hpp"
#include "detail/voronoi_structures.hpp"
@@ -49,25 +47,11 @@
voronoi_builder() {}
+ // Each point creates a single site event.
void insert_point(const int_type& x, const int_type& y) {
site_events_.push_back(site_event_type(x, y));
}
- template <typename PointType>
- void insert(const PointType& point,
- typename enable_if<typename gtl_if<typename is_point_concept<typename geometry_concept<PointType>::type>::type>::type>::type * = 0) {
- insert_point(x(point), y(point));
- }
-
- template <typename PointIterator>
- void insert(PointIterator first_point, PointIterator last_point,
- typename enable_if<typename gtl_if<typename is_point_concept<typename geometry_concept<typename std::iterator_traits<PointIterator>::value_type>::type>::type>::type>::type * = 0) {
- // Create a site event from each input point.
- for (PointIterator it = first_point; it != last_point; ++it) {
- insert(*it);
- }
- }
-
// Each segment creates three site events that correspond to:
// 1) the start point of the segment;
// 2) the end point of the segment;
@@ -85,25 +69,6 @@
}
}
- template <typename PointType>
- void insert_segment(const PointType& point1, const PointType& point2,
- typename enable_if<typename gtl_if<typename is_point_concept<typename geometry_concept<PointType>::type>::type>::type>::type * = 0) {
- insert_segment(x(point1), y(point1), x(point2), y(point2));
- }
-
- template <typename SegmentType>
- void insert_segment(const SegmentType& segment) {
- insert_segment(segment.low(), segment.high());
- }
-
- template <typename SegmentIterator>
- void insert_segments(
- SegmentIterator first_segment, SegmentIterator last_segment) {
- for (SegmentIterator it = first_segment; it != last_segment; ++it) {
- insert_segment(*it);
- }
- }
-
// Run sweepline algorithm and fill output data structure.
template <typename OUTPUT>
void construct(OUTPUT *output) {
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-14 16:37:29 EDT (Sat, 14 Apr 2012)
@@ -2,8 +2,11 @@
<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><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body>
<h1>Voronoi Basic Tutorial<br>
</h1>
@@ -45,35 +48,51 @@
And before you proceed don't forget to:<span style="font-family: Courier New,Courier,monospace;"><br>
<br>
#include "boost/polygon/voronoi.hpp"<br>
-using boost::polygon;<br>
-</span>
-<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>
-
-<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>
-
-For all the other case you should explicitly use Voronoi builder data structure to construct Voronoi diagram.<br>
+using boost::polygon;</span><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>
Point (int x, int y) : a(x), b(y) {}<br>
};</span><span style="font-family: Courier New,Courier,monospace;"><br>
<br>struct Segment {<br>
+ typedef int coordinate_type; // this is temporary required</span><span style="font-family: Courier New,Courier,monospace;"></span><br>
+<span style="font-family: Courier New,Courier,monospace;">
Point p0;<br>
Point p1;<br>
-<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>
-</span>Once those are declared we can create the sample input:<br>
+</span>As we are going to use default routines defined in the
+voronoi.hpp header to construct Voronoi diagram, we are required to map
+our point and segment class to the corresponding Boost.Polygon concepts:<br>
+<br>
+<span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">template <></span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"><br>
+struct geometry_concept<Point> { typedef point_concept type; };</span><br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium;"><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"></span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! imp
ortant; float: none;"> <span class="Apple-converted-space"></span></span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"></span><br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium;"><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inli
ne ! important; float: none;">template <></span><br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium;"><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">struct point_traits<</span><span style="font-family: Courier New,Courier,monospace;">Point</span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal;
widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">> {</span><br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium;"><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"> typedef int coordinate_type;</span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows:
2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"><br>
+ <span class="Apple-converted-space"> </span></span><br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium;"><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"> static inline coordinate_type get(const </span><span style="font-family: Courier New,Courier,monospace;">Point</span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-tra
nsform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">& point,<span class="Apple-converted-space"> </span></span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">orientation_2d orient) {<br>
+ return </span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">(orient == HORIZONTAL) ? point.a : point.b;</span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"></span><br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spaci
ng: 0px; font-size: medium;"><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"> }<br>
+};</span><br>
+<span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">
+<br>
+template <><br>
+</span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">struct geometry_concept<Segment> { typedef directed_line_segment_concept type; };<br>
+<br>
+</span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">template <></span><br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium;">
+<span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">struct point_traits<</span><span style="font-family: Courier New,Courier,monospace;">Segment</span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">> {</span><br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: norm
al; widows: 2; word-spacing: 0px; font-size: medium;">
+<span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"> typedef int coordinate_type;<br>
+ typedef Point point_type;<br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium;">
+</span>
+<span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"> <span class="Apple-converted-space"> </span></span><br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium;">
+<span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"> static inline coordinate_type get(const </span><span style="font-family: Courier New,Courier,monospace;">Segment</span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">& segment,<span class="Apple-converted-space"> direction_1d dir</span></span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: norm
al; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">) {<br>
+ return </span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;">dir.to_int() ? segment.p1() : segment.p0();</span><span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"></span><br style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spaci
ng: 0px; font-size: medium;">
+<span style="color: rgb(0, 0, 0); font-family: 'Courier New'; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; font-size: medium; display: inline ! important; float: none;"> }<br>};</span><br>
+<br>
+It's also possible to use native Boost.Polygon types as point_data and directed_line_segment_data, that won't require the above mapping.<br>
+<br>
+So once we are done we can create the sample input:<br>
<br>
@@ -86,29 +105,13 @@
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>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>
+</h2>At this point we are ready to construct Voronoi diagram:<br>
+<span style="font-family: Courier New,Courier,monospace;"><br>
</span><span style="font-family: Courier New,Courier,monospace;">
-<br>
-</span>So brief, isn't that awesome!<br>
+voronoi_diagram<double> vd;<br>
+construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &vd);<br>
+</span><br>
+So brief, isn't that awesome!<br>
<h2>Traversing Voronoi Graph</h2>
Modified: sandbox/gtl/doc/voronoi_builder.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_builder.htm (original)
+++ sandbox/gtl/doc/voronoi_builder.htm 2012-04-14 16:37:29 EDT (Sat, 14 Apr 2012)
@@ -3,6 +3,7 @@
+
<meta http-equiv="Content-Language" content="en-us">
@@ -12,7 +13,7 @@
<tbody>
<tr>
- <td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1">
+ <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>
@@ -90,14 +91,38 @@
and linear segments. The requirements for the input/output
coordinate types of
the builder geometries are not the same as for the rest of the
-Boost.Polygon library. The main differences are in the following: 1)
-The input coordinate type is not required to be integral (while it
-still should be integer type); 2) The output coordinate type (for
-Voronoi vertices) is required to be IEEE-754 floating point type. Let's
-have a closer look at the voronoi_builder declaration:<br>
+Boost.Polygon library. The main differences are in the following:<br>
+ <ul>
+ <li>The input coordinate type is not required to be integral (while it
+still should be 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
+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 external headers even
+Boost.Polygon itself:<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><br style="font-family: Courier New,Courier,monospace;">
+
+ <span style="font-family: Courier New,Courier,monospace;">#include <voronoi_utils.hpp><br>
+ <br>
+ </span>This also allows to build Voronoi construction APIs on top of the Voronoi builder data strcture.<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;">
<span style="font-family: 'Courier New',Courier,monospace;">
@@ -127,18 +152,7 @@
satisfy the requirements explained in the end of this page. In case those
requirements are not satisfied for the user provided <font face="Courier New"> <span style="font-family: 'Courier New',Courier,monospace;">CTT</span></font>,
proper <font face="Courier New"> <span style="font-family: 'Courier New',Courier,monospace;">VP</span></font>
-implementation is required.<br>
- <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
-use Voronoi builder explicitly. The geometry types inserted into the
-builder should model apropriate Boost.Polygon concepts (e.g. point concept, segment concept). If it's too complicated for the user to follow the concept principles there are two solutions:<br>
-
-
- <ul>
-<li>use Voronoi builder insertion methods, that accept geometry coordinates</li><li>use Boost.Polygon native classes (e.g. point_data), that already model appropriate concepts</li>
- </ul>
+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>
@@ -155,102 +169,21 @@
the specified coordinates into the Voronoi builder.
</td>
</tr>
- <tr>
- <td style="vertical-align: top;"><span style="font-family: Courier New,Courier,monospace;">template
-<typename PointType></span><br style="font-family: Courier New,Courier,monospace;">
- <span style="font-family: Courier New,Courier,monospace;">void
-insert(const PointType& point)</span><br>
- </td>
- <td style="vertical-align: top;">Inserts a point object into
-the Voronoi builder.<br>
-
-Point object should be a model of the point concept.
- </td>
- </tr>
- <tr>
- <td style="font-family: 'Courier New',Courier,monospace;">
-template <typename PointIterator><br>
-void insert(PointIterator first_point, PointIterator last_point)<br>
- </td>
- <td style="vertical-align: top;" width="693">Inserts point
-objects into the Voronoi builder.<br>
-
-Point object should be a model of the point concept.
- </td>
- </tr>
+
+
<tr>
<td style="vertical-align: top;"><span style="font-family: Courier New,Courier,monospace;">void
-insert_segment(<br>
- const int_type& x1,<br>
- const int_type& y1,<br>
- const int_type& x2,<br>
- const int_type& y2)</span><br>
+insert_segment(const int_type& x1, const int_type& y1,<br>
+const int_type& x2, const int_type& y2)</span><br>
</td>
<td style="vertical-align: top;">Inserts a segment object
with the specified coordinates into the Voronoi builder.
</td>
</tr>
- <tr>
- <td style="vertical-align: top;"><span style="font-family: Courier New,Courier,monospace;">template
-<typename PointType></span><span style="font-family: Courier New,Courier,monospace;"><br>
-void insert_segment(<br>
- const PointType& point1,<br>
- const PointType& point2)</span><br>
- </td>
- <td style="vertical-align: top;">Inserts a segment object defined by its endpoints into the Voronoi builder.<br>
-Endpoint object should support x() and y() methods to retrieve its
-coordinates.<br>
-This method is depricated and will be replaced soon to support point concept.<br>
- </td>
- </tr>
- <tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template
-<typename SegmentType><br>
-void insert_segment(const SegmentType& segment)<br>
- </td>
- <td style="vertical-align: top;">Inserts a segment object
-into the Voronoi builder.<br>
-Segment object should support low() and high() methods to retrieve its
-endpoints.<br>
-Endpoint object should support x() and y() methods to retrieve its
-coordinates.<br>
-This method is depricated and will be replaced soon to support point/segment concept.<br>
- </td>
- </tr>
- <tr>
- <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace;">
-template <typename SegmentIterator><br>
-void insert_segments(SegmentIterator first_segment, SegmentIterator
-last_segment)<br>
- </td>
- <td style="vertical-align: top;" width="693">Inserts
-segment objects into the Voronoi builder.<br>
-Segment object should support low() and high() methods to retrieve its
-endpoints.<br>
-Endpoint object should support x() and y() methods to retrieve its
-coordinates.<br>
-This method is depricated and will be replaced soon to support point/segment concept.<br>
- </td>
- </tr>
- <tr>
- <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace;">
-template <typename PointIterator, typename SegmentIterator><br>
-void insert_sites(<br>
- PointIterator first_point,<br>
- PointIterator last_point,<br>
- SegmentIterator first_segment,<br>
- SegmentIterator last_segment)<br>
- </td>
- <td style="vertical-align: top;" width="693">Inserts point
-and segment objects into Voronoi builder.<br>
-
-Segment object should support low() and high() methods to retrieve its
-endpoints.<br>
-
-Endpoint object should support x() and y() methods to retrieve its
-coordinates.<br>This method is depricated and will be replaced soon to support point/segment concept.<br>
- </td>
- </tr>
+
+
+
+
<tr>
<td style="vertical-align: top; font-family: 'Courier New',Courier,monospace;">
template <typename OUTPUT><br>
@@ -418,7 +351,7 @@
</td>
</tr>
<tr>
- <td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1"> </td>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
<table class="docinfo" id="table2" frame="void" rules="none">
<colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> <tbody valign="top">
Modified: sandbox/gtl/doc/voronoi_main.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_main.htm (original)
+++ sandbox/gtl/doc/voronoi_main.htm 2012-04-14 16:37:29 EDT (Sat, 14 Apr 2012)
@@ -5,6 +5,9 @@
+
+
+
<meta http-equiv="Content-Language" content="en-us">
@@ -20,12 +23,12 @@
<meta http-equiv="content-type" content="text/html; charset=utf-8">
- <meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body>
+ <meta http-equiv="content-type" content="text/html; charset=utf-8"><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);" valign="top" nowrap="1">
+ <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>
@@ -198,66 +201,76 @@
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 the following static functions:<br>
+defines the following static functions to integrate Voronoi library functionality with the Boost.Polygon interfaces:<br>
<br>
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
<tbody>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template
-<typename PC, typename VD><br>
-static inline void construct_voronoi(<br>
- const PC &points, VD *output)<br>
- </td>
- <td style="vertical-align: top;">Constructs Voronoi diagram of a set of points.<br>
-Coordinates of the input geometries should belong to the [-2^31,
-2^31-1] integer range.<br>
-PC is a container of points that model point concept.<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template <typename Point, typename VB><br>
+void insert(const Point &point, VB &vb)<br>
+ </td>
+ <td style="vertical-align: top;">Inserts a point into the Voronoi builder data structure.<br>
+Point type should model point concept.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template <typename PointIterator, typename VB><br>
+void insert(PointIterator first, const PointIterator last, VB &vb)<br>
+ </td>
+ <td style="vertical-align: top;">Inserts an iterator range of points into the Voronoi builder data structure.<br>
+Corresponding point type should model point concept.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template <typename Segment, typename VB><br>
+void insert(const Segment &segment, VB &vb)<br>
+ </td>
+ <td style="vertical-align: top;">Inserts a segment into the Voronoi builder data structure.<br>
+Segment type should model segment concept.<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template <typename SegmentIterator, typename VB><br>
+void insert(SegmentIterator first, SegmentIterator last, VB &vb)<br>
+ </td>
+ <td style="vertical-align: top;">Inserts an iterator range of segments into the Voronoi builder data structure.<br>
+Corresponding segment type should model segment concept.<br>
+ </td>
+ </tr>
+<tr>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template <typename PointIterator, typename VD><br>
+void construct_voronoi(PointIterator first, PointIterator last, VD *output)<br>
+ </td>
+ <td style="vertical-align: top;">Constructs Voronoi diagram of a set of points.<br>Corresponding point type should model point concept.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template
-<typename SC, typename VD><br>
-static inline void construct_voronoi_segments(<br>
- const SC &segments, VD *output)<br>
- </td>
- <td style="vertical-align: top;">Constructs Voronoi diagram of a set of segments.<br>
-Coordinates of the input geometries should belong to the [-2^31,
-2^31-1] integer range.<br>
-SC is a container of segments that supports forward iterator.<br>
-Segment object should provide low(), high() public methods to retrieve
-endpoints of a segment.<br>
-This method is deprecated and will be changed to the concept model the first method conforms.<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template <typename SegmentIterator, typename VD><br>
+void construct_voronoi(SegmentIterator first, SegmentIterator last, VD *output)<br>
+ </td>
+ <td style="vertical-align: top;">Constructs Voronoi diagram of a set of segments.<br>Corresponding segment type should model segment concept.<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template
-<typename PC, typename SC, typename VD><br>
-static inline void construct_voronoi(<br>
- const PC &points, const SC &segments, VD
-*output)<br>
+ <td style="vertical-align: top; font-family: Courier New,Courier,monospace;">template <typename PointIterator, typename SegmentIterator, typename VD><br>
+static inline void construct_voronoi(PointIterator p_first, PointIterator p_last,<br>
+
+SegmentIterator s_first, SegmentIterator s_last, VD *output)<br>
</td>
<td style="vertical-align: top;">Constructs Voronoi
-diagram of a set of points and segments.<br>
-Coordinates of the input geometries should belong to the [-2^31,
-2^31-1] integer range.<br>
-
-Segment object should provide low(), high() public methods to retrieve
-endpoints of a segment.<br>
-This method is depricated and will be changed to the concept model the first method conforms.<br>
+diagram of a set of points and segments.<br>Corresponding point type should model point concept.<br>
+Corresponding segment type should model segment concept.<br>
</td>
</tr>
</tbody>
</table>
- <br>
-For the users that don't want to go into the details of the library
-this
+ <br>This
means that it's possible to construct Voronoi diagram with the
-following two lines of code (if this doesn't work for you read Voronoi builder documentation page):<br>
+following two lines of code (if corresponding input types satisfy 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,
-segments, &vd);</span><br>
+ <span style="font-family: Courier New,Courier,monospace;">construct_voronoi(points.begin(), points.end(), &vd);</span><br>
<br>
Isn't that simple? The library also provides the clear interfaces to
<a href="voronoi_basic_tutorial.htm">associate user data</a> with the output geometries, efficiently <a href="voronoi_diagram.htm">traverse Voronoi graph</a> and utilities to
@@ -265,13 +278,20 @@
discretization of the parabolic edges, clipping of the linear edges).
More details on those are covered in the basic Voronoi tutorial. Advanced usage of the library with the configuration of the coordinate
types is explained in the <a href="voronoi_advanced_tutorial.htm">advanced
-Voronoi tutorial</a>.<br>
+Voronoi tutorial</a>.
+The library also allows users to implement their own Voronoi diagram /
+Delaunay triangulation construction routines based on the Voronoi builder API, that doesn't depend on any external code.<br>
<h2>No Third Party Dependencies<br>
- </h2>
-Yes, the library doesn't depend on any 3rd party code. The code depends only on the Boost libraries and STL.
+ </h2>Yes,
+the library doesn't depend on any 3rd party code. Even more than that
+there is only one dependency on the Boost libraries: boost/cstdint.hpp.
All the required multiprecision types functionality is implemented as
-part of the library and is not exposed to the user.<br>
- <h2>Extensible for the User Provided Coordinate Types</h2>
+part of the library and is not exposed to the user. Considering the
+fact that Voronoi implementation consists of just 7 headers (3 public
+and 4 private) it is easy to compile it within a minute after download.
+On the other hand voronoi.hpp header provides integration routines with
+the Boost.Polygon concepts and models with a drawback of additional
+dependencies. <h2>Extensible for the User Provided Coordinate Types</h2>
Our implementation is coordinate type agnostic. That means that as soon
as user provides types that satisfy set of restrictions of the Voronoi builder coordinate type traits
and implements the library required methods no changes are required
@@ -315,9 +335,7 @@
points and segments from the Voronoi builder once the Voronoi diagram is
constructed in O(N) time.<br>
</li>
- <li>Closer integration with the interfaces and functionality of
-the Boost Polygon Library.<br>
- </li>
+
</ul>
High-priority tasks to be considered:<br>
<ul>
@@ -350,13 +368,13 @@
</td>
</tr>
<tr>
- <td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1"> </td>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
<table class="docinfo" id="table2" frame="void" rules="none">
<colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> <tbody valign="top">
<tr>
<th class="docinfo-name">Copyright:</th>
- <td>Copyright © Intel Corporation 2008-2010.</td>
+ <td>Copyright \A9 Intel Corporation 2008-2010.</td>
</tr>
<tr class="field">
<th class="docinfo-name">License:</th>
@@ -371,4 +389,5 @@
</tbody>
</table>
+
</body></html>
\ No newline at end of file
Modified: sandbox/gtl/doc/voronoi_utils.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_utils.htm (original)
+++ sandbox/gtl/doc/voronoi_utils.htm 2012-04-14 16:37:29 EDT (Sat, 14 Apr 2012)
@@ -1,6 +1,7 @@
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head>
+
<meta http-equiv="Content-Language" content="en-us">
@@ -18,7 +19,7 @@
<tbody>
<tr>
- <td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1">
+ <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>
@@ -168,7 +169,7 @@
<h2 style="color: rgb(0, 0, 0); font-family: 'Times New Roman'; font-style: normal; font-variant: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px;">Member Types</h2>
- <br>
+
<table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
<tbody>
<tr>
@@ -350,7 +351,7 @@
</td>
</tr>
<tr>
- <td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1"> </td>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
<table class="docinfo" id="table2" frame="void" rules="none">
<colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> <tbody valign="top">
Modified: sandbox/gtl/libs/polygon/benchmark/voronoi_benchmark_segments.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/benchmark/voronoi_benchmark_segments.cpp (original)
+++ sandbox/gtl/libs/polygon/benchmark/voronoi_benchmark_segments.cpp 2012-04-14 16:37:29 EDT (Sat, 14 Apr 2012)
@@ -97,7 +97,7 @@
POINT_POLYGON(x1, y1), POINT_POLYGON(x1 + dx, y1 + dy)));
}
ssd.clean();
- boost::polygon::construct_voronoi_segments(ssd, &vd);
+ boost::polygon::construct_voronoi(ssd.begin(), ssd.end(), &vd);
}
double time_per_test = (timer.elapsed() - running_times[i]) / NUM_RUNS[i];
format_line(NUM_SEGMENTS[i], NUM_RUNS[i], time_per_test);
Modified: sandbox/gtl/libs/polygon/example/voronoi_advanced_tutorial.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/example/voronoi_advanced_tutorial.cpp (original)
+++ sandbox/gtl/libs/polygon/example/voronoi_advanced_tutorial.cpp 2012-04-14 16:37:29 EDT (Sat, 14 Apr 2012)
@@ -141,7 +141,7 @@
std::string ftime = boost::timer::format(times, 5, "%w");
printf("Construction done in: %s seconds.\n", ftime.c_str());
- printf("Resulting Voronoi graph has following stats:\n");
+ printf("Resulting Voronoi graph has the following stats:\n");
printf("Number of Voronoi cells: %d.\n", vd.num_cells());
printf("Number of Voronoi vertices: %d.\n", vd.num_vertices());
printf("Number of Voronoi edges: %d.\n", vd.num_edges());
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-14 16:37:29 EDT (Sat, 14 Apr 2012)
@@ -17,17 +17,46 @@
struct Point {
int a;
int b;
-
Point (int x, int y) : a(x), b(y) {}
};
struct Segment {
+ typedef int coordinate_type; // this is temporary required
Point p0;
Point p1;
-
Segment (int x1, int y1, int x2, int y2) : p0(x1, y1), p1(x2, y2) {}
};
+namespace boost {
+namespace polygon {
+
+template <>
+struct geometry_concept<Point> { typedef point_concept type; };
+
+template <>
+struct point_traits<Point> {
+ typedef int coordinate_type;
+
+ static inline coordinate_type get(const Point& point, orientation_2d orient) {
+ return (orient == HORIZONTAL) ? point.a : point.b;
+ }
+};
+
+template <>
+struct geometry_concept<Segment> { typedef directed_line_segment_concept type; };
+
+template <>
+struct directed_line_segment_traits<Segment> {
+ typedef int coordinate_type;
+ typedef Point point_type;
+
+ static inline point_type get(const Segment& segment, direction_1d dir) {
+ return dir.to_int() ? segment.p1 : segment.p0;
+ }
+};
+} // polygon
+} // boost
+
// Traversing Voronoi edges using edge iterator.
int iterate_primary_edges1(const voronoi_diagram<double> &vd) {
int result = 0;
@@ -115,13 +144,8 @@
segments.push_back(Segment(3, -11, 13, -1));
// Construction of the Voronoi Diagram.
- voronoi_builder<int> vb;
voronoi_diagram<double> 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);
+ construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &vd);
// Traversing Voronoi Graph.
{
Modified: sandbox/gtl/libs/polygon/example/voronoi_visualizer.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/example/voronoi_visualizer.cpp (original)
+++ sandbox/gtl/libs/polygon/example/voronoi_visualizer.cpp 2012-04-14 16:37:29 EDT (Sat, 14 Apr 2012)
@@ -12,7 +12,8 @@
#include <QtOpenGL/QGLWidget>
#include <QtGui/QtGui>
-#include "boost/polygon/voronoi.hpp"
+#include "boost/polygon/voronoi_builder.hpp"
+#include "boost/polygon/voronoi_diagram.hpp"
#include "boost/polygon/voronoi_utils.hpp"
using namespace boost::polygon;
Modified: sandbox/gtl/libs/polygon/test/voronoi_benchmark_test.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/test/voronoi_benchmark_test.cpp (original)
+++ sandbox/gtl/libs/polygon/test/voronoi_benchmark_test.cpp 2012-04-14 16:37:29 EDT (Sat, 14 Apr 2012)
@@ -62,7 +62,7 @@
y = static_cast<coordinate_type>(gen());
points[cur_point] = point_type(x, y);
}
- construct_voronoi(points, &test_output);
+ construct_voronoi(points.begin(), points.end(), &test_output);
}
double elapsed_time = timer.elapsed();
double time_per_test = elapsed_time / num_tests;
@@ -99,7 +99,7 @@
for (int i = 0; i < POINT_RUNS; ++i) {
voronoi_diagram<double> test_output;
timer.restart();
- construct_voronoi(points, &test_output);
+ construct_voronoi(points.begin(), points.end(), &test_output);
periods.push_back(timer.elapsed());
}
}
@@ -139,7 +139,7 @@
for (int i = 0; i < SEGMENT_RUNS; ++i) {
voronoi_diagram<double> test_output;
timer.restart();
- construct_voronoi_segments(segments, &test_output);
+ construct_voronoi(segments.begin(), segments.end(), &test_output);
periods.push_back(timer.elapsed());
}
}
Modified: sandbox/gtl/libs/polygon/test/voronoi_builder_test.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/test/voronoi_builder_test.cpp (original)
+++ sandbox/gtl/libs/polygon/test/voronoi_builder_test.cpp 2012-04-14 16:37:29 EDT (Sat, 14 Apr 2012)
@@ -54,7 +54,7 @@
std::vector< point_data<T> > points;
points.push_back(point_data<T>(0, 0));
vd_type test_output;
- construct_voronoi(points, &test_output);
+ construct_voronoi(points.begin(), points.end(), &test_output);
VERIFY_OUTPUT(test_output);
BOOST_CHECK(test_output.cells().size() == 1);
@@ -70,7 +70,7 @@
points.push_back(point_data<T>(0, 0));
points.push_back(point_data<T>(0, 1));
vd_type test_output;
- construct_voronoi(points, &test_output);
+ construct_voronoi(points.begin(), points.end(), &test_output);
VERIFY_OUTPUT(test_output);
CHECK_OUTPUT_SIZE(test_output, 2, 0, 1);
@@ -101,7 +101,7 @@
points.push_back(point_data<T>(1, 1));
points.push_back(point_data<T>(2, 2));
vd_type test_output;
- construct_voronoi(points, &test_output);
+ construct_voronoi(points.begin(), points.end(), &test_output);
VERIFY_OUTPUT(test_output);
CHECK_OUTPUT_SIZE(test_output, 3, 0, 2);
@@ -137,7 +137,7 @@
points.push_back(point2);
points.push_back(point3);
vd_type test_output;
- construct_voronoi(points, &test_output);
+ construct_voronoi(points.begin(), points.end(), &test_output);
VERIFY_OUTPUT(test_output);
CHECK_OUTPUT_SIZE(test_output, 3, 1, 3);
@@ -187,7 +187,7 @@
points.push_back(point2);
points.push_back(point3);
vd_type test_output;
- construct_voronoi(points, &test_output);
+ construct_voronoi(points.begin(), points.end(), &test_output);
VERIFY_OUTPUT(test_output);
CHECK_OUTPUT_SIZE(test_output, 3, 1, 3);
@@ -239,7 +239,7 @@
points.push_back(point3);
points.push_back(point4);
vd_type test_output;
- construct_voronoi(points, &test_output);
+ construct_voronoi(points.begin(), points.end(), &test_output);
VERIFY_OUTPUT(test_output);
CHECK_OUTPUT_SIZE(test_output, 4, 1, 4);
@@ -308,8 +308,8 @@
point_vec_small.push_back(point_data<T>(i, j));
point_vec_large.push_back(point_data<T>(koef * i, koef * j));
}
- construct_voronoi(point_vec_small, &test_output_small);
- construct_voronoi(point_vec_large, &test_output_large);
+ construct_voronoi(point_vec_small.begin(), point_vec_small.end(), &test_output_small);
+ construct_voronoi(point_vec_large.begin(), point_vec_large.end(), &test_output_large);
VERIFY_OUTPUT(test_output_small);
VERIFY_OUTPUT(test_output_large);
unsigned int num_cells = grid_size[k] * grid_size[k];
@@ -344,8 +344,8 @@
point_vec_small.push_back(point_data<T>(x, y));
point_vec_large.push_back(point_data<T>(koef * x, koef * y));
}
- construct_voronoi(point_vec_small, &test_output_small);
- construct_voronoi(point_vec_large, &test_output_large);
+ construct_voronoi(point_vec_small.begin(), point_vec_small.end(), &test_output_small);
+ construct_voronoi(point_vec_large.begin(), point_vec_large.end(), &test_output_large);
VERIFY_OUTPUT(test_output_small);
VERIFY_OUTPUT(test_output_large);
BOOST_CHECK_EQUAL(test_output_small.num_cells(),
@@ -366,7 +366,7 @@
std::vector< point_data<T> > point_vec;
for (int i = 0; i < 1000000; i++)
point_vec.push_back(point_data<T>(gen() % 10000 - 5000, gen() % 10000 - 5000));
- construct_voronoi(point_vec, &test_output);
+ construct_voronoi(point_vec.begin(), point_vec.end(), &test_output);
BOOST_CHECK_EQUAL(voronoi_test_helper::verify_output(test_output,
voronoi_test_helper::FAST_VERIFICATION), true);
}
@@ -378,7 +378,7 @@
point_data<T> point1(0, 0);
point_data<T> point2(1, 1);
segments.insert(directed_line_segment_data<T>(point1, point2));
- construct_voronoi_segments(segments, &test_output);
+ construct_voronoi(segments.begin(), segments.end(), &test_output);
CHECK_OUTPUT_SIZE(test_output, 3, 0, 2);
VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
}
@@ -394,7 +394,7 @@
segments.insert(directed_line_segment_data<T>(point1, point2));
points.push_back(point3);
points.push_back(point4);
- construct_voronoi(points, segments, &test_output);
+ construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
CHECK_OUTPUT_SIZE(test_output, 5, 4, 8);
VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
}
@@ -410,7 +410,7 @@
segments.insert(directed_line_segment_data<T>(point1, point2));
points.push_back(point3);
points.push_back(point4);
- construct_voronoi(points, segments, &test_output);
+ construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
CHECK_OUTPUT_SIZE(test_output, 5, 4, 8);
VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
}
@@ -426,7 +426,7 @@
segments.insert(directed_line_segment_data<T>(point1, point2));
points.push_back(point3);
points.push_back(point4);
- construct_voronoi(points, segments, &test_output);
+ construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
CHECK_OUTPUT_SIZE(test_output, 5, 3, 7);
VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
}
@@ -444,7 +444,7 @@
points.push_back(point3);
points.push_back(point4);
points.push_back(point5);
- construct_voronoi(points, segments, &test_output);
+ construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
CHECK_OUTPUT_SIZE(test_output, 6, 4, 9);
VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
}
@@ -458,7 +458,7 @@
point_data<T> point3(1, 2);
segments.insert(directed_line_segment_data<T>(point2, point3));
points.push_back(point1);
- construct_voronoi(points, segments, &test_output);
+ construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
CHECK_OUTPUT_SIZE(test_output, 4, 2, 5);
VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
}
@@ -473,7 +473,7 @@
segments.insert(directed_line_segment_data<T>(point1, point2));
segments.insert(directed_line_segment_data<T>(point2, point3));
segments.insert(directed_line_segment_data<T>(point3, point4));
- construct_voronoi_segments(segments, &test_output);
+ construct_voronoi(segments.begin(), segments.end(), &test_output);
CHECK_OUTPUT_SIZE(test_output, 7, 6, 12);
VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
}
@@ -489,7 +489,7 @@
segments.insert(directed_line_segment_data<T>(point2, point3));
segments.insert(directed_line_segment_data<T>(point3, point4));
segments.insert(directed_line_segment_data<T>(point4, point1));
- construct_voronoi_segments(segments, &test_output);
+ construct_voronoi(segments.begin(), segments.end(), &test_output);
CHECK_OUTPUT_SIZE(test_output, 8, 5, 12);
VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
}
@@ -523,8 +523,8 @@
segments_small.insert(directed_line_segment_data<T>(point3_1, point4_1));
segments_large.insert(directed_line_segment_data<T>(point3_2, point4_2));
}
- construct_voronoi_segments(segments_small, &test_output_small);
- construct_voronoi_segments(segments_large, &test_output_large);
+ construct_voronoi(segments_small.begin(), segments_small.end(), &test_output_small);
+ construct_voronoi(segments_large.begin(), segments_large.end(), &test_output_large);
VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output_small);
VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output_large);
BOOST_CHECK_EQUAL(test_output_small.num_cells(), test_output_large.num_cells());
@@ -562,7 +562,7 @@
segments.insert(directed_line_segment_data<T>(point1, point2));
}
segments.clean();
- construct_voronoi(points, segments, &test_output);
+ construct_voronoi(points.begin(), points.end(), segments.begin(), segments.end(), &test_output);
VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output);
}
}
@@ -611,8 +611,8 @@
point_data<T> point2_large(x2, y2);
segments_large.insert(directed_line_segment_data<T>(point1_large, point2_large));
}
- construct_voronoi_segments(segments_small, &test_output_small);
- construct_voronoi_segments(segments_large, &test_output_large);
+ construct_voronoi(segments_small.begin(), segments_small.end(), &test_output_small);
+ construct_voronoi(segments_large.begin(), segments_large.end(), &test_output_large);
VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output_small);
VERIFY_NO_HALF_EDGE_INTERSECTIONS(test_output_large);
BOOST_CHECK_EQUAL(test_output_small.num_cells(), test_output_large.num_cells());
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