|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r75144 - in sandbox/gtl/boost/polygon: . detail
From: sydorchuk.andriy_at_[hidden]
Date: 2011-10-27 17:34:34
Author: asydorchuk
Date: 2011-10-27 17:34:32 EDT (Thu, 27 Oct 2011)
New Revision: 75144
URL: http://svn.boost.org/trac/boost/changeset/75144
Log:
Removed voronoi traits.
Code/comments clean up.
Text files modified:
sandbox/gtl/boost/polygon/detail/mpt_wrapper.hpp | 8 +-
sandbox/gtl/boost/polygon/detail/voronoi_calc_kernel.hpp | 45 ++++++----------
sandbox/gtl/boost/polygon/detail/voronoi_fpt_kernel.hpp | 17 ++----
sandbox/gtl/boost/polygon/detail/voronoi_structures.hpp | 8 ---
sandbox/gtl/boost/polygon/voronoi.hpp | 22 ++++---
sandbox/gtl/boost/polygon/voronoi_builder.hpp | 105 ++++++++++++++-------------------------
sandbox/gtl/boost/polygon/voronoi_diagram.hpp | 47 ++++++++---------
7 files changed, 100 insertions(+), 152 deletions(-)
Modified: sandbox/gtl/boost/polygon/detail/mpt_wrapper.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/mpt_wrapper.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/mpt_wrapper.hpp 2011-10-27 17:34:32 EDT (Thu, 27 Oct 2011)
@@ -28,9 +28,9 @@
mpt_wrapper() {}
explicit mpt_wrapper(int input) : m_(input) {}
-
+
explicit mpt_wrapper(double input) : m_(input) {}
-
+
mpt_wrapper(const mpt& input) : m_(input) {}
mpt_wrapper(const mpt_wrapper& w) : m_(w.m_) {}
@@ -47,7 +47,7 @@
m_ = that;
return *this;
}
-
+
mpt_wrapper& operator=(const mpt_wrapper& that) {
m_ = that.m_;
return *this;
@@ -205,7 +205,7 @@
template <typename mpt, int N>
int mpt_wrapper<mpt, N>::cur_ = 0;
-
+
template <typename mpt, int N>
mpt_wrapper<mpt, N> mpt_wrapper<mpt, N>::temp_[N];
Modified: sandbox/gtl/boost/polygon/detail/voronoi_calc_kernel.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/voronoi_calc_kernel.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/voronoi_calc_kernel.hpp 2011-10-27 17:34:32 EDT (Thu, 27 Oct 2011)
@@ -30,7 +30,7 @@
public:
typedef double fpt_type;
typedef unsigned long long ulong_long_type;
-
+
static const unsigned int ULPS = 64;
static const unsigned int ULPSx2 = (ULPS << 1);
static const fpt_type fULPS;
@@ -185,7 +185,7 @@
static_cast<fpt_type>(rhs.y());
}
return static_cast<fpt_type>(lhs.lower_x()) <
- static_cast<fpt_type>(rhs.x());
+ static_cast<fpt_type>(rhs.x());
}
bool operator()(const circle_type &lhs, const circle_type &rhs) const {
@@ -219,7 +219,7 @@
class distance_predicate {
public:
typedef Site site_type;
-
+
// Returns true if a horizontal line going through a new site intersects
// right arc at first, else returns false. If horizontal line goes
// through intersection point of the given two arcs returns false also.
@@ -240,7 +240,6 @@
}
}
}
-
private:
typedef typename Site::point_type point_type;
@@ -272,7 +271,7 @@
// The undefined ulp range is equal to 3EPS + 3EPS <= 6ULP.
return dist1 < dist2;
}
-
+
bool ps(const site_type &left_site, const site_type &right_site,
const site_type &new_site, bool reverse_order) const {
kPredicateResult fast_res = fast_ps(
@@ -309,7 +308,7 @@
const point_type &point) const {
fpt_type dx = site.x() - point.x();
fpt_type dy = site.y() - point.y();
- // The relative error is atmost 3EPS.
+ // The relative error is atmost 3EPS.
return (dx * dx + dy * dy) / (static_cast<fpt_type>(2.0) * dx);
}
@@ -336,7 +335,7 @@
} else {
k = (k - b1) / (a1 * a1);
}
- // The relative error is atmost 8EPS.
+ // The relative error is atmost 8EPS.
return robust_cross_product(a1, b1, a3, b3) * k;
}
}
@@ -430,7 +429,6 @@
}
}
}
-
private:
// Get the newer site.
const site_type &get_comparison_site(const node_type &node) const {
@@ -439,7 +437,7 @@
}
return node.right_site();
}
-
+
// Get comparison pair: y coordinate and direction of the newer site.
std::pair<coordinate_type, int> get_comparison_y(
const node_type &node, bool is_new_node = true) const {
@@ -456,7 +454,6 @@
}
return std::make_pair(node.right_site().y(), -1);
}
-
private:
distance_predicate_type predicate_;
};
@@ -466,7 +463,7 @@
public:
typedef typename Site::point_type point_type;
typedef Site site_type;
-
+
bool ppp(const site_type &site1,
const site_type &site2,
const site_type &site3) const {
@@ -630,7 +627,7 @@
static_cast<fpt_type>(site2.y());
teta = line_a * vec_x + line_b * vec_y;
denom = vec_x * line_b - vec_y * line_a;
-
+
dif[0] = static_cast<fpt_type>(site3.point1().y()) -
static_cast<fpt_type>(site1.y());
dif[1] = static_cast<fpt_type>(site1.x()) -
@@ -676,7 +673,7 @@
c_event.x(0.5 * sqrt_expr_.eval2(cA, cB).get_d() / denom_sqr);
}
}
-
+
if (recompute_c_y || recompute_lower_x) {
cA[2] = sum_y * denom * denom + teta * sum_AB * vec_y;
cB[2] = 1;
@@ -687,7 +684,7 @@
denom_sqr);
}
}
-
+
if (recompute_lower_x) {
cB[0] *= segm_len;
cB[1] *= segm_len;
@@ -699,7 +696,7 @@
(denom_sqr * std::sqrt(segm_len.get_d())));
}
}
-
+
// Recompute parameters of the circle event using high-precision library.
void pss(const site_type &site1,
const site_type &site2,
@@ -845,7 +842,7 @@
static_cast<fpt_type>(site2.x0(true));
a[2] = static_cast<fpt_type>(site3.x1(true)) -
static_cast<fpt_type>(site3.x0(true));
-
+
b[0] = static_cast<fpt_type>(site1.y1(true)) -
static_cast<fpt_type>(site1.y0(true));
b[1] = static_cast<fpt_type>(site2.y1(true)) -
@@ -893,7 +890,7 @@
fpt_type c_x = sqrt_expr_.eval3(cA, cB).get_d();
c_event.x(c_x / denom);
}
-
+
if (recompute_lower_x) {
cB[3] = 1;
fpt_type lower_x = sqrt_expr_.eval4(cA, cB).get_d();
@@ -901,7 +898,6 @@
}
}
}
-
private:
template <typename T>
mpt_wrapper<mpz_class, 8> &mpt_cross(T a0, T b0, T a1, T b1) {
@@ -967,7 +963,6 @@
numer = sqrt_expr_.eval4(cA, cB);
return numer / (lh - rh);
}
-
private:
robust_sqrt_expr_type sqrt_expr_;
};
@@ -1245,19 +1240,19 @@
robust_fpt_type b1(static_cast<fpt_type>(site1.y1(true)) -
static_cast<fpt_type>(site1.y0(true)), 0.0);
robust_fpt_type c1(robust_cross_product(site1.x0(true), site1.y0(true), site1.x1(true), site1.y1(true)), 2.0);
-
+
robust_fpt_type a2(static_cast<fpt_type>(site2.x1(true)) -
static_cast<fpt_type>(site2.x0(true)), 0.0);
robust_fpt_type b2(static_cast<fpt_type>(site2.y1(true)) -
static_cast<fpt_type>(site2.y0(true)), 0.0);
robust_fpt_type c2(robust_cross_product(site2.x0(true), site2.y0(true), site2.x1(true), site2.y1(true)), 2.0);
-
+
robust_fpt_type a3(static_cast<fpt_type>(site3.x1(true)) -
static_cast<fpt_type>(site3.x0(true)), 0.0);
robust_fpt_type b3(static_cast<fpt_type>(site3.y1(true)) -
static_cast<fpt_type>(site3.y0(true)), 0.0);
robust_fpt_type c3(robust_cross_product(site3.x0(true), site3.y0(true), site3.x1(true), site3.y1(true)), 2.0);
-
+
robust_fpt_type len1 = (a1 * a1 + b1 * b1).sqrt();
robust_fpt_type len2 = (a2 * a2 + b2 * b2).sqrt();
robust_fpt_type len3 = (a3 * a3 + b3 * b3).sqrt();
@@ -1302,15 +1297,13 @@
recompute_c_x, recompute_c_y, recompute_lower_x);
}
}
-
private:
template <typename T>
T sqr_distance(T dif_x, T dif_y) {
return dif_x * dif_x + dif_y * dif_y;
}
-
private:
- exact_circle_formation_functor_type exact_circle_formation_functor_;
+ exact_circle_formation_functor_type exact_circle_formation_functor_;
};
template <typename Site,
@@ -1384,12 +1377,10 @@
}
return true;
}
-
private:
circle_existence_predicate_type circle_existence_predicate_;
circle_formation_functor_type circle_formation_functor_;
};
-
private:
// Convert value to 64-bit unsigned integer.
// Return true if the value is positive, else false.
Modified: sandbox/gtl/boost/polygon/detail/voronoi_fpt_kernel.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/voronoi_fpt_kernel.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/voronoi_fpt_kernel.hpp 2011-10-27 17:34:32 EDT (Thu, 27 Oct 2011)
@@ -5,7 +5,7 @@
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
-// See http://www.boost.org for updates, documentation, and revision history.
+// See http://www.boost.org for updates, documentation, and revision history.
#ifndef BOOST_POLYGON_VORONOI_FPT_KERNEL
#define BOOST_POLYGON_VORONOI_FPT_KERNEL
@@ -52,7 +52,6 @@
namespace boost {
namespace polygon {
namespace detail {
-
// Represents the result of the epsilon robust predicate.
// If the result is undefined some further processing is usually required.
enum kPredicateResult {
@@ -232,7 +231,7 @@
if ((this->fpv_ >= 0 && that.fpv_ >= 0) ||
(this->fpv_ <= 0 && that.fpv_ <= 0))
this->re_ = (std::max)(this->re_, that.re_) + ROUNDING_ERROR;
- else {
+ else {
floating_point_type temp =
(this->fpv_ * this->re_ - that.fpv_ * that.re_) / fpv;
this->re_ = std::fabs(temp) + ROUNDING_ERROR;
@@ -314,7 +313,6 @@
robust_fpt fabs() const {
return (fpv_ >= 0) ? *this : -(*this);
}
-
private:
floating_point_type fpv_;
relative_error_type re_;
@@ -434,7 +432,6 @@
}
return *this;
}
-
private:
T positive_sum_;
T negative_sum_;
@@ -458,7 +455,7 @@
template<typename T>
robust_dif<T> operator+(const T& lhs, const robust_dif<T>& rhs) {
- if (lhs >= 0) {
+ if (lhs >= 0) {
return robust_dif<T>(lhs + rhs.pos(), rhs.neg());
} else {
return robust_dif<T>(rhs.pos(), rhs.neg() - lhs);
@@ -482,7 +479,7 @@
template<typename T>
robust_dif<T> operator-(const T& lhs, const robust_dif<T>& rhs) {
- if (lhs >= 0) {
+ if (lhs >= 0) {
return robust_dif<T>(lhs + rhs.neg(), rhs.pos());
} else {
return robust_dif<T>(rhs.neg(), rhs.pos() - lhs);
@@ -523,7 +520,7 @@
return robust_dif<T>(-lhs.neg() / val, -lhs.pos() / val);
}
}
-
+
// Used to compute expressions that operate with sqrts with predefined
// relative error. Evaluates expressions of the next type:
// sum(i = 1 .. n)(A[i] * sqrt(B[i])), 1 <= n <= 4.
@@ -577,7 +574,7 @@
return b[2] /= a[2];
}
-
+
// Evaluates expression (re = 25 EPS):
// A[0] * sqrt(B[0]) + A[1] * sqrt(B[1]) +
// A[2] * sqrt(B[2]) + A[3] * sqrt(B[3]).
@@ -605,7 +602,6 @@
b[3] = eval3(dA, dB);
return b[3] /= a[3];
}
-
private:
mpf a[4];
mpf b[4];
@@ -615,7 +611,6 @@
mpt dB[3];
mpt temp[4];
};
-
} // detail
} // polygon
} // boost
Modified: sandbox/gtl/boost/polygon/detail/voronoi_structures.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/voronoi_structures.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/voronoi_structures.hpp 2011-10-27 17:34:32 EDT (Thu, 27 Oct 2011)
@@ -17,7 +17,6 @@
namespace boost {
namespace polygon {
namespace detail {
-
// Cartesian 2D point data structure.
template <typename T>
class point_2d {
@@ -71,7 +70,6 @@
void y(coordinate_type y) {
y_ = y;
}
-
private:
coordinate_type x_;
coordinate_type y_;
@@ -206,7 +204,6 @@
bool is_inverse() const {
return is_inverse_;
}
-
private:
point_type point0_;
point_type point1_;
@@ -275,7 +272,6 @@
void deactivate() {
is_active_ = false;
}
-
private:
coordinate_type center_x_;
coordinate_type center_y_;
@@ -314,7 +310,6 @@
c_.push(c_list_.begin());
return c_list_.front();
}
-
private:
typedef typename std::list<T>::iterator list_iterator_type;
@@ -386,7 +381,6 @@
void right_site(const site_type &site) {
right_site_ = site;
}
-
private:
site_type left_site_;
site_type right_site_;
@@ -418,12 +412,10 @@
void edge(Edge *new_edge) {
edge_ = new_edge;
}
-
private:
Circle *circle_event_;
Edge *edge_;
};
-
} // detail
} // polygon
} // boost
Modified: sandbox/gtl/boost/polygon/voronoi.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi.hpp 2011-10-27 17:34:32 EDT (Thu, 27 Oct 2011)
@@ -1,6 +1,6 @@
-// Boost polygon/voronoi.hpp header file
+// Boost.Polygon library voronoi.hpp header file
-// Copyright Andrii Sydorchuk 2010.
+// Copyright Andrii Sydorchuk 2010-2011.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
@@ -16,19 +16,19 @@
namespace boost {
namespace polygon {
-
// Public methods to compute voronoi diagram.
// points - vector of input points.
// segments - vector of input segments.
// output - voronoi output data structure to hold voronoi diagram.
// The assumption is made that input doesn't contain segments that
// intersect or points lying on the segments. Also coordinates of
- // the points and of the endpoints of the segments should be within
- // signed integer range [-2^31, 2^31-1].
+ // the points and of the endpoints of the segments should belong to
+ // the signed integer range [-2^31, 2^31-1].
// Complexity - O(N*logN), memory usage - O(N), where N is the total
// number of points and segments.
template <typename T, typename PC, typename VD>
- static inline void construct_voronoi_points(const PC &points, VD &output) {
+ static inline void construct_voronoi_points(
+ const PC &points, VD &output) {
voronoi_builder<T, VD> builder;
builder.insert_points(points.begin(), points.end());
builder.construct(output);
@@ -36,7 +36,8 @@
}
template <typename T, typename SC, typename VD>
- static inline void construct_voronoi_segments(const SC &segments, VD &output) {
+ static inline void construct_voronoi_segments(
+ const SC &segments, VD &output) {
voronoi_builder<T, VD> builder;
builder.insert_segments(segments.begin(), segments.end());
builder.construct(output);
@@ -44,13 +45,14 @@
}
template <typename T, typename PC, typename SC, typename VD>
- static inline void construct_voronoi(const PC &points, const SC &segments, VD &output) {
+ static inline void construct_voronoi(
+ const PC &points, const SC &segments, VD &output) {
voronoi_builder<T, VD> builder;
- builder.insert_sites(points.begin(), points.end(), segments.begin(), segments.end());
+ builder.insert_sites(points.begin(), points.end(),
+ segments.begin(), segments.end());
builder.construct(output);
builder.clear();
}
-
}
}
Modified: sandbox/gtl/boost/polygon/voronoi_builder.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi_builder.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi_builder.hpp 2011-10-27 17:34:32 EDT (Thu, 27 Oct 2011)
@@ -1,6 +1,6 @@
-// Boost polygon/voronoi_builder.hpp header file
+// Boost.Polygon library voronoi_builder.hpp header file
-// Copyright Andrii Sydorchuk 2010.
+// Copyright Andrii Sydorchuk 2010-2011.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
@@ -26,33 +26,18 @@
namespace boost {
namespace polygon {
-
- ///////////////////////////////////////////////////////////////////////////
- // VORONOI TRAITS /////////////////////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
-
- template <typename T>
- struct voronoi_builder_traits;
-
- template <>
- struct voronoi_builder_traits<int> {
- typedef detail::voronoi_calc_kernel<int> calc_kernel_type;
- typedef calc_kernel_type::fpt_type coordinate_type;
- };
-
- ///////////////////////////////////////////////////////////////////////////
- // VORONOI BUILDER ////////////////////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
-
+ // GENERAL INFO:
// The sweepline algorithm implementation to compute voronoi diagram of
// input data sets of points and segments (Fortune's algorithm).
// Complexity - O(N*logN), memory usage - O(N), where N is the total
// number of input objects.
+ //
+ // ALGORITHM OVERVIEW:
// Sweepline is a vertical line that sweeps from the left to the right
// along the x-axis positive direction. Each of the input objects is
// wrapped into the site event. Each event is characterized by its
- // coordinates: the point site is defined by the point itself,
- // the segment site is defined by its startpoint. At any moment we
+ // coordinates: the point site event is defined by the point itself,
+ // the segment site event is defined by its startpoint. At any moment we
// consider only the sites that lie to the left of the sweepline. Beach
// line is a curve formed by the parabolic arcs and line segments, that
// consists of the points equidistant from the sweepline and the nearest
@@ -66,35 +51,24 @@
// and processes it appropriately. This is made until there are no events.
// At the end output data structure holds the voronoi diagram of the
// initial set of objects.
+ //
+ // DATA STRUCTURES OVERVIEW:
// Each point creates one site event. Each segment creates three site
// events: two for its endpoints and one for the segment itself (this is
// made to simplify output construction). All the site events are
- // constructed at the algorithm initialization step. After that they
- // are ordered using quicksort algorithm.
+ // constructed and sorted at the algorithm initialization step.
// Priority queue is used to dynamically hold circle events. At each step
// of the algorithm the leftmost event is retrieved by comparing the
// current site event and the topmost element from the circle event queue.
// Standard map container was chosen to hold state of the beach line. The
- // keys of the map correspond to the bisectors and values to the
- // corresponding edges from the output data structure. Specially defined
- // comparison functor is used to make the beach line correctly ordered.
- // Epsilon-based and high-precision approaches are used to guarantee
+ // keys of the map correspond to the neighboring bisectors and values to
+ // the corresponding edges from the output data structure. Specially
+ // defined comparison functor is used to make the beach line correctly
+ // ordered. Epsilon-based and high-precision approaches are used to guarantee
// efficiency and robustness of the algorithm implementation.
- // Member data: 1) site_events_ - vector of the site events;
- // 2) site_event_iterator_ - iterator to the next
- // site event;
- // 3) circle_events_ - priority queue of circle events,
- // allows to retrieve topmost event in O(logN) time;
- // 4) beach_line_ - contains current state of the beach line;
- // 5) end_points_ - maps endpoints of the segment sites with
- // temporary nodes from the beach line. While sweepline
- // sweeps over the second endpoint of the segments
- // temporary nodes are being removed;
- // 6) output_ - contains voronoi diagram itself.
template <typename T, typename VD>
class voronoi_builder {
public:
- typedef typename voronoi_builder_traits<T>::coordinate_type coordinate_type;
typedef VD output_type;
voronoi_builder() {}
@@ -121,8 +95,11 @@
coordinate_type x2 = static_cast<coordinate_type>(it->high().x());
coordinate_type y2 = static_cast<coordinate_type>(it->high().y());
site_events_.push_back(detail::site_event<coordinate_type>(x1, y1, 0));
- site_events_.push_back(detail::site_event<coordinate_type>(x2, y2, 0));
- site_events_.push_back(detail::site_event<coordinate_type>(x1, y1, x2, y2, 0));
+ // Process degenerate segments correctly.
+ if (x1 != x2 || y1 != y2) {
+ site_events_.push_back(detail::site_event<coordinate_type>(x2, y2, 0));
+ site_events_.push_back(detail::site_event<coordinate_type>(x1, y1, x2, y2, 0));
+ }
}
}
@@ -173,28 +150,28 @@
void clear() {
site_events_.clear();
}
-
private:
- typedef voronoi_builder_traits<int>::calc_kernel_type calc_kernel_type;
+ typedef detail::voronoi_calc_kernel<T> CKT;
+ typedef typename CKT::fpt_type coordinate_type;
typedef detail::point_2d<coordinate_type> point_type;
typedef detail::site_event<coordinate_type> site_event_type;
typedef typename std::vector<site_event_type>::const_iterator
site_event_iterator_type;
typedef detail::circle_event<coordinate_type> circle_event_type;
- typedef calc_kernel_type::event_comparison_predicate<site_event_type, circle_event_type>
+ typedef typename CKT::event_comparison_predicate<site_event_type, circle_event_type>
event_comparison_predicate;
- typedef calc_kernel_type::event_equality_predicate<site_event_type, circle_event_type>
+ typedef typename CKT::event_equality_predicate<site_event_type, circle_event_type>
event_equality_predicate;
- typedef calc_kernel_type::circle_formation_predicate<site_event_type, circle_event_type>
+ typedef typename CKT::circle_formation_predicate<site_event_type, circle_event_type>
circle_formation_predicate_type;
typedef typename output_type::voronoi_edge_type edge_type;
typedef detail::beach_line_node_key<site_event_type> key_type;
typedef detail::beach_line_node_data<edge_type, circle_event_type> value_type;
- typedef calc_kernel_type::node_comparison_predicate<key_type> node_comparer_type;
+ typedef typename CKT::node_comparison_predicate<key_type> node_comparer_type;
typedef std::map< key_type, value_type, node_comparer_type > beach_line_type;
typedef typename beach_line_type::iterator beach_line_iterator;
- typedef std::pair<circle_event_type, beach_line_iterator> event_type;
+ typedef std::pair<circle_event_type, beach_line_iterator> event_type;
typedef struct {
bool operator()(const event_type &lhs, const event_type &rhs) const {
return predicate(rhs.first, lhs.first);
@@ -210,18 +187,19 @@
// events for each input segment (both endpoints of a segment and the
// segment itself).
void init_sites_queue() {
- // Sort the site events.
+ // Sort site events.
sort(site_events_.begin(), site_events_.end(), event_comparison_predicate());
// Remove duplicates.
- site_events_.erase(unique(
- site_events_.begin(), site_events_.end(), event_equality_predicate()), site_events_.end());
+ site_events_.erase(unique(site_events_.begin(),
+ site_events_.end(),
+ event_equality_predicate()), site_events_.end());
- // Number the sites.
+ // Index sites.
for (size_t cur = 0; cur < site_events_.size(); ++cur)
site_events_[cur].index(cur);
- // Init the site's iterator.
+ // Init site iterator.
site_event_iterator_ = site_events_.begin();
}
@@ -236,9 +214,9 @@
// Count the number of the sites to init the beach line.
while(site_event_iterator_ != site_events_.end() &&
- calc_kernel_type::is_vertical(site_event_iterator_->point0(),
- site_events_.begin()->point0()) &&
- calc_kernel_type::is_vertical(*site_event_iterator_)) {
+ CKT::is_vertical(site_event_iterator_->point0(),
+ site_events_.begin()->point0()) &&
+ CKT::is_vertical(*site_event_iterator_)) {
++site_event_iterator_;
++skip;
}
@@ -300,12 +278,11 @@
}
}
- // Process a single site.
void process_site_event() {
// Get the site event to process.
site_event_type site_event = *site_event_iterator_;
- // Move the site's iterator.
+ // Move site iterator.
site_event_iterator_type last = site_event_iterator_ + 1;
// If a new site is an end point of some segment,
@@ -335,7 +312,7 @@
// Do further processing depending on the above node position.
// For any two neighbouring nodes the second site of the first node
- // is the same as the first site of the second arc.
+ // is the same as the first site of the second node.
if (it == beach_line_.end()) {
// The above arc corresponds to the second arc of the last node.
// Move the iterator to the last node.
@@ -406,11 +383,10 @@
}
}
- // Process a single circle event.
// In general case circle event is made of the three consequtive sites
// that form two bisector nodes in the beach line data structure.
// Let circle event sites be A, B, C, two bisectors that define
- // circle event be (A, B), (B, C). During circle event processing
+ // circle event are (A, B), (B, C). During circle event processing
// we remove (A, B), (B, C) and insert (A, C). As beach line comparer
// works correctly only if one of the nodes is a new one we remove
// (B, C) bisector and change (A, B) bisector to the (A, C). That's
@@ -490,8 +466,6 @@
// Update the output.
edge_type *edge = output_->insert_new_edge(site_arc2, site_event);
-
- // Update the beach line with the (site_arc1, site_event) bisector.
beach_line_iterator it = beach_line_.insert(position,
typename beach_line_type::value_type(new_right_node, value_type(edge->twin())));
@@ -508,7 +482,6 @@
end_points_.push(std::make_pair(site_event.point1(), temp_it));
}
- // Update the beach line with the (site_event, site_arc2) bisector.
beach_line_.insert(position,
typename beach_line_type::value_type(new_left_node, value_type(edge)));
return it;
@@ -531,7 +504,6 @@
bisector_node->second.circle_event(&e.first);
}
}
-
private:
struct end_point_comparison {
bool operator() (const end_point_type &end1, const end_point_type &end2) const {
@@ -552,7 +524,6 @@
voronoi_builder(const voronoi_builder&);
void operator=(const voronoi_builder&);
};
-
} // polygon
} // boost
Modified: sandbox/gtl/boost/polygon/voronoi_diagram.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi_diagram.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi_diagram.hpp 2011-10-27 17:34:32 EDT (Thu, 27 Oct 2011)
@@ -1,6 +1,6 @@
-// Boost polygon/voronoi_diagram.hpp header file
+// Boost.Polygon library voronoi_diagram.hpp header file
-// Copyright Andrii Sydorchuk 2010.
+// Copyright Andrii Sydorchuk 2010-2011.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
@@ -21,10 +21,6 @@
namespace boost {
namespace polygon {
- ///////////////////////////////////////////////////////////////////////////
- // VORONOI OUTPUT TYPES ///////////////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
-
// Forward declarations.
template <typename T>
class voronoi_cell;
@@ -60,12 +56,16 @@
static_cast<coordinate_type>(p2.y()));
}
- BRect(coordinate_type x_mn, coordinate_type y_mn,
- coordinate_type x_mx, coordinate_type y_mx) {
- x_min_ = (std::min)(x_mn, x_mx);
- y_min_ = (std::min)(y_mn, y_mx);
- x_max_ = (std::max)(x_mn, x_mx);
- y_max_ = (std::max)(y_mn, y_mx);
+ template <typename C>
+ BRect(C x_mn, C y_mn, C x_mx, C y_mx) {
+ x_min_ = (std::min)(static_cast<coordinate_type>(x_mn),
+ static_cast<coordinate_type>(x_mx));
+ y_min_ = (std::min)(static_cast<coordinate_type>(y_mn),
+ static_cast<coordinate_type>(y_mx));
+ x_max_ = (std::max)(static_cast<coordinate_type>(x_mn),
+ static_cast<coordinate_type>(x_mx));
+ y_max_ = (std::max)(static_cast<coordinate_type>(y_mn),
+ static_cast<coordinate_type>(y_mx));
}
// Extend the rectangle with a new point.
@@ -78,9 +78,12 @@
}
// Check whether a point is situated inside the bounding rectangle.
- bool contains(const point_type &p) const {
- return p.x() >= x_min_ && p.x() <= x_max_ &&
- p.y() >= y_min_ && p.y() <= y_max_;
+ template <typename P>
+ bool contains(const P &p) const {
+ return static_cast<coordinate_type>(p.x()) >= x_min_ &&
+ static_cast<coordinate_type>(p.x()) <= x_max_ &&
+ static_cast<coordinate_type>(p.y()) >= y_min_ &&
+ static_cast<coordinate_type>(p.y()) <= y_max_;
}
// Check whether the bounding rectangle has a non-zero area.
@@ -204,11 +207,11 @@
(site1.y() + site2.y()) / 2);
point_type direction(site1.y() - site2.y(),
site2.x() - site1.x());
-
+
// Find intersection points.
find_intersections(origin, direction, LINE,
brect, edge_points);
-
+
// Update endpoints in case edge is a ray.
if (edge->vertex1() != NULL)
edge_points[1] = get_point(edge->vertex1()->vertex());
@@ -251,7 +254,7 @@
// Find intersection points.
find_intersections(point1, direction, LINE,
brect, edge_points);
-
+
// Update endpoints in case edge is a ray.
if (edge->vertex1() != NULL)
edge_points[1] = get_point(edge->vertex1()->vertex());
@@ -346,7 +349,6 @@
origin.x() + fT1 * direction.x(),
origin.y() + fT1 * direction.y()));
}
-
private:
voronoi_helper();
@@ -572,7 +574,6 @@
int num_incident_edges() const { return num_incident_edges_; }
void inc_num_incident_edges() { ++num_incident_edges_; }
void dec_num_incident_edges() { --num_incident_edges_; }
-
private:
point_type point0_;
point_type point1_;
@@ -602,14 +603,13 @@
const point_type &vertex() const { return vertex_; }
voronoi_edge_type *incident_edge() { return incident_edge_; }
- const voronoi_edge_type *incident_edge() const {
+ const voronoi_edge_type *incident_edge() const {
return incident_edge_;
}
void incident_edge(voronoi_edge_type *e) { incident_edge_ = e; }
int num_incident_edges() const { return num_incident_edges_; }
void num_incident_edges(int n) { num_incident_edges_ = n; }
-
private:
point_type vertex_;
voronoi_edge_type *incident_edge_;
@@ -715,7 +715,6 @@
}
return true;
}
-
private:
voronoi_cell_type *cell_;
voronoi_vertex_type *vertex_;
@@ -1103,7 +1102,6 @@
}
}
}
-
private:
// Remove degenerate edge.
void remove_edge(voronoi_edge_type *edge) {
@@ -1162,7 +1160,6 @@
voronoi_diagram(const voronoi_diagram&);
void operator=(const voronoi_diagram&);
};
-
} // polygon
} // boost
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