Subject: [Boost-commit] svn:boost r77509 - in sandbox/gtl/boost/polygon: . detail
From: sydorchuk.andriy_at_[hidden]
Date: 2012-03-23 17:18:25
Author: asydorchuk
Date: 2012-03-23 17:18:24 EDT (Fri, 23 Mar 2012)
New Revision: 77509
URL: http://svn.boost.org/trac/boost/changeset/77509
Log:
Fixing comments.
Code styling.
Text files modified:
sandbox/gtl/boost/polygon/detail/voronoi_ctypes.hpp | 1185 +++++++++++++++++++--------------------
sandbox/gtl/boost/polygon/detail/voronoi_robust_fpt.hpp | 655 ++++++++++-----------
sandbox/gtl/boost/polygon/detail/voronoi_structures.hpp | 2
sandbox/gtl/boost/polygon/voronoi.hpp | 11
sandbox/gtl/boost/polygon/voronoi_builder.hpp | 8
sandbox/gtl/boost/polygon/voronoi_diagram.hpp | 67 +-
sandbox/gtl/boost/polygon/voronoi_utils.hpp | 6
7 files changed, 960 insertions(+), 974 deletions(-)
Modified: sandbox/gtl/boost/polygon/detail/voronoi_ctypes.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/detail/voronoi_ctypes.hpp (original)
+++ sandbox/gtl/boost/polygon/detail/voronoi_ctypes.hpp 2012-03-23 17:18:24 EDT (Fri, 23 Mar 2012)
@@ -32,35 +32,35 @@
template <>
struct ulp_comparison<fpt64> {
- enum Result {
- LESS = -1,
- EQUAL = 0,
- MORE = 1
- };
-
- Result operator()(fpt64 a, fpt64 b, unsigned int maxUlps) const {
- uint64 ll_a, ll_b;
-
- // Reinterpret double bits as 64-bit signed integer.
- memcpy(&ll_a, &a, sizeof(fpt64));
- memcpy(&ll_b, &b, sizeof(fpt64));
-
- // Positive 0.0 is integer zero. Negative 0.0 is 0x8000000000000000.
- // Map negative zero to an integer zero representation - making it
- // identical to positive zero - the smallest negative number is
- // represented by negative one, and downwards from there.
- if (ll_a < 0x8000000000000000ULL)
- ll_a = 0x8000000000000000ULL - ll_a;
- if (ll_b < 0x8000000000000000ULL)
- ll_b = 0x8000000000000000ULL - ll_b;
-
- // Compare 64-bit signed integer representations of input values.
- // Difference in 1 Ulp is equivalent to a relative error of between
- // 1/4,000,000,000,000,000 and 1/8,000,000,000,000,000.
- if (ll_a > ll_b)
- return (ll_a - ll_b <= maxUlps) ? EQUAL : LESS;
- return (ll_b - ll_a <= maxUlps) ? EQUAL : MORE;
- }
+ enum Result {
+ LESS = -1,
+ EQUAL = 0,
+ MORE = 1
+ };
+
+ Result operator()(fpt64 a, fpt64 b, unsigned int maxUlps) const {
+ uint64 ll_a, ll_b;
+
+ // Reinterpret double bits as 64-bit signed integer.
+ memcpy(&ll_a, &a, sizeof(fpt64));
+ memcpy(&ll_b, &b, sizeof(fpt64));
+
+ // Positive 0.0 is integer zero. Negative 0.0 is 0x8000000000000000.
+ // Map negative zero to an integer zero representation - making it
+ // identical to positive zero - the smallest negative number is
+ // represented by negative one, and downwards from there.
+ if (ll_a < 0x8000000000000000ULL)
+ ll_a = 0x8000000000000000ULL - ll_a;
+ if (ll_b < 0x8000000000000000ULL)
+ ll_b = 0x8000000000000000ULL - ll_b;
+
+ // Compare 64-bit signed integer representations of input values.
+ // Difference in 1 Ulp is equivalent to a relative error of between
+ // 1/4,000,000,000,000,000 and 1/8,000,000,000,000,000.
+ if (ll_a > ll_b)
+ return (ll_a - ll_b <= maxUlps) ? EQUAL : LESS;
+ return (ll_b - ll_a <= maxUlps) ? EQUAL : MORE;
+ }
};
// Manages exponent of the floating-point value.
@@ -70,27 +70,28 @@
template <>
class fpt_exponent_accessor<fpt64> {
public:
- static const int64 kExponentMask;
- static const int64 kSignedMantissaMask;
- static const int64 kMinExponent;
- static const int64 kMaxExponent;
- static const int64 kMaxSignificantExpDif;
-
- static int64 set_exponent(fpt64& value, int64 exponent) {
- int64 bits;
- memcpy(&bits, &value, sizeof(fpt64));
- int64 exp = ((bits & kExponentMask) >> 52) - 1023;
- if (exp == exponent) {
- return exp;
- }
- bits = (bits & kSignedMantissaMask) | ((exponent + 1023) << 52);
- memcpy(&value, &bits, sizeof(fpt64));
- return exp;
- }
+ static const int64 kExponentMask;
+ static const int64 kSignedMantissaMask;
+ static const int64 kMinExponent;
+ static const int64 kMaxExponent;
+ static const int64 kMaxSignificantExpDif;
+
+ static int64 set_exponent(fpt64& value, int64 exponent) {
+ int64 bits;
+ memcpy(&bits, &value, sizeof(fpt64));
+ int64 exp = ((bits & kExponentMask) >> 52) - 1023;
+ if (exp == exponent)
+ return exp;
+ bits = (bits & kSignedMantissaMask) | ((exponent + 1023) << 52);
+ memcpy(&value, &bits, sizeof(fpt64));
+ return exp;
+ }
};
-const int64 fpt_exponent_accessor<fpt64>::kExponentMask = 0x7ff0000000000000LL;
-const int64 fpt_exponent_accessor<fpt64>::kSignedMantissaMask = 0x800fffffffffffffLL;
+const int64 fpt_exponent_accessor<fpt64>::kExponentMask =
+ 0x7ff0000000000000LL;
+const int64 fpt_exponent_accessor<fpt64>::kSignedMantissaMask =
+ 0x800fffffffffffffLL;
const int64 fpt_exponent_accessor<fpt64>::kMinExponent = -1023LL;
const int64 fpt_exponent_accessor<fpt64>::kMaxExponent = 1024LL;
const int64 fpt_exponent_accessor<fpt64>::kMaxSignificantExpDif = 54;
@@ -101,173 +102,172 @@
template <typename _fpt>
class extended_exponent_fpt {
public:
- typedef _fpt fpt_type;
- typedef int64 exp_type;
- typedef fpt_exponent_accessor<fpt_type> fea;
-
- explicit extended_exponent_fpt(fpt_type value) {
- if (value == 0.0) {
- exponent_ = 0;
- value_ = 0.0;
- } else {
- exponent_ = fea::set_exponent(value, 0);
- value_ = value;
- }
- }
-
- extended_exponent_fpt(fpt_type value, exp_type exponent) {
- if (value == 0.0) {
- exponent_ = 0;
- value_ = 0.0;
- } else {
- exponent_ = fea::set_exponent(value, 0) + exponent;
- value_ = value;
- }
- }
-
- bool is_pos() const {
- return value_ > 0;
- }
-
- bool is_neg() const {
- return value_ < 0;
- }
-
- bool is_zero() const {
- return value_ == 0;
- }
-
- extended_exponent_fpt operator-() const {
- return extended_exponent_fpt(-value_, exponent_);
- }
-
- extended_exponent_fpt operator+(const extended_exponent_fpt& that) const {
- if (this->value_ == 0.0 ||
- that.exponent_ > this->exponent_ + fea::kMaxSignificantExpDif) {
- return that;
- }
- if (that.value_ == 0.0 ||
- this->exponent_ > that.exponent_ + fea::kMaxSignificantExpDif) {
- return *this;
- }
- if (this->exponent_ >= that.exponent_) {
- exp_type exp_dif = this->exponent_ - that.exponent_;
- fpt_type value = this->value_;
- fea::set_exponent(value, exp_dif);
- value += that.value_;
- return extended_exponent_fpt(value, that.exponent_);
- } else {
- exp_type exp_dif = that.exponent_ - this->exponent_;
- fpt_type value = that.value_;
- fea::set_exponent(value, exp_dif);
- value += this->value_;
- return extended_exponent_fpt(value, this->exponent_);
- }
- }
-
- extended_exponent_fpt operator-(const extended_exponent_fpt& that) const {
- if (this->value_ == 0.0 ||
- that.exponent_ > this->exponent_ + fea::kMaxSignificantExpDif) {
- return extended_exponent_fpt(-that.value_, that.exponent_);
- }
- if (that.value_ == 0.0 ||
- this->exponent_ > that.exponent_ + fea::kMaxSignificantExpDif) {
- return *this;
- }
- if (this->exponent_ >= that.exponent_) {
- exp_type exp_dif = this->exponent_ - that.exponent_;
- fpt_type value = this->value_;
- fea::set_exponent(value, exp_dif);
- value -= that.value_;
- return extended_exponent_fpt(value, that.exponent_);
- } else {
- exp_type exp_dif = that.exponent_ - this->exponent_;
- fpt_type value = -that.value_;
- fea::set_exponent(value, exp_dif);
- value += this->value_;
- return extended_exponent_fpt(value, this->exponent_);
- }
- }
-
- extended_exponent_fpt operator*(const extended_exponent_fpt& that) const {
- fpt_type value = this->value_ * that.value_;
- exp_type exponent = this->exponent_ + that.exponent_;
- return extended_exponent_fpt(value, exponent);
- }
-
- extended_exponent_fpt operator/(const extended_exponent_fpt& that) const {
- fpt_type value = this->value_ / that.value_;
- exp_type exponent = this->exponent_ - that.exponent_;
- return extended_exponent_fpt(value, exponent);
- }
-
- extended_exponent_fpt& operator+=(const extended_exponent_fpt& that) {
- return *this = *this + that;
- }
-
- extended_exponent_fpt& operator-=(const extended_exponent_fpt& that) {
- return *this = *this - that;
- }
-
- extended_exponent_fpt& operator*=(const extended_exponent_fpt& that) {
- return *this = *this * that;
- }
-
- extended_exponent_fpt& operator/=(const extended_exponent_fpt& that) {
- return *this = *this / that;
- }
-
- extended_exponent_fpt sqrt() const {
- fpt_type val = value_;
- exp_type exp = exponent_;
- if (exp & 1) {
- val *= 2.0;
- --exp;
- }
- return extended_exponent_fpt(std::sqrt(val), exp >> 1);
- }
-
- fpt_type d() const {
- fpt_type ret_val = value_;
- exp_type exp = exponent_;
- if (ret_val == 0.0) {
- return ret_val;
- }
- if (exp >= fea::kMaxExponent) {
- ret_val = 1.0;
- exp = fea::kMaxExponent;
- } else if (exp <= fea::kMinExponent) {
- ret_val = 1.0;
- exp = fea::kMinExponent;
- }
- fea::set_exponent(ret_val, exp);
- return ret_val;
- }
+ typedef _fpt fpt_type;
+ typedef int64 exp_type;
+ typedef fpt_exponent_accessor<fpt_type> fea;
+
+ explicit extended_exponent_fpt(fpt_type value) {
+ if (value == 0.0) {
+ exponent_ = 0;
+ value_ = 0.0;
+ } else {
+ exponent_ = fea::set_exponent(value, 0);
+ value_ = value;
+ }
+ }
+
+ extended_exponent_fpt(fpt_type value, exp_type exponent) {
+ if (value == 0.0) {
+ exponent_ = 0;
+ value_ = 0.0;
+ } else {
+ exponent_ = fea::set_exponent(value, 0) + exponent;
+ value_ = value;
+ }
+ }
+
+ bool is_pos() const {
+ return value_ > 0;
+ }
+
+ bool is_neg() const {
+ return value_ < 0;
+ }
+
+ bool is_zero() const {
+ return value_ == 0;
+ }
+
+ extended_exponent_fpt operator-() const {
+ return extended_exponent_fpt(-value_, exponent_);
+ }
+
+ extended_exponent_fpt operator+(const extended_exponent_fpt& that) const {
+ if (this->value_ == 0.0 ||
+ that.exponent_ > this->exponent_ + fea::kMaxSignificantExpDif) {
+ return that;
+ }
+ if (that.value_ == 0.0 ||
+ this->exponent_ > that.exponent_ + fea::kMaxSignificantExpDif) {
+ return *this;
+ }
+ if (this->exponent_ >= that.exponent_) {
+ exp_type exp_dif = this->exponent_ - that.exponent_;
+ fpt_type value = this->value_;
+ fea::set_exponent(value, exp_dif);
+ value += that.value_;
+ return extended_exponent_fpt(value, that.exponent_);
+ } else {
+ exp_type exp_dif = that.exponent_ - this->exponent_;
+ fpt_type value = that.value_;
+ fea::set_exponent(value, exp_dif);
+ value += this->value_;
+ return extended_exponent_fpt(value, this->exponent_);
+ }
+ }
+
+ extended_exponent_fpt operator-(const extended_exponent_fpt& that) const {
+ if (this->value_ == 0.0 ||
+ that.exponent_ > this->exponent_ + fea::kMaxSignificantExpDif) {
+ return extended_exponent_fpt(-that.value_, that.exponent_);
+ }
+ if (that.value_ == 0.0 ||
+ this->exponent_ > that.exponent_ + fea::kMaxSignificantExpDif) {
+ return *this;
+ }
+ if (this->exponent_ >= that.exponent_) {
+ exp_type exp_dif = this->exponent_ - that.exponent_;
+ fpt_type value = this->value_;
+ fea::set_exponent(value, exp_dif);
+ value -= that.value_;
+ return extended_exponent_fpt(value, that.exponent_);
+ } else {
+ exp_type exp_dif = that.exponent_ - this->exponent_;
+ fpt_type value = -that.value_;
+ fea::set_exponent(value, exp_dif);
+ value += this->value_;
+ return extended_exponent_fpt(value, this->exponent_);
+ }
+ }
+
+ extended_exponent_fpt operator*(const extended_exponent_fpt& that) const {
+ fpt_type value = this->value_ * that.value_;
+ exp_type exponent = this->exponent_ + that.exponent_;
+ return extended_exponent_fpt(value, exponent);
+ }
+
+ extended_exponent_fpt operator/(const extended_exponent_fpt& that) const {
+ fpt_type value = this->value_ / that.value_;
+ exp_type exponent = this->exponent_ - that.exponent_;
+ return extended_exponent_fpt(value, exponent);
+ }
+
+ extended_exponent_fpt& operator+=(const extended_exponent_fpt& that) {
+ return *this = *this + that;
+ }
+
+ extended_exponent_fpt& operator-=(const extended_exponent_fpt& that) {
+ return *this = *this - that;
+ }
+
+ extended_exponent_fpt& operator*=(const extended_exponent_fpt& that) {
+ return *this = *this * that;
+ }
+
+ extended_exponent_fpt& operator/=(const extended_exponent_fpt& that) {
+ return *this = *this / that;
+ }
+
+ extended_exponent_fpt sqrt() const {
+ fpt_type val = value_;
+ exp_type exp = exponent_;
+ if (exp & 1) {
+ val *= 2.0;
+ --exp;
+ }
+ return extended_exponent_fpt(std::sqrt(val), exp >> 1);
+ }
+
+ fpt_type d() const {
+ fpt_type ret_val = value_;
+ exp_type exp = exponent_;
+ if (ret_val == 0.0)
+ return ret_val;
+ if (exp >= fea::kMaxExponent) {
+ ret_val = 1.0;
+ exp = fea::kMaxExponent;
+ } else if (exp <= fea::kMinExponent) {
+ ret_val = 1.0;
+ exp = fea::kMinExponent;
+ }
+ fea::set_exponent(ret_val, exp);
+ return ret_val;
+ }
private:
- fpt_type value_;
- exp_type exponent_;
+ fpt_type value_;
+ exp_type exponent_;
};
typedef extended_exponent_fpt<double> efpt64;
template <typename _fpt>
extended_exponent_fpt<_fpt> get_sqrt(const extended_exponent_fpt<_fpt>& that) {
- return that.sqrt();
+ return that.sqrt();
}
template <typename _fpt>
bool is_pos(const extended_exponent_fpt<_fpt>& that) {
- return that.is_pos();
+ return that.is_pos();
}
template <typename _fpt>
bool is_neg(const extended_exponent_fpt<_fpt>& that) {
- return that.is_neg();
+ return that.is_neg();
}
template <typename _fpt>
bool is_zero(const extended_exponent_fpt<_fpt>& that) {
- return that.is_zero();
+ return that.is_zero();
}
// Very efficient stack allocated big integer class.
@@ -275,386 +275,371 @@
template<size_t N>
class extended_int {
public:
- static const uint64 kUInt64LowMask;
- static const uint64 kUInt64HighMask;
-
- extended_int() {}
-
- extended_int(int32 that) {
- if (that > 0) {
- this->chunks_[0] = that;
- this->count_ = 1;
- } else if (that < 0) {
- this->chunks_[0] = -that;
- this->count_ = -1;
- } else {
- this->count_ = 0;
- }
- }
-
- extended_int(int64 that) {
- if (that > 0) {
- this->chunks_[0] = static_cast<uint32>(that & kUInt64LowMask);
- this->chunks_[1] = that >> 32;
- this->count_ = this->chunks_[1] ? 2 : 1;
- } else if (that < 0) {
- that = -that;
- this->chunks_[0] = static_cast<uint32>(that & kUInt64LowMask);
- this->chunks_[1] = that >> 32;
- this->count_ = this->chunks_[1] ? -2 : -1;
- } else {
- this->count_ = 0;
- }
- }
-
- extended_int(const std::vector<uint32>& chunks, bool plus = true) {
- this->count_ = static_cast<int32>((std::min)(N, chunks.size()));
- for (int i = 0; i < this->count_; ++i) {
- this->chunks_[i] = chunks[chunks.size() - i - 1];
- }
- if (!plus) {
- this->count_ = -this->count_;
- }
- }
-
- template <size_t M>
- extended_int(const extended_int<M>& that) {
- if (that.size() > N) return;
- this->count_ = that.count();
- memcpy(this->chunks_, that.chunks(), that.size() * sizeof(uint32));
- }
-
- extended_int& operator=(int32 that) {
- if (that > 0) {
- this->chunks_[0] = that;
- this->count_ = 1;
- } else if (that < 0) {
- this->chunks_[0] = -that;
- this->count_ = -1;
- } else {
- this->count_ = 0;
- }
- return *this;
- }
-
- extended_int& operator=(int64 that) {
- if (that > 0) {
- this->chunks_[0] = static_cast<uint32>(that & kUInt64LowMask);
- this->chunks_[1] = that >> 32;
- this->count_ = this->chunks_[1] ? 2 : 1;
- } else if (that < 0) {
- that = -that;
- this->chunks_[0] = static_cast<uint32>(that & kUInt64LowMask);
- this->chunks_[1] = that >> 32;
- this->count_ = this->chunks_[1] ? -2 : -1;
- } else {
- this->count_ = 0;
- }
- return *this;
- }
-
- template <size_t M>
- extended_int& operator=(const extended_int<M>& that) {
- if (that.size() > N) return;
- this->count_ = that.count();
- memcpy(this->chunks_, that.chunks(), that.size() * sizeof(uint32));
- return *this;
- }
+ static const uint64 kUInt64LowMask;
+ static const uint64 kUInt64HighMask;
- bool is_pos() const {
- return this->count_ > 0;
- }
+ extended_int() {}
- bool is_neg() const {
- return this->count_ < 0;
- }
-
- bool is_zero() const {
- return this->count_ == 0;
- }
-
- template <size_t M>
- bool operator==(const extended_int<M>& that) const {
- if (this->count_ != that.count()) {
- return false;
- }
- for (size_t i = 0; i < this->size(); ++i) {
- if (this->chunks_[i] != that.chunks()[i]) {
- return false;
- }
- }
- return true;
- }
-
- template <size_t M>
- bool operator!=(const extended_int<M>& that) const {
- return !(*this == that);
- }
-
- template <size_t M>
- bool operator<(const extended_int<M>& that) const {
- if (this->count_ != that.count()) {
- return this->count_ < that.count();
- }
- size_t i = this->size();
- if (!i) {
- return false;
- }
- do {
- --i;
- if (this->chunks_[i] != that.chunks()[i]) {
- return (this->chunks_[i] < that.chunks()[i]) ^ (this->count_ < 0);
- }
- } while (i);
+ extended_int(int32 that) {
+ if (that > 0) {
+ this->chunks_[0] = that;
+ this->count_ = 1;
+ } else if (that < 0) {
+ this->chunks_[0] = -that;
+ this->count_ = -1;
+ } else {
+ this->count_ = 0;
+ }
+ }
+
+ extended_int(int64 that) {
+ if (that > 0) {
+ this->chunks_[0] = static_cast<uint32>(that & kUInt64LowMask);
+ this->chunks_[1] = that >> 32;
+ this->count_ = this->chunks_[1] ? 2 : 1;
+ } else if (that < 0) {
+ that = -that;
+ this->chunks_[0] = static_cast<uint32>(that & kUInt64LowMask);
+ this->chunks_[1] = that >> 32;
+ this->count_ = this->chunks_[1] ? -2 : -1;
+ } else {
+ this->count_ = 0;
+ }
+ }
+
+ extended_int(const std::vector<uint32>& chunks, bool plus = true) {
+ this->count_ = static_cast<int32>((std::min)(N, chunks.size()));
+ for (int i = 0; i < this->count_; ++i)
+ this->chunks_[i] = chunks[chunks.size() - i - 1];
+ if (!plus)
+ this->count_ = -this->count_;
+ }
+
+ template <size_t M>
+ extended_int(const extended_int<M>& that) {
+ if (that.size() > N) return;
+ this->count_ = that.count();
+ memcpy(this->chunks_, that.chunks(), that.size() * sizeof(uint32));
+ }
+
+ extended_int& operator=(int32 that) {
+ if (that > 0) {
+ this->chunks_[0] = that;
+ this->count_ = 1;
+ } else if (that < 0) {
+ this->chunks_[0] = -that;
+ this->count_ = -1;
+ } else {
+ this->count_ = 0;
+ }
+ return *this;
+ }
+
+ extended_int& operator=(int64 that) {
+ if (that > 0) {
+ this->chunks_[0] = static_cast<uint32>(that & kUInt64LowMask);
+ this->chunks_[1] = that >> 32;
+ this->count_ = this->chunks_[1] ? 2 : 1;
+ } else if (that < 0) {
+ that = -that;
+ this->chunks_[0] = static_cast<uint32>(that & kUInt64LowMask);
+ this->chunks_[1] = that >> 32;
+ this->count_ = this->chunks_[1] ? -2 : -1;
+ } else {
+ this->count_ = 0;
+ }
+ return *this;
+ }
+
+ template <size_t M>
+ extended_int& operator=(const extended_int<M>& that) {
+ if (that.size() > N) return;
+ this->count_ = that.count();
+ memcpy(this->chunks_, that.chunks(), that.size() * sizeof(uint32));
+ return *this;
+ }
+
+ bool is_pos() const {
+ return this->count_ > 0;
+ }
+
+ bool is_neg() const {
+ return this->count_ < 0;
+ }
+
+ bool is_zero() const {
+ return this->count_ == 0;
+ }
+
+ template <size_t M>
+ bool operator==(const extended_int<M>& that) const {
+ if (this->count_ != that.count())
+ return false;
+ for (size_t i = 0; i < this->size(); ++i)
+ if (this->chunks_[i] != that.chunks()[i])
return false;
- }
-
- template <size_t M>
- bool operator>(const extended_int<M>& that) const {
- return that < *this;
- }
-
- template <size_t M>
- bool operator<=(const extended_int<M>& that) const {
- return !(that < *this);
- }
-
- template <size_t M>
- bool operator>=(const extended_int<M>& that) const {
- return !(*this < that);
- }
-
- extended_int operator-() const {
- extended_int ret_val = *this;
- ret_val.neg();
- return ret_val;
- }
-
- void neg() {
- this->count_ = -this->count_;
- }
-
- template <size_t M>
- extended_int<(N>M?N:M)> operator+(const extended_int<M>& that) const {
- extended_int<(N>M?N:M)> ret_val;
- ret_val.add(*this, that);
- return ret_val;
- }
+ return true;
+ }
- template <size_t N1, size_t N2>
- void add(const extended_int<N1>& e1, const extended_int<N2>& e2) {
- if (!e1.count()) {
- *this = e2;
- return;
- }
- if (!e2.count()) {
- *this = e1;
- return;
- }
- if ((e1.count() > 0) ^ (e2.count() > 0)) {
- dif(e1.chunks(), e1.size(), e2.chunks(), e2.size());
- } else {
- add(e1.chunks(), e1.size(), e2.chunks(), e2.size());
- }
- if (e1.count() < 0) {
- this->count_ = -this->count_;
- }
- }
-
- template <size_t M>
- extended_int<(N>M?N:M)> operator-(const extended_int<M>& that) const {
- extended_int<(N>M?N:M)> ret_val;
- ret_val.dif(*this, that);
- return ret_val;
- }
-
- template <size_t N1, size_t N2>
- void dif(const extended_int<N1>& e1, const extended_int<N2> &e2) {
- if (!e1.count()) {
- *this = e2;
- this->count_ = -this->count_;
- return;
- }
- if (!e2.count()) {
- *this = e1;
- return;
- }
- if ((e1.count() > 0) ^ (e2.count() > 0)) {
- add(e1.chunks(), e1.size(), e2.chunks(), e2.size());
- } else {
- dif(e1.chunks(), e1.size(), e2.chunks(), e2.size());
- }
- if (e1.count() < 0) {
- this->count_ = -this->count_;
- }
- }
-
- extended_int<N> operator*(int32 that) const {
- extended_int<N> temp(that);
- return (*this) * temp;
- }
-
- extended_int<N> operator*(int64 that) const {
- extended_int<N> temp(that);
- return (*this) * temp;
- }
-
- template <size_t M>
- extended_int<(N>M?N:M)> operator*(const extended_int<M>& that) const {
- extended_int<(N>M?N:M)> ret_val;
- ret_val.mul(*this, that);
- return ret_val;
- }
-
- template <size_t N1, size_t N2>
- void mul(const extended_int<N1>& e1, const extended_int<N2>& e2) {
- if (!e1.count() || !e2.count()) {
- this->count_ = 0;
- return;
- }
- mul(e1.chunks(), e1.size(), e2.chunks(), e2.size());
- if ((e1.count() > 0) ^ (e2.count() > 0)) {
- this->count_ = -this->count_;
- }
- }
-
- const uint32* chunks() const {
- return chunks_;
- }
-
- int32 count() const {
- return count_;
- }
-
- size_t size() const {
- return (std::abs)(count_);
- }
-
- std::pair<fpt64, int64> p() const {
- std::pair<fpt64, int64> ret_val(0, 0);
- size_t sz = this->size();
- if (!sz) {
- return ret_val;
- } else {
- if (sz == 1) {
- ret_val.first = static_cast<fpt64>(this->chunks_[0]);
- } else if (sz == 2) {
- ret_val.first = static_cast<fpt64>(this->chunks_[1]) *
- static_cast<fpt64>(0x100000000LL) +
- static_cast<fpt64>(this->chunks_[0]);
- } else {
- for (size_t i = 1; i <= 3; ++i) {
- ret_val.first *= static_cast<fpt64>(0x100000000LL);
- ret_val.first += static_cast<fpt64>(this->chunks_[sz - i]);
- }
- ret_val.second = (sz - 3) << 5;
- }
- }
- if (this->count_ < 0) {
- ret_val.first = -ret_val.first;
- }
- return ret_val;
- }
-
- fpt64 d() const {
- std::pair<fpt64, int64> p = this->p();
- extended_exponent_fpt<fpt64> efpt(p.first, p.second);
- return efpt.d();
- }
+ template <size_t M>
+ bool operator!=(const extended_int<M>& that) const {
+ return !(*this == that);
+ }
+
+ template <size_t M>
+ bool operator<(const extended_int<M>& that) const {
+ if (this->count_ != that.count())
+ return this->count_ < that.count();
+ size_t i = this->size();
+ if (!i)
+ return false;
+ do {
+ --i;
+ if (this->chunks_[i] != that.chunks()[i])
+ return (this->chunks_[i] < that.chunks()[i]) ^ (this->count_ < 0);
+ } while (i);
+ return false;
+ }
+
+ template <size_t M>
+ bool operator>(const extended_int<M>& that) const {
+ return that < *this;
+ }
+
+ template <size_t M>
+ bool operator<=(const extended_int<M>& that) const {
+ return !(that < *this);
+ }
+
+ template <size_t M>
+ bool operator>=(const extended_int<M>& that) const {
+ return !(*this < that);
+ }
+
+ extended_int operator-() const {
+ extended_int ret_val = *this;
+ ret_val.neg();
+ return ret_val;
+ }
+
+ void neg() {
+ this->count_ = -this->count_;
+ }
+
+ template <size_t M>
+ extended_int<(N>M?N:M)> operator+(const extended_int<M>& that) const {
+ extended_int<(N>M?N:M)> ret_val;
+ ret_val.add(*this, that);
+ return ret_val;
+ }
+
+ template <size_t N1, size_t N2>
+ void add(const extended_int<N1>& e1, const extended_int<N2>& e2) {
+ if (!e1.count()) {
+ *this = e2;
+ return;
+ }
+ if (!e2.count()) {
+ *this = e1;
+ return;
+ }
+ if ((e1.count() > 0) ^ (e2.count() > 0)) {
+ dif(e1.chunks(), e1.size(), e2.chunks(), e2.size());
+ } else {
+ add(e1.chunks(), e1.size(), e2.chunks(), e2.size());
+ }
+ if (e1.count() < 0)
+ this->count_ = -this->count_;
+ }
+
+ template <size_t M>
+ extended_int<(N>M?N:M)> operator-(const extended_int<M>& that) const {
+ extended_int<(N>M?N:M)> ret_val;
+ ret_val.dif(*this, that);
+ return ret_val;
+ }
+
+ template <size_t N1, size_t N2>
+ void dif(const extended_int<N1>& e1, const extended_int<N2> &e2) {
+ if (!e1.count()) {
+ *this = e2;
+ this->count_ = -this->count_;
+ return;
+ }
+ if (!e2.count()) {
+ *this = e1;
+ return;
+ }
+ if ((e1.count() > 0) ^ (e2.count() > 0)) {
+ add(e1.chunks(), e1.size(), e2.chunks(), e2.size());
+ } else {
+ dif(e1.chunks(), e1.size(), e2.chunks(), e2.size());
+ }
+ if (e1.count() < 0)
+ this->count_ = -this->count_;
+ }
+
+ extended_int<N> operator*(int32 that) const {
+ extended_int<N> temp(that);
+ return (*this) * temp;
+ }
+
+ extended_int<N> operator*(int64 that) const {
+ extended_int<N> temp(that);
+ return (*this) * temp;
+ }
+
+ template <size_t M>
+ extended_int<(N>M?N:M)> operator*(const extended_int<M>& that) const {
+ extended_int<(N>M?N:M)> ret_val;
+ ret_val.mul(*this, that);
+ return ret_val;
+ }
+
+ template <size_t N1, size_t N2>
+ void mul(const extended_int<N1>& e1, const extended_int<N2>& e2) {
+ if (!e1.count() || !e2.count()) {
+ this->count_ = 0;
+ return;
+ }
+ mul(e1.chunks(), e1.size(), e2.chunks(), e2.size());
+ if ((e1.count() > 0) ^ (e2.count() > 0))
+ this->count_ = -this->count_;
+ }
+
+ const uint32* chunks() const {
+ return chunks_;
+ }
+
+ int32 count() const {
+ return count_;
+ }
+
+ size_t size() const {
+ return (std::abs)(count_);
+ }
+
+ std::pair<fpt64, int64> p() const {
+ std::pair<fpt64, int64> ret_val(0, 0);
+ size_t sz = this->size();
+ if (!sz) {
+ return ret_val;
+ } else {
+ if (sz == 1) {
+ ret_val.first = static_cast<fpt64>(this->chunks_[0]);
+ } else if (sz == 2) {
+ ret_val.first = static_cast<fpt64>(this->chunks_[1]) *
+ static_cast<fpt64>(0x100000000LL) +
+ static_cast<fpt64>(this->chunks_[0]);
+ } else {
+ for (size_t i = 1; i <= 3; ++i) {
+ ret_val.first *= static_cast<fpt64>(0x100000000LL);
+ ret_val.first += static_cast<fpt64>(this->chunks_[sz - i]);
+ }
+ ret_val.second = (sz - 3) << 5;
+ }
+ }
+ if (this->count_ < 0)
+ ret_val.first = -ret_val.first;
+ return ret_val;
+ }
+
+ fpt64 d() const {
+ std::pair<fpt64, int64> p = this->p();
+ extended_exponent_fpt<fpt64> efpt(p.first, p.second);
+ return efpt.d();
+ }
private:
- void add(const uint32* c1, size_t sz1, const uint32* c2, size_t sz2) {
- if (sz1 < sz2) {
- add(c2, sz2, c1, sz1);
- return;
- }
- this->count_ = sz1;
- uint64 temp = 0;
- for (size_t i = 0; i < sz2; ++i) {
- temp += static_cast<uint64>(c1[i]) +
- static_cast<uint64>(c2[i]);
- this->chunks_[i] = static_cast<uint32>(temp & kUInt64LowMask);
- temp >>= 32;
- }
- for (size_t i = sz2; i < sz1; ++i) {
- temp += static_cast<uint64>(c1[i]);
- this->chunks_[i] = static_cast<uint32>(temp & kUInt64LowMask);
- temp >>= 32;
- }
- if (temp && (this->count_ != N)) {
- this->chunks_[this->count_] = static_cast<uint32>(temp & kUInt64LowMask);
- ++this->count_;
- }
+ void add(const uint32* c1, size_t sz1, const uint32* c2, size_t sz2) {
+ if (sz1 < sz2) {
+ add(c2, sz2, c1, sz1);
+ return;
+ }
+ this->count_ = sz1;
+ uint64 temp = 0;
+ for (size_t i = 0; i < sz2; ++i) {
+ temp += static_cast<uint64>(c1[i]) + static_cast<uint64>(c2[i]);
+ this->chunks_[i] = static_cast<uint32>(temp & kUInt64LowMask);
+ temp >>= 32;
+ }
+ for (size_t i = sz2; i < sz1; ++i) {
+ temp += static_cast<uint64>(c1[i]);
+ this->chunks_[i] = static_cast<uint32>(temp & kUInt64LowMask);
+ temp >>= 32;
+ }
+ if (temp && (this->count_ != N)) {
+ this->chunks_[this->count_] = static_cast<uint32>(temp & kUInt64LowMask);
+ ++this->count_;
+ }
+ }
+
+ void dif(const uint32* c1, size_t sz1,
+ const uint32* c2, size_t sz2, bool rec = false) {
+ if (sz1 < sz2) {
+ dif(c2, sz2, c1, sz1, true);
+ this->count_ = -this->count_;
+ return;
+ } else if ((sz1 == sz2) && !rec) {
+ do {
+ --sz1;
+ if (c1[sz1] < c2[sz1]) {
+ ++sz1;
+ dif(c2, sz1, c1, sz1, true);
+ this->count_ = -this->count_;
+ return;
+ } else if (c1[sz1] > c2[sz1]) {
+ ++sz1;
+ break;
+ }
+ } while (sz1);
+ if (!sz1) {
+ this->count_ = 0;
+ return;
+ }
+ sz2 = sz1;
+ }
+ this->count_ = sz1-1;
+ bool flag = false;
+ for (size_t i = 0; i < sz2; ++i) {
+ this->chunks_[i] = c1[i] - c2[i] - (flag?1:0);
+ flag = (c1[i] < c2[i]) || ((c1[i] == c2[i]) && flag);
+ }
+ for (size_t i = sz2; i < sz1; ++i) {
+ this->chunks_[i] = c1[i] - (flag?1:0);
+ flag = !c1[i] && flag;
+ }
+ if (this->chunks_[this->count_])
+ ++this->count_;
+ }
+
+ void mul(const uint32* c1, size_t sz1, const uint32* c2, size_t sz2) {
+ uint64 cur = 0, nxt, tmp;
+ this->count_ = static_cast<int32>((std::min)(N, sz1 + sz2 - 1));
+ for (size_t shift = 0; shift < static_cast<size_t>(this->count_);
+ ++shift) {
+ nxt = 0;
+ for (size_t first = 0; first <= shift; ++first) {
+ if (first >= sz1)
+ break;
+ size_t second = shift - first;
+ if (second >= sz2)
+ continue;
+ tmp = static_cast<uint64>(c1[first]) * static_cast<uint64>(c2[second]);
+ cur += tmp & kUInt64LowMask;
+ nxt += tmp >> 32;
+ }
+ this->chunks_[shift] = static_cast<uint32>(cur & kUInt64LowMask);
+ cur = nxt + (cur >> 32);
+ }
+ if (cur && (this->count_ != N)) {
+ this->chunks_[this->count_] = static_cast<uint32>(cur & kUInt64LowMask);
+ ++this->count_;
}
+ }
- void dif(const uint32* c1, size_t sz1, const uint32* c2, size_t sz2, bool rec = false) {
- if (sz1 < sz2) {
- dif(c2, sz2, c1, sz1, true);
- this->count_ = -this->count_;
- return;
- } else if ((sz1 == sz2) && !rec) {
- do {
- --sz1;
- if (c1[sz1] < c2[sz1]) {
- ++sz1;
- dif(c2, sz1, c1, sz1, true);
- this->count_ = -this->count_;
- return;
- } else if (c1[sz1] > c2[sz1]) {
- ++sz1;
- break;
- }
- } while (sz1);
- if (!sz1) {
- this->count_ = 0;
- return;
- }
- sz2 = sz1;
- }
- this->count_ = sz1-1;
- bool flag = false;
- for (size_t i = 0; i < sz2; ++i) {
- this->chunks_[i] = c1[i] - c2[i] - (flag?1:0);
- flag = (c1[i] < c2[i]) || ((c1[i] == c2[i]) && flag);
- }
- for (size_t i = sz2; i < sz1; ++i) {
- this->chunks_[i] = c1[i] - (flag?1:0);
- flag = !c1[i] && flag;
- }
- if (this->chunks_[this->count_]) {
- ++this->count_;
- }
- }
-
- void mul(const uint32* c1, size_t sz1, const uint32* c2, size_t sz2) {
- uint64 cur = 0, nxt, tmp;
- this->count_ = static_cast<int32>((std::min)(N, sz1 + sz2 - 1));
- for (size_t shift = 0; shift < static_cast<size_t>(this->count_); ++shift) {
- nxt = 0;
- for (size_t first = 0; first <= shift; ++first) {
- if (first >= sz1) {
- break;
- }
- size_t second = shift - first;
- if (second >= sz2) {
- continue;
- }
- tmp = static_cast<uint64>(c1[first]) *
- static_cast<uint64>(c2[second]);
- cur += tmp & kUInt64LowMask;
- nxt += tmp >> 32;
- }
- this->chunks_[shift] = static_cast<uint32>(cur & kUInt64LowMask);
- cur = nxt + (cur >> 32);
- }
- if (cur && (this->count_ != N)) {
- this->chunks_[this->count_] = static_cast<uint32>(cur & kUInt64LowMask);
- ++this->count_;
- }
- }
-
- uint32 chunks_[N];
- int32 count_;
+ uint32 chunks_[N];
+ int32 count_;
};
template <size_t N>
@@ -664,61 +649,61 @@
template <size_t N>
bool is_pos(const extended_int<N>& that) {
- return that.count() > 0;
+ return that.count() > 0;
}
template <size_t N>
bool is_neg(const extended_int<N>& that) {
- return that.count() < 0;
+ return that.count() < 0;
}
template <size_t N>
bool is_zero(const extended_int<N>& that) {
- return !that.count();
+ return !that.count();
}
struct type_converter_fpt {
- template <typename T>
- fpt64 operator()(const T& that) const {
- return static_cast<fpt64>(that);
- }
-
- template <size_t N>
- fpt64 operator()(const extended_int<N>& that) const {
- return that.d();
- }
-
- fpt64 operator()(const extended_exponent_fpt<fpt64>& that) const {
- return that.d();
- }
+ template <typename T>
+ fpt64 operator()(const T& that) const {
+ return static_cast<fpt64>(that);
+ }
+
+ template <size_t N>
+ fpt64 operator()(const extended_int<N>& that) const {
+ return that.d();
+ }
+
+ fpt64 operator()(const extended_exponent_fpt<fpt64>& that) const {
+ return that.d();
+ }
};
struct type_converter_efpt {
- template <size_t N>
- extended_exponent_fpt<fpt64> operator()(const extended_int<N>& that) const {
- std::pair<fpt64, int64> p = that.p();
- return extended_exponent_fpt<fpt64>(p.first, p.second);
- }
+ template <size_t N>
+ extended_exponent_fpt<fpt64> operator()(const extended_int<N>& that) const {
+ std::pair<fpt64, int64> p = that.p();
+ return extended_exponent_fpt<fpt64>(p.first, p.second);
+ }
};
// Voronoi coordinate type traits make it possible to extend algorithm
-// input coordinate range to any user provided integer and algorithm
+// input coordinate range to any user provided integer type and algorithm
// output coordinate range to any ieee-754 like floating point type.
template <typename T>
struct voronoi_ctype_traits;
template <>
struct voronoi_ctype_traits<int32> {
- typedef int32 int_type;
- typedef int64 int_x2_type;
- typedef uint64 uint_x2_type;
- typedef extended_int<64> big_int_type;
- typedef fpt64 fpt_type;
- typedef extended_exponent_fpt<fpt_type> efpt_type;
- typedef ulp_comparison<fpt_type> ulp_cmp_type;
- typedef type_converter_fpt to_fpt_converter_type;
- typedef type_converter_efpt to_efpt_converter_type;
- enum { ULPS = 64 };
+ typedef int32 int_type;
+ typedef int64 int_x2_type;
+ typedef uint64 uint_x2_type;
+ typedef extended_int<64> big_int_type;
+ typedef fpt64 fpt_type;
+ typedef extended_exponent_fpt<fpt_type> efpt_type;
+ typedef ulp_comparison<fpt_type> ulp_cmp_type;
+ typedef type_converter_fpt to_fpt_converter_type;
+ typedef type_converter_efpt to_efpt_converter_type;
+ enum { ULPS = 64 };
};
} // detail
} // polygon
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-03-23 17:18:24 EDT (Fri, 23 Mar 2012)
@@ -57,192 +57,188 @@
template <typename T>
T get_sqrt(const T& that) {
- return (std::sqrt)(that);
+ return (std::sqrt)(that);
}
template <typename T>
bool is_pos(const T& that) {
- return that > 0;
+ return that > 0;
}
template <typename T>
bool is_neg(const T& that) {
- return that < 0;
+ return that < 0;
}
template <typename T>
bool is_zero(const T& that) {
- return that == 0;
+ return that == 0;
}
template <typename _fpt>
class robust_fpt {
public:
- typedef _fpt floating_point_type;
- typedef _fpt relative_error_type;
+ typedef _fpt floating_point_type;
+ typedef _fpt relative_error_type;
- // Rounding error is at most 1 EPS.
- static const relative_error_type ROUNDING_ERROR;
+ // Rounding error is at most 1 EPS.
+ static const relative_error_type ROUNDING_ERROR;
- robust_fpt() : fpv_(0.0), re_(0.0) {}
- explicit robust_fpt(floating_point_type fpv,
- bool rounded = true) : fpv_(fpv) {
- re_ = rounded ? ROUNDING_ERROR : 0;
- }
- robust_fpt(floating_point_type fpv, relative_error_type error) :
- fpv_(fpv), re_(error) {}
-
- floating_point_type fpv() const { return fpv_; }
- relative_error_type re() const { return re_; }
- relative_error_type ulp() const { return re_; }
-
- robust_fpt& operator=(const robust_fpt &that) {
- this->fpv_ = that.fpv_;
- this->re_ = that.re_;
- return *this;
- }
-
- bool has_pos_value() const {
- return is_pos(fpv_);
- }
-
- bool has_neg_value() const {
- return is_neg(fpv_);
- }
-
- bool has_zero_value() const {
- return is_zero(fpv_);
- }
-
- robust_fpt operator-() const {
- return robust_fpt(-fpv_, re_);
- }
-
- robust_fpt& operator+=(const robust_fpt &that) {
- floating_point_type fpv = this->fpv_ + that.fpv_;
- if ((!is_neg(this->fpv_) && !is_neg(that.fpv_)) ||
- (!is_pos(this->fpv_) && !is_pos(that.fpv_)))
- this->re_ = (std::max)(this->re_, that.re_) + ROUNDING_ERROR;
- else {
- floating_point_type temp =
- (this->fpv_ * this->re_ - that.fpv_ * that.re_) / fpv;
- if (is_neg(temp)) {
- temp = -temp;
- }
- this->re_ = temp + ROUNDING_ERROR;
- }
- this->fpv_ = fpv;
- return *this;
- }
-
- robust_fpt& operator-=(const robust_fpt &that) {
- floating_point_type fpv = this->fpv_ - that.fpv_;
- if ((!is_neg(this->fpv_) && !is_pos(that.fpv_)) ||
- (!is_pos(this->fpv_) && !is_neg(that.fpv_)))
- this->re_ = (std::max)(this->re_, that.re_) + ROUNDING_ERROR;
- else {
- floating_point_type temp =
- (this->fpv_ * this->re_ + that.fpv_ * that.re_) / fpv;
- if (is_neg(temp)) {
- temp = -temp;
- }
- this->re_ = temp + ROUNDING_ERROR;
- }
- this->fpv_ = fpv;
- return *this;
- }
-
- robust_fpt& operator*=(const robust_fpt &that) {
- this->re_ += that.re_ + ROUNDING_ERROR;
- this->fpv_ *= that.fpv_;
- return *this;
- }
-
- robust_fpt& operator/=(const robust_fpt &that) {
- this->re_ += that.re_ + ROUNDING_ERROR;
- this->fpv_ /= that.fpv_;
- return *this;
- }
-
- robust_fpt operator+(const robust_fpt &that) const {
- floating_point_type fpv = this->fpv_ + that.fpv_;
- relative_error_type re;
- if ((!is_neg(this->fpv_) && !is_neg(that.fpv_)) ||
- (!is_pos(this->fpv_) && !is_pos(that.fpv_)))
- re = (std::max)(this->re_, that.re_) + ROUNDING_ERROR;
- else {
- floating_point_type temp =
- (this->fpv_ * this->re_ - that.fpv_ * that.re_) / fpv;
- if (is_neg(temp)) {
- temp = -temp;
- }
- re = temp + ROUNDING_ERROR;
- }
- return robust_fpt(fpv, re);
- }
-
- robust_fpt operator-(const robust_fpt &that) const {
- floating_point_type fpv = this->fpv_ - that.fpv_;
- relative_error_type re;
- if ((!is_neg(this->fpv_) && !is_pos(that.fpv_)) ||
- (!is_pos(this->fpv_) && !is_neg(that.fpv_)))
- re = (std::max)(this->re_, that.re_) + ROUNDING_ERROR;
- else {
- floating_point_type temp =
- (this->fpv_ * this->re_ + that.fpv_ * that.re_) / fpv;
- if (is_neg(temp)) {
- temp = -temp;
- }
- re = temp + ROUNDING_ERROR;
- }
- return robust_fpt(fpv, re);
- }
-
- robust_fpt operator*(const robust_fpt &that) const {
- floating_point_type fpv = this->fpv_ * that.fpv_;
- relative_error_type re = this->re_ + that.re_ + ROUNDING_ERROR;
- return robust_fpt(fpv, re);
- }
-
- robust_fpt operator/(const robust_fpt &that) const {
- floating_point_type fpv = this->fpv_ / that.fpv_;
- relative_error_type re = this->re_ + that.re_ + ROUNDING_ERROR;
- return robust_fpt(fpv, re);
- }
-
- robust_fpt sqrt() const {
- return robust_fpt(get_sqrt(fpv_),
- re_ * static_cast<relative_error_type>(0.5) +
- ROUNDING_ERROR);
- }
+ robust_fpt() : fpv_(0.0), re_(0.0) {}
+ explicit robust_fpt(floating_point_type fpv,
+ bool rounded = true) : fpv_(fpv) {
+ re_ = rounded ? ROUNDING_ERROR : 0;
+ }
+ robust_fpt(floating_point_type fpv, relative_error_type error) :
+ fpv_(fpv), re_(error) {}
+
+ floating_point_type fpv() const { return fpv_; }
+ relative_error_type re() const { return re_; }
+ relative_error_type ulp() const { return re_; }
+
+ robust_fpt& operator=(const robust_fpt &that) {
+ this->fpv_ = that.fpv_;
+ this->re_ = that.re_;
+ return *this;
+ }
+
+ bool has_pos_value() const {
+ return is_pos(fpv_);
+ }
+
+ bool has_neg_value() const {
+ return is_neg(fpv_);
+ }
+
+ bool has_zero_value() const {
+ return is_zero(fpv_);
+ }
+
+ robust_fpt operator-() const {
+ return robust_fpt(-fpv_, re_);
+ }
+
+ robust_fpt& operator+=(const robust_fpt &that) {
+ floating_point_type fpv = this->fpv_ + that.fpv_;
+ if ((!is_neg(this->fpv_) && !is_neg(that.fpv_)) ||
+ (!is_pos(this->fpv_) && !is_pos(that.fpv_)))
+ this->re_ = (std::max)(this->re_, that.re_) + ROUNDING_ERROR;
+ else {
+ floating_point_type temp =
+ (this->fpv_ * this->re_ - that.fpv_ * that.re_) / fpv;
+ if (is_neg(temp))
+ temp = -temp;
+ this->re_ = temp + ROUNDING_ERROR;
+ }
+ this->fpv_ = fpv;
+ return *this;
+ }
+
+ robust_fpt& operator-=(const robust_fpt &that) {
+ floating_point_type fpv = this->fpv_ - that.fpv_;
+ if ((!is_neg(this->fpv_) && !is_pos(that.fpv_)) ||
+ (!is_pos(this->fpv_) && !is_neg(that.fpv_)))
+ this->re_ = (std::max)(this->re_, that.re_) + ROUNDING_ERROR;
+ else {
+ floating_point_type temp =
+ (this->fpv_ * this->re_ + that.fpv_ * that.re_) / fpv;
+ if (is_neg(temp))
+ temp = -temp;
+ this->re_ = temp + ROUNDING_ERROR;
+ }
+ this->fpv_ = fpv;
+ return *this;
+ }
+
+ robust_fpt& operator*=(const robust_fpt &that) {
+ this->re_ += that.re_ + ROUNDING_ERROR;
+ this->fpv_ *= that.fpv_;
+ return *this;
+ }
+
+ robust_fpt& operator/=(const robust_fpt &that) {
+ this->re_ += that.re_ + ROUNDING_ERROR;
+ this->fpv_ /= that.fpv_;
+ return *this;
+ }
+
+ robust_fpt operator+(const robust_fpt &that) const {
+ floating_point_type fpv = this->fpv_ + that.fpv_;
+ relative_error_type re;
+ if ((!is_neg(this->fpv_) && !is_neg(that.fpv_)) ||
+ (!is_pos(this->fpv_) && !is_pos(that.fpv_)))
+ re = (std::max)(this->re_, that.re_) + ROUNDING_ERROR;
+ else {
+ floating_point_type temp =
+ (this->fpv_ * this->re_ - that.fpv_ * that.re_) / fpv;
+ if (is_neg(temp))
+ temp = -temp;
+ re = temp + ROUNDING_ERROR;
+ }
+ return robust_fpt(fpv, re);
+ }
+
+ robust_fpt operator-(const robust_fpt &that) const {
+ floating_point_type fpv = this->fpv_ - that.fpv_;
+ relative_error_type re;
+ if ((!is_neg(this->fpv_) && !is_pos(that.fpv_)) ||
+ (!is_pos(this->fpv_) && !is_neg(that.fpv_)))
+ re = (std::max)(this->re_, that.re_) + ROUNDING_ERROR;
+ else {
+ floating_point_type temp =
+ (this->fpv_ * this->re_ + that.fpv_ * that.re_) / fpv;
+ if (is_neg(temp))
+ temp = -temp;
+ re = temp + ROUNDING_ERROR;
+ }
+ return robust_fpt(fpv, re);
+ }
+
+ robust_fpt operator*(const robust_fpt &that) const {
+ floating_point_type fpv = this->fpv_ * that.fpv_;
+ relative_error_type re = this->re_ + that.re_ + ROUNDING_ERROR;
+ return robust_fpt(fpv, re);
+ }
+
+ robust_fpt operator/(const robust_fpt &that) const {
+ floating_point_type fpv = this->fpv_ / that.fpv_;
+ relative_error_type re = this->re_ + that.re_ + ROUNDING_ERROR;
+ return robust_fpt(fpv, re);
+ }
+
+ robust_fpt sqrt() const {
+ return robust_fpt(get_sqrt(fpv_),
+ re_ * static_cast<relative_error_type>(0.5) +
+ ROUNDING_ERROR);
+ }
private:
- floating_point_type fpv_;
- relative_error_type re_;
+ floating_point_type fpv_;
+ relative_error_type re_;
};
template <typename T>
const typename robust_fpt<T>::relative_error_type
- robust_fpt<T>::ROUNDING_ERROR = 1;
+ robust_fpt<T>::ROUNDING_ERROR = 1;
template <typename T>
robust_fpt<T> get_sqrt(const robust_fpt<T>& that) {
- return that.sqrt();
+ return that.sqrt();
}
template <typename T>
bool is_pos(const robust_fpt<T>& that) {
- return that.has_pos_value();
+ return that.has_pos_value();
}
template <typename T>
bool is_neg(const robust_fpt<T>& that) {
- return that.has_neg_value();
+ return that.has_neg_value();
}
template <typename T>
bool is_zero(const robust_fpt<T>& that) {
- return that.has_zero_value();
+ return that.has_zero_value();
}
// robust_dif consists of two not negative values: value1 and value2.
@@ -253,187 +249,186 @@
template <typename T>
class robust_dif {
public:
- robust_dif() :
+ robust_dif() :
positive_sum_(0),
negative_sum_(0) {}
- robust_dif(const T &value) :
+ robust_dif(const T &value) :
positive_sum_((value>0)?value:0),
negative_sum_((value<0)?-value:0) {}
- robust_dif(const T &pos, const T &neg) :
+ robust_dif(const T &pos, const T &neg) :
positive_sum_(pos),
negative_sum_(neg) {}
- T dif() const {
- return positive_sum_ - negative_sum_;
- }
+ T dif() const {
+ return positive_sum_ - negative_sum_;
+ }
+
+ T pos() const {
+ return positive_sum_;
+ }
+
+ T neg() const {
+ return negative_sum_;
+ }
+
+ robust_dif<T> operator-() const {
+ return robust_dif(negative_sum_, positive_sum_);
+ }
+
+ robust_dif<T> &operator+=(const T &val) {
+ if (!is_neg(val))
+ positive_sum_ += val;
+ else
+ negative_sum_ -= val;
+ return *this;
+ }
+
+ robust_dif<T> &operator+=(const robust_dif<T> &that) {
+ positive_sum_ += that.positive_sum_;
+ negative_sum_ += that.negative_sum_;
+ return *this;
+ }
+
+ robust_dif<T> &operator-=(const T &val) {
+ if (!is_neg(val))
+ negative_sum_ += val;
+ else
+ positive_sum_ -= val;
+ return *this;
+ }
+
+ robust_dif<T> &operator-=(const robust_dif<T> &that) {
+ positive_sum_ += that.negative_sum_;
+ negative_sum_ += that.positive_sum_;
+ return *this;
+ }
- T pos() const {
- return positive_sum_;
- }
-
- T neg() const {
- return negative_sum_;
- }
-
- robust_dif<T> operator-() const {
- return robust_dif(negative_sum_, positive_sum_);
- }
-
- robust_dif<T> &operator+=(const T &val) {
- if (!is_neg(val))
- positive_sum_ += val;
- else
- negative_sum_ -= val;
- return *this;
- }
-
- robust_dif<T> &operator+=(const robust_dif<T> &that) {
- positive_sum_ += that.positive_sum_;
- negative_sum_ += that.negative_sum_;
- return *this;
- }
-
- robust_dif<T> &operator-=(const T &val) {
- if (!is_neg(val))
- negative_sum_ += val;
- else
- positive_sum_ -= val;
- return *this;
- }
-
- robust_dif<T> &operator-=(const robust_dif<T> &that) {
- positive_sum_ += that.negative_sum_;
- negative_sum_ += that.positive_sum_;
- return *this;
- }
-
- robust_dif<T> &operator*=(const T &val) {
- if (!is_neg(val)) {
- positive_sum_ *= val;
- negative_sum_ *= val;
- } else {
- positive_sum_ *= -val;
- negative_sum_ *= -val;
- swap();
- }
- return *this;
- }
-
- robust_dif<T> &operator*=(const robust_dif<T> &that) {
- T positive_sum = this->positive_sum_ * that.positive_sum_ +
- this->negative_sum_ * that.negative_sum_;
- T negative_sum = this->positive_sum_ * that.negative_sum_ +
- this->negative_sum_ * that.positive_sum_;
- positive_sum_ = positive_sum;
- negative_sum_ = negative_sum;
- return *this;
- }
+ robust_dif<T> &operator*=(const T &val) {
+ if (!is_neg(val)) {
+ positive_sum_ *= val;
+ negative_sum_ *= val;
+ } else {
+ positive_sum_ *= -val;
+ negative_sum_ *= -val;
+ swap();
+ }
+ return *this;
+ }
+
+ robust_dif<T> &operator*=(const robust_dif<T> &that) {
+ T positive_sum = this->positive_sum_ * that.positive_sum_ +
+ this->negative_sum_ * that.negative_sum_;
+ T negative_sum = this->positive_sum_ * that.negative_sum_ +
+ this->negative_sum_ * that.positive_sum_;
+ positive_sum_ = positive_sum;
+ negative_sum_ = negative_sum;
+ return *this;
+ }
- robust_dif<T> &operator/=(const T &val) {
- if (!is_neg(val)) {
- positive_sum_ /= val;
- negative_sum_ /= val;
- } else {
- positive_sum_ /= -val;
- negative_sum_ /= -val;
- swap();
- }
- return *this;
+ robust_dif<T> &operator/=(const T &val) {
+ if (!is_neg(val)) {
+ positive_sum_ /= val;
+ negative_sum_ /= val;
+ } else {
+ positive_sum_ /= -val;
+ negative_sum_ /= -val;
+ swap();
}
+ return *this;
+ }
private:
- void swap() {
- (std::swap)(positive_sum_, negative_sum_);
- }
+ void swap() {
+ (std::swap)(positive_sum_, negative_sum_);
+ }
- T positive_sum_;
- T negative_sum_;
+ T positive_sum_;
+ T negative_sum_;
};
template<typename T>
robust_dif<T> operator+(const robust_dif<T>& lhs,
const robust_dif<T>& rhs) {
- return robust_dif<T>(lhs.pos() + rhs.pos(),
- lhs.neg() + rhs.neg());
+ return robust_dif<T>(lhs.pos() + rhs.pos(), lhs.neg() + rhs.neg());
}
template<typename T>
robust_dif<T> operator+(const robust_dif<T>& lhs, const T& rhs) {
- if (!is_neg(rhs)) {
- return robust_dif<T>(lhs.pos() + rhs, lhs.neg());
- } else {
- return robust_dif<T>(lhs.pos(), lhs.neg() - rhs);
- }
+ if (!is_neg(rhs)) {
+ return robust_dif<T>(lhs.pos() + rhs, lhs.neg());
+ } else {
+ return robust_dif<T>(lhs.pos(), lhs.neg() - rhs);
+ }
}
template<typename T>
robust_dif<T> operator+(const T& lhs, const robust_dif<T>& rhs) {
- if (!is_neg(lhs)) {
- return robust_dif<T>(lhs + rhs.pos(), rhs.neg());
- } else {
- return robust_dif<T>(rhs.pos(), rhs.neg() - lhs);
- }
+ if (!is_neg(lhs)) {
+ return robust_dif<T>(lhs + rhs.pos(), rhs.neg());
+ } else {
+ return robust_dif<T>(rhs.pos(), rhs.neg() - lhs);
+ }
}
template<typename T>
robust_dif<T> operator-(const robust_dif<T>& lhs,
const robust_dif<T>& rhs) {
- return robust_dif<T>(lhs.pos() + rhs.neg(), lhs.neg() + rhs.pos());
+ return robust_dif<T>(lhs.pos() + rhs.neg(), lhs.neg() + rhs.pos());
}
template<typename T>
robust_dif<T> operator-(const robust_dif<T>& lhs, const T& rhs) {
- if (!is_neg(rhs)) {
- return robust_dif<T>(lhs.pos(), lhs.neg() + rhs);
- } else {
- return robust_dif<T>(lhs.pos() - rhs, lhs.neg());
- }
+ if (!is_neg(rhs)) {
+ return robust_dif<T>(lhs.pos(), lhs.neg() + rhs);
+ } else {
+ return robust_dif<T>(lhs.pos() - rhs, lhs.neg());
+ }
}
template<typename T>
robust_dif<T> operator-(const T& lhs, const robust_dif<T>& rhs) {
- if (!is_neg(lhs)) {
- return robust_dif<T>(lhs + rhs.neg(), rhs.pos());
- } else {
- return robust_dif<T>(rhs.neg(), rhs.pos() - lhs);
- }
+ if (!is_neg(lhs)) {
+ return robust_dif<T>(lhs + rhs.neg(), rhs.pos());
+ } else {
+ return robust_dif<T>(rhs.neg(), rhs.pos() - lhs);
+ }
}
template<typename T>
robust_dif<T> operator*(const robust_dif<T>& lhs,
const robust_dif<T>& rhs) {
- T res_pos = lhs.pos() * rhs.pos() + lhs.neg() * rhs.neg();
- T res_neg = lhs.pos() * rhs.neg() + lhs.neg() * rhs.pos();
- return robust_dif<T>(res_pos, res_neg);
+ T res_pos = lhs.pos() * rhs.pos() + lhs.neg() * rhs.neg();
+ T res_neg = lhs.pos() * rhs.neg() + lhs.neg() * rhs.pos();
+ return robust_dif<T>(res_pos, res_neg);
}
template<typename T>
robust_dif<T> operator*(const robust_dif<T>& lhs, const T& val) {
- 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);
- }
+ 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);
+ }
}
template<typename T>
robust_dif<T> operator*(const T& val, const robust_dif<T>& rhs) {
- 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());
- }
+ 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());
+ }
}
template<typename T>
robust_dif<T> operator/(const robust_dif<T>& lhs, const T& val) {
- 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);
- }
+ 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);
+ }
}
// Used to compute expressions that operate with sqrts with predefined
@@ -442,69 +437,69 @@
template <typename _int, typename _fpt, typename _converter>
class robust_sqrt_expr {
public:
- static const unsigned int EVAL1_MAX_RELATIVE_ERROR;
- static const unsigned int EVAL2_MAX_RELATIVE_ERROR;
- static const unsigned int EVAL3_MAX_RELATIVE_ERROR;
- static const unsigned int EVAL4_MAX_RELATIVE_ERROR;
-
- // Evaluates expression (re = 4 EPS):
- // A[0] * sqrt(B[0]).
- _fpt eval1(_int *A, _int *B) {
- _fpt a = convert(A[0]);
- _fpt b = convert(B[0]);
- return a * get_sqrt(b);
- }
-
- // Evaluates expression (re = 7 EPS):
- // A[0] * sqrt(B[0]) + A[1] * sqrt(B[1]).
- _fpt eval2(_int *A, _int *B) {
- _fpt a = eval1(A, B);
- _fpt b = eval1(A + 1, B + 1);
- if ((!is_neg(a) && !is_neg(b)) ||
- (!is_pos(a) && !is_pos(b)))
- return a + b;
- return convert(A[0] * A[0] * B[0] - A[1] * A[1] * B[1]) / (a - b);
- }
-
- // Evaluates expression (re = 16 EPS):
- // A[0] * sqrt(B[0]) + A[1] * sqrt(B[1]) + A[2] * sqrt(B[2]).
- _fpt eval3(_int *A, _int *B) {
- _fpt a = eval2(A, B);
- _fpt b = eval1(A + 2, B + 2);
- if ((!is_neg(a) && !is_neg(b)) ||
- (!is_pos(a) && !is_pos(b)))
- return a + b;
- tA[3] = A[0] * A[0] * B[0] + A[1] * A[1] * B[1] - A[2] * A[2] * B[2];
- tB[3] = 1;
- tA[4] = A[0] * A[1] * 2;
- tB[4] = B[0] * B[1];
- return eval2(tA + 3, tB + 3) / (a - b);
- }
-
-
- // 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]).
- _fpt eval4(_int *A, _int *B) {
- _fpt a = eval2(A, B);
- _fpt b = eval2(A + 2, B + 2);
- if ((!is_neg(a) && !is_neg(b)) ||
- (!is_pos(a) && !is_pos(b)))
- return a + b;
- tA[0] = A[0] * A[0] * B[0] + A[1] * A[1] * B[1] -
- A[2] * A[2] * B[2] - A[3] * A[3] * B[3];
- tB[0] = 1;
- tA[1] = A[0] * A[1] * 2;
- tB[1] = B[0] * B[1];
- tA[2] = A[2] * A[3] * -2;
- tB[2] = B[2] * B[3];
- return eval3(tA, tB) / (a - b);
- }
+ static const unsigned int EVAL1_MAX_RELATIVE_ERROR;
+ static const unsigned int EVAL2_MAX_RELATIVE_ERROR;
+ static const unsigned int EVAL3_MAX_RELATIVE_ERROR;
+ static const unsigned int EVAL4_MAX_RELATIVE_ERROR;
+
+ // Evaluates expression (re = 4 EPS):
+ // A[0] * sqrt(B[0]).
+ _fpt eval1(_int *A, _int *B) {
+ _fpt a = convert(A[0]);
+ _fpt b = convert(B[0]);
+ return a * get_sqrt(b);
+ }
+
+ // Evaluates expression (re = 7 EPS):
+ // A[0] * sqrt(B[0]) + A[1] * sqrt(B[1]).
+ _fpt eval2(_int *A, _int *B) {
+ _fpt a = eval1(A, B);
+ _fpt b = eval1(A + 1, B + 1);
+ if ((!is_neg(a) && !is_neg(b)) ||
+ (!is_pos(a) && !is_pos(b)))
+ return a + b;
+ return convert(A[0] * A[0] * B[0] - A[1] * A[1] * B[1]) / (a - b);
+ }
+
+ // Evaluates expression (re = 16 EPS):
+ // A[0] * sqrt(B[0]) + A[1] * sqrt(B[1]) + A[2] * sqrt(B[2]).
+ _fpt eval3(_int *A, _int *B) {
+ _fpt a = eval2(A, B);
+ _fpt b = eval1(A + 2, B + 2);
+ if ((!is_neg(a) && !is_neg(b)) ||
+ (!is_pos(a) && !is_pos(b)))
+ return a + b;
+ tA[3] = A[0] * A[0] * B[0] + A[1] * A[1] * B[1] - A[2] * A[2] * B[2];
+ tB[3] = 1;
+ tA[4] = A[0] * A[1] * 2;
+ tB[4] = B[0] * B[1];
+ return eval2(tA + 3, tB + 3) / (a - b);
+ }
+
+
+ // 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]).
+ _fpt eval4(_int *A, _int *B) {
+ _fpt a = eval2(A, B);
+ _fpt b = eval2(A + 2, B + 2);
+ if ((!is_neg(a) && !is_neg(b)) ||
+ (!is_pos(a) && !is_pos(b)))
+ return a + b;
+ tA[0] = A[0] * A[0] * B[0] + A[1] * A[1] * B[1] -
+ A[2] * A[2] * B[2] - A[3] * A[3] * B[3];
+ tB[0] = 1;
+ tA[1] = A[0] * A[1] * 2;
+ tB[1] = B[0] * B[1];
+ tA[2] = A[2] * A[3] * -2;
+ tB[2] = B[2] * B[3];
+ return eval3(tA, tB) / (a - b);
+ }
private:
- _int tA[5];
- _int tB[5];
- _converter convert;
+ _int tA[5];
+ _int tB[5];
+ _converter convert;
};
template <typename _int, typename _fpt, typename _converter>
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 2012-03-23 17:18:24 EDT (Fri, 23 Mar 2012)
@@ -411,7 +411,7 @@
site_type right_site_;
};
-// Represents edge data structure from the voronoi output, that is
+// Represents edge data structure from the Voronoi output, that is
// associated as a value with beach line bisector in the beach
// line. Contains pointer to the circle event in the circle event
// queue if the edge corresponds to the right bisector of the circle event.
Modified: sandbox/gtl/boost/polygon/voronoi.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi.hpp 2012-03-23 17:18:24 EDT (Fri, 23 Mar 2012)
@@ -13,15 +13,16 @@
#include "voronoi_builder.hpp"
#include "voronoi_diagram.hpp"
-// Public methods to compute voronoi diagram.
-// points - container of input points (supports forward iterator).
-// segments - container of input segments (supports forward iterator).
-// output - voronoi output data structure to hold voronoi diagram.
+// Public methods to compute Voronoi diagram.
+// PC - container of input points (should supports forward iterator).
+// SC - container of input segments (should supports forward iterator).
+// output - Voronoi output data structure to hold Voronoi diagram.
+// Segment class should provide low(), high() methods to access its endpoints.
// 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 belong to the signed integer range
// [-2^31, 2^31-1]. To use wider input coordinate range use voronoi_builder
-// structure with user provided coordinate traits.
+// structure with user provided coordinate type traits.
// Complexity - O(N*logN), memory usage - O(N),
// where N is the total number of points and segments.
namespace boost {
Modified: sandbox/gtl/boost/polygon/voronoi_builder.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi_builder.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi_builder.hpp 2012-03-23 17:18:24 EDT (Fri, 23 Mar 2012)
@@ -21,7 +21,7 @@
namespace boost {
namespace polygon {
// GENERAL INFO:
-// The sweepline algorithm implementation to compute voronoi diagram of
+// The sweepline algorithm implementation to compute Voronoi diagram of
// points and non-intersecting segments (except endpoints).
// Complexity - O(N*logN), memory usage - O(N), where N is the total number
// of input geometries. Input geometries should have integer coordinate type.
@@ -36,7 +36,7 @@
// topmost element from the circle event queue. STL map (red-black tree)
// container was chosen to hold state of the beach line. The keys of the map
// correspond to the neighboring sites that form a bisector and values to the
-// corresponding voronoi edge in the output data structure.
+// corresponding Voronoi edge in the output data structure.
template <typename T,
typename CTT = detail::voronoi_ctype_traits<T>,
typename VP = detail::voronoi_predicates<CTT> >
@@ -477,8 +477,8 @@
if (site_event.is_segment()) {
// Update the beach line with temporary bisector, that will
- // disappear after processing site event going through the
- // endpoint of the segment site.
+ // disappear after processing site event corresponding to the
+ // second endpoint of the segment site.
key_type new_node(site_event, site_event);
new_node.right_site().inverse();
position = beach_line_.insert(position,
Modified: sandbox/gtl/boost/polygon/voronoi_diagram.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi_diagram.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi_diagram.hpp 2012-03-23 17:18:24 EDT (Fri, 23 Mar 2012)
@@ -22,11 +22,12 @@
template <typename T>
class voronoi_edge;
-// Represents voronoi cell.
-// Data members: 1) pointer to the incident edge;
-// 2) site inside cell;
-// 3) data associated with a cell.
-// The cell may contain point or segment site.
+// Represents Voronoi cell.
+// Data members:
+// 1) pointer to the incident edge;
+// 2) site inside cell;
+// 3) data associated with a cell.
+// Cell may contain point or segment site inside.
template <typename T>
class voronoi_cell {
public:
@@ -58,11 +59,11 @@
bool is_degenerate() const { return incident_edge_ == NULL; }
// Returns site point in case cell contains point site,
- // the first point of the segment site else.
+ // the first endpoint of the segment site else.
const point_type &point0() const { return point0_; }
// Returns site point in case cell contains point site,
- // the second point of the segment site else.
+ // the second endpoint of the segment site else.
const point_type &point1() const { return point1_; }
voronoi_edge_type *incident_edge() { return incident_edge_; }
@@ -79,10 +80,11 @@
mutable void *data_;
};
-// Represents voronoi vertex.
-// Data members: 1) vertex point itself;
-// 2) pointer to the incident edge;
-// 3) data associated with vertex.
+// Represents Voronoi vertex.
+// Data members:
+// 1) vertex point itself;
+// 2) pointer to the incident edge;
+// 3) data associated with vertex.
template <typename T>
class voronoi_vertex {
public:
@@ -112,14 +114,15 @@
mutable void *data_;
};
-// Half-edge data structure. Represents voronoi edge.
-// Variables: 1) pointer to the corresponding cell;
-// 2) pointer to the vertex that is the starting
-// point of the half-edge;
-// 3) pointer to the twin edge;
-// 4) pointer to the CCW next edge;
-// 5) pointer to the CCW prev edge;
-// 6) pointer to data associated with edge.
+// Half-edge data structure. Represents Voronoi edge.
+// Data members:
+// 1) pointer to the corresponding cell;
+// 2) pointer to the vertex that is the starting
+// point of the half-edge;
+// 3) pointer to the twin edge;
+// 4) pointer to the CCW next edge;
+// 5) pointer to the CCW prev edge;
+// 6) pointer to data associated with edge.
template <typename T>
class voronoi_edge {
public:
@@ -163,7 +166,7 @@
void *data() const { return data_; }
void data(void *d) const { data_ = d; }
- // Return a pointer to the rotation next edge
+ // Returns a pointer to the rotation next edge
// over the starting point of the half-edge.
voronoi_edge_type *rot_next() {
return (vertex_) ? prev_->twin() : NULL;
@@ -172,7 +175,7 @@
return (vertex_) ? prev_->twin() : NULL;
}
- // Return a pointer to the rotation prev edge
+ // Returns a pointer to the rotation prev edge
// over the starting point of the half-edge.
voronoi_edge_type *rot_prev() {
return (vertex_) ? twin_->next() : NULL;
@@ -181,12 +184,12 @@
return (vertex_) ? twin_->next() : NULL;
}
- // Return true if the edge is finite (segment, parabolic arc).
- // Return false if the edge is infinite (ray, line).
+ // Returns true if the edge is finite (segment, parabolic arc).
+ // Returns false if the edge is infinite (ray, line).
bool is_finite() const { return vertex0() && vertex1(); }
- // Return true if the edge is linear (segment, ray, line).
- // Return false if the edge is curved (parabolic arc).
+ // Returns true if the edge is linear (segment, ray, line).
+ // Returns false if the edge is curved (parabolic arc).
bool is_linear() const {
if (!is_primary())
return true;
@@ -201,8 +204,8 @@
return (cell()->contains_segment() ^ twin()->cell()->contains_segment());
}
- // Return false if edge goes through the endpoint of the segment.
- // Return true else.
+ // Returns false if edge goes through the endpoint of the segment.
+ // Returns true else.
bool is_primary() const {
bool flag1 = cell_->contains_segment();
bool flag2 = twin_->cell()->contains_segment();
@@ -279,6 +282,8 @@
typedef typename edge_container_type::iterator edge_iterator;
typedef typename edge_container_type::const_iterator const_edge_iterator;
+ // This builder class is mainly used to hide from the user methods that
+ // construct Voronoi diagram.
class voronoi_diagram_builder {
public:
void vd(voronoi_diagram *vd) {
@@ -372,7 +377,7 @@
edges_.reserve((num_sites << 2) + (num_sites << 1));
}
- // Update the voronoi output in case of a single point input.
+ // Update the Voronoi output in case of a single point input.
template <typename SEvent>
void process_single_site(const SEvent &site) {
// Update cell records.
@@ -426,7 +431,7 @@
// Takes as input two sites that create a new bisector, circle event
// that corresponds to the intersection point of the two old half-edges,
// pointers to those half-edges. Half-edges' direction goes out of the
- // new voronoi vertex point. Returns a pair of pointers to a new half-edges.
+ // new Voronoi vertex point. Returns a pair of pointers to a new half-edges.
template <typename SEvent, typename CEvent>
std::pair<void *, void *> insert_new_edge(
const SEvent &site1, const SEvent &site3, const CEvent &circle,
@@ -434,7 +439,7 @@
edge_type *edge12 = static_cast<edge_type*>(data12);
edge_type *edge23 = static_cast<edge_type*>(data23);
- // Add a new voronoi vertex.
+ // Add a new Voronoi vertex.
vertices_.push_back(vertex_type(prepare_point(circle), NULL));
vertex_type &new_vertex = vertices_.back();
@@ -459,7 +464,7 @@
// Update vertex pointer.
new_edge2.vertex0(&new_vertex);
- // Update voronoi prev/next pointers.
+ // Update Voronoi prev/next pointers.
edge12->prev(&new_edge1);
new_edge1.next(edge12);
edge12->twin()->next(edge23);
Modified: sandbox/gtl/boost/polygon/voronoi_utils.hpp
==============================================================================
--- sandbox/gtl/boost/polygon/voronoi_utils.hpp (original)
+++ sandbox/gtl/boost/polygon/voronoi_utils.hpp 2012-03-23 17:18:24 EDT (Fri, 23 Mar 2012)
@@ -132,7 +132,7 @@
return new_brect;
}
- // Discretizes finite voronoi edge.
+ // Discretizes finite Voronoi edge.
// Disretization absolute error is defined by max_error value.
template <typename CT>
static void discretize(const voronoi_edge<CT> &edge,
@@ -165,7 +165,7 @@
}
}
- // Clip a linear voronoi edge with a given rectangle.
+ // Clip a linear Voronoi edge with a given rectangle.
template <typename CT>
static void clip(const voronoi_edge<CT> &edge,
const brect_type &brect, point_set_type &clipped_edge) {
@@ -317,7 +317,7 @@
// Find intermediate points of the parabola.
// Parabola is a locus of points equidistant from the point and segment
// sites. intermediate_points should contain two initial endpoints
- // of the edge (voronoi vertices). Intermediate points are inserted
+ // of the edge (Voronoi vertices). Intermediate points are inserted
// between the given two endpoints.
// Max_dist is the maximum distance allowed between parabola and line
// segments that discretize it.