|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r76332 - in sandbox/gtl/boost/polygon: . detail
From: sydorchuk.andriy_at_[hidden]
Date: 2012-01-06 08:12:29
Author: asydorchuk
Date: 2012-01-06 08:12:28 EST (Fri, 06 Jan 2012)
New Revision: 76332
URL: http://svn.boost.org/trac/boost/changeset/76332
Log:
Refactoring voronoi_robust_fpt and voronoi_calc_utils before creating voronoi_ctypes (coordinate types).
Text files modified:
sandbox/gtl/boost/polygon/detail/voronoi_calc_utils.hpp | 45 +++++++----
sandbox/gtl/boost/polygon/detail/voronoi_robust_fpt.hpp | 145 +++++++++++----------------------------
sandbox/gtl/boost/polygon/voronoi_builder.hpp | 2
sandbox/gtl/boost/polygon/voronoi_diagram.hpp | 7 +
4 files changed, 75 insertions(+), 124 deletions(-)
Modified: sandbox/gtl/boost/polygon/detail/voronoi_calc_utils.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/voronoi_calc_utils.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/voronoi_calc_utils.hpp 2012-01-06 08:12:28 EST (Fri, 06 Jan 2012)
@@ -50,8 +50,8 @@
// Return orientation based on the sign of the determinant.
template <typename T>
static kOrientation get_orientation(T value) {
- if (value == static_cast<T>(0.0)) return COLLINEAR;
- return (value < static_cast<T>(0.0)) ? RIGHT : LEFT;
+ if (is_zero(value)) return COLLINEAR;
+ return (is_neg(value)) ? RIGHT : LEFT;
}
// Compute robust cross_product: a1 * b2 - b1 * a2.
@@ -209,9 +209,9 @@
// 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.
- bool operator()(const site_type& left_site,
- const site_type& right_site,
- const site_type& new_site) const {
+ bool operator()(const site_type &left_site,
+ const site_type &right_site,
+ const site_type &new_site) const {
if (!left_site.is_segment()) {
if (!right_site.is_segment()) {
return pp(left_site, right_site, new_site);
@@ -318,9 +318,9 @@
static_cast<fpt_type>(segment0.x());
fpt_type b3 = static_cast<fpt_type>(point.y()) -
static_cast<fpt_type>(segment0.y());
- fpt_type k = std::sqrt(a1 * a1 + b1 * b1);
+ fpt_type k = get_sqrt(a1 * a1 + b1 * b1);
// Avoid substraction while computing k.
- if (b1 >= static_cast<fpt_type>(0.0)) {
+ if (!is_neg(b1)) {
k = static_cast<fpt_type>(1.0) / (b1 + k);
} else {
k = (k - b1) / (a1 * a1);
@@ -573,8 +573,12 @@
// If c_x >= 0 then lower_x = c_x + r,
// else lower_x = (c_x * c_x - r * r) / (c_x - r).
// To guarantee epsilon relative error.
- if (circle.x() >= static_cast<fpt_type>(0.0)) {
- circle.lower_x(circle.x() + r * fabs(inv_denom));
+ if (!is_neg(circle.x())) {
+ if (!is_neg(inv_denom)) {
+ circle.lower_x(circle.x() + r * inv_denom);
+ } else {
+ circle.lower_x(circle.x() - r * inv_denom);
+ }
} else {
eint numer = c_x * c_x - sqr_r;
fpt_type lower_x = get_d(numer) * inv_denom /
@@ -1015,9 +1019,9 @@
c_y -= robust_fpt_type(dif_x1 * sum_x1 * dif_x2, 2.0);
c_y -= robust_fpt_type(dif_y1 * sum_y1 * dif_x2, 2.0);
robust_dif_type lower_x(c_x);
- lower_x -= robust_fpt_type(std::sqrt(sqr_distance(dif_x1, dif_y1) *
- sqr_distance(dif_x2, dif_y2) *
- sqr_distance(dif_x3, dif_y3)), 5.0);
+ lower_x -= robust_fpt_type(get_sqrt(sqr_distance(dif_x1, dif_y1) *
+ sqr_distance(dif_x2, dif_y2) *
+ sqr_distance(dif_x3, dif_y3)), 5.0);
c_event = circle_type(c_x.dif().fpv() * inv_orientation.fpv(),
c_y.dif().fpv() * inv_orientation.fpv(),
lower_x.dif().fpv() * inv_orientation.fpv());
@@ -1055,7 +1059,7 @@
static_cast<fpt_type>(site2.x()) -
static_cast<fpt_type>(site3.point1().x())), 1.0);
robust_fpt_type denom(robust_cross_product(vec_x, vec_y, line_a, line_b), 1.0);
- robust_fpt_type inv_segm_len(1.0 / std::sqrt(sqr_distance(line_a, line_b)), 3.0);
+ robust_fpt_type inv_segm_len(1.0 / get_sqrt(sqr_distance(line_a, line_b)), 3.0);
robust_dif_type t;
if (get_orientation(denom) == COLLINEAR) {
t += teta / (robust_fpt_type(8.0, false) * A);
@@ -1083,7 +1087,9 @@
r -= robust_fpt_type(line_b, false) * robust_fpt_type(site3.y0(), false);
r += robust_fpt_type(line_a, false) * c_x;
r += robust_fpt_type(line_b, false) * c_y;
- r.abs();
+ if (r.pos().fpv() < r.neg().fpv()) {
+ r = -r;
+ }
lower_x += r * inv_segm_len;
c_event = circle_type(c_x.dif().fpv(), c_y.dif().fpv(), lower_x.dif().fpv());
bool recompute_c_x = c_x.dif().ulp() > fULPS;
@@ -1163,10 +1169,10 @@
recompute_lower_x = lower_x.dif().ulp() > fULPS;
c_event = circle_type(c_x.dif().fpv(), c_y.dif().fpv(), lower_x.dif().fpv());
} else {
- robust_fpt_type sqr_sum1(std::sqrt(a1 * a1 + b1 * b1), 2.0);
- robust_fpt_type sqr_sum2(std::sqrt(a2 * a2 + b2 * b2), 2.0);
+ robust_fpt_type sqr_sum1(get_sqrt(a1 * a1 + b1 * b1), 2.0);
+ robust_fpt_type sqr_sum2(get_sqrt(a2 * a2 + b2 * b2), 2.0);
robust_fpt_type a(robust_cross_product(a1, b1, -b2, a2), 1.0);
- if (a >= 0) {
+ if (!is_neg(a)) {
a += sqr_sum1 * sqr_sum2;
} else {
a = (orientation * orientation) / (sqr_sum1 * sqr_sum2 - a);
@@ -1217,7 +1223,9 @@
c_x += t * (robust_fpt_type(a2, false) * sqr_sum1);
c_y += t * (robust_fpt_type(b1, false) * sqr_sum2);
c_y += t * (robust_fpt_type(b2, false) * sqr_sum1);
- t.abs();
+ if (t.pos().fpv() < t.neg().fpv()) {
+ t = -t;
+ }
robust_dif_type lower_x(c_x);
lower_x += t * orientation.fabs();
recompute_c_x = c_x.dif().ulp() > fULPS;
@@ -1374,6 +1382,7 @@
}
return true;
}
+
private:
circle_existence_predicate_type circle_existence_predicate_;
circle_formation_functor_type circle_formation_functor_;
Modified: sandbox/gtl/boost/polygon/detail/voronoi_robust_fpt.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/voronoi_robust_fpt.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/voronoi_robust_fpt.hpp 2012-01-06 08:12:28 EST (Fri, 06 Jan 2012)
@@ -60,7 +60,6 @@
typedef boost::int64_t int64;
typedef boost::uint32_t uint32;
typedef boost::uint64_t uint64;
- typedef float fpt32;
typedef double fpt64;
// If two floating-point numbers in the same format are ordered (x < y),
@@ -71,24 +70,6 @@
bool almost_equal(_fpt a, _fpt b, uint32 ulps);
template<>
- bool almost_equal<fpt32>(fpt32 a, fpt32 b, uint32 maxUlps) {
- uint32 ll_a, ll_b;
-
- // Reinterpret double bits as 32-bit signed integer.
- memcpy(&ll_a, &a, sizeof(fpt32));
- memcpy(&ll_b, &b, sizeof(fpt32));
-
- if (ll_a < 0x80000000)
- ll_a = 0x80000000 - ll_a;
- if (ll_b < 0x80000000)
- ll_b = 0x80000000 - ll_b;
-
- if (ll_a > ll_b)
- return ll_a - ll_b <= maxUlps;
- return ll_b - ll_a <= maxUlps;
- }
-
- template<>
bool almost_equal<fpt64>(fpt64 a, fpt64 b, uint32 maxUlps) {
uint64 ll_a, ll_b;
@@ -160,80 +141,28 @@
relative_error_type re() const { return re_; }
relative_error_type ulp() const { return re_; }
- template <typename T>
- bool operator==(T that) const {
- floating_point_type value = static_cast<floating_point_type>(that);
- return almost_equal(this->fpv_,
- value,
- static_cast<uint32>(this->ulp()));
- }
-
- template <typename T>
- bool operator!=(T that) const {
- return !(*this == that);
- }
-
- template <typename T>
- bool operator<(T that) const {
- if (*this == that) return false;
- return this->fpv_ < static_cast<floating_point_type>(that);
- }
-
- template <typename T>
- bool operator<=(T that) const {
- if (*this == that) return true;
- return this->fpv_ < static_cast<floating_point_type>(that);
- }
-
- template <typename T>
- bool operator>(T that) const {
- if (*this == that) return false;
- return this->fpv_ > static_cast<floating_point_type>(that);
- }
-
- template <typename T>
- bool operator>=(T that) const {
- if (*this == that) return true;
- return this->fpv_ > static_cast<floating_point_type>(that);
- }
-
- bool operator==(const robust_fpt &that) const {
- uint32 ulp = static_cast<uint32>(this->re_ + that.re_);
- return almost_equal(this->fpv_, that.fpv_, ulp);
- }
-
- bool operator!=(const robust_fpt &that) const {
- return !(*this == that);
- }
-
- bool operator<(const robust_fpt &that) const {
- if (*this == that)
- return false;
- return this->fpv_ < that.fpv_;
+ robust_fpt& operator=(const robust_fpt &that) {
+ this->fpv_ = that.fpv_;
+ this->re_ = that.re_;
+ return *this;
}
- bool operator>(const robust_fpt &that) const {
- return that < *this;
+ bool is_pos() const {
+ return fpv_ > 0.0;
}
- bool operator<=(const robust_fpt &that) const {
- return !(that < *this);
+ bool is_neg() const {
+ return fpv_ < 0.0;
}
- bool operator>=(const robust_fpt &that) const {
- return !(*this < that);
+ bool is_zero() const {
+ return fpv_ == 0.0;
}
robust_fpt operator-() const {
return robust_fpt(-fpv_, re_);
}
- robust_fpt& operator=(const robust_fpt &that) {
- this->fpv_ = that.fpv_;
- this->re_ = that.re_;
- return *this;
- }
-
robust_fpt& operator+=(const robust_fpt &that) {
floating_point_type fpv = this->fpv_ + that.fpv_;
if ((this->fpv_ >= 0 && that.fpv_ >= 0) ||
@@ -336,6 +265,21 @@
return that.sqrt();
}
+ template <typename T>
+ bool is_pos(const robust_fpt<T>& that) {
+ return that.is_pos();
+ }
+
+ template <typename T>
+ bool is_neg(const robust_fpt<T>& that) {
+ return that.is_neg();
+ }
+
+ template <typename T>
+ bool is_zero(const robust_fpt<T>& that) {
+ return that.is_zero();
+ }
+
// robust_dif consists of two not negative values: value1 and value2.
// The resulting expression is equal to the value1 - value2.
// Substraction of a positive value is equivalent to the addition to value2
@@ -368,25 +312,12 @@
return negative_sum_;
}
- // Equivalent to the unary minus.
- void swap() {
- (std::swap)(positive_sum_, negative_sum_);
- }
-
- bool abs() {
- if (positive_sum_ < negative_sum_) {
- swap();
- return true;
- }
- return false;
- }
-
robust_dif<T> operator-() const {
return robust_dif(negative_sum_, positive_sum_);
}
robust_dif<T> &operator+=(const T &val) {
- if (val >= 0)
+ if (!is_neg(val))
positive_sum_ += val;
else
negative_sum_ -= val;
@@ -400,7 +331,7 @@
}
robust_dif<T> &operator-=(const T &val) {
- if (val >= 0)
+ if (!is_neg(val))
negative_sum_ += val;
else
positive_sum_ -= val;
@@ -414,7 +345,7 @@
}
robust_dif<T> &operator*=(const T &val) {
- if (val >= 0) {
+ if (!is_neg(val)) {
positive_sum_ *= val;
negative_sum_ *= val;
} else {
@@ -436,7 +367,7 @@
}
robust_dif<T> &operator/=(const T &val) {
- if (val >= 0) {
+ if (!is_neg(val)) {
positive_sum_ /= val;
negative_sum_ /= val;
} else {
@@ -448,6 +379,10 @@
}
private:
+ void swap() {
+ (std::swap)(positive_sum_, negative_sum_);
+ }
+
T positive_sum_;
T negative_sum_;
};
@@ -461,7 +396,7 @@
template<typename T>
robust_dif<T> operator+(const robust_dif<T>& lhs, const T& rhs) {
- if (rhs >= 0) {
+ if (!is_neg(rhs)) {
return robust_dif<T>(lhs.pos() + rhs, lhs.neg());
} else {
return robust_dif<T>(lhs.pos(), lhs.neg() - rhs);
@@ -470,7 +405,7 @@
template<typename T>
robust_dif<T> operator+(const T& lhs, const robust_dif<T>& rhs) {
- if (lhs >= 0) {
+ if (!is_neg(lhs)) {
return robust_dif<T>(lhs + rhs.pos(), rhs.neg());
} else {
return robust_dif<T>(rhs.pos(), rhs.neg() - lhs);
@@ -485,7 +420,7 @@
template<typename T>
robust_dif<T> operator-(const robust_dif<T>& lhs, const T& rhs) {
- if (rhs >= 0) {
+ if (!is_neg(rhs)) {
return robust_dif<T>(lhs.pos(), lhs.neg() + rhs);
} else {
return robust_dif<T>(lhs.pos() - rhs, lhs.neg());
@@ -494,7 +429,7 @@
template<typename T>
robust_dif<T> operator-(const T& lhs, const robust_dif<T>& rhs) {
- if (lhs >= 0) {
+ if (!is_neg(lhs)) {
return robust_dif<T>(lhs + rhs.neg(), rhs.pos());
} else {
return robust_dif<T>(rhs.neg(), rhs.pos() - lhs);
@@ -511,7 +446,7 @@
template<typename T>
robust_dif<T> operator*(const robust_dif<T>& lhs, const T& val) {
- if (val >= 0) {
+ if (!is_neg(val)) {
return robust_dif<T>(lhs.pos() * val, lhs.neg() * val);
} else {
return robust_dif<T>(-lhs.neg() * val, -lhs.pos() * val);
@@ -520,7 +455,7 @@
template<typename T>
robust_dif<T> operator*(const T& val, const robust_dif<T>& rhs) {
- if (val >= 0) {
+ if (!is_neg(val)) {
return robust_dif<T>(val * rhs.pos(), val * rhs.neg());
} else {
return robust_dif<T>(-val * rhs.neg(), -val * rhs.pos());
@@ -529,7 +464,7 @@
template<typename T>
robust_dif<T> operator/(const robust_dif<T>& lhs, const T& val) {
- if (val >= 0) {
+ if (!is_neg(val)) {
return robust_dif<T>(lhs.pos() / val, lhs.neg() / val);
} else {
return robust_dif<T>(-lhs.neg() / val, -lhs.pos() / val);
Modified: sandbox/gtl/boost/polygon/voronoi_builder.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi_builder.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi_builder.hpp 2012-01-06 08:12:28 EST (Fri, 06 Jan 2012)
@@ -153,6 +153,7 @@
void clear() {
site_events_.clear();
}
+
private:
typedef detail::voronoi_calc_utils<T> VCU;
typedef typename VCU::fpt_type coordinate_type;
@@ -509,6 +510,7 @@
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 {
Modified: sandbox/gtl/boost/polygon/voronoi_diagram.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi_diagram.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi_diagram.hpp 2012-01-06 08:12:28 EST (Fri, 06 Jan 2012)
@@ -349,6 +349,7 @@
origin.x() + fT1 * direction.x(),
origin.y() + fT1 * direction.y()));
}
+
private:
voronoi_helper();
@@ -572,6 +573,7 @@
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_;
@@ -607,6 +609,7 @@
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_;
@@ -712,6 +715,7 @@
}
return true;
}
+
private:
voronoi_cell_type *cell_;
voronoi_vertex_type *vertex_;
@@ -1040,7 +1044,7 @@
// To guarantee N*lon(N) time we merge vertex with
// less incident edges to the one with more.
if (v1->num_incident_edges() >= v2->num_incident_edges()) {
- remove_edge(&(*edge_it1));
+ remove_edge(&(*edge_it1));
} else {
remove_edge(edge_it1->twin());
}
@@ -1096,6 +1100,7 @@
}
}
}
+
private:
// Remove degenerate edge.
void remove_edge(voronoi_edge_type *edge) {
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