|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r74104 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/example libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2011-08-28 08:05:13
Author: asydorchuk
Date: 2011-08-28 08:05:11 EDT (Sun, 28 Aug 2011)
New Revision: 74104
URL: http://svn.boost.org/trac/boost/changeset/74104
Log:
Refactoring:
1) Merged robust_fpt and sqrt_expr_evaluator into voronoi_fpt_kernel;
2) Merged voronoi_output and voronoi_sweepline into voronoi_diagram;
3) Started to use Boost.Polygon point and directed segment types for input and as the output of the voronoi_helper interpolation procedure;
4) Added type traits (not finished yet);
5) Updated tests.
6) Using segment set clean method to remove intersections from the input segment set.
Removed denominator from the circle_event as it's evaluated in a robust way.
Added:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_fpt_kernel.hpp
- copied, changed from r73453, /sandbox/SOC/2010/sweepline/boost/sweepline/detail/robust_fpt.hpp
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_diagram.hpp
- copied, changed from r73453, /sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp
Removed:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/robust_fpt.hpp
sandbox/SOC/2010/sweepline/boost/sweepline/detail/sqrt_expr_evaluator.hpp
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_sweepline.hpp
sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp
Text files modified:
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp | 289 ++++++++++-------
sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_fpt_kernel.hpp | 113 ++++++
sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_diagram.hpp | 339 +++++++++-----------
sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp | 27
sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp | 23
sandbox/SOC/2010/sweepline/libs/sweepline/test/circle_event_creation_test.cpp | 91 ++--
sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp | 16
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp | 24
sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp | 44 +-
sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp | 10
sandbox/SOC/2010/sweepline/libs/sweepline/test/output_verification.hpp | 133 ++-----
sandbox/SOC/2010/sweepline/libs/sweepline/test/predicates_test.cpp | 288 ++++++++--------
sandbox/SOC/2010/sweepline/libs/sweepline/test/robust_fpt_test.cpp | 2
sandbox/SOC/2010/sweepline/libs/sweepline/test/sqrt_expr_evaluator_test.cpp | 34 +-
sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp | 664 ++++++++++++++++++---------------------
15 files changed, 1074 insertions(+), 1023 deletions(-)
Deleted: sandbox/SOC/2010/sweepline/boost/sweepline/detail/robust_fpt.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/detail/robust_fpt.hpp 2011-08-28 08:05:11 EDT (Sun, 28 Aug 2011)
+++ (empty file)
@@ -1,468 +0,0 @@
-// Boost sweepline/mpt_wrapper.hpp header file
-
-// Copyright Andrii Sydorchuk 2010.
-// 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)
-
-// See http://www.boost.org for updates, documentation, and revision history.
-
-#ifndef VORONOI_SWEEPLINE_ROBUST_FPT
-#define VORONOI_SWEEPLINE_ROBUST_FPT
-
-namespace boost {
-namespace sweepline {
-namespace detail {
-
- // Represents the result of the epsilon robust predicate.
- // If the result is undefined some further processing is usually required.
- enum kPredicateResult {
- LESS = -1,
- UNDEFINED = 0,
- MORE = 1,
- };
-
- // If two floating-point numbers in the same format are ordered (x < y),
- // then they are ordered the same way when their bits are reinterpreted as
- // sign-magnitude integers. Values are considered to be almost equal if
- // their integer reinterpretatoins differ in not more than maxUlps units.
- template <typename T>
- static bool almost_equal(T a, T b, unsigned int ulps);
-
- template<>
- bool almost_equal<float>(float a, float b, unsigned int maxUlps) {
- unsigned int ll_a, ll_b;
-
- // Reinterpret double bits as 32-bit signed integer.
- memcpy(&ll_a, &a, sizeof(float));
- memcpy(&ll_b, &b, sizeof(float));
-
- 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<double>(double a, double b, unsigned int maxUlps) {
- unsigned long long ll_a, ll_b;
-
- // Reinterpret double bits as 64-bit signed integer.
- memcpy(&ll_a, &a, sizeof(double));
- memcpy(&ll_b, &b, sizeof(double));
-
- // 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;
- return ll_b - ll_a <= maxUlps;
- }
-
- template <typename T>
- double get_d(const T& value) {
- return value.get_d();
- }
-
- template <>
- double get_d(const float& value) {
- return value;
- }
-
- template <>
- double get_d(const double& value) {
- return value;
- }
-
- template <typename _fpt>
- class robust_fpt {
- public:
- typedef _fpt floating_point_type;
- typedef double relative_error_type;
-
- // Rounding error is at most 1 EPS.
- static const relative_error_type ROUNDING_ERROR;
-
- // Constructors.
- robust_fpt() : fpv_(0.0), re_(0) {}
- explicit robust_fpt(int fpv) : fpv_(fpv), re_(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_; }
-
- bool operator==(double that) const {
- if (that == 0)
- return this->fpv_ == that;
- return almost_equal(this->fpv_, that,
- static_cast<unsigned int>(this->ulp()));
- }
-
- bool operator!=(double that) const {
- return !(*this == that);
- }
-
- bool operator<(double that) const {
- if (*this == that)
- return false;
- return this->fpv_ < that;
- }
-
- bool operator<=(double that) const {
- if (*this == that)
- return true;
- return this->fpv_ < that;
- }
-
- bool operator>(double that) const {
- if (*this == that)
- return false;
- return this->fpv_ > that;
- }
-
- bool operator>=(double that) const {
- if (*this == that)
- return true;
- return this->fpv_ > that;
- }
-
- bool operator==(const robust_fpt &that) const {
- unsigned int ulp = static_cast<unsigned int>(ceil(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_;
- }
-
- bool operator>(const robust_fpt &that) const {
- return that < *this;
- }
-
- bool operator<=(const robust_fpt &that) const {
- return !(that < *this);
- }
-
- bool operator>=(const robust_fpt &that) const {
- return !(*this < that);
- }
-
- 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) ||
- (this->fpv_ <= 0 && that.fpv_ <= 0))
- this->re_ = (std::max)(this->re_, that.re_) + ROUNDING_ERROR;
- else {
- floating_point_type temp = (this->fpv_ * this->re_ - that.fpv_ * that.re_) / fpv;
- this->re_ = std::fabs(get_d(temp)) + ROUNDING_ERROR;
- }
- this->fpv_ = fpv;
- return *this;
- }
-
- robust_fpt& operator-=(const robust_fpt &that) {
- floating_point_type fpv = this->fpv_ - that.fpv_;
- if ((this->fpv_ >= 0 && that.fpv_ <= 0) ||
- (this->fpv_ <= 0 && that.fpv_ >= 0))
- this->re_ = (std::max)(this->re_, that.re_) + ROUNDING_ERROR;
- else {
- floating_point_type temp = (this->fpv_ * this->re_ + that.fpv_ * that.re_) / fpv;
- this->re_ = std::fabs(get_d(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 ((this->fpv_ >= 0 && that.fpv_ >= 0) ||
- (this->fpv_ <= 0 && that.fpv_ <= 0))
- re = (std::max)(this->re_, that.re_) + ROUNDING_ERROR;
- else {
- floating_point_type temp = (this->fpv_ * this->re_ - that.fpv_ * that.re_) / fpv;
- re = std::fabs(get_d(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 ((this->fpv_ >= 0 && that.fpv_ <= 0) ||
- (this->fpv_ <= 0 && that.fpv_ >= 0))
- re = (std::max)(this->re_, that.re_) + ROUNDING_ERROR;
- else {
- floating_point_type temp = (this->fpv_ * this->re_ + that.fpv_ * that.re_) / fpv;
- re = std::fabs(get_d(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 get_sqrt() const {
- return robust_fpt(std::sqrt(fpv_), re_ * 0.5 + ROUNDING_ERROR);
- }
-
- robust_fpt fabs() const {
- return (fpv_ >= 0) ? *this : -(*this);
- }
-
- private:
- 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;
-
- // Class used to make computations with epsilon relative error.
- // ERC consists of two values: value1 and value2, both positive.
- // The resulting expression is equal to the value1 - value2.
- // The main idea is to represent any expression that consists of
- // addition, substraction, multiplication and division operations
- // to avoid using substraction. Substraction of a positive value
- // is equivalent to the addition to value2 and substraction of
- // a negative value is equivalent to the addition to value1.
- // Cons: ERC gives error relative not to the resulting value,
- // but relative to some expression instead. Example:
- // center_x = 100, ERC's value1 = 10^20, value2 = 10^20,
- // center_x = 1000, ERC's value3 = 10^21, value4 = 10^21,
- // such two centers are considered equal(
- // value1 + value4 = value2 + value3), while they are not.
- // Pros: ERC is much faster then approaches based on the use
- // of high-precision libraries. However this will give correct
- // answer for the previous example.
- // Solution: Use ERCs in case of defined comparison results and use
- // high-precision libraries for undefined results.
- template <typename T>
- class epsilon_robust_comparator {
- public:
- epsilon_robust_comparator() :
- positive_sum_(0),
- negative_sum_(0) {}
-
- epsilon_robust_comparator(const T &value) :
- positive_sum_((value>0)?value:0),
- negative_sum_((value<0)?-value:0) {}
-
- epsilon_robust_comparator(const T &pos, const T &neg) :
- positive_sum_(pos),
- negative_sum_(neg) {}
-
- T dif() const {
- return positive_sum_ - negative_sum_;
- }
-
- T pos() const {
- return positive_sum_;
- }
-
- T neg() const {
- 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;
- }
-
- epsilon_robust_comparator<T> &operator+=(const T &val) {
- if (val >= 0)
- positive_sum_ += val;
- else
- negative_sum_ -= val;
- return *this;
- }
-
- epsilon_robust_comparator<T> &operator+=(
- const epsilon_robust_comparator<T> &erc) {
- positive_sum_ += erc.positive_sum_;
- negative_sum_ += erc.negative_sum_;
- return *this;
- }
-
- epsilon_robust_comparator<T> &operator-=(const T &val) {
- if (val >= 0)
- negative_sum_ += val;
- else
- positive_sum_ -= val;
- return *this;
- }
-
- epsilon_robust_comparator<T> &operator-=(
- const epsilon_robust_comparator<T> &erc) {
- positive_sum_ += erc.negative_sum_;
- negative_sum_ += erc.positive_sum_;
- return *this;
- }
-
- epsilon_robust_comparator<T> &operator*=(const T &val) {
- if (val >= 0) {
- positive_sum_ *= val;
- negative_sum_ *= val;
- } else {
- positive_sum_ *= -val;
- negative_sum_ *= -val;
- swap();
- }
- return *this;
- }
-
- epsilon_robust_comparator<T> &operator/=(const T &val) {
- if (val >= 0) {
- positive_sum_ /= val;
- negative_sum_ /= val;
- } else {
- positive_sum_ /= -val;
- negative_sum_ /= -val;
- swap();
- }
- return *this;
- }
-
- // Compare predicate with value using ulp precision.
- kPredicateResult compare(T value, int ulp = 0) const {
- T lhs = positive_sum_ - ((value < 0) ? value : 0);
- T rhs = negative_sum_ + ((value > 0) ? value : 0);
- if (almost_equal(lhs, rhs, ulp))
- return UNDEFINED;
- return (lhs < rhs) ? LESS : MORE;
- }
-
- // Compare two predicats using ulp precision.
- kPredicateResult compare(const epsilon_robust_comparator &rc,
- int ulp = 0) const {
- T lhs = positive_sum_ + rc.neg();
- T rhs = negative_sum_ + rc.pos();
- if (almost_equal(lhs, rhs, ulp))
- return UNDEFINED;
- return (lhs < rhs) ? LESS : MORE;
- }
-
- // Check whether comparison has undefined result.
- bool compares_undefined(const epsilon_robust_comparator &rc,
- int ulp) const {
- return this->compare(rc, ulp) == UNDEFINED;
- }
-
- private:
- T positive_sum_;
- T negative_sum_;
- };
-
- template<typename T>
- inline epsilon_robust_comparator<T> operator+(
- const epsilon_robust_comparator<T>& lhs,
- const epsilon_robust_comparator<T>& rhs) {
- return epsilon_robust_comparator<T>(lhs.pos() + rhs.pos(),
- lhs.neg() + rhs.neg());
- }
-
- template<typename T>
- inline epsilon_robust_comparator<T> operator-(
- const epsilon_robust_comparator<T>& lhs,
- const epsilon_robust_comparator<T>& rhs) {
- return epsilon_robust_comparator<T>(lhs.pos() - rhs.neg(),
- lhs.neg() + rhs.pos());
- }
-
- template<typename T>
- inline epsilon_robust_comparator<T> operator*(
- const epsilon_robust_comparator<T>& lhs,
- const epsilon_robust_comparator<T>& rhs) {
- double res_pos = lhs.pos() * rhs.pos() + lhs.neg() * rhs.neg();
- double res_neg = lhs.pos() * rhs.neg() + lhs.neg() * rhs.pos();
- return epsilon_robust_comparator<T>(res_pos, res_neg);
- }
-
- template<typename T>
- inline epsilon_robust_comparator<T> operator*(
- const epsilon_robust_comparator<T>& lhs, const T& val) {
- if (val >= 0)
- return epsilon_robust_comparator<T>(lhs.pos() * val,
- lhs.neg() * val);
- return epsilon_robust_comparator<T>(-lhs.neg() * val,
- -lhs.pos() * val);
- }
-
- template<typename T>
- inline epsilon_robust_comparator<T> operator*(
- const T& val, const epsilon_robust_comparator<T>& rhs) {
- if (val >= 0)
- return epsilon_robust_comparator<T>(val * rhs.pos(),
- val * rhs.neg());
- return epsilon_robust_comparator<T>(-val * rhs.neg(),
- -val * rhs.pos());
- }
-
-} // detail
-} // sweepline
-} // boost
-
-#endif
\ No newline at end of file
Deleted: sandbox/SOC/2010/sweepline/boost/sweepline/detail/sqrt_expr_evaluator.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/detail/sqrt_expr_evaluator.hpp 2011-08-28 08:05:11 EDT (Sun, 28 Aug 2011)
+++ (empty file)
@@ -1,124 +0,0 @@
-// Boost sweepline/sqr_expr_evaluator.hpp header file
-
-// Copyright Andrii Sydorchuk 2010.
-// 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)
-
-// See http://www.boost.org for updates, documentation, and revision history.
-
-#ifndef BOOST_SWEEPLINE_SQRT_EXPR_EVALUATOR
-#define BOOST_SWEEPLINE_SQRT_EXPR_EVALUATOR
-
-namespace boost {
-namespace sweepline {
-namespace detail {
-
- template <int N>
- struct sqr_expr_evaluator {
- template <typename mpt, typename mpf>
- static mpf eval(mpt *A, mpt *B);
- };
-
- // Evaluates expression:
- // A[0] * sqrt(B[0]).
- template <>
- struct sqr_expr_evaluator<1> {
- template <typename mpt, typename mpf>
- static mpf eval(mpt *A, mpt *B) {
-#ifndef THREAD_SAFETY
- static
-#endif
- mpf a, b, ret_val;
- a = A[0];
- b = B[0];
- ret_val = a * sqrt(b);
- return ret_val;
- }
- };
-
- // Evaluates expression:
- // A[0] * sqrt(B[0]) + A[1] * sqrt(B[1]) with
- // 7 * EPS relative error in the worst case.
- template <>
- struct sqr_expr_evaluator<2> {
- template <typename mpt, typename mpf>
- static mpf eval(mpt *A, mpt *B) {
-#ifndef THREAD_SAFETY
- static
-#endif
- mpf lhs, rhs, numerator;
- lhs = sqr_expr_evaluator<1>::eval<mpt, mpf>(A, B);
- rhs = sqr_expr_evaluator<1>::eval<mpt, mpf>(A + 1, B + 1);
- if ((lhs >= 0 && rhs >= 0) || (lhs <= 0 && rhs <= 0))
- return lhs + rhs;
- numerator = A[0] * A[0] * B[0] - A[1] * A[1] * B[1];
- return numerator / (lhs - rhs);
- }
- };
-
- // Evaluates expression:
- // A[0] * sqrt(B[0]) + A[1] * sqrt(B[1]) + A[2] * sqrt(B[2])
- // with 16 * EPS relative error in the worst case.
- template <>
- struct sqr_expr_evaluator<3> {
- template <typename mpt, typename mpf>
- static mpf eval(mpt *A, mpt *B) {
-#ifndef THREAD_SAFETY
- static
-#endif
- mpt cA[2], cB[2];
-#ifndef THREAD_SAFETY
- static
-#endif
- mpf lhs, rhs, numer;
- lhs = sqr_expr_evaluator<2>::eval<mpt, mpf>(A, B);
- rhs = sqr_expr_evaluator<1>::eval<mpt, mpf>(A + 2, B + 2);
- if ((lhs >= 0 && rhs >= 0) || (lhs <= 0 && rhs <= 0))
- return lhs + rhs;
- cA[0] = A[0] * A[0] * B[0] + A[1] * A[1] * B[1];
- cA[0] -= A[2] * A[2] * B[2];
- cB[0] = 1;
- cA[1] = A[0] * A[1] * 2;
- cB[1] = B[0] * B[1];
- numer = sqr_expr_evaluator<2>::eval<mpt, mpf>(cA, cB);
- return numer / (lhs - rhs);
- }
- };
-
- // Evaluates expression:
- // A[0] * sqrt(B[0]) + A[1] * sqrt(B[1]) + A[2] * sqrt(B[2]) + A[3] * sqrt(B[3])
- // with 25 * EPS relative error in the worst case.
- template <>
- struct sqr_expr_evaluator<4> {
- template <typename mpt, typename mpf>
- static mpf eval(mpt *A, mpt *B) {
-#ifndef THREAD_SAFETY
- static
-#endif
- mpt cA[3], cB[3];
-#ifndef THREAD_SAFETY
- static
-#endif
- mpf lhs, rhs, numer;
- lhs = sqr_expr_evaluator<2>::eval<mpt, mpf>(A, B);
- rhs = sqr_expr_evaluator<2>::eval<mpt, mpf>(A + 2, B + 2);
- if ((lhs >= 0 && rhs >= 0) || (lhs <= 0 && rhs <= 0))
- return lhs + rhs;
- cA[0] = A[0] * A[0] * B[0] + A[1] * A[1] * B[1];
- cA[0] -= A[2] * A[2] * B[2] + A[3] * A[3] * B[3];
- cB[0] = 1;
- cA[1] = A[0] * A[1] * 2;
- cB[1] = B[0] * B[1];
- cA[2] = A[2] * A[3] * -2;
- cB[2] = B[2] * B[3];
- numer = sqr_expr_evaluator<3>::eval<mpt, mpf>(cA, cB);
- return numer / (lhs - rhs);
- }
- };
-
-} // detail
-} // sweepline
-} // boost
-
-#endif
\ No newline at end of file
Modified: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp 2011-08-28 08:05:11 EDT (Sun, 28 Aug 2011)
@@ -10,8 +10,18 @@
#ifndef BOOST_SWEEPLINE_VORONOI_FORMATION
#define BOOST_SWEEPLINE_VORONOI_FORMATION
+#include "mpt_wrapper.hpp"
+#include "voronoi_fpt_kernel.hpp"
+
namespace boost {
namespace sweepline {
+
+ template <typename T>
+ class voronoi_edge;
+
+ template <typename T>
+ class voronoi_output;
+
namespace detail {
///////////////////////////////////////////////////////////////////////////
@@ -38,6 +48,68 @@
LEFT_ORIENTATION = 1,
};
+ // Cartesian 2D point data structure.
+ template <typename T>
+ class point_2d {
+ public:
+ typedef T coordinate_type;
+
+ point_2d() {}
+
+ point_2d(coordinate_type x, coordinate_type y) {
+ x_ = x;
+ y_ = y;
+ }
+
+ bool operator==(const point_2d &that) const {
+ return (this->x_ == that.x()) && (this->y_ == that.y());
+ }
+
+ bool operator!=(const point_2d &that) const {
+ return (this->x_ != that.x()) || (this->y_ != that.y());
+ }
+
+ // Comparison function.
+ // Defines ordering of the points on the 2D plane.
+ bool operator<(const point_2d &that) const {
+ if (this->x_ != that.x_)
+ return this->x_ < that.x_;
+ return this->y_ < that.y_;
+ }
+
+ bool operator<=(const point_2d &that) const {
+ return !(that < (*this));
+ }
+
+ bool operator>(const point_2d &that) const {
+ return that < (*this);
+ }
+
+ bool operator>=(const point_2d &that) const {
+ return !((*this) < that);
+ }
+
+ coordinate_type x() const {
+ return x_;
+ }
+
+ coordinate_type y() const {
+ return y_;
+ }
+
+ void x(coordinate_type x) {
+ x_ = x;
+ }
+
+ void y(coordinate_type y) {
+ y_ = y;
+ }
+
+ private:
+ coordinate_type x_;
+ coordinate_type y_;
+ };
+
// Site event type.
// Occurs when the sweepline sweeps over one of the initial sites:
// 1) point site;
@@ -64,7 +136,7 @@
class site_event {
public:
typedef T coordinate_type;
- typedef point_2d<T> point_2d_type;
+ typedef point_2d<T> point_type;
// Point site contructors.
site_event() :
@@ -79,7 +151,7 @@
is_vertical_(true),
is_inverse_(false) {}
- site_event(const point_2d_type &point, int index) :
+ site_event(const point_type &point, int index) :
point0_(point),
site_index_(index),
is_segment_(false),
@@ -99,8 +171,8 @@
is_vertical_ = (point0_.x() == point1_.x());
}
- site_event(const point_2d_type &point1,
- const point_2d_type &point2, int index) :
+ site_event(const point_type &point1,
+ const point_type &point2, int index) :
point0_(point1),
point1_(point2),
site_index_(index),
@@ -232,7 +304,7 @@
// Return point for the point sites.
// Return startpoint for the segment sites.
- const point_2d_type &point0(bool oriented = false) const {
+ const point_type &point0(bool oriented = false) const {
if (!oriented)
return point0_;
return is_inverse_ ? point1_ : point0_;
@@ -240,7 +312,7 @@
// Return endpoint of the segment sites.
// Doesn't make sense for the point sites.
- const point_2d_type &point1(bool oriented = false) const {
+ const point_type &point1(bool oriented = false) const {
if (!oriented)
return point1_;
return is_inverse_ ? point0_ : point1_;
@@ -273,8 +345,8 @@
}
private:
- point_2d_type point0_;
- point_2d_type point1_;
+ point_type point0_;
+ point_type point1_;
int site_index_;
bool is_segment_;
bool is_vertical_;
@@ -331,7 +403,7 @@
class circle_event {
public:
typedef T coordinate_type;
- typedef point_2d<T> point_2d_type;
+ typedef point_2d<T> point_type;
typedef site_event<T> site_event_type;
typedef epsilon_robust_comparator<T> erc_type;
typedef beach_line_node<coordinate_type> Key;
@@ -340,7 +412,7 @@
typedef typename std::map< Key, Value, NodeComparer >::iterator
beach_line_iterator;
- circle_event() : denom_(1), is_active_(true) {}
+ circle_event() : is_active_(true) {}
circle_event(coordinate_type c_x,
coordinate_type c_y,
@@ -348,7 +420,6 @@
center_x_(c_x),
center_y_(c_y),
lower_x_(lower_x),
- denom_(1),
is_active_(true) {}
circle_event(const erc_type &c_x,
@@ -357,32 +428,11 @@
center_x_(c_x),
center_y_(c_y),
lower_x_(lower_x),
- denom_(1),
is_active_(true) {}
- circle_event(const erc_type &c_x,
- const erc_type &c_y,
- const erc_type &lower_x,
- const erc_type &denom) :
- center_x_(c_x),
- center_y_(c_y),
- lower_x_(lower_x),
- denom_(denom),
- is_active_(true) {
- if (denom_.abs()) {
- center_x_.swap();
- center_y_.swap();
- lower_x_.swap();
- }
- }
-
bool operator==(const circle_event &that) const {
- erc_type lhs1 = lower_x_ * that.denom_;
- erc_type rhs1 = denom_ * that.lower_x_;
- erc_type lhs2 = center_y_ * that.denom_;
- erc_type rhs2 = denom_ * that.center_y_;
- return (lhs1.compare(rhs1, 128) == UNDEFINED &&
- lhs2.compare(rhs2, 128) == UNDEFINED);
+ return (this->lower_x_.compare(that.lower_x_, 128) == UNDEFINED &&
+ this->center_y_.compare(that.center_y_, 128) == UNDEFINED);
}
bool operator!=(const circle_event &that) const {
@@ -393,22 +443,14 @@
// Each rightmost point has next representation:
// (lower_x / denom, center_y / denom), denom is always positive.
bool operator<(const circle_event &that) const {
- // Evaluate comparison expressions for x-coordinates.
- erc_type lhs1 = lower_x_ * that.denom_;
- erc_type rhs1 = denom_ * that.lower_x_;
-
// Compare x-coordinates of the rightmost points. If the result
// is undefined we assume that x-coordinates are equal.
- kPredicateResult pres = lhs1.compare(rhs1, 128);
+ kPredicateResult pres = this->lower_x_.compare(that.lower_x_, 128);
if (pres != UNDEFINED)
return (pres == LESS);
- // Evaluate comparison expressions for y-coordinates.
- erc_type lhs2 = center_y_ * that.denom_;
- erc_type rhs2 = denom_ * that.center_y_;
-
// Compare y-coordinates of the rightmost points.
- return (lhs2.compare(rhs2, 128) == LESS);
+ return this->center_y_.compare(that.center_y_, 128) == LESS;
}
bool operator<=(const circle_event &that) const {
@@ -430,18 +472,18 @@
// If circle point is greater than site point return 1.
kPredicateResult compare(const site_event_type &s_event) const {
// Compare x-coordinates.
- kPredicateResult pres = lower_x_.compare(denom_ * s_event.x(), 64);
+ kPredicateResult pres = lower_x_.compare(s_event.x(), 64);
// If the comparison result is undefined
// x-coordinates are considered to be equal.
if (pres != UNDEFINED)
return pres;
// Compare y-coordinates in case of equal x-coordinates.
- return center_y_.compare(denom_ * s_event.y(), 64);
+ return center_y_.compare(s_event.y(), 64);
}
// Evaluate x-coordinate of the center of the circle.
coordinate_type x() const {
- return center_x_.dif() / denom_.dif();
+ return center_x_.dif();
}
void x(coordinate_type center_x) {
@@ -450,7 +492,7 @@
// Evaluate y-coordinate of the center of the circle.
coordinate_type y() const {
- return center_y_.dif() / denom_.dif();
+ return center_y_.dif();
}
void y(coordinate_type center_y) {
@@ -459,15 +501,15 @@
// Evaluate x-coordinate of the rightmost point of the circle.
coordinate_type lower_x() const {
- return lower_x_.dif() / denom_.dif();
+ return lower_x_.dif();
}
void lower_x(coordinate_type lower_x) {
lower_x_ = lower_x;
}
- point_2d_type center() const {
- return make_point_2d(x(), y());
+ point_type center() const {
+ return point_type(x(), y());
}
const erc_type &erc_x() const {
@@ -478,10 +520,6 @@
return center_y_;
}
- const erc_type &erc_denom() const {
- return denom_;
- }
-
// Return iterator to the second bisector from the beach line
// data structure that forms current circle event.
const beach_line_iterator &bisector() const {
@@ -504,7 +542,6 @@
erc_type center_x_;
erc_type center_y_;
erc_type lower_x_;
- erc_type denom_;
beach_line_iterator bisector_node_;
bool is_active_;
};
@@ -741,31 +778,23 @@
typedef T coordinate_type;
typedef epsilon_robust_comparator<coordinate_type> erc_type;
- robust_voronoi_vertex(const erc_type &c_x,
- const erc_type &c_y,
- const erc_type &den) :
+ robust_voronoi_vertex(const erc_type &c_x, const erc_type &c_y) :
center_x(c_x),
- center_y(c_y),
- denom(den) {}
+ center_y(c_y) {}
- coordinate_type x() const { return center_x.dif() / denom.dif(); }
+ coordinate_type x() const { return center_x.dif(); }
- coordinate_type y() const { return center_y.dif() / denom.dif(); }
+ coordinate_type y() const { return center_y.dif(); }
// Compare two vertices with the given ulp precision.
bool equals(const robust_voronoi_vertex *that, int ulp) const {
- erc_type lhs1(this->center_x * that->denom);
- erc_type rhs1(this->denom * that->center_x);
- erc_type lhs2(this->center_y * that->denom);
- erc_type rhs2(this->denom * that->center_y);
- return lhs1.compares_undefined(rhs1, ulp) &&
- lhs2.compares_undefined(rhs2, ulp);
+ return this->center_x.compares_undefined(that->center_x, ulp) &&
+ this->center_y.compares_undefined(that->center_y, ulp);
}
private:
erc_type center_x;
erc_type center_y;
- erc_type denom;
};
// Find the x-coordinate (relative to the sweepline position) of the point
@@ -1122,7 +1151,7 @@
c_event.y(0.25 * cA[2].get_d() / denom.get_d());
}
if (recompute_lower_x) {
- c_event.lower_x(0.25 * sqr_expr_evaluator<2>::eval<mpt_type, mpf_type>(cA, cB).get_d() /
+ c_event.lower_x(0.25 * sqrt_expr_evaluator<2>::eval<mpt_type, mpf_type>(cA, cB).get_d() /
(denom.get_d() * std::sqrt(segm_len.get_d())));
}
return true;
@@ -1137,7 +1166,7 @@
cA[1] = (segment_index == 2) ? -vec_x : vec_x;
cB[1] = det;
if (recompute_c_x) {
- c_event.x(0.5 * sqr_expr_evaluator<2>::eval<mpt_type, mpf_type>(cA, cB).get_d() /
+ c_event.x(0.5 * sqrt_expr_evaluator<2>::eval<mpt_type, mpf_type>(cA, cB).get_d() /
denom_sqr);
}
}
@@ -1148,7 +1177,7 @@
cA[3] = (segment_index == 2) ? -vec_y : vec_y;
cB[3] = det;
if (recompute_c_y) {
- c_event.y(0.5 * sqr_expr_evaluator<2>::eval<mpt_type, mpf_type>(&cA[2], &cB[2]).get_d() /
+ c_event.y(0.5 * sqrt_expr_evaluator<2>::eval<mpt_type, mpf_type>(&cA[2], &cB[2]).get_d() /
denom_sqr);
}
}
@@ -1160,7 +1189,7 @@
cB[2] = 1;
cA[3] = (segment_index == 2) ? -teta : teta;
cB[3] = det;
- c_event.lower_x(0.5 * sqr_expr_evaluator<4>::eval<mpt_type, mpf_type>(cA, cB).get_d() /
+ c_event.lower_x(0.5 * sqrt_expr_evaluator<4>::eval<mpt_type, mpf_type>(cA, cB).get_d() /
(denom_sqr * std::sqrt(segm_len.get_d())));
}
@@ -1170,17 +1199,17 @@
// Evaluates A[3] + A[0] * sqrt(B[0]) + A[1] * sqrt(B[1]) +
// A[2] * sqrt(B[3] * (sqrt(B[0] * B[1]) + B[2]));
template <typename mpt, typename mpf>
- static mpf sqr_expr_evaluator_pss(mpt *A, mpt *B) {
+ static mpf sqrt_expr_evaluator_pss(mpt *A, mpt *B) {
static mpt cA[4], cB[4];
static mpf lh, rh, numer;
if (A[3] == 0) {
- lh = sqr_expr_evaluator<2>::eval<mpt, mpf>(A, B);
+ lh = sqrt_expr_evaluator<2>::eval<mpt, mpf>(A, B);
cA[0] = 1;
cB[0] = B[0] * B[1];
cA[1] = B[2];
cB[1] = 1;
rh = A[2].get_d() * std::sqrt(B[3].get_d() *
- sqr_expr_evaluator<2>::eval<mpt, mpf>(cA, cB).get_d());
+ sqrt_expr_evaluator<2>::eval<mpt, mpf>(cA, cB).get_d());
if (((lh >= 0) && (rh >= 0)) || ((lh <= 0) && (rh <= 0))) {
return lh + rh;
}
@@ -1189,7 +1218,7 @@
cB[0] = 1;
cA[1] = A[0] * A[1] * 2 - A[2] * A[2] * B[3];
cB[1] = B[0] * B[1];
- numer = sqr_expr_evaluator<2>::eval<mpt, mpf>(cA, cB);
+ numer = sqrt_expr_evaluator<2>::eval<mpt, mpf>(cA, cB);
return numer / (lh - rh);
}
cA[0] = A[3];
@@ -1198,13 +1227,13 @@
cB[1] = B[0];
cA[2] = A[1];
cB[2] = B[1];
- lh = sqr_expr_evaluator<3>::eval<mpt, mpf>(cA, cB);
+ lh = sqrt_expr_evaluator<3>::eval<mpt, mpf>(cA, cB);
cA[0] = 1;
cB[0] = B[0] * B[1];
cA[1] = B[2];
cB[1] = 1;
rh = A[2].get_d() * std::sqrt(B[3].get_d() *
- sqr_expr_evaluator<2>::eval<mpt, mpf>(cA, cB).get_d());
+ sqrt_expr_evaluator<2>::eval<mpt, mpf>(cA, cB).get_d());
if (((lh >= 0) && (rh >= 0)) || ((lh <= 0) && (rh <= 0))) {
return lh + rh;
}
@@ -1217,7 +1246,7 @@
cB[2] = B[1];
cA[3] = A[0] * A[1] * 2 - A[2] * A[2] * B[3];
cB[3] = B[0] * B[1];
- numer = sqr_expr_evaluator<4>::eval<mpt, mpf>(cA, cB);
+ numer = sqrt_expr_evaluator<4>::eval<mpt, mpf>(cA, cB);
return numer / (lh - rh);
}
@@ -1261,7 +1290,7 @@
cA[1] = a[0] * a[0] * (segm_start1.y() + segm_start2.y()) -
a[0] * b[0] * (segm_start1.x() + segm_start2.x() - 2.0 * site1.x()) +
b[0] * b[0] * (2.0 * site1.y());
- double c_y = sqr_expr_evaluator<2>::eval<mpt_type, mpf_type>(cA, cB).get_d();
+ double c_y = sqrt_expr_evaluator<2>::eval<mpt_type, mpf_type>(cA, cB).get_d();
c_event.y(c_y / denom);
}
@@ -1272,14 +1301,14 @@
a[0] * a[0] * (2.0 * site1.x());
if (recompute_c_x) {
- double c_x = sqr_expr_evaluator<2>::eval<mpt_type, mpf_type>(cA, cB).get_d();
+ double c_x = sqrt_expr_evaluator<2>::eval<mpt_type, mpf_type>(cA, cB).get_d();
c_event.x(c_x / denom);
}
if (recompute_lower_x) {
cA[2] = (c[0] < 0) ? -c[0] : c[0];
cB[2] = a[0] * a[0] + b[0] * b[0];
- double lower_x = sqr_expr_evaluator<3>::eval<mpt_type, mpf_type>(cA, cB).get_d();
+ double lower_x = sqrt_expr_evaluator<3>::eval<mpt_type, mpf_type>(cA, cB).get_d();
c_event.lower_x(lower_x / denom);
}
}
@@ -1308,14 +1337,14 @@
cB[1] = a[1] * a[1] + b[1] * b[1];
cB[2] = a[0] * a[1] + b[0] * b[1];
cB[3] = (a[0] * dy - b[0] * dx) * (a[1] * dy - b[1] * dx) * -2;
- double temp = sqr_expr_evaluator_pss<mpt_type, mpf_type>(cA, cB).get_d();
+ double temp = sqrt_expr_evaluator_pss<mpt_type, mpf_type>(cA, cB).get_d();
double denom = temp * orientation.get_d();
if (recompute_c_y) {
cA[0] = b[1] * (dx * dx + dy * dy) - iy * (dx * a[1] + dy * b[1]);
cA[1] = b[0] * (dx * dx + dy * dy) - iy * (dx * a[0] + dy * b[0]);
cA[2] = iy * sign;
- double cy = sqr_expr_evaluator_pss<mpt_type, mpf_type>(cA, cB).get_d();
+ double cy = sqrt_expr_evaluator_pss<mpt_type, mpf_type>(cA, cB).get_d();
c_event.y(cy / denom);
}
@@ -1325,13 +1354,13 @@
cA[2] = ix * sign;
if (recompute_c_x) {
- double cx = sqr_expr_evaluator_pss<mpt_type, mpf_type>(cA, cB).get_d();
+ double cx = sqrt_expr_evaluator_pss<mpt_type, mpf_type>(cA, cB).get_d();
c_event.x(cx / denom);
}
if (recompute_lower_x) {
cA[3] = orientation * (dx * dx + dy * dy) * (temp < 0 ? -1 : 1);
- double lower_x = sqr_expr_evaluator_pss<mpt_type, mpf_type>(cA, cB).get_d();
+ double lower_x = sqrt_expr_evaluator_pss<mpt_type, mpf_type>(cA, cB).get_d();
c_event.lower_x(lower_x / denom);
}
}
@@ -1384,7 +1413,7 @@
int k = (i+2) % 3;
cross[i] = a[j] * b[k] - a[k] * b[j];
}
- double denom = sqr_expr_evaluator<3>::eval<mpt_type, mpf_type>(cross, sqr_len).get_d();
+ double denom = sqrt_expr_evaluator<3>::eval<mpt_type, mpf_type>(cross, sqr_len).get_d();
if (recompute_c_y) {
for (int i = 0; i < 3; ++i) {
@@ -1392,7 +1421,7 @@
int k = (i+2) % 3;
cross[i] = b[j] * c[k] - b[k] * c[j];
}
- double c_y = sqr_expr_evaluator<3>::eval<mpt_type, mpf_type>(cross, sqr_len).get_d();
+ double c_y = sqrt_expr_evaluator<3>::eval<mpt_type, mpf_type>(cross, sqr_len).get_d();
c_event.y(c_y / denom);
}
@@ -1408,13 +1437,13 @@
}
if (recompute_c_x) {
- double c_x = sqr_expr_evaluator<3>::eval<mpt_type, mpf_type>(cross, sqr_len).get_d();
+ double c_x = sqrt_expr_evaluator<3>::eval<mpt_type, mpf_type>(cross, sqr_len).get_d();
c_event.x(c_x / denom);
}
if (recompute_lower_x) {
sqr_len[3] = 1;
- double lower_x = sqr_expr_evaluator<4>::eval<mpt_type, mpf_type>(cross, sqr_len).get_d();
+ double lower_x = sqrt_expr_evaluator<4>::eval<mpt_type, mpf_type>(cross, sqr_len).get_d();
c_event.lower_x(lower_x / denom);
}
}
@@ -1754,7 +1783,7 @@
class beach_line_node {
public:
typedef T coordinate_type;
- typedef point_2d<T> point_2d_type;
+ typedef point_2d<T> point_type;
typedef site_event<T> site_event_type;
beach_line_node() {}
@@ -1833,7 +1862,7 @@
// Return true if the horizontal line going through the new site
// intersects the arc corresponding to the right_site before the
// arc corresponding to the left_site.
- bool less(const point_2d_type &new_site) const {
+ bool less(const point_type &new_site) const {
if (!left_site_.is_segment()) {
return (!right_site_.is_segment()) ? less_pp(new_site) : less_ps(new_site);
} else {
@@ -1842,19 +1871,19 @@
}
private:
- bool less_pp(const point_2d_type &new_site) const {
+ bool less_pp(const point_type &new_site) const {
return less_predicate(left_site_.point0(), right_site_.point0(), new_site);
}
- bool less_ps(const point_2d_type &new_site) const {
+ bool less_ps(const point_type &new_site) const {
return less_predicate(left_site_.point0(), right_site_, new_site, false);
}
- bool less_sp(const point_2d_type &new_site) const {
+ bool less_sp(const point_type &new_site) const {
return less_predicate(right_site_.point0(), left_site_, new_site, true);
}
- bool less_ss(const point_2d_type &new_site) const {
+ bool less_ss(const point_type &new_site) const {
return less_predicate(left_site_, right_site_, new_site);
}
@@ -1947,6 +1976,24 @@
}
};
+ template <typename T>
+ struct voronoi_traits;
+
+ template <>
+ struct voronoi_traits<int> {
+ typedef int input_coordinate_type;
+ typedef double coordinate_type;
+ typedef double output_coordinate_type;
+
+ typedef point_data<input_coordinate_type> input_point_type;
+ typedef std::vector<input_point_type> input_point_set_type;
+
+ typedef directed_line_segment_data<input_coordinate_type> input_segment_type;
+ typedef directed_line_segment_set_data<input_coordinate_type> input_segment_set_type;
+
+ typedef voronoi_output<output_coordinate_type> output_type;
+ };
+
///////////////////////////////////////////////////////////////////////////
// VORONOI BUILDER ////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
@@ -2001,9 +2048,15 @@
template <typename T>
class voronoi_builder {
public:
- typedef T coordinate_type;
- typedef point_2d<coordinate_type> point_2d_type;
- typedef voronoi_output<coordinate_type> output_type;
+ typedef typename voronoi_traits<T>::input_point_type input_point_type;
+ typedef typename voronoi_traits<T>::input_point_set_type input_point_set_type;
+
+ typedef typename voronoi_traits<T>::input_segment_type input_segment_type;
+ typedef typename voronoi_traits<T>::input_segment_set_type input_segment_set_type;
+
+ typedef typename voronoi_traits<T>::coordinate_type coordinate_type;
+ typedef point_2d<coordinate_type> point_type;
+ typedef typename voronoi_traits<T>::output_type output_type;
typedef site_event<coordinate_type> site_event_type;
typedef circle_event<coordinate_type> circle_event_type;
@@ -2016,37 +2069,33 @@
// There will be one site event for each input point and three site
// events for each input segment (both endpoints of a segment and the
// segment itself).
- template <typename iType>
- void init(const std::vector< point_2d<iType> > &points,
- const std::vector< std::pair< point_2d<iType>, point_2d<iType> > > &segments) {
- typedef std::pair< point_2d<iType>, point_2d<iType> > iSegment2D;
-
+ void init(const input_point_set_type &points,
+ const input_segment_set_type &segments) {
// Clear output.
output_.clear();
- // TODO(asydorchuk): We may add segment intersection checks there.
-
// Avoid additional memory reallocations.
+ segments.clean();
site_events_.reserve(points.size() + segments.size() * 3);
// Create a site event from each input point.
- for (typename std::vector< point_2d<iType> >::const_iterator it = points.begin();
+ for (typename input_point_set_type::const_iterator it = points.begin();
it != points.end(); ++it) {
- site_events_.push_back(make_site_event(static_cast<T>(it->x()),
- static_cast<T>(it->y()),
- 0));
+ site_events_.push_back(make_site_event(
+ static_cast<coordinate_type>(it->x()),
+ static_cast<coordinate_type>(it->y()), 0));
}
// Each segment creates three segment sites:
// 1) the startpoint of the segment;
// 2) the endpoint of the segment;
// 3) the segment itself.
- for (typename std::vector<iSegment2D>::const_iterator it = segments.begin();
+ for (typename input_segment_set_type::iterator_type it = segments.begin();
it != segments.end(); ++it) {
- T x1 = static_cast<T>(it->first.x());
- T y1 = static_cast<T>(it->first.y());
- T x2 = static_cast<T>(it->second.x());
- T y2 = static_cast<T>(it->second.y());
+ coordinate_type x1 = static_cast<coordinate_type>(it->low().x());
+ coordinate_type y1 = static_cast<coordinate_type>(it->low().y());
+ coordinate_type x2 = static_cast<coordinate_type>(it->high().x());
+ coordinate_type y2 = static_cast<coordinate_type>(it->high().y());
site_events_.push_back(make_site_event(x1, y1, 0));
site_events_.push_back(make_site_event(x2, y2, 0));
site_events_.push_back(make_site_event(x1, y1, x2, y2, 0));
@@ -2126,8 +2175,8 @@
}
}
- // Simplify the output (remove zero-length edges).
- output_.simplify();
+ // Clean the output (remove zero-length edges).
+ output_.clean();
clear();
}
@@ -2142,7 +2191,7 @@
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<point_2d_type, beach_line_iterator> end_point_type;
+ typedef std::pair<point_type, beach_line_iterator> end_point_type;
// Init the beach line with the two first sites.
// The first site is always a point.
Copied: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_fpt_kernel.hpp (from r73453, /sandbox/SOC/2010/sweepline/boost/sweepline/detail/robust_fpt.hpp)
==============================================================================
--- /sandbox/SOC/2010/sweepline/boost/sweepline/detail/robust_fpt.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_fpt_kernel.hpp 2011-08-28 08:05:11 EDT (Sun, 28 Aug 2011)
@@ -1,4 +1,4 @@
-// Boost sweepline/mpt_wrapper.hpp header file
+// Boost sweepline/voronoi_fpt_kernel.hpp header file
// Copyright Andrii Sydorchuk 2010.
// Distributed under the Boost Software License, Version 1.0.
@@ -7,8 +7,8 @@
// See http://www.boost.org for updates, documentation, and revision history.
-#ifndef VORONOI_SWEEPLINE_ROBUST_FPT
-#define VORONOI_SWEEPLINE_ROBUST_FPT
+#ifndef BOOST_SWEEPLINE_VORONOI_FPT_KERNEL
+#define BOOST_SWEEPLINE_VORONOI_FPT_KERNEL
namespace boost {
namespace sweepline {
@@ -461,6 +461,113 @@
-val * rhs.pos());
}
+
+ ///////////////////////////////////////////////////////////////////////////
+ // VORONOI SQRT EXPR EVALUATOR ////////////////////////////////////////////
+ ///////////////////////////////////////////////////////////////////////////
+ template <int N>
+ struct sqrt_expr_evaluator {
+ template <typename mpt, typename mpf>
+ static mpf eval(mpt *A, mpt *B);
+ };
+
+ // Evaluates expression:
+ // A[0] * sqrt(B[0]).
+ template <>
+ struct sqrt_expr_evaluator<1> {
+ template <typename mpt, typename mpf>
+ static mpf eval(mpt *A, mpt *B) {
+#ifndef THREAD_SAFETY
+ static
+#endif
+ mpf a, b, ret_val;
+ a = A[0];
+ b = B[0];
+ ret_val = a * sqrt(b);
+ return ret_val;
+ }
+ };
+
+ // Evaluates expression:
+ // A[0] * sqrt(B[0]) + A[1] * sqrt(B[1]) with
+ // 7 * EPS relative error in the worst case.
+ template <>
+ struct sqrt_expr_evaluator<2> {
+ template <typename mpt, typename mpf>
+ static mpf eval(mpt *A, mpt *B) {
+#ifndef THREAD_SAFETY
+ static
+#endif
+ mpf lhs, rhs, numerator;
+ lhs = sqrt_expr_evaluator<1>::eval<mpt, mpf>(A, B);
+ rhs = sqrt_expr_evaluator<1>::eval<mpt, mpf>(A + 1, B + 1);
+ if ((lhs >= 0 && rhs >= 0) || (lhs <= 0 && rhs <= 0))
+ return lhs + rhs;
+ numerator = A[0] * A[0] * B[0] - A[1] * A[1] * B[1];
+ return numerator / (lhs - rhs);
+ }
+ };
+
+ // Evaluates expression:
+ // A[0] * sqrt(B[0]) + A[1] * sqrt(B[1]) + A[2] * sqrt(B[2])
+ // with 16 * EPS relative error in the worst case.
+ template <>
+ struct sqrt_expr_evaluator<3> {
+ template <typename mpt, typename mpf>
+ static mpf eval(mpt *A, mpt *B) {
+#ifndef THREAD_SAFETY
+ static
+#endif
+ mpt cA[2], cB[2];
+#ifndef THREAD_SAFETY
+ static
+#endif
+ mpf lhs, rhs, numer;
+ lhs = sqrt_expr_evaluator<2>::eval<mpt, mpf>(A, B);
+ rhs = sqrt_expr_evaluator<1>::eval<mpt, mpf>(A + 2, B + 2);
+ if ((lhs >= 0 && rhs >= 0) || (lhs <= 0 && rhs <= 0))
+ return lhs + rhs;
+ cA[0] = A[0] * A[0] * B[0] + A[1] * A[1] * B[1];
+ cA[0] -= A[2] * A[2] * B[2];
+ cB[0] = 1;
+ cA[1] = A[0] * A[1] * 2;
+ cB[1] = B[0] * B[1];
+ numer = sqrt_expr_evaluator<2>::eval<mpt, mpf>(cA, cB);
+ return numer / (lhs - rhs);
+ }
+ };
+
+ // Evaluates expression:
+ // A[0] * sqrt(B[0]) + A[1] * sqrt(B[1]) + A[2] * sqrt(B[2]) + A[3] * sqrt(B[3])
+ // with 25 * EPS relative error in the worst case.
+ template <>
+ struct sqrt_expr_evaluator<4> {
+ template <typename mpt, typename mpf>
+ static mpf eval(mpt *A, mpt *B) {
+#ifndef THREAD_SAFETY
+ static
+#endif
+ mpt cA[3], cB[3];
+#ifndef THREAD_SAFETY
+ static
+#endif
+ mpf lhs, rhs, numer;
+ lhs = sqrt_expr_evaluator<2>::eval<mpt, mpf>(A, B);
+ rhs = sqrt_expr_evaluator<2>::eval<mpt, mpf>(A + 2, B + 2);
+ if ((lhs >= 0 && rhs >= 0) || (lhs <= 0 && rhs <= 0))
+ return lhs + rhs;
+ cA[0] = A[0] * A[0] * B[0] + A[1] * A[1] * B[1];
+ cA[0] -= A[2] * A[2] * B[2] + A[3] * A[3] * B[3];
+ cB[0] = 1;
+ cA[1] = A[0] * A[1] * 2;
+ cB[1] = B[0] * B[1];
+ cA[2] = A[2] * A[3] * -2;
+ cB[2] = B[2] * B[3];
+ numer = sqrt_expr_evaluator<3>::eval<mpt, mpf>(cA, cB);
+ return numer / (lhs - rhs);
+ }
+ };
+
} // detail
} // sweepline
} // boost
Copied: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_diagram.hpp (from r73453, /sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp)
==============================================================================
--- /sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp (original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_diagram.hpp 2011-08-28 08:05:11 EDT (Sun, 28 Aug 2011)
@@ -1,4 +1,4 @@
-// Boost sweepline/voronoi_output.hpp header file
+// Boost sweepline/voronoi_diagram.hpp header file
// Copyright Andrii Sydorchuk 2010.
// Distributed under the Boost Software License, Version 1.0.
@@ -7,8 +7,27 @@
// See http://www.boost.org for updates, documentation, and revision history.
-#ifndef BOOST_SWEEPLINE_VORONOI_OUTPUT
-#define BOOST_SWEEPLINE_VORONOI_OUTPUT
+#ifndef BOOST_SWEEPLINE_VORONOI_DIAGRAM
+#define BOOST_SWEEPLINE_VORONOI_DIAGRAM
+
+#include <algorithm>
+#include <cmath>
+#include <cstring>
+#include <list>
+#include <map>
+#include <queue>
+#include <stack>
+#include <vector>
+
+#pragma warning(disable:4800)
+#include <gmpxx.h>
+
+#include "boost/polygon/polygon.hpp"
+using namespace boost::polygon;
+
+#include "detail/mpt_wrapper.hpp"
+#include "detail/voronoi_fpt_kernel.hpp"
+#include "detail/voronoi_formation.hpp"
namespace boost {
namespace sweepline {
@@ -18,20 +37,6 @@
///////////////////////////////////////////////////////////////////////////
// Forward declarations.
- namespace detail {
- template <typename T>
- class site_event;
-
- template <typename T>
- class circle_event;
-
- template <typename T>
- class robust_voronoi_vertex;
-
- template <typename T>
- class voronoi_builder;
- }
-
template <typename T>
class voronoi_cell;
@@ -41,84 +46,17 @@
template <typename T>
class voronoi_output;
- // Cartesian 2D point data structure.
- template <typename T>
- class point_2d {
- public:
- typedef T coordinate_type;
-
- point_2d() {}
-
- point_2d(coordinate_type x, coordinate_type y) {
- x_ = x;
- y_ = y;
- }
-
- bool operator==(const point_2d &that) const {
- return (this->x_ == that.x()) && (this->y_ == that.y());
- }
-
- bool operator!=(const point_2d &that) const {
- return (this->x_ != that.x()) || (this->y_ != that.y());
- }
-
- // Comparison function.
- // Defines ordering of the points on the 2D plane.
- bool operator<(const point_2d &that) const {
- if (this->x_ != that.x_)
- return this->x_ < that.x_;
- return this->y_ < that.y_;
- }
-
- bool operator<=(const point_2d &that) const {
- return !(that < (*this));
- }
-
- bool operator>(const point_2d &that) const {
- return that < (*this);
- }
-
- bool operator>=(const point_2d &that) const {
- return !((*this) < that);
- }
-
- coordinate_type x() const {
- return this->x_;
- }
-
- coordinate_type y() const {
- return this->y_;
- }
-
- void x(coordinate_type x) {
- x_ = x;
- }
-
- void y(coordinate_type y) {
- y_ = y;
- }
-
- private:
- coordinate_type x_;
- coordinate_type y_;
- };
-
- template <typename T>
- static inline point_2d<T> make_point_2d(T x, T y) {
- return point_2d<T>(x,y);
- }
-
// Bounding rectangle data structure. Contains coordinates
// of the bottom left and the upper right points of the rectangle.
template <typename T>
class BRect {
public:
typedef T coordinate_type;
- typedef point_2d<coordinate_type> point_2d_type;
+ typedef detail::point_2d<coordinate_type> point_type;
BRect() {}
- BRect(const point_2d_type &p1, const point_2d_type &p2) {
+ BRect(const point_type &p1, const point_type &p2) {
x_min_ = (std::min)(p1.x(), p2.x());
y_min_ = (std::min)(p1.y(), p2.y());
x_max_ = (std::max)(p1.x(), p2.x());
@@ -134,7 +72,7 @@
}
// Extend the rectangle with a new point.
- void update(const point_2d_type &p) {
+ void update(const point_type &p) {
x_min_ = (std::min)(x_min_, p.x());
y_min_ = (std::min)(y_min_, p.y());
x_max_ = (std::max)(x_max_, p.x());
@@ -142,7 +80,7 @@
}
// Check whether a point is situated inside the bounding rectangle.
- bool contains(const point_2d_type &p) const {
+ bool contains(const point_type &p) const {
return p.x() > x_min_ && p.x() < x_max_ &&
p.y() > y_min_ && p.y() < y_max_;
}
@@ -192,7 +130,10 @@
class voronoi_helper {
public:
typedef T coordinate_type;
- typedef point_2d<coordinate_type> point_2d_type;
+ typedef point_data<coordinate_type> out_point_type;
+ typedef detail::point_2d<coordinate_type> point_type;
+ typedef directed_line_segment_data<coordinate_type> segment_type;
+ typedef directed_line_segment_set_data<coordinate_type> segment_set_type;
typedef BRect<coordinate_type> brect_type;
// There are three different types of edges:
@@ -229,7 +170,7 @@
// Max_error is the maximum distance (relative to the minor of two
// rectangle sides) allowed between the parabola and line segments
// that interpolate it.
- static std::vector<point_2d_type> get_intermediate_points(
+ static std::vector<out_point_type> get_point_interpolation(
const voronoi_edge<coordinate_type> *edge,
const BRect<coordinate_type> &brect,
double max_error) {
@@ -240,7 +181,7 @@
const voronoi_cell<coordinate_type> *cell2 = edge->twin()->cell();
// edge_points - contains intermediate points.
- std::vector<point_2d_type> edge_points;
+ std::vector<point_type> edge_points;
if (!(cell1->contains_segment() ^ cell2->contains_segment())) {
// Edge is a segment, ray, or line.
if (edge->vertex0() != NULL && edge->vertex1() != NULL) {
@@ -250,12 +191,12 @@
} else {
// Edge is a ray or line.
// Clip it with the bounding rectangle.
- const point_2d_type &site1 = cell1->point0();
- const point_2d_type &site2 = cell2->point0();
- point_2d_type origin((site1.x() + site2.x()) * 0.5,
- (site1.y() + site2.y()) * 0.5);
- point_2d_type direction(site1.y() - site2.y(),
- site2.x() - site1.x());
+ const point_type &site1 = cell1->point0();
+ const point_type &site2 = cell2->point0();
+ point_type origin((site1.x() + site2.x()) * 0.5,
+ (site1.y() + site2.y()) * 0.5);
+ point_type direction(site1.y() - site2.y(),
+ site2.x() - site1.x());
// Find intersection points.
find_intersections(origin, direction, LINE,
@@ -269,15 +210,15 @@
}
} else {
// point1 - site point;
- const point_2d_type &point1 = (cell1->contains_segment()) ?
+ const point_type &point1 = (cell1->contains_segment()) ?
cell2->point0() : cell1->point0();
// point2 - startpoint of the segment site;
- const point_2d_type &point2 = (cell1->contains_segment()) ?
+ const point_type &point2 = (cell1->contains_segment()) ?
cell1->point0() : cell2->point0();
// point3 - endpoint of the segment site;
- const point_2d_type &point3 = (cell1->contains_segment()) ?
+ const point_type &point3 = (cell1->contains_segment()) ?
cell1->point1() : cell2->point1();
if (edge->vertex0() != NULL && edge->vertex1() != NULL) {
@@ -296,7 +237,7 @@
coordinate_type dir_y =
(cell1->contains_segment() ^ (point1 == point3)) ?
point2.x() - point3.x() : point3.x() - point2.x();
- point_2d_type direction(dir_x, dir_y);
+ point_type direction(dir_x, dir_y);
// Find intersection points.
find_intersections(point1, direction, LINE,
@@ -309,15 +250,36 @@
edge_points[0] = edge->vertex0()->vertex();
}
}
- return edge_points;
+ std::vector<out_point_type> ret_val;
+ for (typename std::vector<point_type>::const_iterator it = edge_points.begin();
+ it != edge_points.end(); ++it) {
+ coordinate_type x = it->x();
+ coordinate_type y = it->y();
+ ret_val.push_back(out_point_type(x, y));
+ }
+ return ret_val;
+ }
+
+ // Interpolate voronoi edge with a set of segments to satisfy maximal
+ // error requirement.
+ static segment_set_type get_segment_interpolation(
+ const voronoi_edge<coordinate_type> *edge,
+ const BRect<coordinate_type> &brect,
+ double max_error) {
+ std::vector<out_point_type> point_interpolation =
+ get_point_interpolcation(edge, brect, max_error);
+ segment_set_type ret_val;
+ for (size_t i = 1; i < point_interpolation.size(); ++i)
+ ret_val.insert(segment_type(point_interpolation[i-1], point_interpolation[i]));
+ return ret_val;
}
// Find edge-rectangle intersection points.
// Edge is represented by its origin, direction and type.
static void find_intersections(
- const point_2d_type &origin, const point_2d_type &direction,
+ const point_type &origin, const point_type &direction,
kEdgeType edge_type, const brect_type &brect,
- std::vector<point_2d_type> &intersections) {
+ std::vector<point_type> &intersections) {
// Find the center of the rectangle.
coordinate_type center_x = (brect.x_min() + brect.x_max()) * 0.5;
coordinate_type center_y = (brect.y_min() + brect.y_max()) * 0.5;
@@ -373,11 +335,11 @@
// Update intersections vector.
if (fT0_used && check_extent(fT0, edge_type))
- intersections.push_back(make_point_2d(
+ intersections.push_back(point_type(
origin.x() + fT0 * direction.x(),
origin.y() + fT0 * direction.y()));
if (fT1_used && fT0 != fT1 && check_extent(fT1, edge_type))
- intersections.push_back(make_point_2d(
+ intersections.push_back(point_type(
origin.x() + fT1 * direction.x(),
origin.y() + fT1 * direction.y()));
}
@@ -395,10 +357,10 @@
// Max_dist is the maximum distance allowed between parabola and line
// segments that interpolate it.
static void fill_intermediate_points(
- point_2d_type point_site,
- point_2d_type segment_site_start,
- point_2d_type segment_site_end,
- std::vector<point_2d_type> &intermediate_points,
+ point_type point_site,
+ point_type segment_site_start,
+ point_type segment_site_end,
+ std::vector<point_type> &intermediate_points,
double max_dist) {
// Check if bisector is a segment.
if (point_site == segment_site_start ||
@@ -439,7 +401,7 @@
segm_vec_y * point_vec_x;
// Save the last point.
- point_2d_type last_point = intermediate_points[1];
+ point_type last_point = intermediate_points[1];
intermediate_points.pop_back();
// Use stack to avoid recursion.
@@ -478,7 +440,7 @@
(segm_vec_x * new_y + segm_vec_y * new_x) /
sqr_segment_length + segment_site_start.y();
intermediate_points.push_back(
- make_point_2d(inter_x, inter_y));
+ point_type(inter_x, inter_y));
cur_x = new_x;
cur_y = new_y;
} else {
@@ -546,9 +508,9 @@
// Assumption is made that projection of the point lies
// between the startpoint and endpoint of the segment.
static coordinate_type get_point_projection(
- const point_2d_type &point,
- const point_2d_type &segment_start,
- const point_2d_type &segment_end) {
+ const point_type &point,
+ const point_type &segment_start,
+ const point_type &segment_end) {
coordinate_type segment_vec_x = segment_end.x() -
segment_start.x();
coordinate_type segment_vec_y = segment_end.y() -
@@ -572,11 +534,11 @@
class voronoi_cell {
public:
typedef T coordinate_type;
- typedef point_2d<coordinate_type> point_2d_type;
+ typedef detail::point_2d<coordinate_type> point_type;
typedef detail::site_event<coordinate_type> site_event_type;
typedef voronoi_edge<coordinate_type> voronoi_edge_type;
- voronoi_cell(const point_2d_type &p1, const point_2d_type &p2,
+ voronoi_cell(const point_type &p1, const point_type &p2,
bool contains_segment, voronoi_edge_type *edge) :
point0_(p1),
point1_(p2),
@@ -589,28 +551,25 @@
// Returns site point in case cell contains point site,
// the first point of the segment site else.
- const point_2d_type &point0() const { return point0_; }
+ const point_type &point0() const { return point0_; }
// Returns the second site of the segment site.
// Don't use with the point sites.
- const point_2d_type &point1() const { return point1_; }
+ const point_type &point1() const { return point1_; }
voronoi_edge_type *incident_edge() { return incident_edge_; }
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_; }
-
- private:
- friend class voronoi_output<coordinate_type>;
-
- void incident_edge(voronoi_edge_type *e) { incident_edge_ = e; }
void inc_num_incident_edges() { ++num_incident_edges_; }
void dec_num_incident_edges() { --num_incident_edges_; }
- point_2d_type point0_;
- point_2d_type point1_;
+ private:
+ point_type point0_;
+ point_type point1_;
bool contains_segment_;
voronoi_edge_type *incident_edge_;
int num_incident_edges_;
@@ -625,42 +584,30 @@
class voronoi_vertex {
public:
typedef T coordinate_type;
- typedef point_2d<T> point_2d_type;
+ typedef detail::point_2d<T> point_type;
typedef voronoi_edge<coordinate_type> voronoi_edge_type;
+ typedef detail::robust_voronoi_vertex<coordinate_type> robust_voronoi_vertex_type;
- voronoi_vertex(const point_2d_type &vertex, voronoi_edge_type *edge) :
+ voronoi_vertex(const point_type &vertex, voronoi_edge_type *edge) :
vertex_(vertex),
incident_edge_(edge),
num_incident_edges_(3) {}
- const point_2d_type &vertex() const { return vertex_; }
+ const robust_voronoi_vertex_type *robust_vertex() const { return robust_vertex_; }
+ void robust_voronoi_vertex(robust_voronoi_vertex_type *v) { robust_vertex_ = v; }
+
+ const point_type &vertex() const { return vertex_; }
voronoi_edge_type *incident_edge() { return incident_edge_; }
- const voronoi_edge_type *incident_edge() const {
- return incident_edge_;
- }
+ 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_; }
-
- private:
- typedef detail::robust_voronoi_vertex<coordinate_type>
- robust_voronoi_vertex_type;
-
- friend class voronoi_output<coordinate_type>;
-
- const robust_voronoi_vertex_type *robust_vertex() const {
- return robust_vertex_;
- }
-
- void robust_voronoi_vertex(robust_voronoi_vertex_type *v) {
- robust_vertex_ = v;
- }
-
- void incident_edge(voronoi_edge_type *e) { incident_edge_ = e; }
void num_incident_edges(int n) { num_incident_edges_ = n; }
+ private:
robust_voronoi_vertex_type *robust_vertex_;
- point_2d_type vertex_;
+ point_type vertex_;
voronoi_edge_type *incident_edge_;
int num_incident_edges_;
};
@@ -689,39 +636,37 @@
voronoi_cell_type *cell() { return cell_; }
const voronoi_cell_type *cell() const { return cell_; }
+ void cell(voronoi_cell_type *c) { cell_ = c; }
voronoi_vertex_type *vertex0() { return vertex_; }
const voronoi_vertex_type *vertex0() const { return vertex_; }
+ void vertex0(voronoi_vertex_type *v) { vertex_ = v; }
voronoi_vertex_type *vertex1() { return twin_->vertex0(); }
const voronoi_vertex_type *vertex1() const { return twin_->vertex0(); }
+ void vertex1(voronoi_vertex_type *v) { twin_->vertex0(v); }
voronoi_edge_type *twin() { return twin_; }
const voronoi_edge_type *twin() const { return twin_; }
+ void twin(voronoi_edge_type *e) { twin_ = e; }
voronoi_edge_type *next() { return next_; }
const voronoi_edge_type *next() const { return next_; }
+ void next(voronoi_edge_type *e) { next_ = e; }
voronoi_edge_type *prev() { return prev_; }
const voronoi_edge_type *prev() const { return prev_; }
+ void prev(voronoi_edge_type *e) { prev_ = e; }
// Return 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;
- }
- const voronoi_edge_type *rot_next() const {
- return (vertex_) ? prev_->twin() : NULL;
- }
+ voronoi_edge_type *rot_next() { return (vertex_) ? prev_->twin() : NULL; }
+ const voronoi_edge_type *rot_next() const { return (vertex_) ? prev_->twin() : NULL; }
// Return 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;
- }
- const voronoi_edge_type *rot_prev() const {
- return (vertex_) ? twin_->next() : NULL;
- }
+ voronoi_edge_type *rot_prev() { return (vertex_) ? twin_->next() : NULL; }
+ const voronoi_edge_type *rot_prev() const { return (vertex_) ? twin_->next() : NULL; }
// Return true if the edge is finite (segment, parabolic arc).
// Return false if the edge is infinite (ray, line).
@@ -730,15 +675,13 @@
// Return true if the edge is linear.
// Return false if the edge is curved (parabolic arc).
bool is_linear() const {
- return !(cell()->contains_segment() ^
- twin()->cell()->contains_segment());
+ return !(cell()->contains_segment() ^ twin()->cell()->contains_segment());
}
// Returns true if the edge is curved (parabolic arc).
// Returns false if the edge is linear.
bool is_curved() const {
- return (cell()->contains_segment() ^
- twin()->cell()->contains_segment());
+ return (cell()->contains_segment() ^ twin()->cell()->contains_segment());
}
// Return false if edge goes through the endpoint of the segment.
@@ -746,14 +689,12 @@
bool is_primary() const {
voronoi_cell_type *cell1 = cell_;
voronoi_cell_type *cell2 = twin_->cell();
- if (cell1->contains_segment() &&
- !cell2->contains_segment()) {
+ if (cell1->contains_segment() && !cell2->contains_segment()) {
if (cell1->point0() == cell2->point0() ||
cell1->point1() == cell2->point0())
return false;
}
- if (cell2->contains_segment() &&
- !cell1->contains_segment()) {
+ if (cell2->contains_segment() && !cell1->contains_segment()) {
if (cell2->point0() == cell1->point0() ||
cell2->point1() == cell1->point0())
return false;
@@ -762,15 +703,6 @@
}
private:
- friend class voronoi_output<coordinate_type>;
-
- void cell(voronoi_cell_type *c) { cell_ = c; }
- void vertex0(voronoi_vertex_type *v) { vertex_ = v; }
- void vertex1(voronoi_vertex_type *v) { twin_->vertex0(v); }
- void twin(voronoi_edge_type *e) { twin_ = e; }
- void next(voronoi_edge_type *e) { next_ = e; }
- void prev(voronoi_edge_type *e) { prev_ = e; }
-
voronoi_cell_type *cell_;
voronoi_vertex_type *vertex_;
voronoi_edge_type *twin_;
@@ -809,7 +741,7 @@
class voronoi_output {
public:
typedef T coordinate_type;
- typedef point_2d<coordinate_type> point_2d_type;
+ typedef detail::point_2d<coordinate_type> point_type;
typedef voronoi_cell<coordinate_type> voronoi_cell_type;
typedef std::vector<voronoi_cell_type> voronoi_cells_type;
@@ -848,7 +780,7 @@
num_vertex_records_ = 0;
}
- const BRect<T> &bounding_rectangle() const {
+ const BRect<coordinate_type> &bounding_rectangle() const {
return voronoi_rect_;
}
@@ -882,7 +814,7 @@
typedef detail::robust_voronoi_vertex<coordinate_type>
robust_voronoi_vertex_type;
- friend class detail::voronoi_builder<T>;
+ friend class detail::voronoi_builder<int>;
void init(int num_sites) {
// Resize cell vector to avoid reallocations.
@@ -974,13 +906,11 @@
voronoi_edge_type *edge23) {
// Add a new voronoi vertex.
robust_vertices_.push_back(
- robust_voronoi_vertex_type(circle.erc_x(),
- circle.erc_y(),
- circle.erc_denom()));
+ robust_voronoi_vertex_type(circle.erc_x(), circle.erc_y()));
const robust_voronoi_vertex_type &robust_vertex =
robust_vertices_.back();
vertex_records_.push_back(voronoi_vertex_type(
- make_point_2d(robust_vertex.x(), robust_vertex.y()), edge12));
+ point_type(robust_vertex.x(), robust_vertex.y()), edge12));
voronoi_vertex_type &new_vertex = vertex_records_.back();
new_vertex.robust_voronoi_vertex(&robust_vertices_.back());
@@ -1020,7 +950,7 @@
}
// Remove zero-length edges from the voronoi output.
- void simplify() {
+ void clean() {
voronoi_edge_iterator_type edge_it1;
voronoi_edge_iterator_type edge_it = edge_records_.begin();
num_cell_records_ = cell_records_.size();
@@ -1230,6 +1160,43 @@
void operator=(const voronoi_output&);
};
+ // 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].
+ // Complexity - O(N*logN), memory usage - O(N), where N is the total
+ // number of points and segments.
+
+ template <typename T>
+ static inline void build_voronoi(
+ const typename detail::voronoi_traits<T>::input_point_set_type &points,
+ typename detail::voronoi_traits<T>::output_type &output) {
+ typename detail::voronoi_traits<T>::input_segment_set_type segments_empty;
+ build_voronoi<T>(points, segments_empty, output);
+ }
+
+ template <typename T>
+ static inline void build_voronoi(
+ const typename detail::voronoi_traits<T>::input_segment_set_type &segments,
+ typename detail::voronoi_traits<T>::output_type &output) {
+ typename detail::voronoi_traits<T>::input_point_set_type points_empty;
+ build_voronoi<T>(points_empty, segments, output);
+ }
+
+ template <typename T>
+ static inline void build_voronoi(
+ const typename detail::voronoi_traits<T>::input_point_set_type &points,
+ const typename detail::voronoi_traits<T>::input_segment_set_type &segments,
+ typename detail::voronoi_traits<T>::output_type &output) {
+ detail::voronoi_builder<T> builder(output);
+ builder.init(points, segments);
+ builder.run_sweepline();
+ }
+
} // sweepline
} // boost
Deleted: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp 2011-08-28 08:05:11 EDT (Sun, 28 Aug 2011)
+++ (empty file)
@@ -1,1236 +0,0 @@
-// Boost sweepline/voronoi_output.hpp header file
-
-// Copyright Andrii Sydorchuk 2010.
-// 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)
-
-// See http://www.boost.org for updates, documentation, and revision history.
-
-#ifndef BOOST_SWEEPLINE_VORONOI_OUTPUT
-#define BOOST_SWEEPLINE_VORONOI_OUTPUT
-
-namespace boost {
-namespace sweepline {
-
- ///////////////////////////////////////////////////////////////////////////
- // VORONOI OUTPUT TYPES ///////////////////////////////////////////////////
- ///////////////////////////////////////////////////////////////////////////
-
- // Forward declarations.
- namespace detail {
- template <typename T>
- class site_event;
-
- template <typename T>
- class circle_event;
-
- template <typename T>
- class robust_voronoi_vertex;
-
- template <typename T>
- class voronoi_builder;
- }
-
- template <typename T>
- class voronoi_cell;
-
- template <typename T>
- class voronoi_edge;
-
- template <typename T>
- class voronoi_output;
-
- // Cartesian 2D point data structure.
- template <typename T>
- class point_2d {
- public:
- typedef T coordinate_type;
-
- point_2d() {}
-
- point_2d(coordinate_type x, coordinate_type y) {
- x_ = x;
- y_ = y;
- }
-
- bool operator==(const point_2d &that) const {
- return (this->x_ == that.x()) && (this->y_ == that.y());
- }
-
- bool operator!=(const point_2d &that) const {
- return (this->x_ != that.x()) || (this->y_ != that.y());
- }
-
- // Comparison function.
- // Defines ordering of the points on the 2D plane.
- bool operator<(const point_2d &that) const {
- if (this->x_ != that.x_)
- return this->x_ < that.x_;
- return this->y_ < that.y_;
- }
-
- bool operator<=(const point_2d &that) const {
- return !(that < (*this));
- }
-
- bool operator>(const point_2d &that) const {
- return that < (*this);
- }
-
- bool operator>=(const point_2d &that) const {
- return !((*this) < that);
- }
-
- coordinate_type x() const {
- return this->x_;
- }
-
- coordinate_type y() const {
- return this->y_;
- }
-
- void x(coordinate_type x) {
- x_ = x;
- }
-
- void y(coordinate_type y) {
- y_ = y;
- }
-
- private:
- coordinate_type x_;
- coordinate_type y_;
- };
-
- template <typename T>
- static inline point_2d<T> make_point_2d(T x, T y) {
- return point_2d<T>(x,y);
- }
-
- // Bounding rectangle data structure. Contains coordinates
- // of the bottom left and the upper right points of the rectangle.
- template <typename T>
- class BRect {
- public:
- typedef T coordinate_type;
- typedef point_2d<coordinate_type> point_2d_type;
-
- BRect() {}
-
- BRect(const point_2d_type &p1, const point_2d_type &p2) {
- x_min_ = (std::min)(p1.x(), p2.x());
- y_min_ = (std::min)(p1.y(), p2.y());
- x_max_ = (std::max)(p1.x(), p2.x());
- y_max_ = (std::max)(p1.y(), 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);
- }
-
- // Extend the rectangle with a new point.
- void update(const point_2d_type &p) {
- x_min_ = (std::min)(x_min_, p.x());
- y_min_ = (std::min)(y_min_, p.y());
- x_max_ = (std::max)(x_max_, p.x());
- y_max_ = (std::max)(y_max_, p.y());
- }
-
- // Check whether a point is situated inside the bounding rectangle.
- bool contains(const point_2d_type &p) const {
- return p.x() > x_min_ && p.x() < x_max_ &&
- p.y() > y_min_ && p.y() < y_max_;
- }
-
- // Check whether the bounding rectangle has a non-zero area.
- bool is_valid() const {
- return (x_min_ < x_max_) && (y_min_ < y_max_);
- }
-
- // Return the x-coordinate of the bottom left point of the rectangle.
- coordinate_type x_min() const {
- return x_min_;
- }
-
- // Return the y-coordinate of the bottom left point of the rectangle.
- coordinate_type y_min() const {
- return y_min_;
- }
-
- // Return the x-coordinate of the upper right point of the rectangle.
- coordinate_type x_max() const {
- return x_max_;
- }
-
- // Return the y-coordinate of the upper right point of the rectangle.
- coordinate_type y_max() const {
- return y_max_;
- }
-
- coordinate_type min_len() const {
- return (std::min)(x_max_ - x_min_, y_max_ - y_min_);
- }
-
- coordinate_type max_len() const {
- return (std::max)(x_max_ - x_min_, y_max_ - y_min_);
- }
-
- private:
- coordinate_type x_min_;
- coordinate_type y_min_;
- coordinate_type x_max_;
- coordinate_type y_max_;
- };
-
- // Voronoi output postprocessing tools.
- template <typename T>
- class voronoi_helper {
- public:
- typedef T coordinate_type;
- typedef point_2d<coordinate_type> point_2d_type;
- typedef BRect<coordinate_type> brect_type;
-
- // There are three different types of edges:
- // 1) Segment edge - has both endpoints;
- // 2) Ray edge - has one endpoint, infinite
- // in the positive direction;
- // 3) Line edge - is infinite in both directions.
- enum kEdgeType {
- SEGMENT = 0,
- RAY = 1,
- LINE = 2,
- };
-
- // Get a view rectangle based on the voronoi bounding rectangle.
- static BRect<coordinate_type> get_view_rectangle(
- const BRect<coordinate_type> &brect) {
- coordinate_type x_len = (brect.x_max() - brect.x_min());
- coordinate_type y_len = (brect.y_max() - brect.y_min());
- coordinate_type x_mid = (brect.x_max() + brect.x_min()) * 0.5;
- coordinate_type y_mid = (brect.y_max() + brect.y_min()) * 0.5;
- coordinate_type offset = x_len;
- if (offset < y_len)
- offset = y_len;
- if (offset == 0.0)
- offset = 0.5;
- BRect<coordinate_type> new_brect(x_mid - offset, y_mid - offset,
- x_mid + offset, y_mid + offset);
- return new_brect;
- }
-
- // Compute intermediate points for the voronoi edge within the given
- // bounding rectangle. The assumption is made that voronoi rectangle
- // contains all the finite endpoints of the edge.
- // Max_error is the maximum distance (relative to the minor of two
- // rectangle sides) allowed between the parabola and line segments
- // that interpolate it.
- static std::vector<point_2d_type> get_intermediate_points(
- const voronoi_edge<coordinate_type> *edge,
- const BRect<coordinate_type> &brect,
- double max_error) {
- // Retrieve the cell to the left of the current edge.
- const voronoi_cell<coordinate_type> *cell1 = edge->cell();
-
- // Retrieve the cell to the right of the current edge.
- const voronoi_cell<coordinate_type> *cell2 = edge->twin()->cell();
-
- // edge_points - contains intermediate points.
- std::vector<point_2d_type> edge_points;
- if (!(cell1->contains_segment() ^ cell2->contains_segment())) {
- // Edge is a segment, ray, or line.
- if (edge->vertex0() != NULL && edge->vertex1() != NULL) {
- // Edge is a segment. No further processing is required.
- edge_points.push_back(edge->vertex0()->vertex());
- edge_points.push_back(edge->vertex1()->vertex());
- } else {
- // Edge is a ray or line.
- // Clip it with the bounding rectangle.
- const point_2d_type &site1 = cell1->point0();
- const point_2d_type &site2 = cell2->point0();
- point_2d_type origin((site1.x() + site2.x()) * 0.5,
- (site1.y() + site2.y()) * 0.5);
- point_2d_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] = edge->vertex1()->vertex();
- if (edge->vertex0() != NULL)
- edge_points[0] = edge->vertex0()->vertex();
- }
- } else {
- // point1 - site point;
- const point_2d_type &point1 = (cell1->contains_segment()) ?
- cell2->point0() : cell1->point0();
-
- // point2 - startpoint of the segment site;
- const point_2d_type &point2 = (cell1->contains_segment()) ?
- cell1->point0() : cell2->point0();
-
- // point3 - endpoint of the segment site;
- const point_2d_type &point3 = (cell1->contains_segment()) ?
- cell1->point1() : cell2->point1();
-
- if (edge->vertex0() != NULL && edge->vertex1() != NULL) {
- // Edge is a segment or parabolic arc.
- edge_points.push_back(edge->vertex0()->vertex());
- edge_points.push_back(edge->vertex1()->vertex());
- double max_dist = max_error * brect.min_len();
- fill_intermediate_points(point1, point2, point3,
- edge_points, max_dist);
- } else {
- // Edge is a ray or line.
- // Clip it with the bounding rectangle.
- coordinate_type dir_x =
- (cell1->contains_segment() ^ (point1 == point3)) ?
- point3.y() - point2.y() : point2.y() - point3.y();
- coordinate_type dir_y =
- (cell1->contains_segment() ^ (point1 == point3)) ?
- point2.x() - point3.x() : point3.x() - point2.x();
- point_2d_type direction(dir_x, dir_y);
-
- // 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] = edge->vertex1()->vertex();
- if (edge->vertex0() != NULL)
- edge_points[0] = edge->vertex0()->vertex();
- }
- }
- return edge_points;
- }
-
- // Find edge-rectangle intersection points.
- // Edge is represented by its origin, direction and type.
- static void find_intersections(
- const point_2d_type &origin, const point_2d_type &direction,
- kEdgeType edge_type, const brect_type &brect,
- std::vector<point_2d_type> &intersections) {
- // Find the center of the rectangle.
- coordinate_type center_x = (brect.x_min() + brect.x_max()) * 0.5;
- coordinate_type center_y = (brect.y_min() + brect.y_max()) * 0.5;
-
- // Find the half-diagonal vector of the rectangle.
- coordinate_type len_x = brect.x_max() - center_x;
- coordinate_type len_y = brect.y_max() - center_y;
-
- // Find the vector between the origin and the center of the
- // rectangle.
- coordinate_type diff_x = origin.x() - center_x;
- coordinate_type diff_y = origin.y() - center_y;
-
- // Find the vector perpendicular to the direction vector.
- coordinate_type perp_x = direction.y();
- coordinate_type perp_y = -direction.x();
-
- // Projection of the vector between the origin and the center of
- // the rectangle on the line perpendicular to the direction vector.
- coordinate_type lexpr = magnitude(perp_x * diff_x +
- perp_y * diff_y);
-
- // Maximum projection among any of the half-diagonals of the
- // rectangle on the line perpendicular to the direction vector.
- coordinate_type rexpr = magnitude(perp_x * len_x) +
- magnitude(perp_y * len_y);
-
- // Intersection check. Compare projections.
- if (lexpr > rexpr)
- return;
-
- // Intersection parameters. If fT[i]_used is true than:
- // origin + fT[i] * direction = intersection point, i = 0 .. 1.
- // For different edge types next fT values are acceptable:
- // Segment: [0; 1];
- // Ray: [0; infinity];
- // Line: [-infinity; infinity].
- bool fT0_used = false;
- bool fT1_used = false;
- coordinate_type fT0 = 0;
- coordinate_type fT1 = 0;
-
- // Check for the intersections with the lines
- // going through the sides of the bounding rectangle.
- clip_line(+direction.x(), -diff_x - len_x,
- fT0_used, fT1_used, fT0, fT1);
- clip_line(-direction.x(), +diff_x - len_x,
- fT0_used, fT1_used, fT0, fT1);
- clip_line(+direction.y(), -diff_y - len_y,
- fT0_used, fT1_used, fT0, fT1);
- clip_line(-direction.y(), +diff_y - len_y,
- fT0_used, fT1_used, fT0, fT1);
-
- // Update intersections vector.
- if (fT0_used && check_extent(fT0, edge_type))
- intersections.push_back(make_point_2d(
- origin.x() + fT0 * direction.x(),
- origin.y() + fT0 * direction.y()));
- if (fT1_used && fT0 != fT1 && check_extent(fT1, edge_type))
- intersections.push_back(make_point_2d(
- origin.x() + fT1 * direction.x(),
- origin.y() + fT1 * direction.y()));
- }
-
- private:
- voronoi_helper();
-
- // Find intermediate points of the parabola. Number of points
- // is defined by the value of max_dist parameter - maximum distance
- // between parabola and line segments that interpolate it.
- // 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
- // between the given two endpoints.
- // Max_dist is the maximum distance allowed between parabola and line
- // segments that interpolate it.
- static void fill_intermediate_points(
- point_2d_type point_site,
- point_2d_type segment_site_start,
- point_2d_type segment_site_end,
- std::vector<point_2d_type> &intermediate_points,
- double max_dist) {
- // Check if bisector is a segment.
- if (point_site == segment_site_start ||
- point_site == segment_site_end)
- return;
-
- // Apply the linear transformation to move start point of the
- // segment to the point with coordinates (0, 0) and the direction
- // of the segment to coincide the positive direction of the x-axis.
- coordinate_type segm_vec_x = segment_site_end.x() -
- segment_site_start.x();
- coordinate_type segm_vec_y = segment_site_end.y() -
- segment_site_start.y();
- coordinate_type sqr_segment_length = segm_vec_x * segm_vec_x +
- segm_vec_y * segm_vec_y;
-
- // Compute x-coordinates of the endpoints of the edge
- // in the transformed space.
- coordinate_type projection_start = sqr_segment_length *
- get_point_projection(intermediate_points[0],
- segment_site_start,
- segment_site_end);
- coordinate_type projection_end = sqr_segment_length *
- get_point_projection(intermediate_points[1],
- segment_site_start,
- segment_site_end);
-
- // Compute parabola parameterers in the transformed space.
- // Parabola has next representation:
- // f(x) = ((x-rot_x)^2 + rot_y^2) / (2.0*rot_y).
- coordinate_type point_vec_x = point_site.x() -
- segment_site_start.x();
- coordinate_type point_vec_y = point_site.y() -
- segment_site_start.y();
- coordinate_type rot_x = segm_vec_x * point_vec_x +
- segm_vec_y * point_vec_y;
- coordinate_type rot_y = segm_vec_x * point_vec_y -
- segm_vec_y * point_vec_x;
-
- // Save the last point.
- point_2d_type last_point = intermediate_points[1];
- intermediate_points.pop_back();
-
- // Use stack to avoid recursion.
- std::stack< coordinate_type > point_stack;
- point_stack.push(projection_end);
- coordinate_type cur_x = projection_start;
- coordinate_type cur_y = parabola_y(cur_x, rot_x, rot_y);
-
- // Adjust max_dist parameter in the transformed space.
- max_dist *= max_dist * sqr_segment_length;
-
- while (!point_stack.empty()) {
- coordinate_type new_x = point_stack.top();
- coordinate_type new_y = parabola_y(new_x, rot_x, rot_y);
-
- // Compute coordinates of the point of the parabola that is
- // furthest from the current line segment.
- coordinate_type mid_x = (new_y - cur_y) / (new_x - cur_x) *
- rot_y + rot_x;
- coordinate_type mid_y = parabola_y(mid_x, rot_x, rot_y);
-
- // Compute maximum distance between the given parabolic arc
- // and line segment that interpolates it.
- double dist = (new_y - cur_y) * (mid_x - cur_x) -
- (new_x - cur_x) * (mid_y - cur_y);
- dist = dist * dist / ((new_y - cur_y) * (new_y - cur_y) +
- (new_x - cur_x) * (new_x - cur_x));
- if (dist <= max_dist) {
- // Distance between parabola and line segment is
- // not greater than max_dist.
- point_stack.pop();
- coordinate_type inter_x =
- (segm_vec_x * new_x - segm_vec_y * new_y) /
- sqr_segment_length + segment_site_start.x();
- coordinate_type inter_y =
- (segm_vec_x * new_y + segm_vec_y * new_x) /
- sqr_segment_length + segment_site_start.y();
- intermediate_points.push_back(
- make_point_2d(inter_x, inter_y));
- cur_x = new_x;
- cur_y = new_y;
- } else {
- point_stack.push(mid_x);
- }
- }
-
- // Update last point.
- intermediate_points.back() = last_point;
- }
-
- // Compute y(x) = ((x - a) * (x - a) + b * b) / (2 * b).
- static coordinate_type parabola_y(coordinate_type x,
- coordinate_type a,
- coordinate_type b) {
- return ((x - a) * (x - a) + b * b) / (2.0 * b);
- }
-
- // Check whether extent is compatible with the edge type.
- static bool check_extent(coordinate_type extent, kEdgeType etype) {
- switch (etype) {
- case SEGMENT:
- return extent >= static_cast<coordinate_type>(0.0) &&
- extent <= static_cast<coordinate_type>(1.0);
- case RAY: return extent >= static_cast<coordinate_type>(0.0);
- case LINE: return true;
- }
- return true;
- }
-
- // Compute the absolute value.
- static inline coordinate_type magnitude(coordinate_type value) {
- if (value >= static_cast<coordinate_type>(0.0))
- return value;
- return -value;
- }
-
- // Find fT min and max values: fT = numer / denom.
- static void clip_line(coordinate_type denom, coordinate_type numer,
- bool &fT0_used, bool &fT1_used,
- coordinate_type &fT0, coordinate_type &fT1) {
- if (denom > static_cast<coordinate_type>(0.0)) {
- if (fT1_used && numer > denom * fT1)
- return;
- if (!fT0_used || numer > denom * fT0) {
- fT0_used = true;
- fT0 = numer / denom;
- }
- } else if (denom < static_cast<coordinate_type>(0.0)) {
- if (fT0_used && numer > denom * fT0)
- return;
- if (!fT1_used || numer > denom * fT1) {
- fT1_used = true;
- fT1 = numer / denom;
- }
- }
- }
-
- // Get normalized length of the distance between:
- // 1) point projection onto the segment;
- // 2) start point of the segment.
- // Return this length divided by the segment length.
- // This is made to avoid sqrt computation during transformation from
- // the initial space to the transformed one and vice versa.
- // Assumption is made that projection of the point lies
- // between the startpoint and endpoint of the segment.
- static coordinate_type get_point_projection(
- const point_2d_type &point,
- const point_2d_type &segment_start,
- const point_2d_type &segment_end) {
- coordinate_type segment_vec_x = segment_end.x() -
- segment_start.x();
- coordinate_type segment_vec_y = segment_end.y() -
- segment_start.y();
- coordinate_type point_vec_x = point.x() - segment_start.x();
- coordinate_type point_vec_y = point.y() - segment_start.y();
- coordinate_type sqr_segment_length =
- segment_vec_x * segment_vec_x + segment_vec_y * segment_vec_y;
- coordinate_type vec_dot = segment_vec_x * point_vec_x +
- segment_vec_y * point_vec_y;
- return vec_dot / sqr_segment_length;
- }
- };
-
- // Represents voronoi cell.
- // Data members: 1) pointer to the incident edge;
- // 2) site inside the cell;
- // 3) number of incident edges.
- // The cell may contain point or segment site.
- template <typename T>
- class voronoi_cell {
- public:
- typedef T coordinate_type;
- typedef point_2d<coordinate_type> point_2d_type;
- typedef detail::site_event<coordinate_type> site_event_type;
- typedef voronoi_edge<coordinate_type> voronoi_edge_type;
-
- voronoi_cell(const point_2d_type &p1, const point_2d_type &p2,
- bool contains_segment, voronoi_edge_type *edge) :
- point0_(p1),
- point1_(p2),
- contains_segment_(contains_segment),
- incident_edge_(edge),
- num_incident_edges_(0) {}
-
- // Returns true if the cell contains segment site, false else.
- bool contains_segment() const { return contains_segment_; }
-
- // Returns site point in case cell contains point site,
- // the first point of the segment site else.
- const point_2d_type &point0() const { return point0_; }
-
- // Returns the second site of the segment site.
- // Don't use with the point sites.
- const point_2d_type &point1() const { return point1_; }
-
- voronoi_edge_type *incident_edge() { return incident_edge_; }
- const voronoi_edge_type *incident_edge() const {
- return incident_edge_;
- }
-
- int num_incident_edges() const { return num_incident_edges_; }
-
- private:
- friend class voronoi_output<coordinate_type>;
-
- void incident_edge(voronoi_edge_type *e) { incident_edge_ = e; }
- void inc_num_incident_edges() { ++num_incident_edges_; }
- void dec_num_incident_edges() { --num_incident_edges_; }
-
- point_2d_type point0_;
- point_2d_type point1_;
- bool contains_segment_;
- voronoi_edge_type *incident_edge_;
- int num_incident_edges_;
- };
-
- // Represents voronoi vertex.
- // Data members: 1) robust vertex data structure;
- // 2) vertex point itself;
- // 3) pointer to the incident edge;
- // 4) number of incident edges.
- template <typename T>
- class voronoi_vertex {
- public:
- typedef T coordinate_type;
- typedef point_2d<T> point_2d_type;
- typedef voronoi_edge<coordinate_type> voronoi_edge_type;
-
- voronoi_vertex(const point_2d_type &vertex, voronoi_edge_type *edge) :
- vertex_(vertex),
- incident_edge_(edge),
- num_incident_edges_(3) {}
-
- const point_2d_type &vertex() const { return vertex_; }
-
- voronoi_edge_type *incident_edge() { return incident_edge_; }
- const voronoi_edge_type *incident_edge() const {
- return incident_edge_;
- }
-
- int num_incident_edges() const { return num_incident_edges_; }
-
- private:
- typedef detail::robust_voronoi_vertex<coordinate_type>
- robust_voronoi_vertex_type;
-
- friend class voronoi_output<coordinate_type>;
-
- const robust_voronoi_vertex_type *robust_vertex() const {
- return robust_vertex_;
- }
-
- void robust_voronoi_vertex(robust_voronoi_vertex_type *v) {
- robust_vertex_ = v;
- }
-
- void incident_edge(voronoi_edge_type *e) { incident_edge_ = e; }
- void num_incident_edges(int n) { num_incident_edges_ = n; }
-
- robust_voronoi_vertex_type *robust_vertex_;
- point_2d_type vertex_;
- voronoi_edge_type *incident_edge_;
- int num_incident_edges_;
- };
-
- // 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/CW next edge.
- // 5) pointer to the CCW/CW prev edge.
- template <typename T>
- class voronoi_edge {
- public:
- typedef T coordinate_type;
- typedef voronoi_cell<coordinate_type> voronoi_cell_type;
- typedef voronoi_vertex<coordinate_type> voronoi_vertex_type;
- typedef voronoi_edge<coordinate_type> voronoi_edge_type;
-
- voronoi_edge() :
- cell_(NULL),
- vertex_(NULL),
- twin_(NULL),
- next_(NULL),
- prev_(NULL) {}
-
- voronoi_cell_type *cell() { return cell_; }
- const voronoi_cell_type *cell() const { return cell_; }
-
- voronoi_vertex_type *vertex0() { return vertex_; }
- const voronoi_vertex_type *vertex0() const { return vertex_; }
-
- voronoi_vertex_type *vertex1() { return twin_->vertex0(); }
- const voronoi_vertex_type *vertex1() const { return twin_->vertex0(); }
-
- voronoi_edge_type *twin() { return twin_; }
- const voronoi_edge_type *twin() const { return twin_; }
-
- voronoi_edge_type *next() { return next_; }
- const voronoi_edge_type *next() const { return next_; }
-
- voronoi_edge_type *prev() { return prev_; }
- const voronoi_edge_type *prev() const { return prev_; }
-
- // Return 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;
- }
- const voronoi_edge_type *rot_next() const {
- return (vertex_) ? prev_->twin() : NULL;
- }
-
- // Return 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;
- }
- const voronoi_edge_type *rot_prev() const {
- return (vertex_) ? twin_->next() : NULL;
- }
-
- // Return true if the edge is finite (segment, parabolic arc).
- // Return false if the edge is infinite (ray, line).
- bool is_bounded() const { return vertex0() && vertex1(); }
-
- // Return true if the edge is linear.
- // Return false if the edge is curved (parabolic arc).
- bool is_linear() const {
- return !(cell()->contains_segment() ^
- twin()->cell()->contains_segment());
- }
-
- // Returns true if the edge is curved (parabolic arc).
- // Returns false if the edge is linear.
- bool is_curved() const {
- return (cell()->contains_segment() ^
- twin()->cell()->contains_segment());
- }
-
- // Return false if edge goes through the endpoint of the segment.
- // Return true else.
- bool is_primary() const {
- voronoi_cell_type *cell1 = cell_;
- voronoi_cell_type *cell2 = twin_->cell();
- if (cell1->contains_segment() &&
- !cell2->contains_segment()) {
- if (cell1->point0() == cell2->point0() ||
- cell1->point1() == cell2->point0())
- return false;
- }
- if (cell2->contains_segment() &&
- !cell1->contains_segment()) {
- if (cell2->point0() == cell1->point0() ||
- cell2->point1() == cell1->point0())
- return false;
- }
- return true;
- }
-
- private:
- friend class voronoi_output<coordinate_type>;
-
- void cell(voronoi_cell_type *c) { cell_ = c; }
- void vertex0(voronoi_vertex_type *v) { vertex_ = v; }
- void vertex1(voronoi_vertex_type *v) { twin_->vertex0(v); }
- void twin(voronoi_edge_type *e) { twin_ = e; }
- void next(voronoi_edge_type *e) { next_ = e; }
- void prev(voronoi_edge_type *e) { prev_ = e; }
-
- voronoi_cell_type *cell_;
- voronoi_vertex_type *vertex_;
- voronoi_edge_type *twin_;
- voronoi_edge_type *next_;
- voronoi_edge_type *prev_;
- };
-
- // Voronoi output data structure.
- // Data members:
- // 1) cell_records_ - vector of the voronoi cells;
- // 2) vertex_records_ - list of the voronoi vertices;
- // 3) edge_records_ - list of the voronoi edges;
- // 4) robust_vertices_ - list of the robust vertices;
- // 5) voronoi_rect_ - bounding rectangle;
- // 6) num_cell_records_ - number of the voronoi cells;
- // 7) num_vertex_records_ - number of the voronoi vertices;
- // 8) num_edge_records_ - number of the voronoi edges.
- // CCW ordering is used on the faces perimeter and around the vertices.
- // Robust vertices are used to make the simplification stage epsilon
- // robust. Vector data structure is used to store voronoi cells as the
- // number of the cells may be precomputed at the initialization step.
- // As size() method takes O(n) time on the list data structure three
- // additional counters are used to count the number of the voronoi cells,
- // vertices and edges. As we use list data structure to represent voronoi
- // vertices and edges there is no copy method available, because it will
- // invalidate all the pointers. Another approach could be used to make
- // copying available:
- // 1) use vectors to store voronoi vertices and cells;
- // 2) store vector indices instead of the pointers;
- // 3) store additional pointer to the voronoi output data structure
- // in the voronoi cell, vertex, edge data structure.
- // 4) implement simplification via copying not degenerate elements
- // to the new vector as removing elements from a vector takes O(n)
- // time.
- template <typename T>
- class voronoi_output {
- public:
- typedef T coordinate_type;
- typedef point_2d<coordinate_type> point_2d_type;
-
- typedef voronoi_cell<coordinate_type> voronoi_cell_type;
- typedef std::vector<voronoi_cell_type> voronoi_cells_type;
- typedef typename voronoi_cells_type::iterator
- voronoi_cell_iterator_type;
- typedef typename voronoi_cells_type::const_iterator
- voronoi_cell_const_iterator_type;
-
- typedef voronoi_vertex<coordinate_type> voronoi_vertex_type;
- typedef std::list<voronoi_vertex_type> voronoi_vertices_type;
- typedef typename voronoi_vertices_type::iterator
- voronoi_vertex_iterator_type;
- typedef typename voronoi_vertices_type::const_iterator
- voronoi_vertex_const_iterator_type;
-
- typedef voronoi_edge<coordinate_type> voronoi_edge_type;
- typedef std::list<voronoi_edge_type> voronoi_edges_type;
- typedef typename voronoi_edges_type::iterator
- voronoi_edge_iterator_type;
- typedef typename voronoi_edges_type::const_iterator
- voronoi_edge_const_iterator_type;
-
- voronoi_output() :
- num_cell_records_(0),
- num_edge_records_(0),
- num_vertex_records_(0) {}
-
- void clear() {
- robust_vertices_.clear();
- voronoi_cells_type().swap(cell_records_);
- vertex_records_.clear();
- edge_records_.clear();
-
- num_cell_records_ = 0;
- num_edge_records_ = 0;
- num_vertex_records_ = 0;
- }
-
- const BRect<T> &bounding_rectangle() const {
- return voronoi_rect_;
- }
-
- const voronoi_cells_type &cell_records() const {
- return cell_records_;
- }
-
- const voronoi_vertices_type &vertex_records() const {
- return vertex_records_;
- }
-
- const voronoi_edges_type &edge_records() const {
- return edge_records_;
- }
-
- int num_cell_records() const {
- return num_cell_records_;
- }
-
- int num_edge_records() const {
- return num_edge_records_;
- }
-
- int num_vertex_records() const {
- return num_vertex_records_;
- }
-
- private:
- typedef detail::site_event<coordinate_type> site_event_type;
- typedef detail::circle_event<coordinate_type> circle_event_type;
- typedef detail::robust_voronoi_vertex<coordinate_type>
- robust_voronoi_vertex_type;
-
- friend class detail::voronoi_builder<T>;
-
- void init(int num_sites) {
- // Resize cell vector to avoid reallocations.
- cell_records_.reserve(num_sites);
-
- // Init counters.
- num_cell_records_ = 0;
- num_edge_records_ = 0;
- num_vertex_records_ = 0;
- }
-
- // Update the voronoi output in case of a single point input.
- void process_single_site(const site_event_type &site) {
- // Update bounding rectangle.
- voronoi_rect_ = BRect<coordinate_type>(site.point0(),
- site.point0());
-
- // Update cell records.
- cell_records_.push_back(voronoi_cell_type(site.point0(),
- site.point1(),
- site.is_segment(),
- NULL));
- }
-
- // Insert a new half-edge into the output data structure.
- // Takes as input left and right sites that form a new bisector.
- // Returns a pointer to a new half-edge.
- voronoi_edge_type *insert_new_edge(const site_event_type &site1,
- const site_event_type &site2) {
- // Get sites' indices.
- int site_index1 = site1.index();
- int site_index2 = site2.index();
-
- // Create a new half-edge that belongs to the first site.
- edge_records_.push_back(voronoi_edge_type());
- voronoi_edge_type &edge1 = edge_records_.back();
-
- // Create a new half-edge that belongs to the second site.
- edge_records_.push_back(voronoi_edge_type());
- voronoi_edge_type &edge2 = edge_records_.back();
-
- // Add the initial cell during the first edge insertion.
- if (cell_records_.empty()) {
- cell_records_.push_back(voronoi_cell_type(site1.point0(),
- site1.point1(),
- site1.is_segment(),
- &edge1));
- voronoi_rect_ = BRect<coordinate_type>(site1.point0(),
- site1.point0());
- }
- cell_records_[site_index1].inc_num_incident_edges();
-
- // Update the bounding rectangle.
- voronoi_rect_.update(site2.point0());
- if (site2.is_segment()) {
- voronoi_rect_.update(site2.point1());
- }
-
- // The second site represents a new site during site event
- // processing. Add a new cell to the cell records.
- cell_records_.push_back(voronoi_cell_type(site2.point0(),
- site2.point1(),
- site2.is_segment(),
- &edge2));
- cell_records_.back().inc_num_incident_edges();
-
- // Set up pointers to cells.
- edge1.cell(&cell_records_[site_index1]);
- edge2.cell(&cell_records_[site_index2]);
-
- // Set up twin pointers.
- edge1.twin(&edge2);
- edge2.twin(&edge1);
-
- // Return a pointer to the new half-edge.
- return &edge1;
- }
-
- // Insert a new half-edge into the output data structure with the
- // start at the point where two previously added half-edges intersect.
- // Takes as input two sites that create a new bisector, circle event
- // that correponds 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 pointer to the new half-edge.
- voronoi_edge_type *insert_new_edge(const site_event_type &site1,
- const site_event_type &site3,
- const circle_event_type &circle,
- voronoi_edge_type *edge12,
- voronoi_edge_type *edge23) {
- // Add a new voronoi vertex.
- robust_vertices_.push_back(
- robust_voronoi_vertex_type(circle.erc_x(),
- circle.erc_y(),
- circle.erc_denom()));
- const robust_voronoi_vertex_type &robust_vertex =
- robust_vertices_.back();
- vertex_records_.push_back(voronoi_vertex_type(
- make_point_2d(robust_vertex.x(), robust_vertex.y()), edge12));
- voronoi_vertex_type &new_vertex = vertex_records_.back();
- new_vertex.robust_voronoi_vertex(&robust_vertices_.back());
-
- // Update vertex pointers of the old edges.
- edge12->vertex0(&new_vertex);
- edge23->vertex0(&new_vertex);
-
- // Add a new half-edge.
- edge_records_.push_back(voronoi_edge_type());
- voronoi_edge_type &new_edge1 = edge_records_.back();
- new_edge1.cell(&cell_records_[site1.index()]);
- new_edge1.cell()->inc_num_incident_edges();
-
- // Add a new half-edge.
- edge_records_.push_back(voronoi_edge_type());
- voronoi_edge_type &new_edge2 = edge_records_.back();
- new_edge2.cell(&cell_records_[site3.index()]);
- new_edge2.cell()->inc_num_incident_edges();
-
- // Update twin pointers.
- new_edge1.twin(&new_edge2);
- new_edge2.twin(&new_edge1);
-
- // Update vertex pointer.
- new_edge2.vertex0(&new_vertex);
-
- // Update voronoi prev/next pointers.
- edge12->prev(&new_edge1);
- new_edge1.next(edge12);
- edge12->twin()->next(edge23);
- edge23->prev(edge12->twin());
- edge23->twin()->next(&new_edge2);
- new_edge2.prev(edge23->twin());
-
- // Return a pointer to the new half-edge.
- return &new_edge1;
- }
-
- // Remove zero-length edges from the voronoi output.
- void simplify() {
- voronoi_edge_iterator_type edge_it1;
- voronoi_edge_iterator_type edge_it = edge_records_.begin();
- num_cell_records_ = cell_records_.size();
-
- // All the initial sites are colinear.
- if (vertex_records_.empty()) {
- // Update edges counter.
- num_edge_records_ = num_cell_records_ - 1;
-
- // Return if there are no edges.
- if (edge_it == edge_records_.end())
- return;
-
- // Update prev/next pointers of the edges. Those edges won't
- // have any common endpoints, cause they are infinite.
- // But still they follow each other using CCW ordering.
- voronoi_edge_type *edge1 = &(*edge_it);
- edge1->next(edge1);
- edge1->prev(edge1);
- ++edge_it;
- edge1 = &(*edge_it);
- ++edge_it;
-
- while (edge_it != edge_records_.end()) {
- voronoi_edge_type *edge2 = &(*edge_it);
- ++edge_it;
-
- edge1->next(edge2);
- edge1->prev(edge2);
- edge2->next(edge1);
- edge2->prev(edge1);
-
- edge1 = &(*edge_it);
- ++edge_it;
- }
-
- edge1->next(edge1);
- edge1->prev(edge1);
- return;
- }
-
- // Iterate over all the edges and remove degeneracies
- // (zero-length edges). Edge is considered to be zero-length
- // if both its endpoints lie within some epsilon-rectangle.
- while (edge_it != edge_records_.end()) {
- edge_it1 = edge_it;
- std::advance(edge_it, 2);
-
- // Degenerate edges exist only among finite edges.
- if (!edge_it1->vertex0() || !edge_it1->vertex1()) {
- ++num_edge_records_;
- continue;
- }
-
- const voronoi_vertex_type *v1 = edge_it1->vertex0();
- const voronoi_vertex_type *v2 = edge_it1->vertex1();
-
- // Make epsilon robust check.
- if (v1->robust_vertex()->equals(v2->robust_vertex(), 128)) {
- // Decrease number of cell's incident edges.
- edge_it1->cell()->dec_num_incident_edges();
- edge_it1->twin()->cell()->dec_num_incident_edges();
-
- // Corresponding cell incident edge pointer
- // points to the degenerate edge.
- if (edge_it1->cell()->incident_edge() == &(*edge_it1)) {
- // Update incident edge pointer.
- if (edge_it1->cell()->incident_edge() ==
- edge_it1->next()) {
- edge_it1->cell()->incident_edge(NULL);
- } else {
- edge_it1->cell()->incident_edge(edge_it1->next());
- }
- }
-
- // Cell corresponding to the twin edge
- // points to the degenerate edge.
- if (edge_it1->twin()->cell()->incident_edge() ==
- edge_it1->twin()) {
- // Update incident edge pointer.
- if (edge_it1->twin()->cell()->incident_edge() ==
- edge_it1->twin()->next()) {
- edge_it1->twin()->cell()->incident_edge(NULL);
- } else {
- edge_it1->twin()->cell()->incident_edge(
- edge_it1->twin()->next());
- }
- }
-
- // 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));
- } else {
- remove_edge(edge_it1->twin());
- }
-
- // Remove zero-length edge.
- edge_records_.erase(edge_it1, edge_it);
- } else {
- // Count not degenerate edge.
- ++num_edge_records_;
- }
- }
- robust_vertices_.clear();
-
- // Remove degenerate voronoi vertices with zero incident edges.
- for (voronoi_vertex_iterator_type vertex_it =
- vertex_records_.begin();
- vertex_it != vertex_records_.end();) {
- if (vertex_it->incident_edge() == NULL) {
- vertex_it = vertex_records_.erase(vertex_it);
- } else {
- ++vertex_it;
- ++num_vertex_records_;
- }
- }
-
- // Update prev/next pointers for the ray-edges.
- for (voronoi_cell_iterator_type cell_it = cell_records_.begin();
- cell_it != cell_records_.end(); ++cell_it) {
- // Move to the previous edge while
- // it is possible in the CW direction.
- voronoi_edge_type *cur_edge = cell_it->incident_edge();
- if (cur_edge) {
- while (cur_edge->prev() != NULL) {
- cur_edge = cur_edge->prev();
-
- // Terminate if this is not a boundary cell.
- if (cur_edge == cell_it->incident_edge())
- break;
- }
-
- // Rewind incident edge pointer to the
- // CW leftmost edge for the boundary cells.
- cell_it->incident_edge(cur_edge);
-
- // Set up prev/next half-edge pointers for the ray-edges.
- if (cur_edge->prev() == NULL) {
- voronoi_edge_type *last_edge =
- cell_it->incident_edge();
- while (last_edge->next() != NULL)
- last_edge = last_edge->next();
- last_edge->next(cur_edge);
- cur_edge->prev(last_edge);
- }
- }
- }
- }
-
- // Remove degenerate edge.
- void remove_edge(voronoi_edge_type *edge) {
- voronoi_vertex_type *vertex1 = edge->vertex0();
- voronoi_vertex_type *vertex2 = edge->vertex1();
-
- // Update number of incident edges.
- vertex1->num_incident_edges(vertex1->num_incident_edges() +
- vertex2->num_incident_edges() - 2);
-
- // Update the endpoints of the incident edges to the second vertex.
- voronoi_edge_type *updated_edge = edge->twin()->rot_next();
- while (updated_edge != edge->twin()) {
- updated_edge->vertex0(vertex1);
- updated_edge = updated_edge->rot_next();
- }
-
- voronoi_edge_type *edge1 = edge;
- voronoi_edge_type *edge2 = edge->twin();
-
- voronoi_edge_type *edge1_rot_prev = edge1->rot_prev();
- voronoi_edge_type *edge1_rot_next = edge1->rot_next();
-
- voronoi_edge_type *edge2_rot_prev = edge2->rot_prev();
- voronoi_edge_type *edge2_rot_next = edge2->rot_next();
-
- // Update prev/next pointers for the incident edges.
- edge1_rot_next->twin()->next(edge2_rot_prev);
- edge2_rot_prev->prev(edge1_rot_next->twin());
- edge1_rot_prev->prev(edge2_rot_next->twin());
- edge2_rot_next->twin()->next(edge1_rot_prev);
-
- // Change the pointer to the incident edge if it points to the
- // degenerate edge.
- if (vertex1->incident_edge() == edge) {
- vertex1->incident_edge(edge->rot_prev());
- }
-
- // Set the incident edge point of the second vertex to NULL value.
- if (vertex1 != vertex2) {
- vertex2->incident_edge(NULL);
- }
- }
-
- std::list< robust_voronoi_vertex_type > robust_vertices_;
- voronoi_cells_type cell_records_;
- voronoi_vertices_type vertex_records_;
- voronoi_edges_type edge_records_;
-
- int num_cell_records_;
- int num_edge_records_;
- int num_vertex_records_;
-
- BRect<coordinate_type> voronoi_rect_;
-
- // Disallow copy constructor and operator=
- voronoi_output(const voronoi_output&);
- void operator=(const voronoi_output&);
- };
-
-} // sweepline
-} // boost
-
-#endif
Deleted: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_sweepline.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_sweepline.hpp 2011-08-28 08:05:11 EDT (Sun, 28 Aug 2011)
+++ (empty file)
@@ -1,82 +0,0 @@
-// Boost sweepline/voronoi_sweepline.hpp header file
-
-// Copyright Andrii Sydorchuk 2010.
-// 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)
-
-// See http://www.boost.org for updates, documentation, and revision history.
-
-#ifndef BOOST_SWEEPLINE_VORONOI_SWEEPLINE
-#define BOOST_SWEEPLINE_VORONOI_SWEEPLINE
-
-#include <algorithm>
-#include <cmath>
-#include <cstring>
-#include <list>
-#include <map>
-#include <queue>
-#include <stack>
-#include <vector>
-
-#ifndef BOOST_POLYGON_USE_LONG_LONG
-#include <boost/config.hpp>
-#ifdef BOOST_HAS_LONG_LONG
-#define BOOST_POLYGON_USE_LONG_LONG
-typedef boost::long_long_type polygon_long_long_type;
-typedef boost::ulong_long_type polygon_ulong_long_type;
-#endif
-#endif
-
-#pragma warning(disable:4800)
-#include <gmpxx.h>
-
-#include "voronoi_output.hpp"
-#include "detail/mpt_wrapper.hpp"
-#include "detail/robust_fpt.hpp"
-#include "detail/sqrt_expr_evaluator.hpp"
-#include "detail/voronoi_formation.hpp"
-
-namespace boost {
-namespace sweepline {
-
- // 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].
- // Complexity - O(N*logN), memory usage - O(N), where N is the total
- // number of points and segments.
-
- template <typename T>
- static inline void build_voronoi(const std::vector< point_2d<T> > &points,
- voronoi_output<double> &output) {
- std::vector< std::pair< point_2d<T>, point_2d<T> > > segments_empty;
- build_voronoi<T>(points, segments_empty, output);
- }
-
- template <typename T>
- static inline void build_voronoi(
- const std::vector< std::pair< point_2d<T>, point_2d<T> > > &segments,
- voronoi_output<double> &output) {
- std::vector< point_2d<T> > points_empty;
- build_voronoi<T>(points_empty, segments, output);
- }
-
- template <typename T>
- static inline void build_voronoi(
- const std::vector< point_2d<T> > &points,
- const std::vector< std::pair< point_2d<T>, point_2d<T> > > &segments,
- voronoi_output<double> &output) {
- detail::voronoi_builder<double> builder(output);
- builder.init(points, segments);
- builder.run_sweepline();
- }
-
-} // sweepline
-} // boost
-
-#endif
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/example/voronoi_visualizer.cpp 2011-08-28 08:05:11 EDT (Sun, 28 Aug 2011)
@@ -12,7 +12,7 @@
#include <QtOpenGL/QGLWidget>
#include <QtGui/QtGui>
-#include "boost/sweepline/voronoi_sweepline.hpp"
+#include "boost/sweepline/voronoi_diagram.hpp"
using namespace boost::sweepline;
class GLWidget : public QGLWidget {
@@ -29,8 +29,8 @@
}
void build(QString file_path) {
- std::vector<ipoint_2d_type> point_sites;
- std::vector<isegment_2d_type> segment_sites;
+ ipoint_set_type point_sites;
+ isegment_set_type segment_sites;
// Open file.
QFile data(file_path);
@@ -46,18 +46,18 @@
in_stream >> num_point_sites;
for (int i = 0; i < num_point_sites; i++) {
in_stream >> x1 >> y1;
- point_sites.push_back(make_point_2d(x1, y1));
+ point_sites.push_back(ipoint_type(x1, y1));
}
in_stream >> num_edge_sites;
for (int i = 0; i < num_edge_sites; i++) {
in_stream >> x1 >> y1 >> x2 >> y2;
- segment_sites.push_back(std::make_pair(
- make_point_2d(x1, y1), make_point_2d(x2, y2)));
+ segment_sites.insert(isegment_type(
+ ipoint_type(x1, y1), ipoint_type(x2, y2)));
}
in_stream.flush();
// Build voronoi diagram.
- build_voronoi(point_sites, segment_sites, voronoi_output_);
+ build_voronoi<int>(point_sites, segment_sites, voronoi_output_);
brect_ = voronoi_helper<coordinate_type>::get_view_rectangle(
voronoi_output_.bounding_rectangle());
@@ -126,8 +126,8 @@
for (it = edges.begin(); it != edges.end(); it++) {
if (!it->is_primary() && primary_edges_only_)
continue;
- std::vector<point_2d_type> temp_v =
- voronoi_helper<coordinate_type>::get_intermediate_points(&(*it), brect_, 1E-3);
+ std::vector<opoint_type> temp_v =
+ voronoi_helper<coordinate_type>::get_point_interpolation(&(*it), brect_, 1E-3);
for (int i = 0; i < static_cast<int>(temp_v.size()) - 1; i++) {
glVertex2f(temp_v[i].x(), temp_v[i].y());
glVertex2f(temp_v[i+1].x(), temp_v[i+1].y());
@@ -155,9 +155,12 @@
}
typedef double coordinate_type;
- typedef point_2d<coordinate_type> point_2d_type;
- typedef point_2d<int> ipoint_2d_type;
- typedef std::pair<ipoint_2d_type, ipoint_2d_type> isegment_2d_type;
+ typedef boost::sweepline::detail::point_2d<coordinate_type> point_type;
+ typedef point_data<int> ipoint_type;
+ typedef point_data<double> opoint_type;
+ typedef directed_line_segment_data<int> isegment_type;
+ typedef std::vector<ipoint_type> ipoint_set_type;
+ typedef directed_line_segment_set_data<int> isegment_set_type;
typedef voronoi_output<coordinate_type>::voronoi_cells_type voronoi_cells_type;
typedef voronoi_output<coordinate_type>::voronoi_vertices_type voronoi_vertices_type;
typedef voronoi_output<coordinate_type>::voronoi_edges_type voronoi_edges_type;
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/benchmark_test.cpp 2011-08-28 08:05:11 EDT (Sun, 28 Aug 2011)
@@ -7,17 +7,18 @@
// See http://www.boost.org for updates, documentation, and revision history.
+#include <cstdio>
#include <iostream>
-#include <stdio.h>
#define BOOST_TEST_MODULE benchmark_test
+#include <boost/mpl/list.hpp>
#include <boost/random/mersenne_twister.hpp>
#include <boost/test/test_case_template.hpp>
#include <boost/timer.hpp>
-#include "test_type_list.hpp"
-#include "boost/sweepline/voronoi_sweepline.hpp"
-using namespace boost::sweepline;
+#include "boost/sweepline/voronoi_diagram.hpp"
+
+typedef boost::mpl::list<int> test_types;
#ifdef WIN32
#pragma warning( disable : 4996 )
@@ -27,7 +28,7 @@
typedef T coordinate_type;
boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
boost::timer timer;
- voronoi_output<coordinate_type> test_output;
+ typename boost::sweepline::detail::voronoi_traits<coordinate_type>::output_type test_output;
FILE *bench_file = fopen("benchmark.txt", "a");
fprintf(bench_file, "Voronoi Segment Sweepline Benchmark Test (time in seconds):\n");
@@ -39,18 +40,20 @@
int max_points = 100;
#endif
+ typename boost::sweepline::detail::voronoi_traits<coordinate_type>::input_point_set_type points;
+ typedef typename boost::sweepline::detail::voronoi_traits<coordinate_type>::input_point_type
+ input_point_type;
for (int num_points = 10; num_points <= max_points; num_points *= 10) {
- std::vector< point_2d<T> > points;
points.resize(num_points);
-
timer.restart();
int num_tests = max_points / num_points;
for (int cur = 0; cur < num_tests; cur++) {
for (int cur_point = 0; cur_point < num_points; cur_point++) {
- points[cur_point] = point_2d<coordinate_type>(
- static_cast<int>(gen()), static_cast<int>(gen()));
+ points[cur_point] = point_mutable_traits<input_point_type>::construct(
+ static_cast<coordinate_type>(gen()),
+ static_cast<coordinate_type>(gen()));
}
- build_voronoi(points, test_output);
+ boost::sweepline::build_voronoi<coordinate_type>(points, test_output);
}
double elapsed_time = timer.elapsed();
double time_per_test = elapsed_time / num_tests;
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/circle_event_creation_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/circle_event_creation_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/circle_event_creation_test.cpp 2011-08-28 08:05:11 EDT (Sun, 28 Aug 2011)
@@ -7,87 +7,90 @@
// See http://www.boost.org for updates, documentation, and revision history.
-#include "test_type_list.hpp"
-#include "boost/sweepline/voronoi_sweepline.hpp"
-using namespace boost::sweepline;
-
#define BOOST_TEST_MODULE circle_event_creation
+#include <boost/mpl/list.hpp>
#include <boost/test/test_case_template.hpp>
+#include "boost/sweepline/voronoi_diagram.hpp"
+using namespace boost::sweepline;
+using namespace boost::sweepline::detail;
+
+typedef boost::mpl::list<double> test_types;
+
#define CHECK_CIRCLE_EVENT(c_e, c_x, c_y, l_x) \
- BOOST_CHECK_EQUAL(detail::almost_equal(c_e.x(), static_cast<T>(c_x), 10), true); \
- BOOST_CHECK_EQUAL(detail::almost_equal(c_e.y(), static_cast<T>(c_y), 10), true); \
- BOOST_CHECK_EQUAL(detail::almost_equal(c_e.lower_x(), static_cast<T>(l_x), 10), true)
+ BOOST_CHECK_EQUAL(almost_equal(c_e.x(), static_cast<T>(c_x), 10), true); \
+ BOOST_CHECK_EQUAL(almost_equal(c_e.y(), static_cast<T>(c_y), 10), true); \
+ BOOST_CHECK_EQUAL(almost_equal(c_e.lower_x(), static_cast<T>(l_x), 10), true)
// Test for (point, point, point) case.
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_creation_ppp_test1, T, test_types) {
- typedef typename detail::site_event<T> site_event_type;
+ typedef site_event<T> site_event_type;
site_event_type site1(static_cast<T>(0), static_cast<T>(0), 0);
site_event_type site2(static_cast<T>(-8), static_cast<T>(0), 1);
site_event_type site3(static_cast<T>(0), static_cast<T>(6), 2);
- typename detail::circle_event<T> c_event;
- bool is_event = detail::create_circle_event_ppp(site1, site2, site3, c_event);
+ circle_event<T> c_event;
+ bool is_event = create_circle_event_ppp(site1, site2, site3, c_event);
BOOST_CHECK_EQUAL(is_event, true);
CHECK_CIRCLE_EVENT(c_event, -4, 3, 1);
- is_event = detail::create_circle_event_ppp(site2, site1, site3, c_event);
+ is_event = create_circle_event_ppp(site2, site1, site3, c_event);
BOOST_CHECK_EQUAL(is_event, false);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_creation_ppp_test2, T, test_types) {
- typedef typename detail::site_event<T> site_event_type;
+ typedef site_event<T> site_event_type;
int min_int = std::numeric_limits<int>::min();
int max_int = std::numeric_limits<int>::max();
site_event_type site1(static_cast<T>(min_int), static_cast<T>(min_int), 0);
site_event_type site2_1(static_cast<T>(min_int), static_cast<T>(max_int), 1);
site_event_type site2_2(static_cast<T>(max_int-1), static_cast<T>(max_int-1), 1);
site_event_type site3(static_cast<T>(max_int), static_cast<T>(max_int), 2);
- typename detail::circle_event<T> c_event;
- bool is_event = detail::create_circle_event_ppp(site1, site2_1, site3, c_event);
+ circle_event<T> c_event;
+ bool is_event = create_circle_event_ppp(site1, site2_1, site3, c_event);
BOOST_CHECK_EQUAL(is_event, true);
- is_event = detail::create_circle_event_ppp(site1, site2_2, site3, c_event);
+ is_event = create_circle_event_ppp(site1, site2_2, site3, c_event);
BOOST_CHECK_EQUAL(is_event, false);
}
// Test for (point, point, segment) case.
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_creation_pps_test1, T, test_types) {
- typedef typename detail::site_event<T> site_event_type;
+ typedef site_event<T> site_event_type;
site_event_type segm_start(static_cast<T>(-4), static_cast<T>(0), 0);
site_event_type segm_end(static_cast<T>(0), static_cast<T>(4), 0);
site_event_type segm_site(segm_start.point0(), segm_end.point0(), 0);
- typename detail::circle_event<T> c_event;
- bool is_event = detail::create_circle_event_pps(segm_start, segm_end, segm_site, 2, c_event);
+ circle_event<T> c_event;
+ bool is_event = create_circle_event_pps(segm_start, segm_end, segm_site, 2, c_event);
BOOST_CHECK_EQUAL(is_event, false);
site_event_type site1_1(static_cast<T>(-2), static_cast<T>(0), 0);
site_event_type site1_2(static_cast<T>(0), static_cast<T>(2), 0);
- is_event = detail::create_circle_event_pps(site1_1, site1_2, segm_site, 2, c_event);
+ is_event = create_circle_event_pps(site1_1, site1_2, segm_site, 2, c_event);
BOOST_CHECK_EQUAL(is_event, true);
BOOST_CHECK_EQUAL(c_event.center().x() == static_cast<T>(-1), true);
BOOST_CHECK_EQUAL(c_event.center().y() == static_cast<T>(1), true);
- is_event = detail::create_circle_event_pps(site1_1, site1_2, segm_site, 1, c_event);
+ is_event = create_circle_event_pps(site1_1, site1_2, segm_site, 1, c_event);
BOOST_CHECK_EQUAL(is_event, false);
- is_event = detail::create_circle_event_pps(site1_1, site1_2, segm_site, 3, c_event);
+ is_event = create_circle_event_pps(site1_1, site1_2, segm_site, 3, c_event);
BOOST_CHECK_EQUAL(is_event, false);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_creation_pps_test2, T, test_types) {
- typedef typename detail::site_event<T> site_event_type;
+ typedef site_event<T> site_event_type;
site_event_type segm_start(static_cast<T>(-4), static_cast<T>(0), 0);
site_event_type segm_end(static_cast<T>(-4), static_cast<T>(20), 0);
site_event_type segm_site(segm_start.point0(), segm_end.point0(), 0);
- typename detail::circle_event<T> c_event;
+ circle_event<T> c_event;
site_event_type site1_1(static_cast<T>(-2), static_cast<T>(10), 0);
site_event_type site1_2(static_cast<T>(4), static_cast<T>(10), 0);
- bool is_event = detail::create_circle_event_pps(site1_1, site1_2, segm_site, 1, c_event);
+ bool is_event = create_circle_event_pps(site1_1, site1_2, segm_site, 1, c_event);
BOOST_CHECK_EQUAL(is_event, true);
CHECK_CIRCLE_EVENT(c_event, 1, 6, 6);
- is_event = detail::create_circle_event_pps(site1_2, site1_1, segm_site, 3, c_event);
+ is_event = create_circle_event_pps(site1_2, site1_1, segm_site, 3, c_event);
BOOST_CHECK_EQUAL(is_event, true);
CHECK_CIRCLE_EVENT(c_event, 1, 14, 6);
}
// Test for (point, segment, segment) case.
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_creation_pss_test1, T, test_types) {
- typedef typename detail::site_event<T> site_event_type;
+ typedef site_event<T> site_event_type;
point_2d<T> segm1_start(static_cast<T>(1), static_cast<T>(0));
point_2d<T> segm1_end(static_cast<T>(7), static_cast<T>(0));
site_event_type segm_site1(segm1_start, segm1_end, 0);
@@ -95,21 +98,21 @@
point_2d<T> segm2_start(static_cast<T>(-2), static_cast<T>(4));
point_2d<T> segm2_end(static_cast<T>(10), static_cast<T>(4));
site_event_type segm_site2(segm2_start, segm2_end, 1);
- typename detail::circle_event<T> c_event;
+ circle_event<T> c_event;
site_event_type site1(static_cast<T>(6), static_cast<T>(2), 2);
- bool is_event = detail::create_circle_event_pss(site1, segm_site1, segm_site2, 3, c_event);
+ bool is_event = create_circle_event_pss(site1, segm_site1, segm_site2, 3, c_event);
BOOST_CHECK_EQUAL(is_event, true);
CHECK_CIRCLE_EVENT(c_event, 4, 2, 6);
site_event_type site2(static_cast<T>(1), static_cast<T>(0), 2);
- is_event = detail::create_circle_event_pss(site2, segm_site1, segm_site2, 2, c_event);
+ is_event = create_circle_event_pss(site2, segm_site1, segm_site2, 2, c_event);
BOOST_CHECK_EQUAL(is_event, true);
CHECK_CIRCLE_EVENT(c_event, 1, 2, 3);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_creation_pss_test2, T, test_types) {
- typedef typename detail::site_event<T> site_event_type;
+ typedef site_event<T> site_event_type;
point_2d<T> segm1_start(static_cast<T>(-1), static_cast<T>(2));
point_2d<T> segm1_end(static_cast<T>(8), static_cast<T>(-10));
site_event_type segm_site1(segm1_start, segm1_end, 0);
@@ -117,15 +120,15 @@
point_2d<T> segm2_start(static_cast<T>(-1), static_cast<T>(0));
point_2d<T> segm2_end(static_cast<T>(8), static_cast<T>(12));
site_event_type segm_site2(segm2_start, segm2_end, 1);
- typename detail::circle_event<T> c_event;
+ circle_event<T> c_event;
site_event_type site1(static_cast<T>(1), static_cast<T>(1), 2);
- bool is_event = detail::create_circle_event_pss(site1, segm_site1, segm_site2, 2, c_event);
+ bool is_event = create_circle_event_pss(site1, segm_site1, segm_site2, 2, c_event);
BOOST_CHECK_EQUAL(is_event, true);
CHECK_CIRCLE_EVENT(c_event, 6, 1, 11);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_creation_pss_test3, T, test_types) {
- typedef typename detail::site_event<T> site_event_type;
+ typedef site_event<T> site_event_type;
point_2d<T> segm1_start(static_cast<T>(1), static_cast<T>(0));
point_2d<T> segm1_end(static_cast<T>(6), static_cast<T>(0));
site_event_type segm_site1(segm1_start, segm1_end, 0);
@@ -133,15 +136,15 @@
point_2d<T> segm2_start(static_cast<T>(-6), static_cast<T>(4));
point_2d<T> segm2_end(static_cast<T>(0), static_cast<T>(12));
site_event_type segm_site2(segm2_start, segm2_end, 1);
- typename detail::circle_event<T> c_event;
+ circle_event<T> c_event;
site_event_type site1(static_cast<T>(1), static_cast<T>(0), 2);
- bool is_event = detail::create_circle_event_pss(site1, segm_site1, segm_site2, 2, c_event);
+ bool is_event = create_circle_event_pss(site1, segm_site1, segm_site2, 2, c_event);
BOOST_CHECK_EQUAL(is_event, true);
CHECK_CIRCLE_EVENT(c_event, 1, 5, 6);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_creation_pss_test4, T, test_types) {
- typedef typename detail::site_event<T> site_event_type;
+ typedef site_event<T> site_event_type;
point_2d<T> point1(static_cast<T>(1), static_cast<T>(0));
point_2d<T> point2(static_cast<T>(5), static_cast<T>(0));
point_2d<T> point3(static_cast<T>(8), static_cast<T>(6));
@@ -150,8 +153,8 @@
segm_site1.inverse();
site_event_type segm_site2(point3, point4, 1);
site_event_type point_site(point1, 2);
- typename detail::circle_event<T> c_event;
- bool is_event = detail::create_circle_event_pss(
+ circle_event<T> c_event;
+ bool is_event = create_circle_event_pss(
point_site, segm_site1, segm_site2, 2, c_event);
BOOST_CHECK_EQUAL(is_event, true);
CHECK_CIRCLE_EVENT(c_event, 1, 5, 6);
@@ -159,7 +162,7 @@
// Test for (segment, segment, segment) case.
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_creation_sss_test1, T, test_types) {
- typedef typename detail::site_event<T> site_event_type;
+ typedef site_event<T> site_event_type;
point_2d<T> point1(static_cast<T>(4), static_cast<T>(0));
point_2d<T> point2(static_cast<T>(0), static_cast<T>(0));
point_2d<T> point3(static_cast<T>(0), static_cast<T>(4));
@@ -168,14 +171,14 @@
segm_site1.inverse();
site_event_type segm_site2(point2, point3, 1);
site_event_type segm_site3(point3, point4, 2);
- typename detail::circle_event<T> c_event;
- bool is_event = detail::create_circle_event_sss(segm_site1, segm_site2, segm_site3, c_event);
+ circle_event<T> c_event;
+ bool is_event = create_circle_event_sss(segm_site1, segm_site2, segm_site3, c_event);
BOOST_CHECK_EQUAL(is_event, true);
CHECK_CIRCLE_EVENT(c_event, 2, 2, 4);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_creation_sss_test2, T, test_types) {
- typedef typename detail::site_event<T> site_event_type;
+ typedef site_event<T> site_event_type;
point_2d<T> point1(static_cast<T>(41), static_cast<T>(30));
point_2d<T> point2(static_cast<T>(1), static_cast<T>(0));
point_2d<T> point3(static_cast<T>(-39), static_cast<T>(30));
@@ -184,8 +187,8 @@
segm_site1.inverse();
site_event_type segm_site2(point3, point4, 1);
site_event_type segm_site3(point4, point1, 2);
- typename detail::circle_event<T> c_event;
- bool is_event = detail::create_circle_event_sss(segm_site1, segm_site2, segm_site3, c_event);
+ circle_event<T> c_event;
+ bool is_event = create_circle_event_sss(segm_site1, segm_site2, segm_site3, c_event);
BOOST_CHECK_EQUAL(is_event, true);
CHECK_CIRCLE_EVENT(c_event, 1, 30, 25);
}
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/clipping_test.cpp 2011-08-28 08:05:11 EDT (Sun, 28 Aug 2011)
@@ -7,15 +7,15 @@
// See http://www.boost.org for updates, documentation, and revision history.
-#include <stdlib.h>
-#include <time.h>
+#define BOOST_TEST_MODULE voronoi_clipping_test
+#include <boost/mpl/list.hpp>
+#include <boost/test/test_case_template.hpp>
-#include "test_type_list.hpp"
-#include "boost/sweepline/voronoi_sweepline.hpp"
+#include "boost/sweepline/voronoi_diagram.hpp"
using namespace boost::sweepline;
+using namespace boost::sweepline::detail;
-#define BOOST_TEST_MODULE voronoi_clipping_test
-#include <boost/test/test_case_template.hpp>
+typedef boost::mpl::list<double> test_types;
// Test segment clipping.
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_clipping_test1, T, test_types) {
@@ -87,7 +87,6 @@
BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
static_cast<T>(4.0), static_cast<T>(3.0));
std::vector< point_2d<T> > intersections;
- srand(static_cast<unsigned int>(time(NULL)));
point_2d<T> test_origin(2, 1);
for (int i = -50; i <= 50; i++)
@@ -107,7 +106,6 @@
BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
static_cast<T>(4.0), static_cast<T>(3.0));
std::vector< point_2d<T> > intersections;
- srand(static_cast<unsigned int>(time(NULL)));
point_2d<T> test_origin(2, 1);
for (int i = -50; i <= 50; i++)
@@ -179,7 +177,6 @@
BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
static_cast<T>(4.0), static_cast<T>(3.0));
std::vector< point_2d<T> > intersections;
- srand(static_cast<unsigned int>(time(NULL)));
point_2d<T> test_origin(2, 1);
for (int i = -50; i <= 50; i++)
@@ -252,7 +249,6 @@
BRect<T> test_rect(static_cast<T>(0.0), static_cast<T>(-1.0),
static_cast<T>(4.0), static_cast<T>(3.0));
std::vector< point_2d<T> > intersections;
- srand(static_cast<unsigned int>(time(NULL)));
point_2d<T> test_origin(2, 1);
for (int i = -50; i <= 50; i++)
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp 2011-08-28 08:05:11 EDT (Sun, 28 Aug 2011)
@@ -9,26 +9,29 @@
#include <cmath>
-#include "test_type_list.hpp"
-#include "boost/sweepline/voronoi_sweepline.hpp"
-using namespace boost::sweepline;
-
#define BOOST_TEST_MODULE event_queue_test
+#include <boost/mpl/list.hpp>
#include <boost/test/test_case_template.hpp>
+#include "boost/sweepline/voronoi_diagram.hpp"
+using namespace boost::sweepline;
+using namespace boost::sweepline::detail;
+
+typedef boost::mpl::list<double> test_types;
+
#define CHECK_TOP_ELEMENT_EQUALITY(TOP, X, Y) \
BOOST_CHECK_EQUAL(TOP.lower_x() == static_cast<T>(X) && \
TOP.y() == static_cast<T>(Y), true)
BOOST_AUTO_TEST_CASE_TEMPLATE(event_queue_test1, T, test_types) {
- detail::circle_events_queue<T> event_q;
+ circle_events_queue<T> event_q;
BOOST_CHECK_EQUAL(event_q.empty(), true);
event_q.clear();
for (int i = 0; i < 10; i++) {
T x = static_cast<T>(-i);
T y = static_cast<T>(10-i);
- event_q.push(detail::make_circle_event<T>(x, y, x + static_cast<T>(10)));
+ event_q.push(make_circle_event<T>(x, y, x + static_cast<T>(10)));
}
for (int i = 0; i < 10; i++) {
@@ -40,15 +43,14 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(event_queue_test2, T, test_types) {
- typedef detail::circle_event<T> circle_event_type;
- detail::circle_events_queue<T> event_q;
- detail::site_event<T> temp_site =
- detail::make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0);
+ typedef circle_event<T> circle_event_type;
+ circle_events_queue<T> event_q;
+ site_event<T> temp_site = make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0);
for (int i = 0; i < 10; i++) {
T x = static_cast<T>(10-i);
T y = static_cast<T>(10-i);
- circle_event_type c = detail::make_circle_event<T>(x, y, x);
+ circle_event_type c = make_circle_event<T>(x, y, x);
if (i&1)
event_q.push(c)->deactivate();
else
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp 2011-08-28 08:05:11 EDT (Sun, 28 Aug 2011)
@@ -7,13 +7,15 @@
// See http://www.boost.org for updates, documentation, and revision history.
-#include "test_type_list.hpp"
-#include "boost/sweepline/voronoi_sweepline.hpp"
+#define BOOST_TEST_MODULE event_types_test
+#include <boost/mpl/list.hpp>
+#include <boost/test/test_case_template.hpp>
+
+#include "boost/sweepline/voronoi_diagram.hpp"
using namespace boost::sweepline;
using namespace boost::sweepline::detail;
-#define BOOST_TEST_MODULE event_types_test
-#include <boost/test/test_case_template.hpp>
+typedef boost::mpl::list<double> test_types;
#define EVENT_TYPES_CHECK_COMPARISON(A, B, ARR) \
BOOST_CHECK_EQUAL((A)<(B), (ARR)[0]); \
@@ -24,21 +26,21 @@
BOOST_CHECK_EQUAL((A)!=(B), (ARR)[5])
BOOST_AUTO_TEST_CASE_TEMPLATE(point_2d_test1, T, test_types) {
- point_2d<T> point1 = make_point_2d(static_cast<T>(1), static_cast<T>(2));
+ point_2d<T> point1 = point_2d<T>(static_cast<T>(1), static_cast<T>(2));
point_2d<T> point2;
BOOST_CHECK_EQUAL(point1.x(), static_cast<T>(1));
BOOST_CHECK_EQUAL(point1.y(), static_cast<T>(2));
- point2 = make_point_2d(static_cast<T>(0), static_cast<T>(2));
+ point2 = point_2d<T>(static_cast<T>(0), static_cast<T>(2));
bool arr1[] = { false, true, false, true, false, true };
EVENT_TYPES_CHECK_COMPARISON(point1, point2, arr1);
- point2 = make_point_2d(static_cast<T>(1), static_cast<T>(3));
+ point2 = point_2d<T>(static_cast<T>(1), static_cast<T>(3));
bool arr2[] = { true, false, true, false, false, true };
EVENT_TYPES_CHECK_COMPARISON(point1, point2, arr2);
- point2 = make_point_2d(static_cast<T>(1), static_cast<T>(2));
+ point2 = point_2d<T>(static_cast<T>(1), static_cast<T>(2));
bool arr3[] = { false, false, true, true, true, false };
EVENT_TYPES_CHECK_COMPARISON(point1, point2, arr3);
}
@@ -66,11 +68,11 @@
BOOST_AUTO_TEST_CASE_TEMPLATE(site_event_test2, T, test_types) {
- point_2d<T> point1 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(2));
- point_2d<T> point2 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(0));
- point_2d<T> point3 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(-2));
- point_2d<T> point4 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(-1));
- point_2d<T> point5 = make_point_2d<T>(static_cast<T>(1), static_cast<T>(1));
+ point_2d<T> point1 = point_2d<T>(static_cast<T>(0), static_cast<T>(2));
+ point_2d<T> point2 = point_2d<T>(static_cast<T>(0), static_cast<T>(0));
+ point_2d<T> point3 = point_2d<T>(static_cast<T>(0), static_cast<T>(-2));
+ point_2d<T> point4 = point_2d<T>(static_cast<T>(0), static_cast<T>(-1));
+ point_2d<T> point5 = point_2d<T>(static_cast<T>(1), static_cast<T>(1));
site_event<T> site1 = make_site_event<T>(point1, point2, 0);
BOOST_CHECK_EQUAL(point1 == site1.point1(), true);
@@ -113,10 +115,10 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(site_event_test3, T, test_types) {
- point_2d<T> point1 = make_point_2d<T>(static_cast<T>(10), static_cast<T>(10));
- point_2d<T> point2 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(0));
- point_2d<T> point3 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(1));
- point_2d<T> point4 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(10));
+ point_2d<T> point1 = point_2d<T>(static_cast<T>(10), static_cast<T>(10));
+ point_2d<T> point2 = point_2d<T>(static_cast<T>(0), static_cast<T>(0));
+ point_2d<T> point3 = point_2d<T>(static_cast<T>(0), static_cast<T>(1));
+ point_2d<T> point4 = point_2d<T>(static_cast<T>(0), static_cast<T>(10));
site_event<T> site1 = make_site_event<T>(point1, point2, 0);
BOOST_CHECK_EQUAL(point1 == site1.point1(), true);
@@ -142,18 +144,18 @@
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1_1);
EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr1_2);
- point3 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(-10));
- point4 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(-1));
+ point3 = point_2d<T>(static_cast<T>(0), static_cast<T>(-10));
+ point4 = point_2d<T>(static_cast<T>(0), static_cast<T>(-1));
site2 = make_site_event<T>(point3, point4, 0);
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1_1);
EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr1_2);
- point4 = make_point_2d<T>(static_cast<T>(10), static_cast<T>(9));
+ point4 = point_2d<T>(static_cast<T>(10), static_cast<T>(9));
site2 = make_site_event<T>(point2, point4, 0);
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1_2);
EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr1_1);
- point4 = make_point_2d<T>(static_cast<T>(9), static_cast<T>(10));
+ point4 = point_2d<T>(static_cast<T>(9), static_cast<T>(10));
site2 = make_site_event<T>(point2, point4, 0);
EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1_1);
EVENT_TYPES_CHECK_COMPARISON(site2, site1, arr1_2);
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp 2011-08-28 08:05:11 EDT (Sun, 28 Aug 2011)
@@ -7,13 +7,15 @@
// See http://www.boost.org for updates, documentation, and revision history.
-#include "test_type_list.hpp"
-#include "boost/sweepline/voronoi_sweepline.hpp"
+#define BOOST_TEST_MODULE node_comparer_test
+#include <boost/mpl/list.hpp>
+#include <boost/test/test_case_template.hpp>
+
+#include "boost/sweepline/voronoi_diagram.hpp"
using namespace boost::sweepline;
using namespace boost::sweepline::detail;
-#define BOOST_TEST_MODULE node_comparer_test
-#include <boost/test/test_case_template.hpp>
+typedef boost::mpl::list<double> test_types;
BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test_pp1, T, test_types) {
typedef site_event<T> site_event_type;
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/output_verification.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/output_verification.hpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/output_verification.hpp 2011-08-28 08:05:11 EDT (Sun, 28 Aug 2011)
@@ -14,27 +14,27 @@
#include <vector>
template <typename Point2D>
-detail::kOrientation get_orientation(const Point2D &point1,
- const Point2D &point2,
- const Point2D &point3) {
+kOrientation get_orientation(const Point2D &point1,
+ const Point2D &point2,
+ const Point2D &point3) {
typename Point2D::coordinate_type a = (point2.x() - point1.x()) * (point3.y() - point2.y());
typename Point2D::coordinate_type b = (point2.y() - point1.y()) * (point3.x() - point2.x());
if (a == b)
- return detail::COLLINEAR;
- return (a < b) ? detail::RIGHT_ORIENTATION : detail::LEFT_ORIENTATION;
+ return COLLINEAR;
+ return (a < b) ? RIGHT_ORIENTATION : LEFT_ORIENTATION;
}
template <typename Output>
bool verify_half_edge_orientation(const Output &output) {
- typedef typename Output::point_2d_type point_2d_type;
+ typedef typename Output::point_type point_type;
typename Output::voronoi_edge_const_iterator_type edge_it;
for (edge_it = output.edge_records().begin();
edge_it != output.edge_records().end(); edge_it++) {
if (edge_it->is_bounded()) {
- const point_2d_type &site_point = edge_it->cell()->point0();
- const point_2d_type &start_point = edge_it->vertex0()->vertex();
- const point_2d_type &end_point = edge_it->vertex1()->vertex();
- if (get_orientation(start_point, end_point, site_point) != detail::LEFT_ORIENTATION)
+ const point_type &site_point = edge_it->cell()->point0();
+ const point_type &start_point = edge_it->vertex0()->vertex();
+ const point_type &end_point = edge_it->vertex1()->vertex();
+ if (get_orientation(start_point, end_point, site_point) != LEFT_ORIENTATION)
return false;
}
}
@@ -43,7 +43,7 @@
template <typename Output>
bool verify_cell_convexity(const Output &output) {
- typedef typename Output::point_2d_type point_2d_type;
+ typedef typename Output::point_type point_type;
typename Output::voronoi_cell_const_iterator_type cell_it;
for (cell_it = output.cell_records().begin();
cell_it != output.cell_records().end(); cell_it++) {
@@ -58,10 +58,10 @@
edge->vertex1() != NULL &&
edge->vertex1() == edge->next()->vertex0() &&
edge->next()->vertex1() != NULL) {
- const point_2d_type &vertex1 = edge->vertex0()->vertex();
- const point_2d_type &vertex2 = edge->vertex1()->vertex();
- const point_2d_type &vertex3 = edge->next()->vertex1()->vertex();
- if (get_orientation(vertex1, vertex2, vertex3) != detail::LEFT_ORIENTATION)
+ const point_type &vertex1 = edge->vertex0()->vertex();
+ const point_type &vertex2 = edge->vertex1()->vertex();
+ const point_type &vertex3 = edge->next()->vertex1()->vertex();
+ if (get_orientation(vertex1, vertex2, vertex3) != LEFT_ORIENTATION)
return false;
}
edge = edge->next();
@@ -72,7 +72,7 @@
template <typename Output>
bool verify_incident_edges_ccw_order(const Output &output) {
- typedef typename Output::point_2d_type point_2d_type;
+ typedef typename Output::point_type point_type;
typedef typename Output::voronoi_edge_type voronoi_edge_type;
typename Output::voronoi_vertex_const_iterator_type vertex_it;
for (vertex_it = output.vertex_records().begin();
@@ -83,11 +83,11 @@
do {
const voronoi_edge_type *edge_next1 = edge->rot_next();
const voronoi_edge_type *edge_next2 = edge_next1->rot_next();
- const point_2d_type &site1 = edge->cell()->point0();
- const point_2d_type &site2 = edge_next1->cell()->point0();
- const point_2d_type &site3 = edge_next2->cell()->point0();
+ const point_type &site1 = edge->cell()->point0();
+ const point_type &site2 = edge_next1->cell()->point0();
+ const point_type &site3 = edge_next2->cell()->point0();
- if (get_orientation(site1, site2, site3) != detail::LEFT_ORIENTATION)
+ if (get_orientation(site1, site2, site3) != LEFT_ORIENTATION)
return false;
edge = edge->rot_next();
@@ -101,35 +101,41 @@
// Create map from edges with first point less than the second one.
// Key is the first point of the edge, value is a vector of second points
// with the same first point.
- typedef typename Output::point_2d_type point_2d_type;
- std::map< point_2d_type, std::vector<point_2d_type> > edge_map;
- typedef typename std::map< point_2d_type, std::vector<point_2d_type> >::const_iterator
- edge_map_iterator;
+ typedef typename Output::point_type point_type;
+ std::map< point_type, std::vector<point_type> > edge_map;
typename Output::voronoi_edge_const_iterator_type edge_it;
for (edge_it = output.edge_records().begin();
edge_it != output.edge_records().end(); edge_it++) {
if (edge_it->is_bounded()) {
- const point_2d_type &vertex0 = edge_it->vertex0()->vertex();
- const point_2d_type &vertex1 = edge_it->vertex1()->vertex();
+ const point_type &vertex0 = edge_it->vertex0()->vertex();
+ const point_type &vertex1 = edge_it->vertex1()->vertex();
if (vertex0 < vertex1)
edge_map[vertex0].push_back(vertex1);
}
}
+ return !intersection_check(edge_map);
+}
+template <typename Point2D>
+bool intersection_check(const std::map< Point2D, std::vector<Point2D> > &edge_map) {
// Iterate over map of edges and check if there are any intersections.
// All the edges are stored by the low x value. That's why we iterate
// left to right checking for intersections between all pairs of edges
// that overlap in the x dimension.
// Complexity. Approximately N*sqrt(N). Worst case N^2.
- typedef typename std::vector<point_2d_type>::size_type size_type;
+ typedef Point2D point_type;
+ typedef typename point_type::coordinate_type coordinate_type;
+ typedef typename std::map< point_type, std::vector<point_type> >::const_iterator
+ edge_map_iterator;
+ typedef typename std::vector<point_type>::size_type size_type;
edge_map_iterator edge_map_it1, edge_map_it2, edge_map_it_bound;
for (edge_map_it1 = edge_map.begin();
edge_map_it1 != edge_map.end(); edge_map_it1++) {
- const point_2d_type &point1 = edge_map_it1->first;
+ const point_type &point1 = edge_map_it1->first;
for (size_type i = 0; i < edge_map_it1->second.size(); i++) {
- const point_2d_type &point2 = edge_map_it1->second[i];
- typename Output::coordinate_type min_y1 = std::min(point1.y(), point2.y());
- typename Output::coordinate_type max_y1 = std::max(point1.y(), point2.y());
+ const point_type &point2 = edge_map_it1->second[i];
+ coordinate_type min_y1 = std::min(point1.y(), point2.y());
+ coordinate_type max_y1 = std::max(point1.y(), point2.y());
// Find the first edge with greater or equal first point.
edge_map_it_bound = edge_map.lower_bound(point2);
@@ -137,11 +143,11 @@
edge_map_it2 = edge_map_it1;
edge_map_it2++;
for (; edge_map_it2 != edge_map_it_bound; edge_map_it2++) {
- const point_2d_type &point3 = edge_map_it2->first;
+ const point_type &point3 = edge_map_it2->first;
for (size_type j = 0; j < edge_map_it2->second.size(); j++) {
- const point_2d_type &point4 = edge_map_it2->second[j];
- typename Output::coordinate_type min_y2 = std::min(point3.y(), point4.y());
- typename Output::coordinate_type max_y2 = std::max(point3.y(), point4.y());
+ const point_type &point4 = edge_map_it2->second[j];
+ coordinate_type min_y2 = std::min(point3.y(), point4.y());
+ coordinate_type max_y2 = std::max(point3.y(), point4.y());
// In most cases it is enought to make
// simple intersection check in the y dimension.
@@ -150,68 +156,17 @@
// Intersection check.
if (get_orientation(point1, point2, point3) *
- get_orientation(point1, point2, point4) == detail::RIGHT_ORIENTATION &&
+ get_orientation(point1, point2, point4) == RIGHT_ORIENTATION &&
get_orientation(point3, point4, point1) *
- get_orientation(point3, point4, point2) == detail::RIGHT_ORIENTATION)
- return false;
+ get_orientation(point3, point4, point2) == RIGHT_ORIENTATION)
+ return true;
}
}
}
}
- return true;
-}
-
-template <typename P>
-bool do_intersect(const P &p1, const P &p2, const P &p3, const P &p4) {
- if ((std::max)(p1.y(), p2.y()) < (std::min)(p3.y(), p4.y()) ||
- (std::max)(p3.y(), p4.y()) < (std::min)(p1.y(), p2.y()))
- return false;
- if (p1 == p3)
- return detail::orientation_test(p1, p2, p4) == detail::COLLINEAR;
- if (p2 == p4)
- return detail::orientation_test(p1, p2, p3) == detail::COLLINEAR;
- if (p2 == p3)
- return false;
- if ((get_orientation(p1, p2, p3) * get_orientation(p1, p2, p4) != detail::LEFT_ORIENTATION) &&
- (get_orientation(p3, p4, p1) * get_orientation(p3, p4, p2) != detail::LEFT_ORIENTATION))
- return true;
return false;
}
-template <typename P>
-struct segm_comparison {
- bool operator()(const std::pair<P, P> &segm1, const std::pair<P, P> &segm2) const {
- return segm1.first.x() < segm2.first.x();
- }
-};
-
-template <typename P>
-void remove_intersections(std::vector< std::pair<P, P> > &segm_vec) {
- for (int i = 0; i < static_cast<int>(segm_vec.size()); i++) {
- if (segm_vec[i].first > segm_vec[i].second) {
- (std::swap(segm_vec[i].first, segm_vec[i].second));
- }
- }
- sort(segm_vec.begin(), segm_vec.end());
- std::vector< std::pair<P, P> > dest_vec;
- typename std::vector< std::pair<P, P> >::iterator it, b_it, l_bound;
- for (it = segm_vec.begin(); it != segm_vec.end(); it++) {
- std::pair<P, P> bound = std::make_pair(it->second, it->second);
- l_bound = upper_bound(segm_vec.begin(), segm_vec.end(), bound, segm_comparison<P>());
- bool add = true;
- for (b_it = it + 1; b_it != l_bound; b_it++) {
- if (do_intersect(it->first, it->second, b_it->first, b_it->second)) {
- add = false;
- break;
- }
- }
- if (add) {
- dest_vec.push_back(*it);
- }
- }
- segm_vec.swap(dest_vec);
-}
-
enum kVerification {
HALF_EDGE_ORIENTATION = 1,
CELL_CONVEXITY = 2,
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/predicates_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/predicates_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/predicates_test.cpp 2011-08-28 08:05:11 EDT (Sun, 28 Aug 2011)
@@ -7,216 +7,219 @@
// See http://www.boost.org for updates, documentation, and revision history.
-#include "test_type_list.hpp"
-#include "boost/sweepline/voronoi_sweepline.hpp"
-using namespace boost::sweepline;
-
#define BOOST_TEST_MODULE predicates_test
+#include <boost/mpl/list.hpp>
#include <boost/test/test_case_template.hpp>
+#include "boost/sweepline/voronoi_diagram.hpp"
+using namespace boost::sweepline;
+using namespace boost::sweepline::detail;
+
+typedef boost::mpl::list<double> test_types;
+
#define CHECK_ORIENTATION_EQUAL(p1, p2, p3, exp) \
- BOOST_CHECK_EQUAL(detail::orientation_test(p1, p2, p3) == exp, true)
+ BOOST_CHECK_EQUAL(orientation_test(p1, p2, p3) == exp, true)
#define CHECK_LESS_PREDICATE_PP(lp, rp, np, exp) \
- BOOST_CHECK_EQUAL(detail::less_predicate(lp, rp, np) == exp, true)
+ BOOST_CHECK_EQUAL(less_predicate(lp, rp, np) == exp, true)
#define CHECK_FAST_LESS_PREDICATE_PS(lp, rs, np, reverse, exp) \
- BOOST_CHECK_EQUAL(detail::fast_less_predicate(lp, rs, np, reverse) == exp, true); \
- if (exp != detail::UNDEFINED) { \
- bool exp_res = (exp == detail::LESS) ? true : false; \
- BOOST_CHECK_EQUAL(detail::less_predicate(lp, rs, np, reverse), exp_res); \
+ BOOST_CHECK_EQUAL(fast_less_predicate(lp, rs, np, reverse) == exp, true); \
+ if (exp != UNDEFINED) { \
+ bool exp_res = (exp == LESS) ? true : false; \
+ BOOST_CHECK_EQUAL(less_predicate(lp, rs, np, reverse), exp_res); \
}
#define CHECK_LESS_PREDICATE_PS(lp, rs, np, reverse, exp) \
- BOOST_CHECK_EQUAL(detail::less_predicate(lp, rs, np, reverse) == exp, true)
+ BOOST_CHECK_EQUAL(less_predicate(lp, rs, np, reverse) == exp, true)
#define CHECK_LESS_PREDICATE_SS(ls, rs, np, exp) \
- BOOST_CHECK_EQUAL(detail::less_predicate(ls, rs, np) == exp, true)
+ BOOST_CHECK_EQUAL(less_predicate(ls, rs, np) == exp, true)
// This test uses integer values in the range [-2^31, 2^31), to validate
// orientation predicate for the hole integer range input coordinates.
BOOST_AUTO_TEST_CASE_TEMPLATE(orientation_test1, T, test_types) {
int min_int = std::numeric_limits<int>::min();
int max_int = std::numeric_limits<int>::max();
- point_2d<T> point1 = make_point_2d<T>(min_int, min_int);
- point_2d<T> point2 = make_point_2d<T>(0, 0);
- point_2d<T> point3 = make_point_2d<T>(max_int, max_int);
- point_2d<T> point4 = make_point_2d<T>(min_int, max_int);
- point_2d<T> point5 = make_point_2d<T>(max_int - 1, max_int);
-
- CHECK_ORIENTATION_EQUAL(point1, point2, point3, detail::COLLINEAR);
- CHECK_ORIENTATION_EQUAL(point1, point3, point2, detail::COLLINEAR);
- CHECK_ORIENTATION_EQUAL(point2, point3, point1, detail::COLLINEAR);
- CHECK_ORIENTATION_EQUAL(point2, point1, point3, detail::COLLINEAR);
- CHECK_ORIENTATION_EQUAL(point3, point1, point2, detail::COLLINEAR);
- CHECK_ORIENTATION_EQUAL(point3, point2, point1, detail::COLLINEAR);
-
- CHECK_ORIENTATION_EQUAL(point1, point4, point3, detail::RIGHT_ORIENTATION);
- CHECK_ORIENTATION_EQUAL(point1, point3, point4, detail::LEFT_ORIENTATION);
- CHECK_ORIENTATION_EQUAL(point4, point1, point3, detail::LEFT_ORIENTATION);
- CHECK_ORIENTATION_EQUAL(point4, point3, point1, detail::RIGHT_ORIENTATION);
- CHECK_ORIENTATION_EQUAL(point3, point4, point1, detail::LEFT_ORIENTATION);
- CHECK_ORIENTATION_EQUAL(point3, point1, point4, detail::RIGHT_ORIENTATION);
-
- CHECK_ORIENTATION_EQUAL(point1, point5, point3, detail::RIGHT_ORIENTATION);
- CHECK_ORIENTATION_EQUAL(point1, point3, point5, detail::LEFT_ORIENTATION);
- CHECK_ORIENTATION_EQUAL(point5, point1, point3, detail::LEFT_ORIENTATION);
- CHECK_ORIENTATION_EQUAL(point5, point3, point1, detail::RIGHT_ORIENTATION);
- CHECK_ORIENTATION_EQUAL(point3, point5, point1, detail::LEFT_ORIENTATION);
- CHECK_ORIENTATION_EQUAL(point3, point1, point5, detail::RIGHT_ORIENTATION);
+ point_2d<T> point1 = point_2d<T>(min_int, min_int);
+ point_2d<T> point2 = point_2d<T>(0, 0);
+ point_2d<T> point3 = point_2d<T>(max_int, max_int);
+ point_2d<T> point4 = point_2d<T>(min_int, max_int);
+ point_2d<T> point5 = point_2d<T>(max_int - 1, max_int);
+
+ CHECK_ORIENTATION_EQUAL(point1, point2, point3, COLLINEAR);
+ CHECK_ORIENTATION_EQUAL(point1, point3, point2, COLLINEAR);
+ CHECK_ORIENTATION_EQUAL(point2, point3, point1, COLLINEAR);
+ CHECK_ORIENTATION_EQUAL(point2, point1, point3, COLLINEAR);
+ CHECK_ORIENTATION_EQUAL(point3, point1, point2, COLLINEAR);
+ CHECK_ORIENTATION_EQUAL(point3, point2, point1, COLLINEAR);
+
+ CHECK_ORIENTATION_EQUAL(point1, point4, point3, RIGHT_ORIENTATION);
+ CHECK_ORIENTATION_EQUAL(point1, point3, point4, LEFT_ORIENTATION);
+ CHECK_ORIENTATION_EQUAL(point4, point1, point3, LEFT_ORIENTATION);
+ CHECK_ORIENTATION_EQUAL(point4, point3, point1, RIGHT_ORIENTATION);
+ CHECK_ORIENTATION_EQUAL(point3, point4, point1, LEFT_ORIENTATION);
+ CHECK_ORIENTATION_EQUAL(point3, point1, point4, RIGHT_ORIENTATION);
+
+ CHECK_ORIENTATION_EQUAL(point1, point5, point3, RIGHT_ORIENTATION);
+ CHECK_ORIENTATION_EQUAL(point1, point3, point5, LEFT_ORIENTATION);
+ CHECK_ORIENTATION_EQUAL(point5, point1, point3, LEFT_ORIENTATION);
+ CHECK_ORIENTATION_EQUAL(point5, point3, point1, RIGHT_ORIENTATION);
+ CHECK_ORIENTATION_EQUAL(point3, point5, point1, LEFT_ORIENTATION);
+ CHECK_ORIENTATION_EQUAL(point3, point1, point5, RIGHT_ORIENTATION);
}
// Test main point-point predicate.
BOOST_AUTO_TEST_CASE_TEMPLATE(less_predicates_point_point_test1, T, test_types) {
- point_2d<T> point1 = make_point_2d<T>(static_cast<T>(-5), static_cast<T>(0));
- point_2d<T> point2 = make_point_2d<T>(static_cast<T>(-8), static_cast<T>(9));
- point_2d<T> point3 = make_point_2d<T>(static_cast<T>(-2), static_cast<T>(1));
+ point_2d<T> point1 = point_2d<T>(static_cast<T>(-5), static_cast<T>(0));
+ point_2d<T> point2 = point_2d<T>(static_cast<T>(-8), static_cast<T>(9));
+ point_2d<T> point3 = point_2d<T>(static_cast<T>(-2), static_cast<T>(1));
- point_2d<T> site1 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(5));
+ point_2d<T> site1 = point_2d<T>(static_cast<T>(0), static_cast<T>(5));
CHECK_LESS_PREDICATE_PP(point1, point2, site1, false);
CHECK_LESS_PREDICATE_PP(point3, point1, site1, false);
- point_2d<T> site2 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(4));
+ point_2d<T> site2 = point_2d<T>(static_cast<T>(0), static_cast<T>(4));
CHECK_LESS_PREDICATE_PP(point1, point2, site2, false);
CHECK_LESS_PREDICATE_PP(point3, point1, site2, false);
- point_2d<T> site3 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(6));
+ point_2d<T> site3 = point_2d<T>(static_cast<T>(0), static_cast<T>(6));
CHECK_LESS_PREDICATE_PP(point1, point2, site3, true);
CHECK_LESS_PREDICATE_PP(point3, point1, site3, true);
}
// Vertical segment case.
BOOST_AUTO_TEST_CASE_TEMPLATE(fast_less_predicate_point_segment_test1, T, test_types) {
- point_2d<T> segm_start = make_point_2d<T>(static_cast<T>(-4), static_cast<T>(0));
- point_2d<T> segm_end = make_point_2d<T>(static_cast<T>(-4), static_cast<T>(20));
- typename detail::site_event<T> segm_site(segm_start, segm_end, 0);
-
- point_2d<T> site_p = make_point_2d<T>(static_cast<T>(-2), static_cast<T>(10));
- point_2d<T> new_p1 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(11));
- point_2d<T> new_p2 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(9));
-
- CHECK_FAST_LESS_PREDICATE_PS(site_p, segm_site, new_p1, false, detail::UNDEFINED);
- CHECK_FAST_LESS_PREDICATE_PS(site_p, segm_site, new_p2, false, detail::MORE);
- CHECK_FAST_LESS_PREDICATE_PS(site_p, segm_site, new_p1, true, detail::LESS);
- CHECK_FAST_LESS_PREDICATE_PS(site_p, segm_site, new_p2, true, detail::UNDEFINED);
+ point_2d<T> segm_start = point_2d<T>(static_cast<T>(-4), static_cast<T>(0));
+ point_2d<T> segm_end = point_2d<T>(static_cast<T>(-4), static_cast<T>(20));
+ site_event<T> segm_site(segm_start, segm_end, 0);
+
+ point_2d<T> site_p = point_2d<T>(static_cast<T>(-2), static_cast<T>(10));
+ point_2d<T> new_p1 = point_2d<T>(static_cast<T>(0), static_cast<T>(11));
+ point_2d<T> new_p2 = point_2d<T>(static_cast<T>(0), static_cast<T>(9));
+
+ CHECK_FAST_LESS_PREDICATE_PS(site_p, segm_site, new_p1, false, UNDEFINED);
+ CHECK_FAST_LESS_PREDICATE_PS(site_p, segm_site, new_p2, false, MORE);
+ CHECK_FAST_LESS_PREDICATE_PS(site_p, segm_site, new_p1, true, LESS);
+ CHECK_FAST_LESS_PREDICATE_PS(site_p, segm_site, new_p2, true, UNDEFINED);
}
// Not vertical segment case. Site is to the left of the segment vector.
BOOST_AUTO_TEST_CASE_TEMPLATE(fast_less_predicate_point_segment_test2, T, test_types) {
- point_2d<T> segm_start = make_point_2d<T>(static_cast<T>(-5), static_cast<T>(5));
- point_2d<T> segm_end = make_point_2d<T>(static_cast<T>(2), static_cast<T>(-2));
- typename detail::site_event<T> segm_site(segm_start, segm_end, 0);
+ point_2d<T> segm_start = point_2d<T>(static_cast<T>(-5), static_cast<T>(5));
+ point_2d<T> segm_end = point_2d<T>(static_cast<T>(2), static_cast<T>(-2));
+ site_event<T> segm_site(segm_start, segm_end, 0);
- point_2d<T> site_p1 = make_point_2d<T>(static_cast<T>(-2), static_cast<T>(4));
- point_2d<T> new_p1 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(-1));
+ point_2d<T> site_p1 = point_2d<T>(static_cast<T>(-2), static_cast<T>(4));
+ point_2d<T> new_p1 = point_2d<T>(static_cast<T>(0), static_cast<T>(-1));
segm_site.inverse();
- CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p1, false, detail::MORE);
- CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p1, true, detail::MORE);
+ CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p1, false, MORE);
+ CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p1, true, MORE);
- point_2d<T> new_p2 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(1));
- CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p2, false, detail::MORE);
- CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p2, true, detail::UNDEFINED);
-
- point_2d<T> new_p3 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(4));
- CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p3, false, detail::MORE);
- CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p3, true, detail::UNDEFINED);
-
- point_2d<T> new_p4 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(5));
- CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p4, false, detail::UNDEFINED);
- CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p4, true, detail::LESS);
+ point_2d<T> new_p2 = point_2d<T>(static_cast<T>(0), static_cast<T>(1));
+ CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p2, false, MORE);
+ CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p2, true, UNDEFINED);
+
+ point_2d<T> new_p3 = point_2d<T>(static_cast<T>(0), static_cast<T>(4));
+ CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p3, false, MORE);
+ CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p3, true, UNDEFINED);
+
+ point_2d<T> new_p4 = point_2d<T>(static_cast<T>(0), static_cast<T>(5));
+ CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p4, false, UNDEFINED);
+ CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p4, true, LESS);
}
// Not vertical segment case. Site is to the right of the segment vector.
BOOST_AUTO_TEST_CASE_TEMPLATE(fast_less_predicate_point_segment_test3, T, test_types) {
- point_2d<T> segm_start = make_point_2d<T>(static_cast<T>(-5), static_cast<T>(5));
- point_2d<T> segm_end = make_point_2d<T>(static_cast<T>(2), static_cast<T>(-2));
- typename detail::site_event<T> segm_site(segm_start, segm_end, 0);
-
- point_2d<T> site_p1 = make_point_2d<T>(static_cast<T>(-2), static_cast<T>(-4));
- point_2d<T> site_p2 = make_point_2d<T>(static_cast<int>(-4), static_cast<int>(1));
-
- point_2d<T> new_p1 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(1));
- CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p1, false, detail::LESS);
- CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p1, true, detail::LESS);
- CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p1, false, detail::LESS);
- CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p1, true, detail::LESS);
-
- point_2d<T> new_p2 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(-2));
- CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p2, false, detail::UNDEFINED);
- CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p2, true, detail::LESS);
- CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p2, false, detail::UNDEFINED);
- CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p2, true, detail::LESS);
-
- point_2d<T> new_p3 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(-8));
- CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p3, false, detail::UNDEFINED);
- CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p3, true, detail::LESS);
- CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p3, false, detail::UNDEFINED);
- CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p3, true, detail::LESS);
-
- point_2d<T> new_p4 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(-9));
- CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p4, false, detail::MORE);
- CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p4, true, detail::UNDEFINED);
- CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p4, false, detail::MORE);
- CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p4, true, detail::UNDEFINED);
+ point_2d<T> segm_start = point_2d<T>(static_cast<T>(-5), static_cast<T>(5));
+ point_2d<T> segm_end = point_2d<T>(static_cast<T>(2), static_cast<T>(-2));
+ site_event<T> segm_site(segm_start, segm_end, 0);
+
+ point_2d<T> site_p1 = point_2d<T>(static_cast<T>(-2), static_cast<T>(-4));
+ point_2d<T> site_p2 = point_2d<T>(static_cast<int>(-4), static_cast<int>(1));
+
+ point_2d<T> new_p1 = point_2d<T>(static_cast<T>(0), static_cast<T>(1));
+ CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p1, false, LESS);
+ CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p1, true, LESS);
+ CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p1, false, LESS);
+ CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p1, true, LESS);
+
+ point_2d<T> new_p2 = point_2d<T>(static_cast<T>(0), static_cast<T>(-2));
+ CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p2, false, UNDEFINED);
+ CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p2, true, LESS);
+ CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p2, false, UNDEFINED);
+ CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p2, true, LESS);
+
+ point_2d<T> new_p3 = point_2d<T>(static_cast<T>(0), static_cast<T>(-8));
+ CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p3, false, UNDEFINED);
+ CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p3, true, LESS);
+ CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p3, false, UNDEFINED);
+ CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p3, true, LESS);
+
+ point_2d<T> new_p4 = point_2d<T>(static_cast<T>(0), static_cast<T>(-9));
+ CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p4, false, MORE);
+ CHECK_FAST_LESS_PREDICATE_PS(site_p1, segm_site, new_p4, true, UNDEFINED);
+ CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p4, false, MORE);
+ CHECK_FAST_LESS_PREDICATE_PS(site_p2, segm_site, new_p4, true, UNDEFINED);
}
// Test main point-segment predicate.
BOOST_AUTO_TEST_CASE_TEMPLATE(less_predicate_point_segment_test1, T, test_types) {
- point_2d<T> segm_start = make_point_2d<T>(static_cast<T>(-5), static_cast<T>(5));
- point_2d<T> segm_end = make_point_2d<T>(static_cast<T>(2), static_cast<T>(-2));
- typename detail::site_event<T> segm_site1(segm_start, segm_end, 0);
- typename detail::site_event<T> segm_site2(segm_start, segm_end, 0);
+ point_2d<T> segm_start = point_2d<T>(static_cast<T>(-5), static_cast<T>(5));
+ point_2d<T> segm_end = point_2d<T>(static_cast<T>(2), static_cast<T>(-2));
+ site_event<T> segm_site1(segm_start, segm_end, 0);
+ site_event<T> segm_site2(segm_start, segm_end, 0);
segm_site2.inverse();
- point_2d<T> site_p1 = make_point_2d<T>(static_cast<T>(-2), static_cast<T>(4));
- point_2d<T> site_p2 = make_point_2d<T>(static_cast<T>(-2), static_cast<T>(-4));
- point_2d<T> site_p3 = make_point_2d<T>(static_cast<int>(-4), static_cast<int>(1));
+ point_2d<T> site_p1 = point_2d<T>(static_cast<T>(-2), static_cast<T>(4));
+ point_2d<T> site_p2 = point_2d<T>(static_cast<T>(-2), static_cast<T>(-4));
+ point_2d<T> site_p3 = point_2d<T>(static_cast<int>(-4), static_cast<int>(1));
- point_2d<T> new_p1 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(1));
+ point_2d<T> new_p1 = point_2d<T>(static_cast<T>(0), static_cast<T>(1));
CHECK_LESS_PREDICATE_PS(site_p1, segm_site2, new_p1, true, false);
- point_2d<T> new_p2 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(4));
+ point_2d<T> new_p2 = point_2d<T>(static_cast<T>(0), static_cast<T>(4));
CHECK_LESS_PREDICATE_PS(site_p1, segm_site2, new_p2, true, true);
- point_2d<T> new_p3 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(5));
+ point_2d<T> new_p3 = point_2d<T>(static_cast<T>(0), static_cast<T>(5));
CHECK_LESS_PREDICATE_PS(site_p1, segm_site2, new_p3, false, false);
- point_2d<T> new_p4 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(7));
+ point_2d<T> new_p4 = point_2d<T>(static_cast<T>(0), static_cast<T>(7));
CHECK_LESS_PREDICATE_PS(site_p1, segm_site2, new_p4, false, true);
- point_2d<T> new_p5 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(-2));
+ point_2d<T> new_p5 = point_2d<T>(static_cast<T>(0), static_cast<T>(-2));
CHECK_LESS_PREDICATE_PS(site_p2, segm_site1, new_p5, false, false);
CHECK_LESS_PREDICATE_PS(site_p3, segm_site1, new_p5, false, false);
- point_2d<T> new_p6 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(-8));
+ point_2d<T> new_p6 = point_2d<T>(static_cast<T>(0), static_cast<T>(-8));
CHECK_LESS_PREDICATE_PS(site_p2, segm_site1, new_p6, false, false);
CHECK_LESS_PREDICATE_PS(site_p3, segm_site1, new_p6, false, false);
- point_2d<T> new_p7 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(-9));
+ point_2d<T> new_p7 = point_2d<T>(static_cast<T>(0), static_cast<T>(-9));
CHECK_LESS_PREDICATE_PS(site_p2, segm_site1, new_p7, true, true);
CHECK_LESS_PREDICATE_PS(site_p3, segm_site1, new_p7, true, true);
- point_2d<T> new_p8 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(-18));
+ point_2d<T> new_p8 = point_2d<T>(static_cast<T>(0), static_cast<T>(-18));
CHECK_LESS_PREDICATE_PS(site_p2, segm_site1, new_p8, true, false);
CHECK_LESS_PREDICATE_PS(site_p3, segm_site1, new_p8, true, false);
- point_2d<T> new_p9 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(-1));
+ point_2d<T> new_p9 = point_2d<T>(static_cast<T>(0), static_cast<T>(-1));
CHECK_LESS_PREDICATE_PS(site_p2, segm_site1, new_p9, false, true);
CHECK_LESS_PREDICATE_PS(site_p3, segm_site1, new_p9, false, true);
}
// Test main segment-segment predicate.
BOOST_AUTO_TEST_CASE_TEMPLATE(less_predicate_segment_segment_test1, T, test_types) {
- point_2d<T> segm_start1 = make_point_2d<T>(static_cast<T>(-5), static_cast<T>(0));
- point_2d<T> segm_end1 = make_point_2d<T>(static_cast<T>(2), static_cast<T>(7));
- typename detail::site_event<T> segm_site1_1(segm_start1, segm_end1, 0);
- typename detail::site_event<T> segm_site1_2(segm_start1, segm_end1, 0);
+ point_2d<T> segm_start1 = point_2d<T>(static_cast<T>(-5), static_cast<T>(0));
+ point_2d<T> segm_end1 = point_2d<T>(static_cast<T>(2), static_cast<T>(7));
+ site_event<T> segm_site1_1(segm_start1, segm_end1, 0);
+ site_event<T> segm_site1_2(segm_start1, segm_end1, 0);
segm_site1_2.inverse();
// New sites.
- point_2d<T> new_site1 = make_point_2d<T>(static_cast<T>(2), static_cast<T>(7));
- point_2d<T> new_site2 = make_point_2d<T>(static_cast<T>(1), static_cast<T>(5));
- point_2d<T> new_site3 = make_point_2d<T>(static_cast<T>(-1), static_cast<T>(5));
+ point_2d<T> new_site1 = point_2d<T>(static_cast<T>(2), static_cast<T>(7));
+ point_2d<T> new_site2 = point_2d<T>(static_cast<T>(1), static_cast<T>(5));
+ point_2d<T> new_site3 = point_2d<T>(static_cast<T>(-1), static_cast<T>(5));
CHECK_LESS_PREDICATE_SS(segm_site1_1, segm_site1_2, new_site1, false);
CHECK_LESS_PREDICATE_SS(segm_site1_1, segm_site1_2, new_site2, false);
@@ -224,23 +227,23 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(less_predicate_segment_segment_test2, T, test_types) {
- typedef typename detail::site_event<T> site_event_type;
+ typedef site_event<T> site_event_type;
- point_2d<T> segm_start1 = make_point_2d<T>(static_cast<T>(-5), static_cast<T>(5));
- point_2d<T> segm_end1 = make_point_2d<T>(static_cast<T>(2), static_cast<T>(-2));
+ point_2d<T> segm_start1 = point_2d<T>(static_cast<T>(-5), static_cast<T>(5));
+ point_2d<T> segm_end1 = point_2d<T>(static_cast<T>(2), static_cast<T>(-2));
site_event_type segm_site1_1(segm_start1, segm_end1, 0);
site_event_type segm_site1_2(segm_start1, segm_end1, 0);
segm_site1_2.inverse();
// New sites.
- point_2d<T> new_site1 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(2));
- point_2d<T> new_site2 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(5));
- point_2d<T> new_site3 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(6));
- point_2d<T> new_site4 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(8));
+ point_2d<T> new_site1 = point_2d<T>(static_cast<T>(0), static_cast<T>(2));
+ point_2d<T> new_site2 = point_2d<T>(static_cast<T>(0), static_cast<T>(5));
+ point_2d<T> new_site3 = point_2d<T>(static_cast<T>(0), static_cast<T>(6));
+ point_2d<T> new_site4 = point_2d<T>(static_cast<T>(0), static_cast<T>(8));
// Common end points.
- point_2d<T> segm_start2 = make_point_2d<T>(static_cast<T>(-5), static_cast<T>(5));
- point_2d<T> segm_end2 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(6));
+ point_2d<T> segm_start2 = point_2d<T>(static_cast<T>(-5), static_cast<T>(5));
+ point_2d<T> segm_end2 = point_2d<T>(static_cast<T>(0), static_cast<T>(6));
site_event_type segm_site2(segm_start2, segm_end2, 1);
CHECK_LESS_PREDICATE_SS(segm_site1_2, segm_site2, new_site1, false);
CHECK_LESS_PREDICATE_SS(segm_site1_2, segm_site2, new_site2, true);
@@ -248,8 +251,8 @@
CHECK_LESS_PREDICATE_SS(segm_site1_2, segm_site2, new_site4, true);
// No common end points.
- point_2d<T> segm_start3 = make_point_2d<T>(static_cast<T>(-2), static_cast<T>(4));
- point_2d<T> segm_end3 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(4));
+ point_2d<T> segm_start3 = point_2d<T>(static_cast<T>(-2), static_cast<T>(4));
+ point_2d<T> segm_end3 = point_2d<T>(static_cast<T>(0), static_cast<T>(4));
site_event_type segm_site3(segm_start3, segm_end3, 2);
CHECK_LESS_PREDICATE_SS(segm_site1_2, segm_site3, new_site1, false);
CHECK_LESS_PREDICATE_SS(segm_site1_2, segm_site3, new_site2, true);
@@ -263,11 +266,10 @@
}
BOOST_AUTO_TEST_CASE_TEMPLATE(less_predicate_segment_segment_test3, T, test_types) {
- typedef typename detail::site_event<T> site_event_type;
-
- point_2d<T> segm_start1 = make_point_2d<T>(static_cast<T>(-5), static_cast<T>(3));
- point_2d<T> segm_start2 = make_point_2d<T>(static_cast<T>(-5), static_cast<T>(5));
- point_2d<T> segm_end = make_point_2d<T>(static_cast<T>(-2), static_cast<T>(2));
+ typedef site_event<T> site_event_type;
+ point_2d<T> segm_start1 = point_2d<T>(static_cast<T>(-5), static_cast<T>(3));
+ point_2d<T> segm_start2 = point_2d<T>(static_cast<T>(-5), static_cast<T>(5));
+ point_2d<T> segm_end = point_2d<T>(static_cast<T>(-2), static_cast<T>(2));
site_event_type segm_site1(segm_start1, segm_end, 0);
segm_site1.inverse();
site_event_type segm_site2(segm_start2, segm_end, 1);
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/robust_fpt_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/robust_fpt_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/robust_fpt_test.cpp 2011-08-28 08:05:11 EDT (Sun, 28 Aug 2011)
@@ -11,7 +11,7 @@
#include <boost/mpl/list.hpp>
#include <boost/test/test_case_template.hpp>
-#include "boost/sweepline/voronoi_sweepline.hpp"
+#include "boost/sweepline/voronoi_diagram.hpp"
using namespace boost::sweepline::detail;
typedef boost::mpl::list<double, mpf_class, mpt_wrapper<mpf_class, 8> > test_types;
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/sqrt_expr_evaluator_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/sqrt_expr_evaluator_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/sqrt_expr_evaluator_test.cpp 2011-08-28 08:05:11 EDT (Sun, 28 Aug 2011)
@@ -7,25 +7,26 @@
// See http://www.boost.org for updates, documentation, and revision history.
-#include <stdlib.h>
-#include <time.h>
+#include <ctime>
#define BOOST_TEST_MODULE sqrt_expr_evaluator_test
+#include <boost/random/mersenne_twister.hpp>
#include <boost/test/test_case_template.hpp>
-#include "boost/sweepline/voronoi_sweepline.hpp"
+#include "boost/sweepline/voronoi_diagram.hpp"
using namespace boost::sweepline::detail;
template <int N>
-struct test_sqr_evaluator {
+struct test_sqrt_evaluator {
template <typename mpz, typename mpf>
static bool run() {
+ static boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
bool ret_val = true;
static mpz A[N], B[N];
double a[N], b[N];
for (int i = 0; i < N; ++i) {
- a[i] = rand() % 1000 - 500;
- int rand_number = rand() % 1000 - 500;
+ a[i] = gen() % 1000 - 500;
+ int rand_number = gen() % 1000 - 500;
b[i] = rand_number * rand_number;
}
int mask = (1 << N);
@@ -42,28 +43,27 @@
expected_val -= a[j] * sqrt(b[j]);
}
}
- mpf received_val = (sqr_expr_evaluator<N>::template eval<mpz, mpf>(A, B));
+ mpf received_val = (sqrt_expr_evaluator<N>::template eval<mpz, mpf>(A, B));
ret_val &= almost_equal(expected_val, received_val.get_d(), 1);
}
return ret_val;
}
};
-BOOST_AUTO_TEST_CASE(mpz_sqr_evaluator_test) {
- srand(static_cast<unsigned int>(time(0)));
+BOOST_AUTO_TEST_CASE(mpz_sqrt_evaluator_test) {
typedef mpt_wrapper<mpz_class, 4> mpz_wrapper_type;
typedef mpt_wrapper<mpf_class, 1> mpf_wrapper_type;
for (int i = 0; i < 1000; i++) {
- BOOST_CHECK((test_sqr_evaluator<1>::run<mpz_class, mpf_class>()));
- BOOST_CHECK((test_sqr_evaluator<2>::run<mpz_class, mpf_class>()));
- BOOST_CHECK((test_sqr_evaluator<3>::run<mpz_class, mpf_class>()));
- BOOST_CHECK((test_sqr_evaluator<4>::run<mpz_class, mpf_class>()));
+ BOOST_CHECK((test_sqrt_evaluator<1>::run<mpz_class, mpf_class>()));
+ BOOST_CHECK((test_sqrt_evaluator<2>::run<mpz_class, mpf_class>()));
+ BOOST_CHECK((test_sqrt_evaluator<3>::run<mpz_class, mpf_class>()));
+ BOOST_CHECK((test_sqrt_evaluator<4>::run<mpz_class, mpf_class>()));
}
for (int i = 0; i < 1000; i++) {
- BOOST_CHECK((test_sqr_evaluator<1>::run<mpz_wrapper_type, mpf_wrapper_type>()));
- BOOST_CHECK((test_sqr_evaluator<2>::run<mpz_wrapper_type, mpf_wrapper_type>()));
- BOOST_CHECK((test_sqr_evaluator<3>::run<mpz_wrapper_type, mpf_wrapper_type>()));
- BOOST_CHECK((test_sqr_evaluator<4>::run<mpz_wrapper_type, mpf_wrapper_type>()));
+ BOOST_CHECK((test_sqrt_evaluator<1>::run<mpz_wrapper_type, mpf_wrapper_type>()));
+ BOOST_CHECK((test_sqrt_evaluator<2>::run<mpz_wrapper_type, mpf_wrapper_type>()));
+ BOOST_CHECK((test_sqrt_evaluator<3>::run<mpz_wrapper_type, mpf_wrapper_type>()));
+ BOOST_CHECK((test_sqrt_evaluator<4>::run<mpz_wrapper_type, mpf_wrapper_type>()));
}
}
Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp (original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/sweepline_test.cpp 2011-08-28 08:05:11 EDT (Sun, 28 Aug 2011)
@@ -7,49 +7,58 @@
// See http://www.boost.org for updates, documentation, and revision history.
-#include <stdlib.h>
-#include <time.h>
+#include <ctime>
-#include "test_type_list.hpp"
-#include "boost/sweepline/voronoi_sweepline.hpp"
+#define BOOST_TEST_MODULE sweepline_test
+#include <boost/mpl/list.hpp>
+#include <boost/random/mersenne_twister.hpp>
+#include <boost/test/test_case_template.hpp>
+
+#include "boost/sweepline/voronoi_diagram.hpp"
using namespace boost::sweepline;
+using namespace boost::sweepline::detail;
#include "output_verification.hpp"
-#define BOOST_TEST_MODULE sweepline_test
-#include <boost/test/test_case_template.hpp>
+typedef boost::mpl::list<int> test_types;
#define CHECK_EQUAL_POINTS(p1, p2) \
- BOOST_CHECK_EQUAL(p1.x() == static_cast<T>(p2.x()) && \
- p1.y() == static_cast<T>(p2.y()), true)
+ BOOST_CHECK_EQUAL(p1.x() == static_cast<T>(p2.x()), true); \
+ BOOST_CHECK_EQUAL(p1.y() == static_cast<T>(p2.y()), true)
-#define VERIFY_VORONOI_OUTPUT(output, mask) BOOST_CHECK_EQUAL(verify_output(output, mask), true)
+#define CHECK_BRECT(brect, xmin, ymin, xmax, ymax) \
+ BOOST_CHECK_EQUAL(brect.x_min() == static_cast<coordinate_type>(xmin), true); \
+ BOOST_CHECK_EQUAL(brect.y_min() == static_cast<coordinate_type>(ymin), true); \
+ BOOST_CHECK_EQUAL(brect.x_max() == static_cast<coordinate_type>(xmax), true); \
+ BOOST_CHECK_EQUAL(brect.y_max() == static_cast<coordinate_type>(ymax), true)
+
+#define CHECK_OUTPUT_SIZE(output, cells, vertices, edges) \
+ BOOST_CHECK_EQUAL(output.cell_records().size() == cells, true); \
+ BOOST_CHECK_EQUAL(output.num_cell_records() == cells, true); \
+ BOOST_CHECK_EQUAL(output.vertex_records().size() == vertices, true); \
+ BOOST_CHECK_EQUAL(output.num_vertex_records() == vertices, true); \
+ BOOST_CHECK_EQUAL(output.edge_records().size() == (edges << 1), true); \
+ BOOST_CHECK_EQUAL(output.num_edge_records() == edges, true)
+
+#define VERIFY_OUTPUT(output) \
+ BOOST_CHECK_EQUAL(verify_output(output, HALF_EDGE_ORIENTATION), true); \
+ BOOST_CHECK_EQUAL(verify_output(output, CELL_CONVEXITY), true); \
+ BOOST_CHECK_EQUAL(verify_output(output, INCIDENT_EDGES_CCW_ORDER), true); \
+ BOOST_CHECK_EQUAL(verify_output(output, NO_HALF_EDGE_INTERSECTIONS), true)
// Sites: (0, 0).
BOOST_AUTO_TEST_CASE_TEMPLATE(single_site_test, T, test_types) {
- typedef T coordinate_type;
+ typedef typename voronoi_traits<T>::coordinate_type coordinate_type;
typedef typename voronoi_output<coordinate_type>::voronoi_cell_const_iterator_type
voronoi_cell_const_iterator_type;
- std::vector< point_2d<coordinate_type> > points;
- points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
- static_cast<coordinate_type>(0)));
+ std::vector< point_data<T> > points;
+ points.push_back(point_data<T>(0, 0));
voronoi_output<coordinate_type> test_output;
- build_voronoi(points, test_output);
- VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
+ build_voronoi<T>(points, test_output);
+ VERIFY_OUTPUT(test_output);
- BRect<coordinate_type> bounding_rectangle = test_output.bounding_rectangle();
- BOOST_CHECK_EQUAL(bounding_rectangle.x_min() == static_cast<coordinate_type>(0) &&
- bounding_rectangle.y_min() == static_cast<coordinate_type>(0) &&
- bounding_rectangle.x_max() == static_cast<coordinate_type>(0) &&
- bounding_rectangle.y_max() == static_cast<coordinate_type>(0), true);
-
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.cell_records().size()), 1);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records().size()), 0);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.edge_records().size()), 0);
-
- BOOST_CHECK_EQUAL(test_output.num_cell_records(), 1);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 0);
- BOOST_CHECK_EQUAL(test_output.num_edge_records(), 0);
+ CHECK_BRECT(test_output.bounding_rectangle(), 0, 0, 0, 0);
+ CHECK_OUTPUT_SIZE(test_output, 1, 0, 0);
voronoi_cell_const_iterator_type it = test_output.cell_records().begin();
BOOST_CHECK_EQUAL(it->num_incident_edges(), 0);
@@ -58,33 +67,20 @@
// Sites: (0, 0), (0, 1).
BOOST_AUTO_TEST_CASE_TEMPLATE(collinear_sites_test1, T, test_types) {
- typedef T coordinate_type;
+ typedef typename voronoi_traits<T>::coordinate_type coordinate_type;
typedef typename voronoi_output<coordinate_type>::voronoi_edge_type voronoi_edge_type;
typedef typename voronoi_output<coordinate_type>::voronoi_cell_const_iterator_type
voronoi_cell_const_iterator_type;
- std::vector< point_2d<coordinate_type> > points;
- points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
- static_cast<coordinate_type>(0)));
- points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
- static_cast<coordinate_type>(1)));
+ std::vector< point_data<T> > points;
+ points.push_back(point_data<T>(0, 0));
+ points.push_back(point_data<T>(0, 1));
voronoi_output<coordinate_type> test_output;
- build_voronoi(points, test_output);
- VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
+ build_voronoi<T>(points, test_output);
+ VERIFY_OUTPUT(test_output);
- BRect<coordinate_type> bounding_rectangle = test_output.bounding_rectangle();
- BOOST_CHECK_EQUAL(bounding_rectangle.x_min() == static_cast<coordinate_type>(0) &&
- bounding_rectangle.y_min() == static_cast<coordinate_type>(0) &&
- bounding_rectangle.x_max() == static_cast<coordinate_type>(0) &&
- bounding_rectangle.y_max() == static_cast<coordinate_type>(1), true);
-
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.cell_records().size()), 2);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records().size()), 0);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.edge_records().size()), 2);
-
- BOOST_CHECK_EQUAL(test_output.num_cell_records(), 2);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 0);
- BOOST_CHECK_EQUAL(test_output.num_edge_records(), 1);
+ CHECK_BRECT(test_output.bounding_rectangle(), 0, 0, 0, 1);
+ CHECK_OUTPUT_SIZE(test_output, 2, 0, 1);
voronoi_cell_const_iterator_type cell_it = test_output.cell_records().begin();
BOOST_CHECK_EQUAL(cell_it->num_incident_edges(), 1);
@@ -110,35 +106,21 @@
// Sites: (0, 0), (1, 1), (2, 2).
BOOST_AUTO_TEST_CASE_TEMPLATE(collinear_sites_test2, T, test_types) {
- typedef T coordinate_type;
+ typedef typename voronoi_traits<T>::coordinate_type coordinate_type;
typedef typename voronoi_output<coordinate_type>::voronoi_edge_type voronoi_edge_type;
typedef typename voronoi_output<coordinate_type>::voronoi_cell_const_iterator_type
voronoi_cell_const_iterator_type;
- std::vector< point_2d<coordinate_type> > points;
- points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
- static_cast<coordinate_type>(0)));
- points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(1),
- static_cast<coordinate_type>(1)));
- points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(2),
- static_cast<coordinate_type>(2)));
+ std::vector< point_data<T> > points;
+ points.push_back(point_data<T>(0, 0));
+ points.push_back(point_data<T>(1, 1));
+ points.push_back(point_data<T>(2, 2));
voronoi_output<coordinate_type> test_output;
- build_voronoi(points, test_output);
- VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
+ build_voronoi<T>(points, test_output);
+ VERIFY_OUTPUT(test_output);
- BRect<coordinate_type> bounding_rectangle = test_output.bounding_rectangle();
- BOOST_CHECK_EQUAL(bounding_rectangle.x_min() == static_cast<coordinate_type>(0) &&
- bounding_rectangle.y_min() == static_cast<coordinate_type>(0) &&
- bounding_rectangle.x_max() == static_cast<coordinate_type>(2) &&
- bounding_rectangle.y_max() == static_cast<coordinate_type>(2), true);
-
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.cell_records().size()), 3);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records().size()), 0);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.edge_records().size()), 4);
-
- BOOST_CHECK_EQUAL(test_output.num_cell_records(), 3);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 0);
- BOOST_CHECK_EQUAL(test_output.num_edge_records(), 2);
+ CHECK_BRECT(test_output.bounding_rectangle(), 0, 0, 2, 2);
+ CHECK_OUTPUT_SIZE(test_output, 3, 0, 2);
voronoi_cell_const_iterator_type cell_it = test_output.cell_records().begin();
BOOST_CHECK_EQUAL(cell_it->num_incident_edges(), 1);
@@ -167,38 +149,30 @@
// Sites: (0, 0), (0, 4), (2, 1).
BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test1, T, test_types) {
- typedef T coordinate_type;
+ typedef typename voronoi_traits<T>::coordinate_type coordinate_type;
typedef typename voronoi_output<coordinate_type>::voronoi_edge_type voronoi_edge_type;
typedef typename voronoi_output<coordinate_type>::voronoi_vertex_const_iterator_type
voronoi_vertex_const_iterator_type;
- point_2d<coordinate_type> point1 = make_point_2d<coordinate_type>(
+ point_2d<coordinate_type> point1 = point_2d<coordinate_type>(
static_cast<coordinate_type>(0), static_cast<coordinate_type>(0));
- point_2d<coordinate_type> point2 = make_point_2d<coordinate_type>(
+ point_2d<coordinate_type> point2 = point_2d<coordinate_type>(
static_cast<coordinate_type>(0), static_cast<coordinate_type>(4));
- point_2d<coordinate_type> point3 = make_point_2d<coordinate_type>(
+ point_2d<coordinate_type> point3 = point_2d<coordinate_type>(
static_cast<coordinate_type>(2), static_cast<coordinate_type>(1));
- std::vector< point_2d<coordinate_type> > points;
- points.push_back(point1);
- points.push_back(point2);
- points.push_back(point3);
-
+ std::vector< point_data<T> > points;
+ points.push_back(point_data<T>(point1.x(), point1.y()));
+ points.push_back(point_data<T>(point2.x(), point2.y()));
+ points.push_back(point_data<T>(point3.x(), point3.y()));
voronoi_output<coordinate_type> test_output;
- build_voronoi(points, test_output);
- VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
-
- BRect<coordinate_type> bounding_rectangle = test_output.bounding_rectangle();
- BOOST_CHECK_EQUAL(bounding_rectangle.x_min() == static_cast<coordinate_type>(0) &&
- bounding_rectangle.y_min() == static_cast<coordinate_type>(0) &&
- bounding_rectangle.x_max() == static_cast<coordinate_type>(2) &&
- bounding_rectangle.y_max() == static_cast<coordinate_type>(4), true);
+ build_voronoi<T>(points, test_output);
+ VERIFY_OUTPUT(test_output);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.cell_records().size()), 3);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records().size()), 1);
+ CHECK_BRECT(test_output.bounding_rectangle(), 0, 0, 2, 4);
+ CHECK_OUTPUT_SIZE(test_output, 3, 1, 3);
voronoi_vertex_const_iterator_type it = test_output.vertex_records().begin();
- BOOST_CHECK_EQUAL(it->num_incident_edges(), 3);
BOOST_CHECK_EQUAL(it->vertex().x() == static_cast<coordinate_type>(0.25) &&
it->vertex().y() == static_cast<coordinate_type>(2.0), true);
@@ -236,32 +210,30 @@
// Sites: (0, 1), (2, 0), (2, 4).
BOOST_AUTO_TEST_CASE_TEMPLATE(triangle_test2, T, test_types) {
- typedef T coordinate_type;
+ typedef typename voronoi_traits<T>::coordinate_type coordinate_type;
typedef typename voronoi_output<coordinate_type>::voronoi_edge_type voronoi_edge_type;
typedef typename voronoi_output<coordinate_type>::voronoi_vertex_const_iterator_type
voronoi_vertex_const_iterator_type;
- point_2d<coordinate_type> point1 = make_point_2d<coordinate_type>(
+ point_2d<coordinate_type> point1 = point_2d<coordinate_type>(
static_cast<coordinate_type>(0), static_cast<coordinate_type>(1));
- point_2d<coordinate_type> point2 = make_point_2d<coordinate_type>(
+ point_2d<coordinate_type> point2 = point_2d<coordinate_type>(
static_cast<coordinate_type>(2), static_cast<coordinate_type>(0));
- point_2d<coordinate_type> point3 = make_point_2d<coordinate_type>(
+ point_2d<coordinate_type> point3 = point_2d<coordinate_type>(
static_cast<coordinate_type>(2), static_cast<coordinate_type>(4));
- std::vector< point_2d<coordinate_type> > points;
- points.push_back(point1);
- points.push_back(point2);
- points.push_back(point3);
-
+ std::vector< point_data<T> > points;
+ points.push_back(point_data<T>(point1.x(), point1.y()));
+ points.push_back(point_data<T>(point2.x(), point2.y()));
+ points.push_back(point_data<T>(point3.x(), point3.y()));
voronoi_output<coordinate_type> test_output;
- build_voronoi(points, test_output);
- VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
+ build_voronoi<T>(points, test_output);
+ VERIFY_OUTPUT(test_output);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.cell_records().size()), 3);
- BOOST_CHECK_EQUAL(static_cast<int>(test_output.vertex_records().size()), 1);
+ CHECK_BRECT(test_output.bounding_rectangle(), 0, 0, 2, 4);
+ CHECK_OUTPUT_SIZE(test_output, 3, 1, 3);
voronoi_vertex_const_iterator_type it = test_output.vertex_records().begin();
- BOOST_CHECK_EQUAL(it->num_incident_edges(), 3);
BOOST_CHECK_EQUAL(it->vertex().x() == static_cast<coordinate_type>(1.75) &&
it->vertex().y() == static_cast<coordinate_type>(2.0), true);
@@ -299,32 +271,34 @@
// Sites: (0, 0), (0, 1), (1, 0), (1, 1).
BOOST_AUTO_TEST_CASE_TEMPLATE(square_test1, T, test_types) {
- typedef T coordinate_type;
+ typedef typename voronoi_traits<T>::coordinate_type coordinate_type;
typedef typename voronoi_output<coordinate_type>::voronoi_edge_type voronoi_edge_type;
typedef typename voronoi_output<coordinate_type>::voronoi_vertex_const_iterator_type
voronoi_vertex_const_iterator_type;
- std::vector< point_2d<coordinate_type> > points;
- points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
- static_cast<coordinate_type>(0)));
- points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(0),
- static_cast<coordinate_type>(1)));
- points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(1),
- static_cast<coordinate_type>(0)));
- points.push_back(make_point_2d<coordinate_type>(static_cast<coordinate_type>(1),
- static_cast<coordinate_type>(1)));
-
+ point_2d<coordinate_type> point1 = point_2d<coordinate_type>(
+ static_cast<coordinate_type>(0), static_cast<coordinate_type>(0));
+ point_2d<coordinate_type> point2 = point_2d<coordinate_type>(
+ static_cast<coordinate_type>(0), static_cast<coordinate_type>(1));
+ point_2d<coordinate_type> point3 = point_2d<coordinate_type>(
+ static_cast<coordinate_type>(1), static_cast<coordinate_type>(0));
+ point_2d<coordinate_type> point4 = point_2d<coordinate_type>(
+ static_cast<coordinate_type>(1), static_cast<coordinate_type>(1));
+
+ std::vector< point_data<T> > points;
+ points.push_back(point_data<T>(point1.x(), point1.y()));
+ points.push_back(point_data<T>(point2.x(), point2.y()));
+ points.push_back(point_data<T>(point3.x(), point3.y()));
+ points.push_back(point_data<T>(point4.x(), point4.y()));
voronoi_output<coordinate_type> test_output;
- build_voronoi(points, test_output);
- VERIFY_VORONOI_OUTPUT(test_output, COMPLETE_VERIFICATION);
+ build_voronoi<T>(points, test_output);
+ VERIFY_OUTPUT(test_output);
- BOOST_CHECK_EQUAL(test_output.num_cell_records(), 4);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 1);
- BOOST_CHECK_EQUAL(test_output.num_edge_records(), 4);
+ CHECK_BRECT(test_output.bounding_rectangle(), 0, 0, 1, 1);
+ CHECK_OUTPUT_SIZE(test_output, 4, 1, 4);
// Check voronoi vertex.
voronoi_vertex_const_iterator_type it = test_output.vertex_records().begin();
- BOOST_CHECK_EQUAL(it->num_incident_edges(), 4);
BOOST_CHECK_EQUAL(it->vertex().x() == static_cast<coordinate_type>(0.5) &&
it->vertex().y() == static_cast<coordinate_type>(0.5), true);
@@ -372,37 +346,41 @@
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(grid_test, T, test_types) {
- voronoi_output<T> test_output_small, test_output_large;
- std::vector< point_2d<T> > point_vec_small, point_vec_large;
- int grid_size[4] = {10, 33, 100, 333};
- int max_value[4] = {10, 33, 100, 333};
+ voronoi_output<typename voronoi_traits<T>::coordinate_type>
+ test_output_small, test_output_large;
+ std::vector< point_data<T> > point_vec_small, point_vec_large;
+ int grid_size[4] = {10, 33, 101, 163};
+ int max_value[4] = {10, 33, 101, 163};
int array_length = sizeof(grid_size) / sizeof(int);
for (int k = 0; k < array_length; k++) {
+ point_vec_small.clear();
+ point_vec_large.clear();
int koef = std::numeric_limits<int>::max() / max_value[k];
for (int i = 0; i < grid_size[k]; i++)
for (int j = 0; j < grid_size[k]; j++) {
- point_vec_small.push_back(make_point_2d<T>(i, j));
- point_vec_large.push_back(make_point_2d<T>(koef * i, koef * j));
+ point_vec_small.push_back(point_data<T>(i, j));
+ point_vec_large.push_back(point_data<T>(koef * i, koef * j));
}
- build_voronoi(point_vec_small, test_output_small);
- build_voronoi(point_vec_large, test_output_large);
- VERIFY_VORONOI_OUTPUT(test_output_small, COMPLETE_VERIFICATION);
- VERIFY_VORONOI_OUTPUT(test_output_large, COMPLETE_VERIFICATION);
- BOOST_CHECK_EQUAL(test_output_small.num_cell_records(), test_output_large.num_cell_records());
- BOOST_CHECK_EQUAL(test_output_small.num_vertex_records(), test_output_large.num_vertex_records());
- BOOST_CHECK_EQUAL(test_output_small.num_edge_records(), test_output_large.num_edge_records());
- point_vec_small.clear();
- point_vec_large.clear();
+ build_voronoi<T>(point_vec_small, test_output_small);
+ build_voronoi<T>(point_vec_large, test_output_large);
+ VERIFY_OUTPUT(test_output_small);
+ VERIFY_OUTPUT(test_output_large);
+ int num_cells = grid_size[k] * grid_size[k];
+ int num_vertices = num_cells - 2 * grid_size[k] + 1;
+ int num_edges = 2 * num_cells - 2 * grid_size[k];
+ CHECK_OUTPUT_SIZE(test_output_small, num_cells, num_vertices, num_edges);
+ CHECK_OUTPUT_SIZE(test_output_large, num_cells, num_vertices, num_edges);
}
}
#endif
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(random_test, T, test_types) {
- srand(static_cast<unsigned int>(time(NULL)));
- voronoi_output<T> test_output_small, test_output_large;
- std::vector< point_2d<T> > point_vec_small, point_vec_large;
- int num_points[] = {10, 100, 1000, 10000, 100000};
+ boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
+ voronoi_output<typename voronoi_traits<T>::coordinate_type>
+ test_output_small, test_output_large;
+ std::vector< point_data<T> > point_vec_small, point_vec_large;
+ int num_points[] = {5, 100, 1000, 10000, 100000};
int num_runs[] = {10000, 1000, 100, 10, 1};
int mod_koef[] = {10, 100, 100, 1000, 10000};
int max_value[] = {5, 50, 50, 5000, 5000};
@@ -410,24 +388,24 @@
for (int k = 0; k < array_length; k++) {
int koef = std::numeric_limits<int>::max() / max_value[k];
for (int i = 0; i < num_runs[k]; i++) {
+ point_vec_small.clear();
+ point_vec_large.clear();
for (int j = 0; j < num_points[k]; j++) {
- T x = rand() % mod_koef[k] - mod_koef[k] / 2;
- T y = rand() % mod_koef[k] - mod_koef[k] / 2;
- point_vec_small.push_back(make_point_2d<T>(x, y));
- point_vec_large.push_back(make_point_2d<T>(koef * x, koef * y));
+ T x = gen() % mod_koef[k] - mod_koef[k] / 2;
+ T y = gen() % mod_koef[k] - mod_koef[k] / 2;
+ point_vec_small.push_back(point_data<T>(x, y));
+ point_vec_large.push_back(point_data<T>(koef * x, koef * y));
}
- build_voronoi(point_vec_small, test_output_small);
- build_voronoi(point_vec_large, test_output_large);
- VERIFY_VORONOI_OUTPUT(test_output_small, COMPLETE_VERIFICATION);
- VERIFY_VORONOI_OUTPUT(test_output_large, COMPLETE_VERIFICATION);
+ build_voronoi<T>(point_vec_small, test_output_small);
+ build_voronoi<T>(point_vec_large, test_output_large);
+ VERIFY_OUTPUT(test_output_small);
+ VERIFY_OUTPUT(test_output_large);
BOOST_CHECK_EQUAL(test_output_small.num_cell_records(),
test_output_large.num_cell_records());
BOOST_CHECK_EQUAL(test_output_small.num_vertex_records(),
test_output_large.num_vertex_records());
BOOST_CHECK_EQUAL(test_output_small.num_edge_records(),
test_output_large.num_edge_records());
- point_vec_small.clear();
- point_vec_large.clear();
}
}
}
@@ -435,282 +413,264 @@
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(enormous_random_test, T, test_types) {
- srand(static_cast<unsigned int>(time(NULL)));
- voronoi_output<T> test_output;
- std::vector< point_2d<T> > point_vec;
+ boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
+ voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output;
+ std::vector< point_data<T> > point_vec;
for (int i = 0; i < 1000000; i++)
- point_vec.push_back(make_point_2d<T>(rand() % 10000 - 5000, rand() % 10000 - 5000));
- build_voronoi(point_vec, test_output);
- VERIFY_VORONOI_OUTPUT(test_output, FAST_VERIFICATION);
+ point_vec.push_back(point_data<T>(gen() % 10000 - 5000, gen() % 10000 - 5000));
+ build_voronoi<T>(point_vec, test_output);
+ BOOST_CHECK_EQUAL(verify_output(test_output, FAST_VERIFICATION), true);
}
#endif
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test1, T, test_types) {
typedef T coordinate_type;
- voronoi_output<coordinate_type> test_output;
- std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec;
- point_2d<T> point1 = make_point_2d<T>(0, 0);
- point_2d<T> point2 = make_point_2d<T>(1, 1);
- segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
- build_voronoi(segm_vec, test_output);
- BOOST_CHECK_EQUAL(test_output.num_cell_records(), 3);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 0);
- BOOST_CHECK_EQUAL(test_output.num_edge_records(), 2);
- VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+ voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output;
+ directed_line_segment_set_data<T> segments;
+ point_data<T> point1(0, 0);
+ point_data<T> point2(1, 1);
+ segments.insert(directed_line_segment_data<T>(point1, point2));
+ build_voronoi<T>(segments, test_output);
+ CHECK_OUTPUT_SIZE(test_output, 3, 0, 2);
+ BOOST_CHECK_EQUAL(verify_output(test_output, NO_HALF_EDGE_INTERSECTIONS), true);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test2, T, test_types) {
typedef T coordinate_type;
- voronoi_output<coordinate_type> test_output;
- std::vector< point_2d<T> > point_vec;
- std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec;
- point_2d<T> point1 = make_point_2d<T>(0, 0);
- point_2d<T> point2 = make_point_2d<T>(4, 4);
- point_2d<T> point3 = make_point_2d<T>(3, 1);
- point_2d<T> point4 = make_point_2d<T>(1, 3);
- segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
- point_vec.push_back(point3);
- point_vec.push_back(point4);
- build_voronoi(point_vec, segm_vec, test_output);
- BOOST_CHECK_EQUAL(test_output.num_cell_records(), 5);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 4);
- BOOST_CHECK_EQUAL(test_output.num_edge_records(), 8);
- VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+ voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output;
+ std::vector< point_data<T> > points;
+ directed_line_segment_set_data<T> segments;
+ point_data<T> point1(0, 0);
+ point_data<T> point2(4, 4);
+ point_data<T> point3(3, 1);
+ point_data<T> point4(1, 3);
+ segments.insert(directed_line_segment_data<T>(point1, point2));
+ points.push_back(point3);
+ points.push_back(point4);
+ build_voronoi<T>(points, segments, test_output);
+ CHECK_OUTPUT_SIZE(test_output, 5, 4, 8);
+ BOOST_CHECK_EQUAL(verify_output(test_output, NO_HALF_EDGE_INTERSECTIONS), true);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test3, T, test_types) {
typedef T coordinate_type;
- voronoi_output<coordinate_type> test_output;
- std::vector< point_2d<T> > point_vec;
- std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec;
- point_2d<T> point1 = make_point_2d<T>(4, 0);
- point_2d<T> point2 = make_point_2d<T>(0, 4);
- point_2d<T> point3 = make_point_2d<T>(3, 3);
- point_2d<T> point4 = make_point_2d<T>(1, 1);
- segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
- point_vec.push_back(point3);
- point_vec.push_back(point4);
- build_voronoi(point_vec, segm_vec, test_output);
- BOOST_CHECK_EQUAL(test_output.num_cell_records(), 5);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 4);
- BOOST_CHECK_EQUAL(test_output.num_edge_records(), 8);
- VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+ voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output;
+ std::vector< point_data<T> > points;
+ directed_line_segment_set_data<T> segments;
+ point_data<T> point1(4, 0);
+ point_data<T> point2(0, 4);
+ point_data<T> point3(3, 3);
+ point_data<T> point4(1, 1);
+ segments.insert(directed_line_segment_data<T>(point1, point2));
+ points.push_back(point3);
+ points.push_back(point4);
+ build_voronoi<T>(points, segments, test_output);
+ CHECK_OUTPUT_SIZE(test_output, 5, 4, 8);
+ BOOST_CHECK_EQUAL(verify_output(test_output, NO_HALF_EDGE_INTERSECTIONS), true);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_sites_test4, T, test_types) {
typedef T coordinate_type;
- voronoi_output<coordinate_type> test_output;
- std::vector< point_2d<T> > point_vec;
- std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec;
- point_2d<T> point1 = make_point_2d<T>(4, 0);
- point_2d<T> point2 = make_point_2d<T>(0, 4);
- point_2d<T> point3 = make_point_2d<T>(3, 2);
- point_2d<T> point4 = make_point_2d<T>(2, 3);
- segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
- point_vec.push_back(point3);
- point_vec.push_back(point4);
- build_voronoi(point_vec, segm_vec, test_output);
- BOOST_CHECK_EQUAL(test_output.num_cell_records(), 5);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 3);
- BOOST_CHECK_EQUAL(test_output.num_edge_records(), 7);
- VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+ voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output;
+ std::vector< point_data<T> > points;
+ directed_line_segment_set_data<T> segments;
+ point_data<T> point1(4, 0);
+ point_data<T> point2(0, 4);
+ point_data<T> point3(3, 2);
+ point_data<T> point4(2, 3);
+ segments.insert(directed_line_segment_data<T>(point1, point2));
+ points.push_back(point3);
+ points.push_back(point4);
+ build_voronoi<T>(points, segments, test_output);
+ CHECK_OUTPUT_SIZE(test_output, 5, 3, 7);
+ BOOST_CHECK_EQUAL(verify_output(test_output, NO_HALF_EDGE_INTERSECTIONS), true);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test5, T, test_types) {
typedef T coordinate_type;
- voronoi_output<coordinate_type> test_output;
- std::vector< point_2d<T> > point_vec;
- std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec;
- point_2d<T> point1 = make_point_2d<T>(0, 0);
- point_2d<T> point2 = make_point_2d<T>(0, 8);
- point_2d<T> point3 = make_point_2d<T>(-2, -2);
- point_2d<T> point4 = make_point_2d<T>(-2, 4);
- point_2d<T> point5 = make_point_2d<T>(-2, 10);
- segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point1, point2));
- point_vec.push_back(point3);
- point_vec.push_back(point4);
- point_vec.push_back(point5);
- build_voronoi(point_vec, segm_vec, test_output);
- BOOST_CHECK_EQUAL(test_output.num_cell_records(), 6);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 4);
- BOOST_CHECK_EQUAL(test_output.num_edge_records(), 9);
- VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+ voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output;
+ std::vector< point_data<T> > points;
+ directed_line_segment_set_data<T> segments;
+ point_data<T> point1(0, 0);
+ point_data<T> point2(0, 8);
+ point_data<T> point3(-2, -2);
+ point_data<T> point4(-2, 4);
+ point_data<T> point5(-2, 10);
+ segments.insert(directed_line_segment_data<T>(point1, point2));
+ points.push_back(point3);
+ points.push_back(point4);
+ points.push_back(point5);
+ build_voronoi<T>(points, segments, test_output);
+ CHECK_OUTPUT_SIZE(test_output, 6, 4, 9);
+ BOOST_CHECK_EQUAL(verify_output(test_output, NO_HALF_EDGE_INTERSECTIONS), true);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test6, T, test_types) {
typedef T coordinate_type;
- voronoi_output<coordinate_type> test_output;
- std::vector< point_2d<T> > point_vec;
- std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec;
- point_2d<T> point1 = make_point_2d<T>(-1, 1);
- point_2d<T> point2 = make_point_2d<T>(1, 0);
- point_2d<T> point3 = make_point_2d<T>(1, 2);
- segm_vec.push_back(std::make_pair< point_2d<T>, point_2d<T> >(point2, point3));
- point_vec.push_back(point1);
- build_voronoi(point_vec, segm_vec, test_output);
- BOOST_CHECK_EQUAL(test_output.num_cell_records(), 4);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 2);
- BOOST_CHECK_EQUAL(test_output.num_edge_records(), 5);
- VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+ voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output;
+ std::vector< point_data<T> > points;
+ directed_line_segment_set_data<T> segments;
+ point_data<T> point1(-1, 1);
+ point_data<T> point2(1, 0);
+ point_data<T> point3(1, 2);
+ segments.insert(directed_line_segment_data<T>(point2, point3));
+ points.push_back(point1);
+ build_voronoi<T>(points, segments, test_output);
+ CHECK_OUTPUT_SIZE(test_output, 4, 2, 5);
+ BOOST_CHECK_EQUAL(verify_output(test_output, NO_HALF_EDGE_INTERSECTIONS), true);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test7, T, test_types) {
typedef T coordinate_type;
- voronoi_output<coordinate_type> test_output;
- std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec;
- point_2d<T> point1 = make_point_2d<T>(0, 0);
- point_2d<T> point2 = make_point_2d<T>(4, 0);
- point_2d<T> point3 = make_point_2d<T>(0, 4);
- point_2d<T> point4 = make_point_2d<T>(4, 4);
- segm_vec.push_back(std::make_pair(point1, point2));
- segm_vec.push_back(std::make_pair(point2, point3));
- segm_vec.push_back(std::make_pair(point3, point4));
- build_voronoi(segm_vec, test_output);
- BOOST_CHECK_EQUAL(test_output.num_cell_records(), 7);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 6);
- BOOST_CHECK_EQUAL(test_output.num_edge_records(), 12);
- VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
-
+ voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output;
+ directed_line_segment_set_data<T> segments;
+ point_data<T> point1(0, 0);
+ point_data<T> point2(4, 0);
+ point_data<T> point3(0, 4);
+ point_data<T> point4(4, 4);
+ segments.insert(directed_line_segment_data<T>(point1, point2));
+ segments.insert(directed_line_segment_data<T>(point2, point3));
+ segments.insert(directed_line_segment_data<T>(point3, point4));
+ build_voronoi<T>(segments, test_output);
+ CHECK_OUTPUT_SIZE(test_output, 7, 6, 12);
+ BOOST_CHECK_EQUAL(verify_output(test_output, NO_HALF_EDGE_INTERSECTIONS), true);
}
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_site_test8, T, test_types) {
typedef T coordinate_type;
- voronoi_output<coordinate_type> test_output;
- std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec;
- point_2d<T> point1 = make_point_2d<T>(0, 0);
- point_2d<T> point2 = make_point_2d<T>(4, 0);
- point_2d<T> point3 = make_point_2d<T>(4, 4);
- point_2d<T> point4 = make_point_2d<T>(0, 4);
- segm_vec.push_back(std::make_pair(point1, point2));
- segm_vec.push_back(std::make_pair(point2, point3));
- segm_vec.push_back(std::make_pair(point3, point4));
- segm_vec.push_back(std::make_pair(point4, point1));
- build_voronoi(segm_vec, test_output);
- BOOST_CHECK_EQUAL(test_output.num_cell_records(), 8);
- BOOST_CHECK_EQUAL(test_output.num_vertex_records(), 5);
- BOOST_CHECK_EQUAL(test_output.num_edge_records(), 12);
- VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
+ voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output;
+ directed_line_segment_set_data<T> segments;
+ point_data<T> point1(0, 0);
+ point_data<T> point2(4, 0);
+ point_data<T> point3(4, 4);
+ point_data<T> point4(0, 4);
+ segments.insert(directed_line_segment_data<T>(point1, point2));
+ segments.insert(directed_line_segment_data<T>(point2, point3));
+ segments.insert(directed_line_segment_data<T>(point3, point4));
+ segments.insert(directed_line_segment_data<T>(point4, point1));
+ build_voronoi<T>(segments, test_output);
+ CHECK_OUTPUT_SIZE(test_output, 8, 5, 12);
+ BOOST_CHECK_EQUAL(verify_output(test_output, NO_HALF_EDGE_INTERSECTIONS), true);
}
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_grid_test, T, test_types) {
- voronoi_output<T> test_output_small, test_output_large;
- std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec_small, segm_vec_large;
- int grid_size[] = {10, 33, 100, 333};
- int max_value[] = {100, 330, 1000, 3330};
+ voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output_small, test_output_large;
+ directed_line_segment_set_data<T> segments_small, segments_large;
+ int grid_size[] = {10, 33, 100};
+ int max_value[] = {100, 330, 1000};
int array_length = sizeof(grid_size) / sizeof(int);
for (int k = 0; k < array_length; k++) {
+ segments_small.clear();
+ segments_large.clear();
int cur_sz = grid_size[k];
int koef = std::numeric_limits<int>::max() / max_value[k];
for (int i = 0; i < cur_sz + 1; i++)
for (int j = 0; j < cur_sz; j++) {
- point_2d<T> point1_1(10 * i, 10 * j);
- point_2d<T> point1_2(koef * 10 * i, koef * 10 * j);
- point_2d<T> point2_1(10 * i, 10 * j + 10);
- point_2d<T> point2_2(koef * 10 * i, koef * (10 * j + 10));
- segm_vec_small.push_back(std::make_pair(point1_1, point2_1));
- segm_vec_large.push_back(std::make_pair(point1_2, point2_2));
- point_2d<T> point3_1(10 * j, 10 * i);
- point_2d<T> point3_2(koef * 10 * j, koef * 10 * i);
- point_2d<T> point4_1(10 * j + 10, 10 * i);
- point_2d<T> point4_2(koef * (10 * j + 10), koef * 10 * i);
- segm_vec_small.push_back(std::make_pair(point3_1, point4_1));
- segm_vec_large.push_back(std::make_pair(point3_2, point4_2));
+ point_data<T> point1_1(10 * i, 10 * j);
+ point_data<T> point1_2(koef * 10 * i, koef * 10 * j);
+ point_data<T> point2_1(10 * i, 10 * j + 10);
+ point_data<T> point2_2(koef * 10 * i, koef * (10 * j + 10));
+ segments_small.insert(directed_line_segment_data<T>(point1_1, point2_1));
+ segments_large.insert(directed_line_segment_data<T>(point1_2, point2_2));
+ point_data<T> point3_1(10 * j, 10 * i);
+ point_data<T> point3_2(koef * 10 * j, koef * 10 * i);
+ point_data<T> point4_1(10 * j + 10, 10 * i);
+ point_data<T> point4_2(koef * (10 * j + 10), koef * 10 * i);
+ segments_small.insert(directed_line_segment_data<T>(point3_1, point4_1));
+ segments_large.insert(directed_line_segment_data<T>(point3_2, point4_2));
}
- build_voronoi(segm_vec_small, test_output_small);
- build_voronoi(segm_vec_large, test_output_large);
- VERIFY_VORONOI_OUTPUT(test_output_small, NO_HALF_EDGE_INTERSECTIONS);
- VERIFY_VORONOI_OUTPUT(test_output_large, NO_HALF_EDGE_INTERSECTIONS);
- BOOST_CHECK_EQUAL(test_output_small.num_cell_records(),
- test_output_large.num_cell_records());
- BOOST_CHECK_EQUAL(test_output_small.num_vertex_records(),
- test_output_large.num_vertex_records());
- BOOST_CHECK_EQUAL(test_output_small.num_edge_records(),
- test_output_large.num_edge_records());
- segm_vec_small.clear();
- segm_vec_large.clear();
+ build_voronoi<T>(segments_small, test_output_small);
+ build_voronoi<T>(segments_large, test_output_large);
+ BOOST_CHECK_EQUAL(verify_output(test_output_small, NO_HALF_EDGE_INTERSECTIONS), true);
+ BOOST_CHECK_EQUAL(verify_output(test_output_large, NO_HALF_EDGE_INTERSECTIONS), true);
+ BOOST_CHECK_EQUAL(test_output_small.num_cell_records(), test_output_large.num_cell_records());
+ BOOST_CHECK_EQUAL(test_output_small.num_vertex_records(), test_output_large.num_vertex_records());
+ BOOST_CHECK_EQUAL(test_output_small.num_edge_records(), test_output_large.num_edge_records());
}
}
#endif
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_random_test1, T, test_types) {
- srand(static_cast<unsigned int>(time(NULL)));
- voronoi_output<T> test_output;
- std::vector< point_2d<T> > point_vec;
- std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec;
- int num_runs = 10000;
- int num_segments = 5;
- point_vec.push_back(make_point_2d<T>(-100, -100));
- point_vec.push_back(make_point_2d<T>(-100, 100));
- point_vec.push_back(make_point_2d<T>(100, -100));
- point_vec.push_back(make_point_2d<T>(100, 100));
+ boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
+ voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output;
+ std::vector< point_data<T> > points;
+ directed_line_segment_set_data<T> segments;
+ int num_runs = 1000;
+ int num_segments = 10;
+ points.push_back(point_data<T>(-100, -100));
+ points.push_back(point_data<T>(-100, 100));
+ points.push_back(point_data<T>(100, -100));
+ points.push_back(point_data<T>(100, 100));
for (int i = 0; i < num_runs; i++) {
+ segments.clear();
for (int j = 0; j < num_segments; j++) {
T x1 = 0, y1 = 0, x2 = 0, y2 = 0;
while (x1 == x2 && y1 == y2) {
- x1 = (rand() % 100) - 50;
- y1 = (rand() % 100) - 50;
- x2 = (rand() % 100) - 50;
- y2 = (rand() % 100) - 50;
+ x1 = (gen() % 100) - 50;
+ y1 = (gen() % 100) - 50;
+ x2 = (gen() % 100) - 50;
+ y2 = (gen() % 100) - 50;
}
- point_2d<T> point1(x1, y1);
- point_2d<T> point2(x2, y2);
- segm_vec.push_back(std::make_pair(point1, point2));
+ point_data<T> point1(x1, y1);
+ point_data<T> point2(x2, y2);
+ segments.insert(directed_line_segment_data<T>(point1, point2));
}
- remove_intersections(segm_vec);
- build_voronoi(point_vec, segm_vec, test_output);
- VERIFY_VORONOI_OUTPUT(test_output, NO_HALF_EDGE_INTERSECTIONS);
- segm_vec.clear();
+ build_voronoi<T>(points, segments, test_output);
+ BOOST_CHECK_EQUAL(verify_output(test_output, NO_HALF_EDGE_INTERSECTIONS), true);
}
}
#endif
#ifdef NDEBUG
BOOST_AUTO_TEST_CASE_TEMPLATE(segment_random_test2, T, test_types) {
- srand(static_cast<unsigned int>(time(NULL)));
- voronoi_output<T> test_output_small, test_output_large;
- std::vector< std::pair< point_2d<T>, point_2d<T> > > segm_vec;
- int num_segments[] = {10, 100, 1000, 10000};
+ boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
+ voronoi_output<typename voronoi_traits<T>::coordinate_type> test_output_small, test_output_large;
+ directed_line_segment_set_data<T> segments_small, segments_large;
+ int num_segments[] = {5, 25, 125, 625};
int num_runs[] = {1000, 100, 10, 1};
- int mod_koef1[] = {100, 1000, 10000, 100000};
- int mod_koef2[] = {100, 200, 300, 400};
- int max_value[] = {100, 600, 5150, 50200};
+ int mod_koef1[] = {10, 100, 200, 300};
+ int mod_koef2[] = {10, 20, 50, 100};
+ int max_value[] = {10, 60, 125, 200};
int array_length = sizeof(num_segments) / sizeof(int);
for (int k = 0; k < array_length; k++) {
int koef = std::numeric_limits<int>::max() / max_value[k];
for (int i = 0; i < num_runs[k]; i++) {
+ segments_small.clear();
+ segments_large.clear();
for (int j = 0; j < num_segments[k]; j++) {
- T x1 = (rand() % mod_koef1[k]) - mod_koef1[k] / 2;
- T y1 = (rand() % mod_koef1[k]) - mod_koef1[k] / 2;
+ T x1 = (gen() % mod_koef1[k]) - mod_koef1[k] / 2;
+ T y1 = (gen() % mod_koef1[k]) - mod_koef1[k] / 2;
T dx = 0, dy = 0;
while (dx == 0 && dy == 0) {
- dx = (rand() % mod_koef2[k]) - mod_koef2[k] / 2;
- dy = (rand() % mod_koef2[k]) - mod_koef2[k] / 2;
+ dx = (gen() % mod_koef2[k]) - mod_koef2[k] / 2;
+ dy = (gen() % mod_koef2[k]) - mod_koef2[k] / 2;
}
T x2 = x1 + dx;
T y2 = y1 + dy;
- point_2d<T> point1_small(x1, y1);
- point_2d<T> point2_small(x2, y2);
- segm_vec.push_back(std::make_pair(point1_small, point2_small));
+ point_data<T> point1_small(x1, y1);
+ point_data<T> point2_small(x2, y2);
+ segments_small.insert(directed_line_segment_data<T>(point1_small, point2_small));
}
- remove_intersections(segm_vec);
- build_voronoi(segm_vec, test_output_small);
- for (size_t j = 0; j < segm_vec.size(); j++) {
- segm_vec[j].first.x(segm_vec[j].first.x() * koef);
- segm_vec[j].first.y(segm_vec[j].first.y() * koef);
- segm_vec[j].second.x(segm_vec[j].second.x() * koef);
- segm_vec[j].second.y(segm_vec[j].second.y() * koef);
+ segments_small.clean();
+ for (typename directed_line_segment_set_data<T>::iterator_type it = segments_small.begin();
+ it != segments_small.end(); ++it) {
+ T x1 = it->low().x() * koef;
+ T y1 = it->low().y() * koef;
+ T x2 = it->high().x() * koef;
+ T y2 = it->high().y() * koef;
+ point_data<T> point1_large(x1, y1);
+ point_data<T> point2_large(x2, y2);
+ segments_large.insert(directed_line_segment_data<T>(point1_large, point2_large));
}
- build_voronoi(segm_vec, test_output_large);
- VERIFY_VORONOI_OUTPUT(test_output_large, NO_HALF_EDGE_INTERSECTIONS);
- BOOST_CHECK_EQUAL(test_output_small.num_cell_records(),
- test_output_large.num_cell_records());
- BOOST_CHECK_EQUAL(test_output_small.num_vertex_records(),
- test_output_large.num_vertex_records());
- BOOST_CHECK_EQUAL(test_output_small.num_edge_records(),
- test_output_large.num_edge_records());
- segm_vec.clear();
+ build_voronoi<T>(segments_small, test_output_small);
+ build_voronoi<T>(segments_large, test_output_large);
+ BOOST_CHECK_EQUAL(verify_output(test_output_small, NO_HALF_EDGE_INTERSECTIONS), true);
+ BOOST_CHECK_EQUAL(verify_output(test_output_large, NO_HALF_EDGE_INTERSECTIONS), true);
+ BOOST_CHECK_EQUAL(test_output_small.num_cell_records(), test_output_large.num_cell_records());
+ BOOST_CHECK_EQUAL(test_output_small.num_vertex_records(), test_output_large.num_vertex_records());
+ BOOST_CHECK_EQUAL(test_output_small.num_edge_records(), test_output_large.num_edge_records());
}
}
}
Deleted: sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp 2011-08-28 08:05:11 EDT (Sun, 28 Aug 2011)
+++ (empty file)
@@ -1,17 +0,0 @@
-// Boost sweepline library test_type_list.hpp file
-
-// Copyright Andrii Sydorchuk 2010.
-// 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)
-
-// See http://www.boost.org for updates, documentation, and revision history.
-
-#ifndef BOOST_SWEEPLINE_TEST_TYPE_LIST
-#define BOOST_SWEEPLINE_TEST_TYPE_LIST
-
-#include <boost/mpl/list.hpp>
-
-typedef boost::mpl::list<double> test_types;
-
-#endif
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