|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r74743 - in sandbox/gtl: boost/polygon boost/polygon/detail libs/polygon libs/polygon/example libs/polygon/example/input_data libs/polygon/example/input_data/failure libs/polygon/example/input_data/polygon libs/polygon/example/input_data/primary libs/polygon/example/input_data/random libs/polygon/example/output_data libs/polygon/example/output_data/failure libs/polygon/example/output_data/polygon libs/polygon/example/output_data/primary libs/polygon/example/output_data/random
From: sydorchuk.andriy_at_[hidden]
Date: 2011-10-05 16:04:25
Author: asydorchuk
Date: 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
New Revision: 74743
URL: http://svn.boost.org/trac/boost/changeset/74743
Log:
Merged gtl and sweepline.
Moved examples directory (tests not moved yet).
Renamed all the namespace from sweepline to polygon.
Added:
sandbox/gtl/boost/polygon/detail/mpt_wrapper.hpp (contents, props changed)
sandbox/gtl/boost/polygon/detail/voronoi_calc_kernel.hpp (contents, props changed)
sandbox/gtl/boost/polygon/detail/voronoi_formation.hpp (contents, props changed)
sandbox/gtl/boost/polygon/detail/voronoi_fpt_kernel.hpp (contents, props changed)
sandbox/gtl/boost/polygon/voronoi.hpp (contents, props changed)
sandbox/gtl/boost/polygon/voronoi_builder.hpp (contents, props changed)
sandbox/gtl/boost/polygon/voronoi_diagram.hpp (contents, props changed)
sandbox/gtl/libs/polygon/example/
sandbox/gtl/libs/polygon/example/Jamfile.v2 (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/
sandbox/gtl/libs/polygon/example/input_data/failure/
sandbox/gtl/libs/polygon/example/input_data/failure/failure_001.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/polygon/
sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_001.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_002.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_003.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_004.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_005.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_006.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_007.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_008.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_009.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_010.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/
sandbox/gtl/libs/polygon/example/input_data/primary/primary_001.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_002.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_003.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_004.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_005.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_006.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_007.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_008.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_009.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_010.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_011.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_012.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_013.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_014.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_015.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_016.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_017.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_018.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_019.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_020.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_021.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_022.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_023.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_024.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_025.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_026.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_027.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_028.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_029.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_030.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_031.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_032.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_033.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_034.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_035.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_036.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_037.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_038.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_039.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_040.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_041.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_042.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_043.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_044.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_045.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_046.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_047.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/primary/primary_048.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/
sandbox/gtl/libs/polygon/example/input_data/random/random_001.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_002.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_003.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_004.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_005.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_006.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_007.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_008.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_009.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_010.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_011.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_012.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_013.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_014.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_015.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_016.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_017.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_018.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_019.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_020.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_021.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_022.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_023.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_024.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_025.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_026.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_027.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/input_data/random/random_028.txt (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/
sandbox/gtl/libs/polygon/example/output_data/failure/
sandbox/gtl/libs/polygon/example/output_data/failure/failure_001.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/polygon/
sandbox/gtl/libs/polygon/example/output_data/polygon/polygon_001.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/polygon/polygon_002.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/polygon/polygon_003.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/polygon/polygon_004.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/polygon/polygon_005.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/polygon/polygon_006.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/polygon/polygon_007.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/polygon/polygon_008.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/polygon/polygon_009.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/polygon/polygon_010.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/
sandbox/gtl/libs/polygon/example/output_data/primary/primary_001.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_002.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_003.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_004.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_005.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_006.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_007.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_008.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_009.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_010.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_011.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_012.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_013.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_014.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_015.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_016.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_017.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_018.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_019.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_020.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_021.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_022.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_023.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_024.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_025.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_026.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_027.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_028.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_029.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_030.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_031.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_032.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_033.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_034.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_035.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_036.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_037.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_038.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_039.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_040.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_041.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_042.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_043.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_044.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_045.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_046.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_047.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/primary/primary_048.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/
sandbox/gtl/libs/polygon/example/output_data/random/random_001.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_002.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_003.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_004.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_005.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_006.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_007.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_008.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_009.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_010.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_011.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_012.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_013.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_014.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_015.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_016.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_017.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_018.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_019.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_020.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_021.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_022.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_023.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_024.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_025.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_026.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_027.png (contents, props changed)
sandbox/gtl/libs/polygon/example/output_data/random/random_028.png (contents, props changed)
sandbox/gtl/libs/polygon/example/voronoi_visualizer.cpp (contents, props changed)
Text files modified:
sandbox/gtl/libs/polygon/Jamroot | 38 +++++++++++++++++++++++++++++++++-----
1 files changed, 33 insertions(+), 5 deletions(-)
Added: sandbox/gtl/boost/polygon/detail/mpt_wrapper.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/boost/polygon/detail/mpt_wrapper.hpp 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,221 @@
+// Boost polygon/detail/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 BOOST_POLYGON_MPT_WRAPPER
+#define BOOST_POLYGON_MPT_WRAPPER
+
+#include <cmath>
+#include <string>
+
+namespace boost {
+namespace polygon {
+namespace detail {
+
+ // Allows to compute expression without allocation of additional memory.
+ // Expression evaluation should contain less then N temporary variables
+ // (e.g. (a1 * b1) + (a2 * b2) - requires two temporary variables to hold
+ // a1 * b1 and a2 * b2). This class is not thread safe, use mpz_class or
+ // mpq_class instead (however there'll be at least 2 times slowdown).
+ template <typename mpt, int N>
+ class mpt_wrapper {
+ public:
+ mpt_wrapper() {}
+
+ explicit mpt_wrapper(int input) : m_(input) {}
+
+ explicit mpt_wrapper(double input) : m_(input) {}
+
+ mpt_wrapper(const mpt& input) : m_(input) {}
+
+ mpt_wrapper(const mpt_wrapper& w) : m_(w.m_) {}
+
+ template <typename mpt2, int N2>
+ mpt_wrapper(const mpt_wrapper<mpt2, N2>& w) : m_(w.m_) {}
+
+ mpt_wrapper& operator=(int that) {
+ m_ = that;
+ return *this;
+ }
+
+ mpt_wrapper& operator=(double that) {
+ m_ = that;
+ return *this;
+ }
+
+ mpt_wrapper& operator=(const mpt_wrapper& that) {
+ m_ = that.m_;
+ return *this;
+ }
+
+ template <typename mpt2, int N2>
+ mpt_wrapper& operator=(const mpt_wrapper<mpt2, N2>& that) {
+ m_ = that.get_mpt();
+ return *this;
+ }
+
+ double get_d() const {
+ return m_.get_d();
+ }
+
+ std::string get_str() const {
+ return m_.get_str();
+ }
+
+ const mpt& get_mpt() const {
+ return m_;
+ }
+
+ bool operator==(const mpt_wrapper& that) const {
+ return m_ == that.m_;
+ }
+
+ bool operator!=(const mpt_wrapper& that) const {
+ return m_ != that.m_;
+ }
+
+ bool operator<(const mpt_wrapper& that) const {
+ return m_ < that.m_;
+ }
+
+ bool operator<=(const mpt_wrapper& that) const {
+ return m_ <= that.m_;
+ }
+
+ bool operator>(const mpt_wrapper& that) const {
+ return m_ > that.m_;
+ }
+
+ bool operator>=(const mpt_wrapper& that) const {
+ return m_ >= that.m_;
+ }
+
+ bool operator==(int that) const {
+ if (that == 0)
+ return m_.__get_mp()->_mp_size == 0;
+ temp_[cur_] = that;
+ return m_ == temp_[cur_].m_;
+ }
+
+ bool operator!=(int that) const {
+ return !(*this == that);
+ }
+
+ bool operator<(int that) const {
+ if (that == 0)
+ return m_.__get_mp()->_mp_size < 0;
+ temp_[cur_] = that;
+ return m_ < temp_[cur_].m_;
+ }
+
+ bool operator<=(int that) const {
+ if (that == 0)
+ return m_.__get_mp()->_mp_size <= 0;
+ temp_[cur_] = that;
+ return m_ <= temp_[cur_].m_;
+ }
+
+ bool operator>(int that) const {
+ if (that == 0)
+ return m_.__get_mp()->_mp_size > 0;
+ temp_[cur_] = that;
+ return m_ > temp_[cur_].m_;
+ }
+
+ bool operator>=(int that) const {
+ if (that == 0)
+ return m_.__get_mp()->_mp_size >= 0;
+ temp_[cur_] = that;
+ return m_ >= temp_[cur_].m_;
+ }
+
+ mpt_wrapper& operator-() const {
+ temp_[cur_].m_ = -this->m_;
+ return temp_[next_cur()];
+ }
+
+ mpt_wrapper& operator+(const mpt_wrapper& that) const {
+ temp_[cur_].m_ = this->m_ + that.m_;
+ return temp_[next_cur()];
+ }
+
+ mpt_wrapper& operator-(const mpt_wrapper& that) const {
+ temp_[cur_].m_ = this->m_ - that.m_;
+ return temp_[next_cur()];
+ }
+
+ mpt_wrapper& operator*(const mpt_wrapper& that) const {
+ temp_[cur_].m_ = this->m_ * that.m_;
+ return temp_[next_cur()];
+ }
+
+ mpt_wrapper& operator/(const mpt_wrapper& that) const {
+ temp_[cur_].m_ = this->m_ / that.m_;
+ return temp_[next_cur()];
+ }
+
+ mpt_wrapper& operator*(double that) const {
+ temp_[cur_].m_ = that;
+ temp_[cur_].m_ *= this->m_;
+ return temp_[next_cur()];
+ }
+
+ mpt_wrapper& operator+=(const mpt_wrapper& that) {
+ this->m_ += that.m_;
+ return *this;
+ }
+
+ mpt_wrapper& operator-=(const mpt_wrapper& that) {
+ this->m_ -= that.m_;
+ return *this;
+ }
+
+ mpt_wrapper& operator*=(const mpt_wrapper& that) {
+ this->m_ *= that.m_;
+ return *this;
+ }
+
+ mpt_wrapper& operator/=(const mpt_wrapper& that) {
+ this->m_ /= that.m_;
+ return *this;
+ }
+
+ mpt_wrapper& get_sqrt() {
+ temp_[cur_].m_ = sqrt(m_);
+ return temp_[next_cur()];
+ }
+
+ private:
+ static int next_cur() {
+ int ret_val = cur_++;
+ if (cur_ == N)
+ cur_ = 0;
+ return ret_val;
+ }
+
+ mpt m_;
+ static int cur_;
+ static mpt_wrapper temp_[N];
+ };
+
+ template <typename mpt, int N>
+ int mpt_wrapper<mpt, N>::cur_ = 0;
+
+ template <typename mpt, int N>
+ mpt_wrapper<mpt, N> mpt_wrapper<mpt, N>::temp_[N];
+
+ template<int N>
+ mpt_wrapper<mpf_class, N>& sqrt(mpt_wrapper<mpf_class, N>& value) {
+ return value.get_sqrt();
+ }
+
+} // detail
+} // polygon
+} // boost
+
+#endif
Added: sandbox/gtl/boost/polygon/detail/voronoi_calc_kernel.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/boost/polygon/detail/voronoi_calc_kernel.hpp 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,1332 @@
+// Boost polygon/detail/voronoi_calc_kernel.hpp header file
+
+// Copyright Andrii Sydorchuk 2010-2011.
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org for updates, documentation, and revision history.
+
+#ifndef BOOST_POLYGON_VORONOI_CALC_KERNEL
+#define BOOST_POLYGON_VORONOI_CALC_KERNEL
+
+#include "voronoi_fpt_kernel.hpp"
+
+namespace boost {
+namespace polygon {
+namespace detail {
+
+template <typename T>
+class voronoi_calc_kernel;
+
+// Geometry predicates with floating-point variables usually require
+// high-precision predicates to retrieve the correct result.
+// Epsilon robust predicates give the result within some epsilon relative
+// error, but are a lot faster than high-precision predicates.
+// To make algorithm robust and efficient epsilon robust predicates are
+// used at the first step. In case of the undefined result high-precision
+// arithmetic is used to produce required robustness. This approach
+// requires exact computation of epsilon intervals within which epsilon
+// robust predicates have undefined value.
+// There are two ways to measure an error of floating-point calculations:
+// relative error and ULPs(units in the last place).
+// Let EPS be machine epsilon, then next inequalities have place:
+// 1 EPS <= 1 ULP <= 2 EPS (1), 0.5 ULP <= 1 EPS <= 1 ULP (2).
+// ULPs are good for measuring rounding errors and comparing values.
+// Relative erros are good for computation of general relative
+// errors of formulas or expressions. So to calculate epsilon
+// intervals within which epsilon robust predicates have undefined result
+// next schema is used:
+// 1) Compute rounding errors of initial variables using ULPs;
+// 2) Transform ULPs to epsilons using upper bound of the (1);
+// 3) Compute relative error of the formula using epsilon arithmetic;
+// 4) Transform epsilon to ULPs using upper bound of the (2);
+// In case two values are inside undefined ULP range use high-precision
+// arithmetic to produce the correct result, else output the result.
+// Look at almost_equal function to see how two floating-point variables
+// are checked to fit in the ULP range.
+// If A has relative error of r(A) and B has relative error of r(B) then:
+// 1) r(A + B) <= max(r(A), r(B)), for A * B >= 0;
+// 2) r(A - B) <= B*r(A)+A*r(B)/(A-B), for A * B >= 0;
+// 2) r(A * B) <= r(A) + r(B);
+// 3) r(A / B) <= r(A) + r(B);
+// In addition rounding error should be added, that is always equal to
+// 0.5 ULP or atmost 1 epsilon. As you might see from the above formulas
+// substraction relative error may be extremely large, that's why
+// epsilon robust comparator class is used to store floating point values
+// and avoid substraction.
+// For further information about relative errors and ULPs try this link:
+// http://docs.sun.com/source/806-3568/ncg_goldberg.html
+template <>
+class voronoi_calc_kernel<int> {
+public:
+ typedef double fpt_type;
+ typedef polygon_ulong_long_type ulong_long_type;
+
+ enum kOrientation {
+ RIGHT = -1,
+ COLLINEAR = 0,
+ LEFT = 1,
+ };
+
+ // Value is a determinant of two vectors.
+ // Return orientation based on the sign of the determinant.
+ template <typename T>
+ static kOrientation get_orientation(T value) {
+ if (value == static_cast<T>(0.0)) return COLLINEAR;
+ return (value < static_cast<T>(0.0)) ? RIGHT : LEFT;
+ }
+
+ // Compute robust cross_product: a1 * b2 - b1 * a2.
+ // The result is correct with epsilon relative error equal to 2EPS.
+ template <typename T>
+ static fpt_type robust_cross_product(T a1_, T b1_, T a2_, T b2_) {
+ ulong_long_type a1, b1, a2, b2;
+ bool a1_plus, a2_plus, b1_plus, b2_plus;
+ a1_plus = convert_to_65_bit(a1_, a1);
+ b1_plus = convert_to_65_bit(b1_, b1);
+ a2_plus = convert_to_65_bit(a2_, a2);
+ b2_plus = convert_to_65_bit(b2_, b2);
+
+ ulong_long_type expr_l = a1 * b2;
+ bool expr_l_plus = (a1_plus == b2_plus) ? true : false;
+ ulong_long_type expr_r = b1 * a2;
+ bool expr_r_plus = (a2_plus == b1_plus) ? true : false;
+
+ if (expr_l == 0) expr_l_plus = true;
+ if (expr_r == 0) expr_r_plus = true;
+
+ if ((expr_l_plus == expr_r_plus) && (expr_l == expr_r))
+ return static_cast<fpt_type>(0.0);
+
+ // Produce the result with epsilon relative error.
+ if (!expr_l_plus) {
+ if (expr_r_plus)
+ return -static_cast<fpt_type>(expr_l) -
+ static_cast<fpt_type>(expr_r);
+ else return (expr_l > expr_r) ?
+ -static_cast<fpt_type>(expr_l - expr_r) :
+ static_cast<fpt_type>(expr_r - expr_l);
+ } else {
+ if (!expr_r_plus)
+ return static_cast<fpt_type>(expr_l) +
+ static_cast<fpt_type>(expr_r);
+ else
+ return (expr_l < expr_r) ?
+ -static_cast<fpt_type>(expr_r - expr_l) :
+ static_cast<fpt_type>(expr_l - expr_r);
+ }
+ }
+
+ // Robust orientation test. Works correctly for any input type that
+ // can be casted without lose of data to the integer type within a range
+ // [-2^32, 2^32-1].
+ // Arguments: dif_x1_, dif_y1 - coordinates of the first vector.
+ // dif_x2_, dif_y2 - coordinates of the second vector.
+ // Returns orientation test result for input vectors.
+ template <typename T>
+ static kOrientation get_orientation(T dif_x1_, T dif_y1_, T dif_x2_, T dif_y2_) {
+ return get_orientation(robust_cross_product(dif_x1_, dif_y1_, dif_x2_, dif_y2_));
+ }
+
+ // Robust orientation test. Works correctly for any input coordinate type
+ // that can be casted without lose of data to integer type within a range
+ // [-2^31, 2^31 - 1] - signed integer type.
+ // Arguments: point1, point2 - represent the first vector;
+ // point2, point3 - represent the second vector;
+ // Returns orientation test result for input vectors.
+ template <typename Point>
+ static kOrientation get_orientation(const Point &point1,
+ const Point &point2,
+ const Point &point3) {
+ return get_orientation(robust_cross_product(point1.x() - point2.x(),
+ point1.y() - point2.y(),
+ point2.x() - point3.x(),
+ point2.y() - point3.y()));
+ }
+
+ template <typename Site>
+ struct site_comparison_predicate {
+ typedef Site site_type;
+
+ bool operator()(const site_type &lhs, const site_type &rhs) const {
+ if (lhs.x0() != rhs.x0()) return lhs.x0() < rhs.x0();
+ if (!lhs.is_segment()) {
+ if (!rhs.is_segment()) return lhs.y0() < rhs.y0();
+ if (rhs.is_vertical()) return lhs.y0() <= rhs.y0();
+ return true;
+ } else {
+ if (rhs.is_vertical()) {
+ if(lhs.is_vertical()) return lhs.y0() < rhs.y0();
+ return false;
+ }
+ if (lhs.is_vertical()) return true;
+ if (lhs.y0() != rhs.y0()) return lhs.y0() < rhs.y0();
+ return get_orientation(lhs.point1(), lhs.point0(), rhs.point1()) == LEFT;
+ }
+ }
+ };
+
+ template <typename Site>
+ struct site_equality_predicate {
+ typedef Site site_type;
+
+ bool operator()(const site_type &lhs, const site_type &rhs) const {
+ return lhs.point0() == rhs.point0() &&
+ lhs.point1() == rhs.point1();
+ }
+ };
+
+ template <typename Circle>
+ struct circle_comparison_predicate {
+ typedef Circle circle_type;
+
+ static const unsigned int ULPS = 128;
+
+ bool operator()(const circle_type &lhs, const circle_type &rhs) const {
+ if (almost_equal(lhs.lower_x(), rhs.lower_x(), ULPS)) {
+ if (almost_equal(lhs.lower_y(), rhs.lower_y(), ULPS)) {
+ return false;
+ }
+ return lhs.lower_y() < rhs.lower_y();
+ }
+ return lhs.lower_x() < rhs.lower_x();
+ }
+ };
+
+ template <typename Site, typename Circle>
+ struct event_comparison_predicate {
+ typedef Site site_type;
+ typedef Circle circle_type;
+
+ static const unsigned int ULPS = 64;
+
+ bool operator()(const site_type &lhs, const circle_type &rhs) const {
+ if (almost_equal(lhs.x(), rhs.lower_x(), ULPS)) {
+ if (almost_equal(lhs.y(), rhs.lower_y(), ULPS)) return false;
+ return lhs.y() < rhs.lower_y();
+ }
+ return lhs.x() < rhs.lower_x();
+ }
+ };
+
+ template <typename Site>
+ class distance_predicate {
+ public:
+ typedef typename Site::point_type point_type;
+ typedef Site site_type;
+
+ // Robust predicate, avoids using high-precision libraries.
+ // Returns true if a horizontal line going through the new point site
+ // intersects right arc at first, else returns false. If horizontal line
+ // goes through intersection point of the given two arcs returns false.
+ // Works correctly for any input coordinate type that can be casted without
+ // lose of data to the integer type within a range [-2^31, 2^31-1].
+ bool pp(const site_type &left_site,
+ const site_type &right_site,
+ const site_type &new_site) const {
+ // Any two point sites with different x-coordinates create two
+ // bisectors. Each bisector is defined by the order the sites
+ // appear in its representation. Predicates used in this function
+ // won't produce the correct result for the any arrangment of the
+ // input sites. That's why some preprocessing is required to handle
+ // such cases.
+ const point_type &left_point = left_site.point0();
+ const point_type &right_point = right_site.point0();
+ const point_type &new_point = new_site.point0();
+ if (left_point.x() > right_point.x()) {
+ if (new_point.y() <= left_point.y())
+ return false;
+ } else if (left_point.x() < right_point.x()) {
+ if (new_point.y() >= right_point.y())
+ return true;
+ } else {
+ // If x-coordinates of the sites are equal, we may produce the
+ // result without any further computations.
+ return left_point.y() + right_point.y() < 2.0 * new_point.y();
+ }
+
+ fpt_type dist1 = find_distance_to_point_arc(left_site, new_point);
+ fpt_type dist2 = find_distance_to_point_arc(right_site, new_point);
+
+ // The undefined ulp range is equal to 3EPS + 3EPS <= 6ULP.
+ return dist1 < dist2;
+ }
+
+ // Returns true if a horizontal line going through a new site intersects
+ // right arc at first, else returns false. If horizontal line goes
+ // through intersection point of the given two arcs returns false also.
+ // reverse_order flag defines arrangement of the sites. If it's false
+ // the order is (point, segment), else - (segment, point).
+ bool ps(const site_type &left_site, const site_type &right_site,
+ const site_type &new_site, bool reverse_order) const {
+ kPredicateResult fast_res = fast_ps(
+ left_site, right_site, new_site, reverse_order);
+ if (fast_res != UNDEFINED) {
+ return (fast_res == LESS);
+ }
+
+ fpt_type dist1 = find_distance_to_point_arc(left_site, new_site.point0());
+ fpt_type dist2 = find_distance_to_segment_arc(right_site, new_site.point0());
+
+ // The undefined ulp range is equal to 3EPS + 8EPS <= 11ULP.
+ return reverse_order ^ (dist1 < dist2);
+ }
+
+ // Returns true if a horizontal line going through a new site intersects
+ // right arc at first, else returns false. If horizontal line goes
+ // through intersection point of the given two arcs returns false also.
+ bool ss(const site_type &left_site,
+ const site_type &right_site,
+ const site_type &new_site) const {
+ // Handle temporary segment sites.
+ if (left_site.index() == right_site.index()) {
+ return get_orientation(left_site.point0(),
+ left_site.point1(),
+ new_site.point0()) == LEFT;
+ }
+
+ // Distances between the x-coordinate of the sweepline and
+ // the x-coordinates of the points of the intersections of the
+ // horizontal line going through the new site with arcs corresponding
+ // to the first and to the second segment sites respectively.
+ fpt_type dist1 = find_distance_to_segment_arc(left_site, new_site.point0());
+ fpt_type dist2 = find_distance_to_segment_arc(right_site, new_site.point0());
+
+ // The undefined ulp range is equal to 8EPS + 8EPS <= 16ULP.
+ return dist1 < dist2;
+ }
+
+ private:
+ // Find the x-coordinate (relative to the sweepline position) of the point
+ // of the intersection of the horizontal line going through the new site
+ // with the arc corresponding to the point site.
+ // The relative error is atmost 3EPS.
+ fpt_type find_distance_to_point_arc(const site_type &site,
+ const point_type &point) const {
+ fpt_type dx = site.x() - point.x();
+ fpt_type dy = site.y() - point.y();
+ return (dx * dx + dy * dy) / (2.0 * dx);
+ }
+
+ // Find the x-coordinate (relative to the sweepline position) of the point
+ // of the intersection of the horizontal line going through the new site
+ // with the arc corresponding to the segment site.
+ // The relative error is atmost 8EPS.
+ fpt_type find_distance_to_segment_arc(const site_type &site,
+ const point_type &point) const {
+ if (site.is_vertical()) {
+ return (static_cast<fpt_type>(site.x()) - static_cast<fpt_type>(point.x())) *
+ static_cast<fpt_type>(0.5);
+ } else {
+ const point_type &segment0 = site.point0(true);
+ const point_type &segment1 = site.point1(true);
+ fpt_type a1 = segment1.x() - segment0.x();
+ fpt_type b1 = segment1.y() - segment0.y();
+ fpt_type a3 = point.x() - segment0.x();
+ fpt_type b3 = point.y() - segment0.y();
+ fpt_type k = std::sqrt(a1 * a1 + b1 * b1);
+ // Avoid substraction while computing k.
+ if (b1 >= 0.0) k = 1.0 / (b1 + k);
+ else k = (k - b1) / (a1 * a1);
+ // Relative error of the robust cross product is 2EPS.
+ // Relative error of the k is atmost 5EPS.
+ // The resulting relative error is atmost 8EPS.
+ return robust_cross_product(a1, b1, a3, b3) * k;
+ }
+ }
+
+ kPredicateResult fast_ps(const site_type &left_site, const site_type &right_site,
+ const site_type &new_site, bool reverse_order) const {
+ const point_type &site_point = left_site.point0();
+ const point_type &segment_start = right_site.point0(true);
+ const point_type &segment_end = right_site.point1(true);
+ const point_type &new_point = new_site.point0();
+ if (get_orientation(segment_start, segment_end, new_point) != RIGHT) {
+ return (!right_site.is_inverse()) ? LESS : MORE;
+ }
+
+ fpt_type dif_x = new_point.x() - site_point.x();
+ fpt_type dif_y = new_point.y() - site_point.y();
+ fpt_type a = segment_end.x() - segment_start.x();
+ fpt_type b = segment_end.y() - segment_start.y();
+
+ if (right_site.is_vertical()) {
+ if (new_point.y() < site_point.y() && !reverse_order)
+ return MORE;
+ else if (new_point.y() > site_point.y() && reverse_order)
+ return LESS;
+ return UNDEFINED;
+ } else {
+ kOrientation orientation = get_orientation(a, b, dif_x, dif_y);
+ if (orientation == LEFT) {
+ if (!right_site.is_inverse())
+ return reverse_order ? LESS : UNDEFINED;
+ return reverse_order ? UNDEFINED : MORE;
+ }
+ }
+
+ fpt_type fast_left_expr = a * (dif_y + dif_x) * (dif_y - dif_x);
+ fpt_type fast_right_expr = (2.0 * b) * dif_x * dif_y;
+ if (!(almost_equal(fast_left_expr, fast_right_expr, 4))) {
+ if ((fast_left_expr > fast_right_expr) ^ reverse_order)
+ return reverse_order ? LESS : MORE;
+ return UNDEFINED;
+ }
+ return UNDEFINED;
+ }
+ };
+
+ template <typename Node>
+ class node_comparison_predicate {
+ public:
+ typedef Node node_type;
+ typedef typename Node::coordinate_type coordinate_type;
+ typedef typename Node::site_event_type site_type;
+ typedef distance_predicate<site_type> distance_predicate_type;
+
+ // Compares nodes in the balanced binary search tree. Nodes are
+ // compared based on the y coordinates of the arcs intersection points.
+ // Nodes with less y coordinate of the intersection point go first.
+ // Comparison is only called during the new site events processing.
+ // That's why one of the nodes will always lie on the sweepline and may
+ // be represented as a straight horizontal line.
+ bool operator() (const node_type &node1,
+ const node_type &node2) const {
+ // Get x coordinate of the righmost site from both nodes.
+ const site_type &site1 = get_comparison_site(node1);
+ const site_type &site2 = get_comparison_site(node2);
+
+ if (site1.x() < site2.x()) {
+ // The second node contains a new site.
+ return less(node1.left_site(), node1.right_site(), site2);
+ } else if (site1.x() > site2.x()) {
+ // The first node contains a new site.
+ return !less(node2.left_site(), node2.right_site(), site1);
+ } else {
+ // This checks were evaluated experimentally.
+ if (site1.index() == site2.index()) {
+ // Both nodes are new (inserted during the same site event processing).
+ return get_comparison_y(node1) < get_comparison_y(node2);
+ } else if (site1.index() < site2.index()) {
+ std::pair<coordinate_type, int> y1 = get_comparison_y(node1, false);
+ std::pair<coordinate_type, int> y2 = get_comparison_y(node2, true);
+ if (y1.first != y2.first) return y1.first < y2.first;
+ return (!site1.is_segment()) ? (y1.second < 0) : false;
+ } else {
+ std::pair<coordinate_type, int> y1 = get_comparison_y(node1, true);
+ std::pair<coordinate_type, int> y2 = get_comparison_y(node2, false);
+ if (y1.first != y2.first) return y1.first < y2.first;
+ return (!site2.is_segment()) ? (y2.second > 0) : true;
+ }
+ }
+ }
+
+ private:
+ // Get the newer site.
+ const site_type &get_comparison_site(const node_type &node) const {
+ if (node.left_site().index() > node.right_site().index()) {
+ return node.left_site();
+ }
+ return node.right_site();
+ }
+
+ // Get comparison pair: y coordinate and direction of the newer site.
+ std::pair<coordinate_type, int> get_comparison_y(const node_type &node,
+ bool is_new_node = true) const {
+ if (node.left_site().index() == node.right_site().index()) {
+ return std::make_pair(node.left_site().y(), 0);
+ }
+ if (node.left_site().index() > node.right_site().index()) {
+ if (!is_new_node &&
+ node.left_site().is_segment() &&
+ node.left_site().is_vertical()) {
+ return std::make_pair(node.left_site().y1(), 1);
+ }
+ return std::make_pair(node.left_site().y(), 1);
+ }
+ return std::make_pair(node.right_site().y(), -1);
+ }
+
+ bool less(const site_type& left_site,
+ const site_type& right_site,
+ const site_type& new_site) const {
+ if (!left_site.is_segment()) {
+ if (!right_site.is_segment()) {
+ return predicate_.pp(left_site, right_site, new_site);
+ } else {
+ return predicate_.ps(left_site, right_site, new_site, false);
+ }
+ } else {
+ if (!right_site.is_segment()) {
+ return predicate_.ps(right_site, left_site, new_site, true);
+ } else {
+ return predicate_.ss(left_site, right_site, new_site);
+ }
+ }
+ }
+
+ private:
+ distance_predicate_type predicate_;
+ };
+
+ template <typename Site>
+ class circle_existence_predicate {
+ public:
+ typedef typename Site::point_type point_type;
+ typedef Site site_type;
+
+ bool ppp(const site_type &site1,
+ const site_type &site2,
+ const site_type &site3) const {
+ return get_orientation(site1.point0(), site2.point0(), site3.point0()) == RIGHT;
+ }
+
+ bool pps(const site_type &site1,
+ const site_type &site2,
+ const site_type &site3,
+ int segment_index) const {
+ if (segment_index != 2) {
+ kOrientation orient1 = get_orientation(site1.point0(),
+ site2.point0(), site3.point0(true));
+ kOrientation orient2 = get_orientation(site1.point0(),
+ site2.point0(), site3.point1(true));
+ if (segment_index == 1 && site1.x0() >= site2.x0()) {
+ if (orient1 != RIGHT)
+ return false;
+ } else if (segment_index == 3 && site2.x0() >= site1.x0()) {
+ if (orient2 != RIGHT)
+ return false;
+ } else if (orient1 != RIGHT && orient2 != RIGHT) {
+ return false;
+ }
+ } else {
+ if (site3.point0(true) == site1.point0() &&
+ site3.point1(true) == site2.point0())
+ return false;
+ }
+ return true;
+ }
+
+ bool pss(const site_type &site1,
+ const site_type &site2,
+ const site_type &site3,
+ int point_index) const {
+ if (site2.index() == site3.index()) {
+ return false;
+ }
+ if (point_index == 2) {
+ if (!site2.is_inverse() && site3.is_inverse())
+ return false;
+ if (site2.is_inverse() == site3.is_inverse() &&
+ get_orientation(site2.point0(true), site1.point0(), site3.point1(true)) != RIGHT)
+ return false;
+ }
+ return true;
+ }
+
+ bool sss(const site_type &site1,
+ const site_type &site2,
+ const site_type &site3) const {
+ if (site1.index() == site2.index())
+ return false;
+ if (site2.index() == site3.index())
+ return false;
+ return true;
+ }
+ };
+
+ template <typename Site, typename Circle>
+ class gmp_circle_formation_functor {
+ public:
+ typedef typename Site::point_type point_type;
+ typedef Site site_type;
+ typedef Circle circle_type;
+
+ bool ppp(const site_type &site1,
+ const site_type &site2,
+ const site_type &site3,
+ circle_type &circle,
+ bool recompute_c_x = true,
+ bool recompute_c_y = true,
+ bool recompute_lower_x = true) {
+ typedef mpt_wrapper<mpz_class, 8> mpt_type;
+ static mpt_type mpz_dif_x[3], mpz_dif_y[3], mpz_sum_x[2], mpz_sum_y[2],
+ mpz_numerator[3], mpz_c_x, mpz_c_y, mpz_sqr_r, denom,
+ cA[2], cB[2];
+ mpz_dif_x[0] = site1.x() - site2.x();
+ mpz_dif_x[1] = site2.x() - site3.x();
+ mpz_dif_x[2] = site1.x() - site3.x();
+ mpz_dif_y[0] = site1.y() - site2.y();
+ mpz_dif_y[1] = site2.y() - site3.y();
+ mpz_dif_y[2] = site1.y() - site3.y();
+ mpz_sum_x[0] = site1.x() + site2.x();
+ mpz_sum_x[1] = site2.x() + site3.x();
+ mpz_sum_y[0] = site1.y() + site2.y();
+ mpz_sum_y[1] = site2.y() + site3.y();
+
+ denom = (mpz_dif_x[0] * mpz_dif_y[1] - mpz_dif_x[1] * mpz_dif_y[0]) * 2.0;
+ mpz_numerator[1] = mpz_dif_x[0] * mpz_sum_x[0] + mpz_dif_y[0] * mpz_sum_y[0];
+ mpz_numerator[2] = mpz_dif_x[1] * mpz_sum_x[1] + mpz_dif_y[1] * mpz_sum_y[1];
+
+ if (recompute_c_x || recompute_lower_x) {
+ mpz_c_x = mpz_numerator[1] * mpz_dif_y[1] - mpz_numerator[2] * mpz_dif_y[0];
+ circle.x(mpz_c_x.get_d() / denom.get_d());
+
+ if (recompute_lower_x) {
+ // Evaluate radius of the circle.
+ mpz_sqr_r = 1.0;
+ for (int i = 0; i < 3; ++i)
+ mpz_sqr_r *= mpz_dif_x[i] * mpz_dif_x[i] + mpz_dif_y[i] * mpz_dif_y[i];
+ double r = std::sqrt(mpz_sqr_r.get_d());
+
+ // If c_x >= 0 then lower_x = c_x + r,
+ // else lower_x = (c_x * c_x - r * r) / (c_x - r).
+ // To guarantee epsilon relative error.
+ if (circle.x() >= 0) {
+ circle.lower_x(circle.x() + r / fabs(denom.get_d()));
+ } else {
+ mpz_numerator[0] = mpz_c_x * mpz_c_x - mpz_sqr_r;
+ double lower_x = mpz_numerator[0].get_d() /
+ (denom.get_d() * (mpz_c_x.get_d() + r));
+ circle.lower_x(lower_x);
+ }
+ }
+ }
+
+ if (recompute_c_y) {
+ mpz_c_y = mpz_numerator[2] * mpz_dif_x[0] - mpz_numerator[1] * mpz_dif_x[1];
+ circle.y(mpz_c_y.get_d() / denom.get_d());
+ }
+
+ return true;
+ }
+
+ // Recompute parameters of the circle event using high-precision library.
+ bool pps(const site_type &site1,
+ const site_type &site2,
+ const site_type &site3,
+ int segment_index,
+ circle_type &c_event,
+ bool recompute_c_x = true,
+ bool recompute_c_y = true,
+ bool recompute_lower_x = true) {
+ typedef mpt_wrapper<mpz_class, 8> mpt_type;
+ typedef mpt_wrapper<mpf_class, 2> mpf_type;
+ static mpt_type line_a, line_b, segm_len, vec_x, vec_y, sum_x, sum_y, teta,
+ denom, A, B, sum_AB, dif[2], numer, cA[4], cB[4], det;
+
+ line_a = site3.point1(true).y() - site3.point0(true).y();
+ line_b = site3.point0(true).x() - site3.point1(true).x();
+ segm_len = line_a * line_a + line_b * line_b;
+ vec_x = site2.y() - site1.y();
+ vec_y = site1.x() - site2.x();
+ sum_x = site1.x() + site2.x();
+ sum_y = site1.y() + site2.y();
+ teta = line_a * vec_x + line_b * vec_y;
+ denom = vec_x * line_b - vec_y * line_a;
+
+ dif[0] = site3.point1().y() - site1.y();
+ dif[1] = site1.x() - site3.point1().x();
+ A = line_a * dif[1] - line_b * dif[0];
+ dif[0] = site3.point1().y() - site2.y();
+ dif[1] = site2.x() - site3.point1().x();
+ B = line_a * dif[1] - line_b * dif[0];
+ sum_AB = A + B;
+
+ if (denom == 0) {
+ numer = teta * teta - sum_AB * sum_AB;
+ denom = teta * sum_AB;
+ cA[0] = denom * sum_x * 2 + numer * vec_x;
+ cB[0] = segm_len;
+ cA[1] = denom * sum_AB * 2 + numer * teta;
+ cB[1] = 1;
+ cA[2] = denom * sum_y * 2 + numer * vec_y;
+ if (recompute_c_x) {
+ c_event.x(0.25 * cA[0].get_d() / denom.get_d());
+ }
+ if (recompute_c_y) {
+ c_event.y(0.25 * cA[2].get_d() / denom.get_d());
+ }
+ if (recompute_lower_x) {
+ 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;
+ }
+
+ det = (teta * teta + denom * denom) * A * B * 4;
+ double denom_sqr = denom.get_d() * denom.get_d();
+
+ if (recompute_c_x || recompute_lower_x) {
+ cA[0] = sum_x * denom * denom + teta * sum_AB * vec_x;
+ cB[0] = 1;
+ cA[1] = (segment_index == 2) ? -vec_x : vec_x;
+ cB[1] = det;
+ if (recompute_c_x) {
+ c_event.x(0.5 * sqrt_expr_evaluator<2>::eval<mpt_type, mpf_type>(cA, cB).get_d() /
+ denom_sqr);
+ }
+ }
+
+ if (recompute_c_y || recompute_lower_x) {
+ cA[2] = sum_y * denom * denom + teta * sum_AB * vec_y;
+ cB[2] = 1;
+ cA[3] = (segment_index == 2) ? -vec_y : vec_y;
+ cB[3] = det;
+ if (recompute_c_y) {
+ c_event.y(0.5 * sqrt_expr_evaluator<2>::eval<mpt_type, mpf_type>(&cA[2], &cB[2]).get_d() /
+ denom_sqr);
+ }
+ }
+
+ if (recompute_lower_x) {
+ cB[0] *= segm_len;
+ cB[1] *= segm_len;
+ cA[2] = sum_AB * (denom * denom + teta * teta);
+ cB[2] = 1;
+ cA[3] = (segment_index == 2) ? -teta : teta;
+ cB[3] = det;
+ 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())));
+ }
+
+ return true;
+ }
+
+ // Recompute parameters of the circle event using high-precision library.
+ bool pss(const site_type &site1,
+ const site_type &site2,
+ const site_type &site3,
+ int point_index,
+ circle_type &c_event,
+ bool recompute_c_x = true,
+ bool recompute_c_y = true,
+ bool recompute_lower_x = true) {
+ typedef mpt_wrapper<mpz_class, 8> mpt_type;
+ typedef mpt_wrapper<mpf_class, 2> mpf_type;
+ static mpt_type a[2], b[2], c[2], cA[4], cB[4], orientation, dx, dy, ix, iy;
+
+ const point_type &segm_start1 = site2.point1(true);
+ const point_type &segm_end1 = site2.point0(true);
+ const point_type &segm_start2 = site3.point0(true);
+ const point_type &segm_end2 = site3.point1(true);
+
+ a[0] = segm_end1.x() - segm_start1.x();
+ b[0] = segm_end1.y() - segm_start1.y();
+ a[1] = segm_end2.x() - segm_start2.x();
+ b[1] = segm_end2.y() - segm_start2.y();
+ orientation = a[1] * b[0] - a[0] * b[1];
+ if (orientation == 0) {
+ double denom = (a[0] * a[0] + b[0] * b[0]).get_d() * 2.0;
+ c[0] = b[0] * (segm_start2.x() - segm_start1.x()) -
+ a[0] * (segm_start2.y() - segm_start1.y());
+ dx = a[0] * (site1.y() - segm_start1.y()) -
+ b[0] * (site1.x() - segm_start1.x());
+ dy = b[0] * (site1.x() - segm_start2.x()) -
+ a[0] * (site1.y() - segm_start2.y());
+ cB[0] = dx * dy;
+ cB[1] = 1;
+
+ if (recompute_c_y) {
+ cA[0] = b[0] * ((point_index == 2) ? 2 : -2);
+ 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 = sqrt_expr_evaluator<2>::eval<mpt_type, mpf_type>(cA, cB).get_d();
+ c_event.y(c_y / denom);
+ }
+
+ if (recompute_c_x || recompute_lower_x) {
+ cA[0] = a[0] * ((point_index == 2) ? 2 : -2);
+ cA[1] = b[0] * b[0] * (segm_start1.x() + segm_start2.x()) -
+ a[0] * b[0] * (segm_start1.y() + segm_start2.y() - 2.0 * site1.y()) +
+ a[0] * a[0] * (2.0 * site1.x());
+
+ if (recompute_c_x) {
+ 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 = sqrt_expr_evaluator<3>::eval<mpt_type, mpf_type>(cA, cB).get_d();
+ c_event.lower_x(lower_x / denom);
+ }
+ }
+ return true;
+ }
+ c[0] = b[0] * segm_end1.x() - a[0] * segm_end1.y();
+ c[1] = a[1] * segm_end2.y() - b[1] * segm_end2.x();
+ ix = a[0] * c[1] + a[1] * c[0];
+ iy = b[0] * c[1] + b[1] * c[0];
+ dx = ix - orientation * site1.x();
+ dy = iy - orientation * site1.y();
+ if ((dx == 0) && (dy == 0)) {
+ double denom = orientation.get_d();
+ double c_x = ix.get_d() / denom;
+ double c_y = iy.get_d() / denom;
+ c_event = circle_type(c_x, c_y, c_x);
+ return true;
+ }
+
+ double sign = ((point_index == 2) ? 1 : -1) * ((orientation < 0) ? 1 : -1);
+ cA[0] = a[1] * -dx + b[1] * -dy;
+ cA[1] = a[0] * -dx + b[0] * -dy;
+ cA[2] = sign;
+ cA[3] = 0;
+ cB[0] = a[0] * a[0] + b[0] * b[0];
+ 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 = 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 = sqrt_expr_evaluator_pss<mpt_type, mpf_type>(cA, cB).get_d();
+ c_event.y(cy / denom);
+ }
+
+ if (recompute_c_x || recompute_lower_x) {
+ cA[0] = a[1] * (dx * dx + dy * dy) - ix * (dx * a[1] + dy * b[1]);
+ cA[1] = a[0] * (dx * dx + dy * dy) - ix * (dx * a[0] + dy * b[0]);
+ cA[2] = ix * sign;
+
+ if (recompute_c_x) {
+ 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 = sqrt_expr_evaluator_pss<mpt_type, mpf_type>(cA, cB).get_d();
+ c_event.lower_x(lower_x / denom);
+ }
+ }
+
+ return true;
+ }
+
+ // Recompute parameters of the circle event using high-precision library.
+ bool sss(const site_type &site1,
+ const site_type &site2,
+ const site_type &site3,
+ circle_type &c_event,
+ bool recompute_c_x = true,
+ bool recompute_c_y = true,
+ bool recompute_lower_x = true) {
+ typedef mpt_wrapper<mpz_class, 8> mpt_type;
+ typedef mpt_wrapper<mpf_class, 2> mpf_type;
+ static mpt_type a[3], b[3], c[3], sqr_len[4], cross[4];
+
+ a[0] = site1.x1(true) - site1.x0(true);
+ a[1] = site2.x1(true) - site2.x0(true);
+ a[2] = site3.x1(true) - site3.x0(true);
+
+ b[0] = site1.y1(true) - site1.y0(true);
+ b[1] = site2.y1(true) - site2.y0(true);
+ b[2] = site3.y1(true) - site3.y0(true);
+
+ c[0] = mpt_cross(site1.x0(true), site1.y0(true), site1.x1(true), site1.y1(true));
+ c[1] = mpt_cross(site2.x0(true), site2.y0(true), site2.x1(true), site2.y1(true));
+ c[2] = mpt_cross(site3.x0(true), site3.y0(true), site3.x1(true), site3.y1(true));
+
+ for (int i = 0; i < 3; ++i) {
+ sqr_len[i] = a[i] * a[i] + b[i] * b[i];
+ }
+
+ for (int i = 0; i < 3; ++i) {
+ int j = (i+1) % 3;
+ int k = (i+2) % 3;
+ cross[i] = a[j] * b[k] - a[k] * b[j];
+ }
+ 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) {
+ int j = (i+1) % 3;
+ int k = (i+2) % 3;
+ cross[i] = b[j] * c[k] - b[k] * c[j];
+ }
+ double c_y = sqrt_expr_evaluator<3>::eval<mpt_type, mpf_type>(cross, sqr_len).get_d();
+ c_event.y(c_y / denom);
+ }
+
+ if (recompute_c_x || recompute_lower_x) {
+ cross[3] = 0;
+ for (int i = 0; i < 3; ++i) {
+ int j = (i+1) % 3;
+ int k = (i+2) % 3;
+ cross[i] = a[j] * c[k] - a[k] * c[j];
+ if (recompute_lower_x) {
+ cross[3] += cross[i] * b[i];
+ }
+ }
+
+ if (recompute_c_x) {
+ 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 = sqrt_expr_evaluator<4>::eval<mpt_type, mpf_type>(cross, sqr_len).get_d();
+ c_event.lower_x(lower_x / denom);
+ }
+ }
+
+ return true;
+ }
+
+ private:
+ template <typename T>
+ mpt_wrapper<mpz_class, 8> &mpt_cross(T a0, T b0, T a1, T b1) {
+ static mpt_wrapper<mpz_class, 8> temp[2];
+ temp[0] = a0;
+ temp[1] = b0;
+ temp[0] = temp[0] * b1;
+ temp[1] = temp[1] * a1;
+ temp[0] -= temp[1];
+ return temp[0];
+ }
+
+ // 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>
+ 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 = 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() *
+ sqrt_expr_evaluator<2>::eval<mpt, mpf>(cA, cB).get_d());
+ if (((lh >= 0) && (rh >= 0)) || ((lh <= 0) && (rh <= 0))) {
+ return lh + rh;
+ }
+ cA[0] = A[0] * A[0] * B[0] + A[1] * A[1] * B[1];
+ cA[0] -= A[2] * A[2] * B[3] * B[2];
+ cB[0] = 1;
+ cA[1] = A[0] * A[1] * 2 - A[2] * A[2] * B[3];
+ cB[1] = B[0] * B[1];
+ numer = sqrt_expr_evaluator<2>::eval<mpt, mpf>(cA, cB);
+ return numer / (lh - rh);
+ }
+ cA[0] = A[3];
+ cB[0] = 1;
+ cA[1] = A[0];
+ cB[1] = B[0];
+ cA[2] = A[1];
+ cB[2] = B[1];
+ 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() *
+ sqrt_expr_evaluator<2>::eval<mpt, mpf>(cA, cB).get_d());
+ if (((lh >= 0) && (rh >= 0)) || ((lh <= 0) && (rh <= 0))) {
+ return lh + rh;
+ }
+ cA[0] = A[0] * A[0] * B[0] + A[1] * A[1] * B[1];
+ cA[0] += A[3] * A[3] - A[2] * A[2] * B[2] * B[3];
+ cB[0] = 1;
+ cA[1] = A[3] * A[0] * 2;
+ cB[1] = B[0];
+ cA[2] = A[3] * A[1] * 2;
+ cB[2] = B[1];
+ cA[3] = A[0] * A[1] * 2 - A[2] * A[2] * B[3];
+ cB[3] = B[0] * B[1];
+ numer = sqrt_expr_evaluator<4>::eval<mpt, mpf>(cA, cB);
+ return numer / (lh - rh);
+ }
+ };
+
+ template <typename Site, typename Circle>
+ class lazy_circle_formation_functor {
+ public:
+ typedef typename Site::point_type point_type;
+ typedef Site site_type;
+ typedef Circle circle_type;
+ typedef gmp_circle_formation_functor<site_type, circle_type>
+ exact_circle_formation_functor_type;
+
+ // Find parameters of the inscribed circle that is tangent to three
+ // point sites.
+ bool ppp(const site_type &site1,
+ const site_type &site2,
+ const site_type &site3,
+ circle_type &c_event) {
+ double dif_x1 = site1.x() - site2.x();
+ double dif_x2 = site2.x() - site3.x();
+ double dif_y1 = site1.y() - site2.y();
+ double dif_y2 = site2.y() - site3.y();
+ double orientation = robust_cross_product(dif_x1, dif_y1, dif_x2, dif_y2);
+ robust_fpt<double> inv_orientation(0.5 / orientation, 3.0);
+ double sum_x1 = site1.x() + site2.x();
+ double sum_x2 = site2.x() + site3.x();
+ double sum_y1 = site1.y() + site2.y();
+ double sum_y2 = site2.y() + site3.y();
+ double dif_x3 = site1.x() - site3.x();
+ double dif_y3 = site1.y() - site3.y();
+ epsilon_robust_comparator< robust_fpt<double> > c_x, c_y;
+ c_x += robust_fpt<double>(dif_x1 * sum_x1 * dif_y2, 2.0);
+ c_x += robust_fpt<double>(dif_y1 * sum_y1 * dif_y2, 2.0);
+ c_x -= robust_fpt<double>(dif_x2 * sum_x2 * dif_y1, 2.0);
+ c_x -= robust_fpt<double>(dif_y2 * sum_y2 * dif_y1, 2.0);
+ c_y += robust_fpt<double>(dif_x2 * sum_x2 * dif_x1, 2.0);
+ c_y += robust_fpt<double>(dif_y2 * sum_y2 * dif_x1, 2.0);
+ c_y -= robust_fpt<double>(dif_x1 * sum_x1 * dif_x2, 2.0);
+ c_y -= robust_fpt<double>(dif_y1 * sum_y1 * dif_x2, 2.0);
+ epsilon_robust_comparator< robust_fpt<double> > lower_x(c_x);
+ lower_x -= robust_fpt<double>(std::sqrt(sqr_distance(dif_x1, dif_y1) *
+ sqr_distance(dif_x2, dif_y2) *
+ sqr_distance(dif_x3, dif_y3)), 5.0);
+ c_event = circle_type(c_x.dif().fpv() * inv_orientation.fpv(),
+ c_y.dif().fpv() * inv_orientation.fpv(),
+ lower_x.dif().fpv() * inv_orientation.fpv());
+ bool recompute_c_x = c_x.dif().ulp() >= 128;
+ bool recompute_c_y = c_y.dif().ulp() >= 128;
+ bool recompute_lower_x = lower_x.dif().ulp() >= 128;
+ if (recompute_c_x || recompute_c_y || recompute_lower_x) {
+ return exact_circle_formation_functor_.ppp(
+ site1, site2, site3, c_event, recompute_c_x, recompute_c_y, recompute_lower_x);
+ }
+ return true;
+ }
+
+ // Find parameters of the inscribed circle that is tangent to two
+ // point sites and on segment site.
+ bool pps(const site_type &site1,
+ const site_type &site2,
+ const site_type &site3,
+ int segment_index,
+ circle_type &c_event) {
+ double line_a = site3.point1(true).y() - site3.point0(true).y();
+ double line_b = site3.point0(true).x() - site3.point1(true).x();
+ double vec_x = site2.y() - site1.y();
+ double vec_y = site1.x() - site2.x();
+ robust_fpt<double> teta(robust_cross_product(line_a, line_b, -vec_y, vec_x), 2.0);
+ robust_fpt<double> A(robust_cross_product(line_a, line_b,
+ site3.point1().y() - site1.y(),
+ site1.x() - site3.point1().x()), 2.0);
+ robust_fpt<double> B(robust_cross_product(line_a, line_b,
+ site3.point1().y() - site2.y(),
+ site2.x() - site3.point1().x()), 2.0);
+ robust_fpt<double> denom(robust_cross_product(vec_x, vec_y, line_a, line_b), 2.0);
+ robust_fpt<double> inv_segm_len(1.0 / std::sqrt(sqr_distance(line_a, line_b)), 3.0);
+ epsilon_robust_comparator< robust_fpt<double> > t;
+ if (get_orientation(denom) == COLLINEAR) {
+ t += teta / (robust_fpt<double>(8.0) * A);
+ t -= A / (robust_fpt<double>(2.0) * teta);
+ } else {
+ robust_fpt<double> det = ((teta * teta + denom * denom) * A * B).sqrt();
+ if (segment_index == 2) {
+ t -= det / (denom * denom);
+ } else {
+ t += det / (denom * denom);
+ }
+ t += teta * (A + B) / (robust_fpt<double>(2.0) * denom * denom);
+ }
+ epsilon_robust_comparator< robust_fpt<double> > c_x, c_y;
+ c_x += robust_fpt<double>(0.5 * (site1.x() + site2.x()));
+ c_x += robust_fpt<double>(vec_x) * t;
+ c_y += robust_fpt<double>(0.5 * (site1.y() + site2.y()));
+ c_y += robust_fpt<double>(vec_y) * t;
+ epsilon_robust_comparator< robust_fpt<double> > r, lower_x(c_x);
+ r -= robust_fpt<double>(line_a) * robust_fpt<double>(site3.x0());
+ r -= robust_fpt<double>(line_b) * robust_fpt<double>(site3.y0());
+ r += robust_fpt<double>(line_a) * c_x;
+ r += robust_fpt<double>(line_b) * c_y;
+ r.abs();
+ lower_x += r * inv_segm_len;
+ c_event = circle_type(c_x.dif().fpv(), c_y.dif().fpv(), lower_x.dif().fpv());
+ bool recompute_c_x = c_x.dif().ulp() >= 128;
+ bool recompute_c_y = c_y.dif().ulp() >= 128;
+ bool recompute_lower_x = lower_x.dif().ulp() >= 128;
+ if (recompute_c_x || recompute_c_y || recompute_lower_x) {
+ return exact_circle_formation_functor_.pps(
+ site1, site2, site3, segment_index, c_event,
+ recompute_c_x, recompute_c_y, recompute_lower_x);
+ }
+ return true;
+ }
+
+ // Find parameters of the inscribed circle that is tangent to one
+ // point site and two segment sites.
+ bool pss(const site_type &site1,
+ const site_type &site2,
+ const site_type &site3,
+ int point_index,
+ circle_type &c_event) {
+ const point_type &segm_start1 = site2.point1(true);
+ const point_type &segm_end1 = site2.point0(true);
+ const point_type &segm_start2 = site3.point0(true);
+ const point_type &segm_end2 = site3.point1(true);
+ double a1 = segm_end1.x() - segm_start1.x();
+ double b1 = segm_end1.y() - segm_start1.y();
+ double a2 = segm_end2.x() - segm_start2.x();
+ double b2 = segm_end2.y() - segm_start2.y();
+ bool recompute_c_x, recompute_c_y, recompute_lower_x;
+ robust_fpt<double> orientation(robust_cross_product(b1, a1, b2, a2), 2.0);
+ if (get_orientation(orientation) == COLLINEAR) {
+ robust_fpt<double> a(a1 * a1 + b1 * b1, 2.0);
+ robust_fpt<double> c(robust_cross_product(b1, a1, segm_start2.y() - segm_start1.y(),
+ segm_start2.x() - segm_start1.x()), 2.0);
+ robust_fpt<double> det(robust_cross_product(a1, b1, site1.x() - segm_start1.x(),
+ site1.y() - segm_start1.y()) *
+ robust_cross_product(b1, a1, site1.y() - segm_start2.y(),
+ site1.x() - segm_start2.x()), 5.0);
+ epsilon_robust_comparator< robust_fpt<double> > t;
+ t -= robust_fpt<double>(a1) * robust_fpt<double>((segm_start1.x() + segm_start2.x()) * 0.5 - site1.x());
+ t -= robust_fpt<double>(b1) * robust_fpt<double>((segm_start1.y() + segm_start2.y()) * 0.5 - site1.y());
+ if (point_index == 2) {
+ t += det.sqrt();
+ } else {
+ t -= det.sqrt();
+ }
+ t /= a;
+ epsilon_robust_comparator< robust_fpt<double> > c_x, c_y;
+ c_x += robust_fpt<double>(0.5 * (segm_start1.x() + segm_start2.x()));
+ c_x += robust_fpt<double>(a1) * t;
+ c_y += robust_fpt<double>(0.5 * (segm_start1.y() + segm_start2.y()));
+ c_y += robust_fpt<double>(b1) * t;
+ epsilon_robust_comparator< robust_fpt<double> > lower_x(c_x);
+ lower_x += robust_fpt<double>(0.5) * c.fabs() / a.sqrt();
+ recompute_c_x = c_x.dif().ulp() > 128;
+ recompute_c_y = c_y.dif().ulp() > 128;
+ recompute_lower_x = lower_x.dif().ulp() > 128;
+ c_event = circle_type(c_x.dif().fpv(), c_y.dif().fpv(), lower_x.dif().fpv());
+ } else {
+ robust_fpt<double> sqr_sum1(std::sqrt(a1 * a1 + b1 * b1), 2.0);
+ robust_fpt<double> sqr_sum2(std::sqrt(a2 * a2 + b2 * b2), 2.0);
+ robust_fpt<double> a(robust_cross_product(a1, b1, -b2, a2), 2.0);
+ if (a >= 0) {
+ a += sqr_sum1 * sqr_sum2;
+ } else {
+ a = (orientation * orientation) / (sqr_sum1 * sqr_sum2 - a);
+ }
+ robust_fpt<double> or1(robust_cross_product(b1, a1, segm_end1.y() - site1.y(),
+ segm_end1.x() - site1.x()), 2.0);
+ robust_fpt<double> or2(robust_cross_product(a2, b2, segm_end2.x() - site1.x(),
+ segm_end2.y() - site1.y()), 2.0);
+ robust_fpt<double> det = robust_fpt<double>(2.0) * a * or1 * or2;
+ robust_fpt<double> c1(robust_cross_product(b1, a1, segm_end1.y(), segm_end1.x()), 2.0);
+ robust_fpt<double> c2(robust_cross_product(a2, b2, segm_end2.x(), segm_end2.y()), 2.0);
+ robust_fpt<double> inv_orientation = robust_fpt<double>(1.0) / orientation;
+ epsilon_robust_comparator< robust_fpt<double> > t, b, ix, iy;
+ ix += robust_fpt<double>(a2) * c1 * inv_orientation;
+ ix += robust_fpt<double>(a1) * c2 * inv_orientation;
+ iy += robust_fpt<double>(b1) * c2 * inv_orientation;
+ iy += robust_fpt<double>(b2) * c1 * inv_orientation;
+
+ b += ix * (robust_fpt<double>(a1) * sqr_sum2);
+ b += ix * (robust_fpt<double>(a2) * sqr_sum1);
+ b += iy * (robust_fpt<double>(b1) * sqr_sum2);
+ b += iy * (robust_fpt<double>(b2) * sqr_sum1);
+ b -= sqr_sum1 * robust_fpt<double>(robust_cross_product(a2, b2, -site1.y(), site1.x()), 2.0);
+ b -= sqr_sum2 * robust_fpt<double>(robust_cross_product(a1, b1, -site1.y(), site1.x()), 2.0);
+ t -= b;
+ if (point_index == 2) {
+ t += det.sqrt();
+ } else {
+ t -= det.sqrt();
+ }
+ t /= (a * a);
+ epsilon_robust_comparator< robust_fpt<double> > c_x(ix), c_y(iy);
+ c_x += t * (robust_fpt<double>(a1) * sqr_sum2);
+ c_x += t * (robust_fpt<double>(a2) * sqr_sum1);
+ c_y += t * (robust_fpt<double>(b1) * sqr_sum2);
+ c_y += t * (robust_fpt<double>(b2) * sqr_sum1);
+ t.abs();
+ epsilon_robust_comparator< robust_fpt<double> > lower_x(c_x);
+ lower_x += t * orientation.fabs();
+ recompute_c_x = c_x.dif().ulp() > 128;
+ recompute_c_y = c_y.dif().ulp() > 128;
+ recompute_lower_x = lower_x.dif().ulp() > 128;
+ c_event = circle_type(c_x.dif().fpv(), c_y.dif().fpv(), lower_x.dif().fpv());
+ }
+ if (recompute_c_x || recompute_c_y || recompute_lower_x) {
+ return exact_circle_formation_functor_.pss(
+ site1, site2, site3, point_index, c_event,
+ recompute_c_x, recompute_c_y, recompute_lower_x);
+ }
+ return true;
+ }
+
+ // Find parameters of the inscribed circle that is tangent to three
+ // segment sites.
+ bool sss(const site_type &site1,
+ const site_type &site2,
+ const site_type &site3,
+ circle_type &c_event) {
+ robust_fpt<double> a1(site1.x1(true) - site1.x0(true), 0.0);
+ robust_fpt<double> b1(site1.y1(true) - site1.y0(true), 0.0);
+ robust_fpt<double> c1(robust_cross_product(site1.x0(true), site1.y0(true), site1.x1(true), site1.y1(true)), 2.0);
+
+ robust_fpt<double> a2(site2.x1(true) - site2.x0(true), 0.0);
+ robust_fpt<double> b2(site2.y1(true) - site2.y0(true), 0.0);
+ robust_fpt<double> c2(robust_cross_product(site2.x0(true), site2.y0(true), site2.x1(true), site2.y1(true)), 2.0);
+
+ robust_fpt<double> a3(site3.x1(true) - site3.x0(true), 0.0);
+ robust_fpt<double> b3(site3.y1(true) - site3.y0(true), 0.0);
+ robust_fpt<double> c3(robust_cross_product(site3.x0(true), site3.y0(true), site3.x1(true), site3.y1(true)), 2.0);
+
+ robust_fpt<double> len1 = (a1 * a1 + b1 * b1).sqrt();
+ robust_fpt<double> len2 = (a2 * a2 + b2 * b2).sqrt();
+ robust_fpt<double> len3 = (a3 * a3 + b3 * b3).sqrt();
+ robust_fpt<double> cross_12(robust_cross_product(a1.fpv(), b1.fpv(), a2.fpv(), b2.fpv()), 2.0);
+ robust_fpt<double> cross_23(robust_cross_product(a2.fpv(), b2.fpv(), a3.fpv(), b3.fpv()), 2.0);
+ robust_fpt<double> cross_31(robust_cross_product(a3.fpv(), b3.fpv(), a1.fpv(), b1.fpv()), 2.0);
+ epsilon_robust_comparator< robust_fpt<double> > denom, c_x, c_y, r;
+
+ // denom = cross_12 * len3 + cross_23 * len1 + cross_31 * len2.
+ denom += cross_12 * len3;
+ denom += cross_23 * len1;
+ denom += cross_31 * len2;
+
+ // denom * r = (b2 * c_x - a2 * c_y - c2 * denom) / len2.
+ r -= cross_12 * c3;
+ r -= cross_23 * c1;
+ r -= cross_31 * c2;
+
+ c_x += a1 * c2 * len3;
+ c_x -= a2 * c1 * len3;
+ c_x += a2 * c3 * len1;
+ c_x -= a3 * c2 * len1;
+ c_x += a3 * c1 * len2;
+ c_x -= a1 * c3 * len2;
+ c_y += b1 * c2 * len3;
+ c_y -= b2 * c1 * len3;
+ c_y += b2 * c3 * len1;
+ c_y -= b3 * c2 * len1;
+ c_y += b3 * c1 * len2;
+ c_y -= b1 * c3 * len2;
+ epsilon_robust_comparator< robust_fpt<double> > lower_x(c_x + r);
+ bool recompute_c_x = c_x.dif().ulp() > 128;
+ bool recompute_c_y = c_y.dif().ulp() > 128;
+ bool recompute_lower_x = lower_x.dif().ulp() > 128;
+ bool recompute_denom = denom.dif().ulp() > 128;
+ c_event = circle_type(c_x.dif().fpv() / denom.dif().fpv(),
+ c_y.dif().fpv() / denom.dif().fpv(),
+ lower_x.dif().fpv() / denom.dif().fpv());
+ if (recompute_c_x || recompute_c_y || recompute_lower_x || recompute_denom) {
+ return exact_circle_formation_functor_.sss(
+ site1, site2, site3, c_event,
+ recompute_c_x, recompute_c_y, recompute_lower_x);
+ }
+ return true;
+ }
+
+ private:
+ template <typename T>
+ T sqr_distance(T dif_x, T dif_y) {
+ return dif_x * dif_x + dif_y * dif_y;
+ }
+
+ private:
+ exact_circle_formation_functor_type exact_circle_formation_functor_;
+ };
+
+ template <typename Site, typename Circle>
+ class circle_formation_predicate {
+ public:
+ typedef Site site_type;
+ typedef Circle circle_type;
+ typedef circle_existence_predicate<site_type> circle_existence_predicate_type;
+ typedef lazy_circle_formation_functor<site_type, circle_type>
+ circle_formation_functor_type;
+
+ // Create a circle event from the given three sites.
+ // Returns true if the circle event exists, else false.
+ // If exists circle event is saved into the c_event variable.
+ bool operator()(const site_type &site1, const site_type &site2,
+ const site_type &site3, circle_type &circle) {
+ if (!site1.is_segment()) {
+ if (!site2.is_segment()) {
+ if (!site3.is_segment()) {
+ // (point, point, point) sites.
+ if (!circle_existence_predicate_.ppp(site1, site2, site3))
+ return false;
+ circle_formation_functor_.ppp(site1, site2, site3, circle);
+ } else {
+ // (point, point, segment) sites.
+ if (!circle_existence_predicate_.pps(site1, site2, site3, 3))
+ return false;
+ circle_formation_functor_.pps(site1, site2, site3, 3, circle);
+ }
+ } else {
+ if (!site3.is_segment()) {
+ // (point, segment, point) sites.
+ if (!circle_existence_predicate_.pps(site1, site3, site2, 2))
+ return false;
+ circle_formation_functor_.pps(site1, site3, site2, 2, circle);
+ } else {
+ // (point, segment, segment) sites.
+ if (!circle_existence_predicate_.pss(site1, site2, site3, 1))
+ return false;
+ circle_formation_functor_.pss(site1, site2, site3, 1, circle);
+ }
+ }
+ } else {
+ if (!site2.is_segment()) {
+ if (!site3.is_segment()) {
+ // (segment, point, point) sites.
+ if (!circle_existence_predicate_.pps(site2, site3, site1, 1))
+ return false;
+ circle_formation_functor_.pps(site2, site3, site1, 1, circle);
+ } else {
+ // (segment, point, segment) sites.
+ if (!circle_existence_predicate_.pss(site2, site1, site3, 2))
+ return false;
+ circle_formation_functor_.pss(site2, site1, site3, 2, circle);
+ }
+ } else {
+ if (!site3.is_segment()) {
+ // (segment, segment, point) sites.
+ if (!circle_existence_predicate_.pss(site3, site1, site2, 3))
+ return false;
+ circle_formation_functor_.pss(site3, site1, site2, 3, circle);
+ } else {
+ // (segment, segment, segment) sites.
+ if (!circle_existence_predicate_.sss(site1, site2, site3))
+ return false;
+ circle_formation_functor_.sss(site1, site2, site3, circle);
+ }
+ }
+ }
+ return true;
+ }
+
+ private:
+ circle_existence_predicate_type circle_existence_predicate_;
+ circle_formation_functor_type circle_formation_functor_;
+ };
+
+private:
+ // Convert value to 64-bit unsigned integer.
+ // Return true if the value is positive, else false.
+ template <typename T>
+ static bool convert_to_65_bit(T value, ulong_long_type &res) {
+ if (value >= static_cast<T>(0)) {
+ res = static_cast<ulong_long_type>(value);
+ return true;
+ } else {
+ res = static_cast<ulong_long_type>(-value);
+ return false;
+ }
+ }
+};
+
+} // detail
+} // polygon
+} // boost
+
+#endif
Added: sandbox/gtl/boost/polygon/detail/voronoi_formation.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/boost/polygon/detail/voronoi_formation.hpp 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,503 @@
+// Boost polygon/detail/voronoi_formation.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_POLYGON_VORONOI_FORMATION
+#define BOOST_POLYGON_VORONOI_FORMATION
+
+#include "mpt_wrapper.hpp"
+#include "voronoi_fpt_kernel.hpp"
+
+namespace boost {
+namespace polygon {
+namespace detail {
+
+ ///////////////////////////////////////////////////////////////////////////
+ // VORONOI EVENT TYPES ////////////////////////////////////////////////////
+ ///////////////////////////////////////////////////////////////////////////
+
+ // Represents the result of the orientation test.
+ enum kOrientation {
+ RIGHT_ORIENTATION = -1,
+ COLLINEAR = 0,
+ 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;
+ // 2) startpoint of the segment site;
+ // 3) endpoint of the segment site.
+ // Implicit segment direction is defined: the startpoint of
+ // the segment compares less than its endpoint.
+ // Each input segment is divided onto two site events:
+ // 1) One going from the startpoint to the endpoint
+ // (is_inverse_ = false);
+ // 2) Another going from the endpoint to the startpoint
+ // (is_inverse_ = true).
+ // In beach line data structure segment sites of the first
+ // type preceed sites of the second type for the same segment.
+ // Variables: point0_ - point site or segment's startpoint;
+ // point1_ - segment's endpoint if site is a segment;
+ // index_ - site event index among other sites;
+ // is_segment_ - flag whether site is a segment;
+ // is_vertical_ - flag whether site is vertical;
+ // is_inverse_ - defines type of the segment site.
+ // Note: for all the point sites is_vertical_ flag is true,
+ // is_inverse_ flag is false.
+ template <typename T>
+ class site_event {
+ public:
+ typedef T coordinate_type;
+ typedef point_2d<T> point_type;
+
+ // Point site contructors.
+ site_event() :
+ point0_(0, 0),
+ point1_(0, 0),
+ is_segment_(false),
+ is_vertical_(true),
+ is_inverse_(false) {}
+
+ site_event(coordinate_type x, coordinate_type y, int index) :
+ point0_(x, y),
+ point1_(x, y),
+ site_index_(index),
+ is_segment_(false),
+ is_vertical_(true),
+ is_inverse_(false) {}
+
+ site_event(const point_type &point, int index) :
+ point0_(point),
+ point1_(point),
+ site_index_(index),
+ is_segment_(false),
+ is_vertical_(true),
+ is_inverse_(false) {}
+
+ // Segment site constructors.
+ site_event(coordinate_type x1, coordinate_type y1,
+ coordinate_type x2, coordinate_type y2, int index):
+ point0_(x1, y1),
+ point1_(x2, y2),
+ site_index_(index),
+ is_segment_(true),
+ is_inverse_(false) {
+ if (point0_ > point1_)
+ (std::swap)(point0_, point1_);
+ is_vertical_ = (point0_.x() == point1_.x());
+ }
+
+ site_event(const point_type &point1,
+ const point_type &point2, int index) :
+ point0_(point1),
+ point1_(point2),
+ site_index_(index),
+ is_segment_(true),
+ is_inverse_(false) {
+ if (point0_ > point1_)
+ (std::swap)(point0_, point1_);
+ is_vertical_ = (point0_.x() == point1_.x());
+ }
+
+ coordinate_type x(bool oriented = false) const {
+ return x0(oriented);
+ }
+
+ coordinate_type y(bool oriented = false) const {
+ return y0(oriented);
+ }
+
+ // Return x-coordinate of the point for the point sites.
+ // Return x-coordinate of the startpoint for the segment sites.
+ coordinate_type x0(bool oriented = false) const {
+ if (!oriented)
+ return point0_.x();
+ return is_inverse_ ? point1_.x() : point0_.x();
+ }
+
+ // Return y-coordinate of the point for the point sites.
+ // Return y-coordinate of the startpoint for the segment sites.
+ coordinate_type y0(bool oriented = false) const {
+ if (!oriented)
+ return point0_.y();
+ return is_inverse_ ? point1_.y() : point0_.y();
+ }
+
+ // Return x-coordinate of the endpoint of the segment sites.
+ // Doesn't make sense for the point sites.
+ coordinate_type x1(bool oriented = false) const {
+ if (!oriented)
+ return point1_.x();
+ return is_inverse_ ? point0_.x() : point1_.x();
+ }
+
+ // Return y-coordinate of the endpoint of the segment sites.
+ // Doesn't make sense for the point sites.
+ coordinate_type y1(bool oriented = false) const {
+ if (!oriented)
+ return point1_.y();
+ return is_inverse_ ? point0_.y() : point1_.y();
+ }
+
+ // Return point for the point sites.
+ // Return startpoint for the segment sites.
+ const point_type &point0(bool oriented = false) const {
+ if (!oriented)
+ return point0_;
+ return is_inverse_ ? point1_ : point0_;
+ }
+
+ // Return endpoint of the segment sites.
+ // Doesn't make sense for the point sites.
+ const point_type &point1(bool oriented = false) const {
+ if (!oriented)
+ return point1_;
+ return is_inverse_ ? point0_ : point1_;
+ }
+
+ // Return index of the site among all the other sites.
+ void index(int index) {
+ site_index_ = index;
+ }
+
+ // Change segment site orientation to the opposite one.
+ void inverse() {
+ is_inverse_ ^= true;
+ }
+
+ int index() const {
+ return site_index_;
+ }
+
+ bool is_segment() const {
+ return is_segment_;
+ }
+
+ bool is_vertical() const {
+ return is_vertical_;
+ }
+
+ bool is_inverse() const {
+ return is_inverse_;
+ }
+
+ private:
+ point_type point0_;
+ point_type point1_;
+ int site_index_;
+ bool is_segment_;
+ bool is_vertical_;
+ bool is_inverse_;
+ };
+
+ // Circle event type.
+ // Occrus when the sweepline sweeps over the rightmost point of the voronoi
+ // circle (with the center at the intersection point of the bisectors).
+ // Circle event is made by the two consequtive nodes in the beach line data
+ // structure. In case another node was inserted during algorithm execution
+ // between the given two nodes circle event becomes inactive.
+ // Circle events order is based on the comparison of the rightmost points
+ // of the circles. The order is the same like for the point_2d class.
+ // However as coordinates of the circle events might be not integers extra
+ // comparison checks are required to make the comparison robust.
+ // Next representation is used to store parameters of the circle:
+ // each of the parameters is represented as fraction
+ // numerator / denominator. Denominator is common for each of the
+ // three parameters. Epsilon robust comparator class is used
+ // to represent parameters of the circle events.
+ // Variables: center_x_ - numerator of the center's x-coordinate.
+ // center_y_ - numerator of the center's y-coordinate.
+ // lower_x_ - numerator of the bottom point's x-coordinate.
+ // denom_ - positive denominator for the previous three values.
+ // bisector_node_ - iterator to the second bisector's node.
+ // is_active_ - flag whether circle event is still active.
+ // lower_y coordinate is always equal to center_y.
+ template <typename T>
+ class circle_event {
+ public:
+ typedef T coordinate_type;
+
+ circle_event() : is_active_(true) {}
+
+ circle_event(coordinate_type c_x,
+ coordinate_type c_y,
+ coordinate_type lower_x) :
+ center_x_(c_x),
+ center_y_(c_y),
+ lower_x_(lower_x),
+ is_active_(true) {}
+
+ // Evaluate x-coordinate of the center of the circle.
+ coordinate_type x() const {
+ return center_x_;
+ }
+
+ void x(coordinate_type center_x) {
+ center_x_ = center_x;
+ }
+
+ // Evaluate y-coordinate of the center of the circle.
+ coordinate_type y() const {
+ return center_y_;
+ }
+
+ void y(coordinate_type center_y) {
+ center_y_ = center_y;
+ }
+
+ // Evaluate x-coordinate of the rightmost point of the circle.
+ coordinate_type lower_x() const {
+ return lower_x_;
+ }
+
+ coordinate_type lower_y() const {
+ return center_y_;
+ }
+
+ void lower_x(coordinate_type lower_x) {
+ lower_x_ = lower_x;
+ }
+
+ bool is_active() const {
+ return is_active_;
+ }
+
+ void deactivate() {
+ is_active_ = false;
+ }
+
+ private:
+ coordinate_type center_x_;
+ coordinate_type center_y_;
+ coordinate_type lower_x_;
+ bool is_active_;
+ };
+
+ ///////////////////////////////////////////////////////////////////////////
+ // VORONOI CIRCLE EVENTS QUEUE ////////////////////////////////////////////
+ ///////////////////////////////////////////////////////////////////////////
+
+ // Event queue data structure, holds circle events.
+ // During algorithm run, some of the circle events disappear(become
+ // inactive). Priority queue data structure by itself doesn't support
+ // iterators (there is no direct ability to modify its elements).
+ // Instead list is used to store all the circle events and priority queue
+ // of the iterators to the list elements is used to keep the correct circle
+ // events ordering.
+ template <typename T, typename Predicate>
+ class ordered_queue {
+ public:
+ ordered_queue() {}
+
+ bool empty() {
+ return c_.empty();
+ }
+
+ const T &top() {
+ return *c_.top();
+ }
+
+ void pop() {
+ list_iterator_type it = c_.top();
+ c_.pop();
+ c_list_.erase(it);
+ }
+
+ T &push(const T &e) {
+ c_list_.push_front(e);
+ c_.push(c_list_.begin());
+ return c_list_.front();
+ }
+
+ private:
+ typedef typename std::list<T>::iterator list_iterator_type;
+
+ struct comparison {
+ Predicate cmp_;
+ bool operator() (const list_iterator_type &it1,
+ const list_iterator_type &it2) const {
+ return cmp_(*it1, *it2);
+ }
+ };
+
+ std::priority_queue< list_iterator_type,
+ std::vector<list_iterator_type>,
+ comparison > c_;
+ std::list<T> c_list_;
+
+ //Disallow copy constructor and operator=
+ ordered_queue(const ordered_queue&);
+ void operator=(const ordered_queue&);
+ };
+
+ ///////////////////////////////////////////////////////////////////////////
+ // VORONOI BEACH LINE DATA TYPES //////////////////////////////////////////
+ ///////////////////////////////////////////////////////////////////////////
+
+ // Represents a bisector node made by two arcs that correspond to the left
+ // and right sites. Arc is defined as a curve with points equidistant from
+ // the site and from the sweepline. If the site is a point then the arc is
+ // a parabola, otherwise it's a line segment. A segment site event will
+ // produce different bisectors depending on its direction.
+ // In the general case two sites will create two opposite bisectors. That's
+ // why the order of the sites is important to define the unique bisector.
+ // The one site is considered to be newer than the other in case it was
+ // processed by the algorithm later.
+ template <typename SEvent>
+ class beach_line_node_key {
+ public:
+ typedef SEvent site_event_type;
+ typedef typename site_event_type::coordinate_type coordinate_type;
+ typedef typename site_event_type::point_type point_type;
+
+ beach_line_node_key() {}
+
+ // Constructs degenerate bisector, used to search an arc that is above
+ // the given site. The input to the constructor is the new site point.
+ explicit beach_line_node_key(const site_event_type &new_site) :
+ left_site_(new_site),
+ right_site_(new_site) {}
+
+ // Constructs a new bisector. The input to the constructor is the two
+ // sites that create the bisector. The order of sites is important.
+ beach_line_node_key(const site_event_type &left_site, const site_event_type &right_site) :
+ left_site_(left_site),
+ right_site_(right_site) {}
+
+ const site_event_type &left_site() const {
+ return left_site_;
+ }
+
+ const site_event_type &right_site() const {
+ return right_site_;
+ }
+
+ void left_site(const site_event_type &site) {
+ left_site_ = site;
+ }
+
+ void right_site(const site_event_type &site) {
+ right_site_ = site;
+ }
+
+ void inverse_left_site() {
+ left_site_.inverse();
+ }
+
+ void inverse_right_site() {
+ right_site_.inverse();
+ }
+
+ private:
+ site_event_type left_site_;
+ site_event_type right_site_;
+ };
+
+ // Represents edge data sturcture from the voronoi output, that is
+ // associated as a value with beach line bisector as a key in the beach
+ // line. Contains iterator to the circle event in the circle event
+ // queue in case it's the second bisector that forms a circle event.
+ template <typename CEvent>
+ class beach_line_node_data {
+ public:
+ explicit beach_line_node_data(void *new_edge) :
+ circle_event_(0),
+ edge_(new_edge) {}
+
+ void activate_circle_event(CEvent *circle_event) {
+ circle_event_ = circle_event;
+ }
+
+ void deactivate_circle_event() {
+ if (circle_event_) {
+ circle_event_->deactivate();
+ circle_event_ = 0;
+ }
+ }
+
+ void *edge() const {
+ return edge_;
+ }
+
+ void edge(void *new_edge) {
+ edge_ = new_edge;
+ }
+
+ private:
+ CEvent *circle_event_;
+ void *edge_;
+ };
+
+} // detail
+} // polygon
+} // boost
+
+#endif
Added: sandbox/gtl/boost/polygon/detail/voronoi_fpt_kernel.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/boost/polygon/detail/voronoi_fpt_kernel.hpp 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,572 @@
+// Boost polygon/detail/voronoi_fpt_kernel.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_POLYGON_VORONOI_FPT_KERNEL
+#define BOOST_POLYGON_VORONOI_FPT_KERNEL
+
+namespace boost {
+namespace polygon {
+namespace detail {
+
+ template <typename T>
+ class epsilon_robust_comparator;
+
+ // 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>
+ 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_; }
+
+ template <typename T>
+ bool operator==(T that) const {
+ floating_point_type value = static_cast<floating_point_type>(that);
+ return almost_equal(this->fpv_, value, static_cast<unsigned int>(this->ulp()));
+ }
+
+ template <typename T>
+ bool operator!=(T that) const {
+ return !(*this == that);
+ }
+
+ template <typename T>
+ bool operator<(T that) const {
+ if (*this == that) return false;
+ return this->fpv_ < static_cast<floating_point_type>(that);
+ }
+
+ template <typename T>
+ bool operator<=(T that) const {
+ if (*this == that) return true;
+ return this->fpv_ < static_cast<floating_point_type>(that);
+ }
+
+ template <typename T>
+ bool operator>(T that) const {
+ if (*this == that) return false;
+ return this->fpv_ > static_cast<floating_point_type>(that);
+ }
+
+ template <typename T>
+ bool operator>=(T that) const {
+ if (*this == that) return true;
+ return this->fpv_ > static_cast<floating_point_type>(that);
+ }
+
+ bool operator==(const robust_fpt &that) const {
+ 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 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;
+ }
+
+ 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());
+ }
+
+
+ ///////////////////////////////////////////////////////////////////////////
+ // 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
+} // polygon
+} // boost
+
+#endif
Added: sandbox/gtl/boost/polygon/voronoi.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/boost/polygon/voronoi.hpp 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,57 @@
+// Boost polygon/voronoi.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_POLYGON_VORONOI
+#define BOOST_POLYGON_VORONOI
+
+#include "polygon.hpp"
+#include "voronoi_builder.hpp"
+#include "voronoi_diagram.hpp"
+
+namespace boost {
+namespace polygon {
+
+ // Public methods to compute voronoi diagram.
+ // points - vector of input points.
+ // segments - vector of input segments.
+ // output - voronoi output data structure to hold voronoi diagram.
+ // The assumption is made that input doesn't contain segments that
+ // intersect or points lying on the segments. Also coordinates of
+ // the points and of the endpoints of the segments should be within
+ // signed integer range [-2^31, 2^31-1].
+ // Complexity - O(N*logN), memory usage - O(N), where N is the total
+ // number of points and segments.
+ template <typename T, typename PC, typename VD>
+ static inline void construct_voronoi_points(const PC &points, VD &output) {
+ voronoi_builder<T, VD> builder;
+ builder.insert_points(points.begin(), points.end());
+ builder.construct(output);
+ builder.clear();
+ }
+
+ template <typename T, typename SC, typename VD>
+ static inline void construct_voronoi_segments(const SC &segments, VD &output) {
+ voronoi_builder<T, VD> builder;
+ builder.insert_segments(segments.begin(), segments.end());
+ builder.construct(output);
+ builder.clear();
+ }
+
+ template <typename T, typename PC, typename SC, typename VD>
+ static inline void construct_voronoi(const PC &points, const SC &segments, VD &output) {
+ voronoi_builder<T, VD> builder;
+ builder.insert_sites(points.begin(), points.end(), segments.begin(), segments.end());
+ builder.construct(output);
+ builder.clear();
+ }
+
+}
+}
+
+#endif
Added: sandbox/gtl/boost/polygon/voronoi_builder.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/boost/polygon/voronoi_builder.hpp 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,559 @@
+// Boost polygon/voronoi_builder.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_POLYGON_VORONOI_BUILDER
+#define BOOST_POLYGON_VORONOI_BUILDER
+
+#include <algorithm>
+#include <cmath>
+#include <cstring>
+#include <list>
+#include <map>
+#include <queue>
+#include <vector>
+
+#pragma warning(disable:4800)
+#include <gmpxx.h>
+
+#include "polygon.hpp"
+
+#include "detail/mpt_wrapper.hpp"
+#include "detail/voronoi_calc_kernel.hpp"
+#include "detail/voronoi_fpt_kernel.hpp"
+#include "detail/voronoi_formation.hpp"
+
+namespace boost {
+namespace polygon {
+
+ ///////////////////////////////////////////////////////////////////////////
+ // VORONOI TRAITS /////////////////////////////////////////////////////////
+ ///////////////////////////////////////////////////////////////////////////
+
+ template <typename T>
+ struct voronoi_builder_traits;
+
+ template <>
+ struct voronoi_builder_traits<int> {
+ typedef detail::voronoi_calc_kernel<int> calc_kernel_type;
+ typedef calc_kernel_type::fpt_type coordinate_type;
+ };
+
+ ///////////////////////////////////////////////////////////////////////////
+ // VORONOI BUILDER ////////////////////////////////////////////////////////
+ ///////////////////////////////////////////////////////////////////////////
+
+ // The sweepline algorithm implementation to compute voronoi diagram of
+ // input data sets of points and segments (Fortune's algorithm).
+ // Complexity - O(N*logN), memory usage - O(N), where N is the total
+ // number of input objects.
+ // Sweepline is a vertical line that sweeps from the left to the right
+ // along the x-axis positive direction. Each of the input objects is
+ // wrapped into the site event. Each event is characterized by its
+ // coordinates: the point site is defined by the point itself,
+ // the segment site is defined by its startpoint. At any moment we
+ // consider only the sites that lie to the left of the sweepline. Beach
+ // line is a curve formed by the parabolic arcs and line segments, that
+ // consists of the points equidistant from the sweepline and the nearest
+ // site to the left of the sweepline. The part of the generated diagram to
+ // the left of the beach line remains unchanged until the end of the
+ // algorithm. Each node in the beach line corresponds to some voronoi edge.
+ // Each node is represented by two sites. Two neighboring nodes has a
+ // common site. Circle event appears at the rightmost point of the circle
+ // tangent to the three sites that correspond to the two consecutive
+ // bisectors. At each step algorithm goes over the leftmost event
+ // and processes it appropriately. This is made until there are no events.
+ // At the end output data structure holds the voronoi diagram of the
+ // initial set of objects.
+ // Each point creates one site event. Each segment creates three site
+ // events: two for its endpoints and one for the segment itself (this is
+ // made to simplify output construction). All the site events are
+ // constructed at the algorithm initialization step. After that they
+ // are ordered using quicksort algorithm.
+ // Priority queue is used to dynamically hold circle events. At each step
+ // of the algorithm the leftmost event is retrieved by comparing the
+ // current site event and the topmost element from the circle event queue.
+ // Standard map container was chosen to hold state of the beach line. The
+ // keys of the map correspond to the bisectors and values to the
+ // corresponding edges from the output data structure. Specially defined
+ // comparison functor is used to make the beach line correctly ordered.
+ // Epsilon-based and high-precision approaches are used to guarantee
+ // efficiency and robustness of the algorithm implementation.
+ // Member data: 1) site_events_ - vector of the site events;
+ // 2) site_event_iterator_ - iterator to the next
+ // site event;
+ // 3) circle_events_ - priority queue of circle events,
+ // allows to retrieve topmost event in O(logN) time;
+ // 4) beach_line_ - contains current state of the beach line;
+ // 5) end_points_ - maps endpoints of the segment sites with
+ // temporary nodes from the beach line. While sweepline
+ // sweeps over the second endpoint of the segments
+ // temporary nodes are being removed;
+ // 6) output_ - contains voronoi diagram itself.
+ template <typename T, typename VD>
+ class voronoi_builder {
+ public:
+ typedef typename voronoi_builder_traits<T>::coordinate_type coordinate_type;
+ typedef VD output_type;
+
+ voronoi_builder() {}
+
+ template <typename PointIterator>
+ void insert_points(PointIterator first_point, PointIterator last_point) {
+ // Create a site event from each input point.
+ for (PointIterator it = first_point; it != last_point; ++it) {
+ site_events_.push_back(detail::site_event<coordinate_type>(
+ static_cast<coordinate_type>(it->x()),
+ static_cast<coordinate_type>(it->y()), 0));
+ }
+ }
+
+ template <typename SegmentIterator>
+ void insert_segments(SegmentIterator first_segment, SegmentIterator last_segment) {
+ // Each segment creates three segment sites:
+ // 1) the startpoint of the segment;
+ // 2) the endpoint of the segment;
+ // 3) the segment itself.
+ for (SegmentIterator it = first_segment; it != last_segment; ++it) {
+ 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(detail::site_event<coordinate_type>(x1, y1, 0));
+ site_events_.push_back(detail::site_event<coordinate_type>(x2, y2, 0));
+ site_events_.push_back(detail::site_event<coordinate_type>(x1, y1, x2, y2, 0));
+ }
+ }
+
+ template <typename PointIterator, typename SegmentIterator>
+ void insert_sites(PointIterator first_point, PointIterator last_point,
+ SegmentIterator first_segment, SegmentIterator last_segment) {
+ insert_points(first_point, last_point);
+ insert_segments(first_segment, last_segment);
+ }
+
+ // Run the sweepline algorithm.
+ void construct(output_type &output) {
+ // Init structures.
+ output_ = &output;
+ output_->clear();
+ output_->reserve(site_events_.size());
+ init_sites_queue();
+ init_beach_line();
+
+ // The algorithm stops when there are no events to process.
+ // The circle events with the same rightmost point as the next
+ // site event go first.
+ event_comparison_predicate event_comparison;
+ while (!circle_events_.empty() ||
+ !(site_event_iterator_ == site_events_.end())) {
+ if (circle_events_.empty()) {
+ process_site_event();
+ } else if (site_event_iterator_ == site_events_.end()) {
+ process_circle_event();
+ } else {
+ if (event_comparison(*site_event_iterator_, circle_events_.top().first)) {
+ process_site_event();
+ } else {
+ process_circle_event();
+ }
+ }
+ while (!circle_events_.empty() && !circle_events_.top().first.is_active()) {
+ circle_events_.pop();
+ }
+ }
+
+ beach_line_.clear();
+
+ // Clean the output (remove zero-length edges).
+ output_->clean();
+ }
+
+ void clear() {
+ site_events_.clear();
+ }
+
+ private:
+ typedef voronoi_builder_traits<int>::calc_kernel_type calc_kernel_type;
+
+ typedef detail::point_2d<coordinate_type> point_type;
+ typedef detail::site_event<coordinate_type> site_event_type;
+ typedef calc_kernel_type::site_comparison_predicate<site_event_type>
+ site_comparison_predicate;
+ typedef calc_kernel_type::site_equality_predicate<site_event_type>
+ site_equality_predicate;
+ typedef typename std::vector<site_event_type>::const_iterator
+ site_event_iterator_type;
+ typedef detail::circle_event<coordinate_type> circle_event_type;
+ typedef calc_kernel_type::circle_comparison_predicate<circle_event_type>
+ circle_comparison_predicate;
+ typedef calc_kernel_type::event_comparison_predicate<site_event_type, circle_event_type>
+ event_comparison_predicate;
+ typedef calc_kernel_type::circle_formation_predicate<site_event_type, circle_event_type>
+ circle_formation_predicate_type;
+ typedef detail::beach_line_node_key<site_event_type> key_type;
+ typedef detail::beach_line_node_data<circle_event_type> value_type;
+ typedef calc_kernel_type::node_comparison_predicate<key_type> node_comparer_type;
+ typedef std::map< key_type, value_type, node_comparer_type > beach_line_type;
+ typedef typename beach_line_type::iterator beach_line_iterator;
+ typedef std::pair<circle_event_type, beach_line_iterator> event_type;
+ typedef struct {
+ bool operator()(const event_type &lhs, const event_type &rhs) const {
+ return predicate(rhs.first, lhs.first);
+ }
+ circle_comparison_predicate predicate;
+ } event_comparison_type;
+ typedef detail::ordered_queue<event_type, event_comparison_type>
+ circle_event_queue_type;
+ typedef typename output_type::voronoi_edge_type edge_type;
+ typedef std::pair<point_type, beach_line_iterator> end_point_type;
+
+ // Create site events.
+ // 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).
+ void init_sites_queue() {
+ // Sort the site events.
+ sort(site_events_.begin(), site_events_.end(), site_comparison_predicate());
+
+ // Remove duplicates.
+ site_events_.erase(unique(
+ site_events_.begin(), site_events_.end(), site_equality_predicate()), site_events_.end());
+
+ // Number the sites.
+ for (size_t cur = 0; cur < site_events_.size(); ++cur)
+ site_events_[cur].index(cur);
+
+ // Init the site's iterator.
+ site_event_iterator_ = site_events_.begin();
+ }
+
+ void init_beach_line() {
+ if (site_events_.empty()) return;
+ if (site_events_.size() == 1) {
+ // Handle one input site case.
+ output_->process_single_site(site_events_[0]);
+ ++site_event_iterator_;
+ } else {
+ int skip = 0;
+
+ // Count the number of the sites to init the beach line.
+ while(site_event_iterator_ != site_events_.end() &&
+ site_event_iterator_->x() == site_events_.begin()->x() &&
+ site_event_iterator_->is_vertical()) {
+ ++site_event_iterator_;
+ ++skip;
+ }
+
+ if (skip == 1) {
+ // Init the beach line with the two first sites.
+ init_beach_line_default();
+ } else {
+ // Init the beach line with the sites situated on the same
+ // vertical line. This could be a set of point and vertical
+ // segment sites.
+ init_beach_line_collinear_sites();
+ }
+ }
+ }
+
+ // Init the beach line with the two first sites.
+ // The first site is always a point.
+ void init_beach_line_default() {
+ // Get the first and the second site events.
+ site_event_iterator_type it_first = site_events_.begin();
+ site_event_iterator_type it_second = site_events_.begin();
+ ++it_second;
+
+ // Update the beach line.
+ insert_new_arc(*it_first, *it_first, *it_second, beach_line_.begin());
+
+ // The second site has been already processed.
+ // Move the site's iterator.
+ ++site_event_iterator_;
+ }
+
+ // Insert bisectors for all collinear initial sites.
+ void init_beach_line_collinear_sites() {
+ site_event_iterator_type it_first = site_events_.begin();
+ site_event_iterator_type it_second = site_events_.begin();
+ ++it_second;
+ while (it_second != site_event_iterator_) {
+ // Create a new beach line node.
+ key_type new_node(*it_first, *it_second);
+
+ // Update the output.
+ edge_type *edge = output_->insert_new_edge(*it_first, *it_second);
+
+ // Insert a new bisector into the beach line.
+ beach_line_.insert(
+ std::pair<key_type, value_type>(new_node, value_type(edge)));
+
+ // Update iterators.
+ ++it_first;
+ ++it_second;
+ }
+ }
+
+ // Process a single site.
+ void process_site_event() {
+ // Get the site event to process.
+ site_event_type site_event = *site_event_iterator_;
+
+ // Move the site's iterator.
+ site_event_iterator_type last = site_event_iterator_ + 1;
+
+ // If a new site is an end point of some segment,
+ // remove temporary nodes from the beach line data structure.
+ if (!site_event.is_segment()) {
+ while (!end_points_.empty() &&
+ end_points_.top().first == site_event.point0()) {
+ beach_line_iterator b_it = end_points_.top().second;
+ end_points_.pop();
+ beach_line_.erase(b_it);
+ }
+ } else {
+ while (last != site_events_.end() &&
+ last->is_segment() && last->point0() == site_event.point0())
+ last++;
+ }
+
+ for (; site_event_iterator_ != last; ++site_event_iterator_) {
+ site_event = *site_event_iterator_;
+ // Create degenerate node.
+ key_type new_key(site_event);
+
+ // Find the node in the binary search tree with left arc
+ // lying above the new site point.
+ beach_line_iterator it = beach_line_.lower_bound(new_key);
+ int it_dist = site_event.is_segment() ? 2 : 1;
+
+ // Do further processing depending on the above node position.
+ // For any two neighbouring nodes the second site of the first node
+ // is the same as the first site of the second arc.
+ if (it == beach_line_.end()) {
+ // The above arc corresponds to the second arc of the last node.
+ // Move the iterator to the last node.
+ --it;
+
+ // Get the second site of the last node
+ const site_event_type &site_arc = it->first.right_site();
+
+ // Insert new nodes into the beach line. Update the output.
+ beach_line_iterator new_node_it =
+ insert_new_arc(site_arc, site_arc, site_event, it);
+
+ // Add a candidate circle to the circle event queue.
+ // There could be only one new circle event formed by
+ // a new bisector and the one on the left.
+ std::advance(new_node_it, -it_dist);
+ activate_circle_event(it->first.left_site(),
+ it->first.right_site(),
+ site_event, new_node_it);
+ } else if (it == beach_line_.begin()) {
+ // The above arc corresponds to the first site of the first node.
+ const site_event_type &site_arc = it->first.left_site();
+
+ // Insert new nodes into the beach line. Update the output.
+ insert_new_arc(site_arc, site_arc, site_event, it);
+
+ // If the site event is a segment, update its direction.
+ if (site_event.is_segment()) {
+ site_event.inverse();
+ }
+
+ // Add a candidate circle to the circle event queue.
+ // There could be only one new circle event formed by
+ // a new bisector and the one on the right.
+ activate_circle_event(site_event, it->first.left_site(),
+ it->first.right_site(), it);
+ } else {
+ // The above arc corresponds neither to the first,
+ // nor to the last site in the beach line.
+ const site_event_type &site_arc2 = it->first.left_site();
+ const site_event_type &site3 = it->first.right_site();
+
+ // Remove the candidate circle from the event queue.
+ it->second.deactivate_circle_event();
+ --it;
+ const site_event_type &site_arc1 = it->first.right_site();
+ const site_event_type &site1 = it->first.left_site();
+
+ // Insert new nodes into the beach line. Update the output.
+ beach_line_iterator new_node_it =
+ insert_new_arc(site_arc1, site_arc2, site_event, it);
+
+ // Add candidate circles to the circle event queue.
+ // There could be up to two circle events formed by
+ // a new bisector and the one on the left or right.
+ std::advance(new_node_it, -it_dist);
+ activate_circle_event(site1, site_arc1, site_event,
+ new_node_it);
+
+ // If the site event is a segment, update its direction.
+ if (site_event.is_segment()) {
+ site_event.inverse();
+ }
+ std::advance(new_node_it, it_dist + 1);
+ activate_circle_event(site_event, site_arc2, site3,
+ new_node_it);
+ }
+ }
+ }
+
+ // Process a single circle event.
+ // In general case circle event is made of the three consequtive sites
+ // that form two bisector nodes in the beach line data structure.
+ // Let circle event sites be A, B, C, two bisectors that define
+ // circle event be (A, B), (B, C). During circle event processing
+ // we remove (A, B), (B, C) and insert (A, C). As beach line comparer
+ // works correctly only if one of the nodes is a new one we remove
+ // (B, C) bisector and change (A, B) bisector to the (A, C). That's
+ // why we use const_cast there and take all the responsibility that
+ // map data structure keeps correct ordering.
+ void process_circle_event() {
+ // Get the topmost circle event.
+ const event_type &e = circle_events_.top();
+ const circle_event_type &circle_event = e.first;
+ beach_line_iterator it_first = e.second;
+ beach_line_iterator it_last = it_first;
+
+ // Get the C site.
+ site_event_type site3 = it_first->first.right_site();
+
+ // Get the half-edge corresponding to the second bisector - (B, C).
+ edge_type *bisector2 = static_cast<edge_type *>(it_first->second.edge());
+
+ // Get the half-edge corresponding to the first bisector - (A, B).
+ --it_first;
+ edge_type *bisector1 = static_cast<edge_type *>(it_first->second.edge());
+
+ // Get the A site.
+ site_event_type site1 = it_first->first.left_site();
+
+ if (!site1.is_segment() && site3.is_segment() &&
+ site3.point1(true) == site1.point0()) {
+ site3.inverse();
+ }
+
+ // Change the (A, B) bisector node to the (A, C) bisector node.
+ const_cast<key_type &>(it_first->first).right_site(site3);
+
+ // Insert the new bisector into the beach line.
+ it_first->second.edge(output_->insert_new_edge(site1, site3, circle_event,
+ bisector1, bisector2));
+
+ // Remove the (B, C) bisector node from the beach line.
+ beach_line_.erase(it_last);
+ it_last = it_first;
+
+ // Pop the topmost circle event from the event queue.
+ circle_events_.pop();
+
+ // Check new triplets formed by the neighboring arcs
+ // to the left for potential circle events.
+ if (it_first != beach_line_.begin()) {
+ it_first->second.deactivate_circle_event();
+ --it_first;
+ const site_event_type &site_l1 = it_first->first.left_site();
+ activate_circle_event(site_l1, site1, site3, it_last);
+ }
+
+ // Check the new triplet formed by the neighboring arcs
+ // to the right for potential circle events.
+ ++it_last;
+ if (it_last != beach_line_.end()) {
+ it_last->second.deactivate_circle_event();
+ const site_event_type &site_r1 = it_last->first.right_site();
+ activate_circle_event(site1, site3, site_r1, it_last);
+ }
+ }
+
+ // Insert new nodes into the beach line. Update the output.
+ beach_line_iterator insert_new_arc(const site_event_type &site_arc1,
+ const site_event_type &site_arc2,
+ const site_event_type &site_event,
+ const beach_line_iterator &position) {
+ // Create two new bisectors with opposite directions.
+ key_type new_left_node(site_arc1, site_event);
+ key_type new_right_node(site_event, site_arc2);
+
+ // Set correct orientation for the first site of the second node.
+ if (site_event.is_segment()) {
+ new_right_node.inverse_left_site();
+ }
+
+ // Update the output.
+ edge_type *edge = output_->insert_new_edge(site_arc2, site_event);
+
+ // Update the beach line with the (site_arc1, site_event) bisector.
+ beach_line_iterator it = beach_line_.insert(position,
+ typename beach_line_type::value_type(new_right_node, value_type(edge->twin())));
+
+ if (site_event.is_segment()) {
+ // Update the beach line with temporary bisector, that will
+ // disappear after processing site event going through the
+ // endpoint of the segment site.
+ key_type new_node(site_event, site_event);
+ new_node.inverse_right_site();
+ beach_line_iterator temp_it = beach_line_.insert(position,
+ typename beach_line_type::value_type(new_node, value_type(NULL)));
+
+ // Update the data structure that holds temporary bisectors.
+ end_points_.push(std::make_pair(site_event.point1(), temp_it));
+ }
+
+ // Update the beach line with the (site_event, site_arc2) bisector.
+ beach_line_.insert(position,
+ typename beach_line_type::value_type(new_left_node, value_type(edge)));
+ return it;
+ }
+
+ // Add a new circle event to the event queue.
+ // bisector_node corresponds to the (site2, site3) bisector.
+ void activate_circle_event(const site_event_type &site1,
+ const site_event_type &site2,
+ const site_event_type &site3,
+ beach_line_iterator bisector_node) {
+ circle_event_type c_event;
+ // Check if the three input sites create a circle event.
+ if (circle_formation_predicate_(site1, site2, site3, c_event)) {
+ // Add the new circle event to the circle events queue.
+ // Update bisector's circle event iterator to point to the
+ // new circle event in the circle event queue.
+ event_type &e = circle_events_.push(
+ std::pair<circle_event_type, beach_line_iterator>(c_event, bisector_node));
+ bisector_node->second.activate_circle_event(&e.first);
+ }
+ }
+
+ private:
+ struct end_point_comparison {
+ bool operator() (const end_point_type &end1, const end_point_type &end2) const {
+ return end1.first > end2.first;
+ }
+ };
+
+ std::vector<site_event_type> site_events_;
+ site_event_iterator_type site_event_iterator_;
+ std::priority_queue< end_point_type, std::vector<end_point_type>,
+ end_point_comparison > end_points_;
+ circle_event_queue_type circle_events_;
+ beach_line_type beach_line_;
+ output_type *output_;
+ circle_formation_predicate_type circle_formation_predicate_;
+
+ //Disallow copy constructor and operator=
+ voronoi_builder(const voronoi_builder&);
+ void operator=(const voronoi_builder&);
+ };
+
+} // polygon
+} // boost
+
+#endif
Added: sandbox/gtl/boost/polygon/voronoi_diagram.hpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/boost/polygon/voronoi_diagram.hpp 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,1133 @@
+// Boost polygon/voronoi_diagram.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_POLYGON_VORONOI_DIAGRAM
+#define BOOST_POLYGON_VORONOI_DIAGRAM
+
+#include <cmath>
+#include <list>
+#include <stack>
+#include <vector>
+
+#include "polygon.hpp"
+#include "detail/voronoi_fpt_kernel.hpp"
+
+namespace boost {
+namespace polygon {
+
+ ///////////////////////////////////////////////////////////////////////////
+ // VORONOI OUTPUT TYPES ///////////////////////////////////////////////////
+ ///////////////////////////////////////////////////////////////////////////
+
+ // Forward declarations.
+ template <typename T>
+ class voronoi_cell;
+
+ template <typename T>
+ class voronoi_edge;
+
+ // 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_data<coordinate_type> point_type;
+
+ BRect() {}
+
+ template <typename P>
+ BRect(const P &p) {
+ x_min_ = x_max_ = static_cast<coordinate_type>(p.x());
+ y_min_ = y_max_ = static_cast<coordinate_type>(p.y());
+ }
+
+ template <typename P>
+ BRect(const P &p1, const P &p2) {
+ x_min_ = (std::min)(static_cast<coordinate_type>(p1.x()), static_cast<coordinate_type>(p2.x()));
+ y_min_ = (std::min)(static_cast<coordinate_type>(p1.y()), static_cast<coordinate_type>(p2.y()));
+ x_max_ = (std::max)(static_cast<coordinate_type>(p1.x()), static_cast<coordinate_type>(p2.x()));
+ y_max_ = (std::max)(static_cast<coordinate_type>(p1.y()), static_cast<coordinate_type>(p2.y()));
+ }
+
+ BRect(coordinate_type x_mn, coordinate_type y_mn,
+ coordinate_type x_mx, coordinate_type y_mx) {
+ x_min_ = (std::min)(x_mn, x_mx);
+ y_min_ = (std::min)(y_mn, y_mx);
+ x_max_ = (std::max)(x_mn, x_mx);
+ y_max_ = (std::max)(y_mn, y_mx);
+ }
+
+ // Extend the rectangle with a new point.
+ template <typename P>
+ void update(const P &p) {
+ x_min_ = (std::min)(x_min_, static_cast<coordinate_type>(p.x()));
+ y_min_ = (std::min)(y_min_, static_cast<coordinate_type>(p.y()));
+ x_max_ = (std::max)(x_max_, static_cast<coordinate_type>(p.x()));
+ y_max_ = (std::max)(y_max_, static_cast<coordinate_type>(p.y()));
+ }
+
+ // Check whether a point is situated inside the bounding rectangle.
+ bool contains(const point_type &p) const {
+ return p.x() >= x_min_ && p.x() <= x_max_ &&
+ p.y() >= y_min_ && p.y() <= y_max_;
+ }
+
+ // Check whether the bounding rectangle has a non-zero area.
+ bool verify() 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_data<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:
+ // 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_type> get_point_interpolation(
+ 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_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_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,
+ 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_type &point1 = (cell1->contains_segment()) ?
+ cell2->point0() : cell1->point0();
+
+ // point2 - startpoint of the segment site;
+ const point_type &point2 = (cell1->contains_segment()) ?
+ cell1->point0() : cell2->point0();
+
+ // point3 - endpoint of the segment site;
+ const point_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_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;
+ }
+
+ // 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<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_type &origin, const point_type &direction,
+ kEdgeType edge_type, const brect_type &brect,
+ 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;
+
+ // 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(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(point_type(
+ 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_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 ||
+ 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_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(
+ point_type(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_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() -
+ 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_data<coordinate_type> point_type;
+ typedef voronoi_edge<coordinate_type> voronoi_edge_type;
+
+ template <typename P>
+ voronoi_cell(const P &p1, const P &p2,
+ bool contains_segment, voronoi_edge_type *edge) :
+ point0_(static_cast<coordinate_type>(p1.x()), static_cast<coordinate_type>(p1.y())),
+ point1_(static_cast<coordinate_type>(p2.x()), static_cast<coordinate_type>(p2.y())),
+ 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_type &point0() const { return point0_; }
+
+ // Returns the second site of the segment site.
+ // Don't use with the point sites.
+ 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_; }
+ void inc_num_incident_edges() { ++num_incident_edges_; }
+ void dec_num_incident_edges() { --num_incident_edges_; }
+
+ private:
+ point_type point0_;
+ point_type point1_;
+ bool contains_segment_;
+ voronoi_edge_type *incident_edge_;
+ int num_incident_edges_;
+ };
+
+ // Represents voronoi vertex.
+ // Data members: 1) vertex point itself;
+ // 2) pointer to the incident edge;
+ // 3) number of incident edges.
+ template <typename T>
+ class voronoi_vertex {
+ public:
+ typedef T coordinate_type;
+ typedef point_data<T> point_type;
+ typedef voronoi_edge<coordinate_type> voronoi_edge_type;
+
+ template <typename P>
+ voronoi_vertex(const P &vertex, voronoi_edge_type *edge) :
+ vertex_(static_cast<coordinate_type>(vertex.x()), static_cast<coordinate_type>(vertex.y())),
+ incident_edge_(edge),
+ num_incident_edges_(3) {}
+
+ 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_; }
+ void incident_edge(voronoi_edge_type *e) { incident_edge_ = e; }
+
+ int num_incident_edges() const { return num_incident_edges_; }
+ void num_incident_edges(int n) { num_incident_edges_ = n; }
+
+ private:
+ point_type vertex_;
+ voronoi_edge_type *incident_edge_;
+ 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_; }
+ 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; }
+
+ // 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:
+ 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) voronoi_rect_ - bounding rectangle;
+ // 5) num_cell_records_ - number of the voronoi cells;
+ // 6) num_vertex_records_ - number of the voronoi vertices;
+ // 7) 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_diagram {
+ public:
+ typedef T coordinate_type;
+ typedef point_data<coordinate_type> point_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_diagram() :
+ num_cell_records_(0),
+ num_edge_records_(0),
+ num_vertex_records_(0) {}
+
+ void 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<coordinate_type> &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_;
+ }
+
+ void reserve(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.
+ template <typename SEvent>
+ void process_single_site(const SEvent &site) {
+ // Update bounding rectangle.
+ voronoi_rect_ = BRect<coordinate_type>(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.
+ template <typename SEvent>
+ voronoi_edge_type *insert_new_edge(const SEvent &site1, const SEvent &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.
+ template <typename SEvent, typename CEvent>
+ voronoi_edge_type *insert_new_edge(const SEvent &site1,
+ const SEvent &site3,
+ const CEvent &circle,
+ voronoi_edge_type *edge12,
+ voronoi_edge_type *edge23) {
+ // Add a new voronoi vertex.
+ vertex_records_.push_back(voronoi_vertex_type(
+ point_type(circle.x(), circle.y()), edge12));
+ voronoi_vertex_type &new_vertex = vertex_records_.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 clean() {
+ 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 (detail::almost_equal(v1->vertex().x(), v2->vertex().x(), 256) &&
+ detail::almost_equal(v1->vertex().y(), v2->vertex().y(), 256)) {
+ // 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_;
+ }
+ }
+
+ // 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);
+ }
+ }
+ }
+ }
+
+ private:
+ // 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);
+ }
+ }
+
+ 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_diagram(const voronoi_diagram&);
+ void operator=(const voronoi_diagram&);
+ };
+
+} // polygon
+} // boost
+
+#endif
Modified: sandbox/gtl/libs/polygon/Jamroot
==============================================================================
--- sandbox/gtl/libs/polygon/Jamroot (original)
+++ sandbox/gtl/libs/polygon/Jamroot 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -6,14 +6,42 @@
# Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
# http://www.boost.org/LICENSE_1_0.txt)
+import os ;
+path-constant BOOST_ROOT : [ os.environ BOOST_ROOT ] ;
+path-constant GMP_PATH : "c:/Users/Slevin/SWE/Sweepline/gmp" ;
+#path-constant GMP_PATH : "/usr/local" ;
+
+lib gmp
+ : # sources
+ : # requirements
+ <name>gmp <search>$(GMP_PATH)/lib
+ : #default-build
+ : # usage-requirements
+ ;
+
+lib gmpxx
+ : # sources
+ : # requirements
+ <name>gmpxx <search>$(GMP_PATH)/lib
+ : # default-build
+ : # usage-requirements
+ ;
+
+alias gmp_libs : gmp gmpxx : <link>static ;
+
+
project
: requirements
- <warnings>all
- <toolset>intel:<warnings>on
- <toolset>gcc:<cxxflags>"-pedantic -Wall -Wstrict-aliasing -fstrict-aliasing -Wno-long-long"
- <toolset>msvc:<cxxflags>/W4
+# <warnings>all
+# <toolset>intel:<warnings>on
+# <toolset>gcc:<cxxflags>"-pedantic -Wall -Wstrict-aliasing -fstrict-aliasing -Wno-long-long"
+# <toolset>msvc:<cxxflags>/W4
<include>../..
<include>.
+ <include>$(BOOST_ROOT)
+ <include>$(GMP_PATH)/include
+ <library>gmp_libs
+ :
+ build-dir bin.v2
;
-
Added: sandbox/gtl/libs/polygon/example/Jamfile.v2
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/Jamfile.v2 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,12 @@
+# 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)
+
+import cast ;
+lib opengl : : <name>opengl32 ;
+exe voronoi_visualizer : voronoi_visualizer.cpp
+ [ cast _ moccable-cpp : voronoi_visualizer.cpp ]
+ /qt//QtOpenGL
+ : <target-os>windows:<library>opengl
+ ;
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/failure/failure_001.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/failure/failure_001.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,5 @@
+1
+9 72
+2
+-2 0 -1 -50
+-1 -50 0 -99
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_001.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_001.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,10 @@
+0
+8
+0 0 -3 5
+-3 5 2 10
+2 10 4 6
+4 6 10 12
+10 12 13 6
+13 6 11 1
+11 1 5 1
+5 1 0 0
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_002.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_002.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,16 @@
+0
+14
+0 0 -3 5
+-3 5 2 10
+2 10 4 6
+4 6 10 12
+10 12 13 6
+13 6 11 1
+11 1 5 1
+5 1 0 0
+1 2 0 5
+0 5 5 2
+5 2 1 2
+10 3 8 6
+8 6 10 8
+10 8 10 3
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_003.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_003.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,10 @@
+0
+8
+0 0 0 8
+0 8 4 12
+4 12 9 13
+9 13 13 13
+13 13 13 4
+13 4 10 0
+10 0 5 -1
+5 -1 0 0
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_004.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_004.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,10 @@
+0
+8
+0 0 0 8
+0 8 4 12
+4 12 9 13
+9 13 7 7
+7 7 13 4
+13 4 10 0
+10 0 5 -1
+5 -1 0 0
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_005.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_005.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,8 @@
+0
+6
+0 0 10 0
+10 0 16 -6
+16 -6 22 0
+22 0 22 -12
+22 -12 10 -12
+10 -12 0 0
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_006.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_006.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,9 @@
+0
+7
+0 0 0 10
+0 10 6 10
+6 10 10 7
+10 7 14 10
+14 10 20 10
+20 10 20 0
+20 0 0 0
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_007.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_007.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,14 @@
+0
+12
+0 0 8 3
+8 3 10 13
+10 13 16 6
+16 6 16 15
+16 15 25 10
+25 10 15 1
+15 1 27 -1
+27 -1 14 -4
+14 -4 13 3
+13 3 11 -5
+11 -5 10 0
+10 0 0 0
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_008.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_008.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,12 @@
+0
+10
+0 0 1 8
+1 8 10 7
+10 7 20 10
+20 10 25 9
+25 9 28 5
+28 5 23 -2
+23 -2 24 -7
+24 -7 13 -9
+13 -9 10 -3
+10 -3 0 0
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_009.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_009.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,6 @@
+0
+4
+0 0 0 10
+0 10 30 10
+30 10 30 0
+30 0 0 0
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_010.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/polygon/polygon_010.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,25 @@
+0
+23
+-12 4 -12 -4
+-12 -4 -8 -4
+-8 -4 -8 -1
+-8 -1 -9 0
+-9 0 -8 1
+-8 1 -8 4
+-8 4 -12 4
+-4 4 -4 -4
+-4 -4 0 -4
+0 -4 0 4
+0 4 -4 4
+4 4 4 -4
+4 -4 8 -4
+8 -4 8 4
+8 4 4 4
+-4 -8 -8 -8
+-8 -8 -8 -12
+-8 -12 -4 -12
+-4 -12 -4 -16
+-4 -16 -8 -16
+0 -8 2 -8
+2 -8 4 -8
+2 -8 2 -16
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_001.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_001.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,2 @@
+1
+0 0
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_002.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_002.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,3 @@
+2
+0 0
+1 0
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_003.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_003.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,3 @@
+2
+0 0
+0 1
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_004.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_004.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,3 @@
+2
+0 0
+1 1
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_005.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_005.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,11 @@
+10
+0 0
+0 1
+0 2
+0 3
+0 4
+0 -1
+0 -2
+0 -3
+0 -4
+0 -5
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_006.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_006.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,11 @@
+10
+0 0
+1 0
+2 0
+3 0
+4 0
+5 0
+-1 0
+-2 0
+-3 0
+-4 0
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_007.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_007.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,12 @@
+11
+0 0
+1 1
+2 2
+3 3
+4 4
+5 5
+6 6
+7 7
+8 8
+9 9
+10 10
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_008.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_008.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,11 @@
+10
+-46 -37
+-40 -30
+-34 -23
+-28 -16
+-22 -09
+-16 -02
+-10 05
+-04 12
+02 19
+08 26
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_009.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_009.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,11 @@
+10
+33333 11111
+66666 0
+99999 -11111
+133332 -22222
+166665 -33333
+199998 -44444
+233331 -55555
+266664 -66666
+299997 -77777
+333330 -88888
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_010.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_010.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,4 @@
+3
+0 0
+2005 2005
+10025 10025
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_011.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_011.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,4 @@
+3
+0 0
+0 4
+1 1
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_012.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_012.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,5 @@
+4
+0 0
+0 1
+1 0
+1 1
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_013.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_013.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,14 @@
+13
+0 5
+0 -5
+-4 -3
+4 -3
+4 3
+-4 3
+3 -4
+-3 4
+-3 -4
+3 4
+-5 0
+5 0
+0 0
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_014.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_014.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,13 @@
+12
+0 5
+0 -5
+-4 -3
+4 -3
+4 3
+-4 3
+3 -4
+-3 4
+-3 -4
+3 4
+-5 0
+5 0
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_015.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_015.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,5 @@
+4
+4 3
+4 8
+9 2
+9 9
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_016.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_016.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,101 @@
+100
+100 0
+99 6
+99 12
+98 18
+96 24
+95 30
+92 36
+90 42
+87 48
+84 53
+80 58
+77 63
+72 68
+68 72
+63 77
+58 80
+53 84
+48 87
+42 90
+36 92
+30 95
+24 96
+18 98
+12 99
+6 99
+0 99
+-6 99
+-12 99
+-18 98
+-24 96
+-30 95
+-36 93
+-42 90
+-48 87
+-53 84
+-58 80
+-63 77
+-68 72
+-72 68
+-76 63
+-80 58
+-84 53
+-87 48
+-90 42
+-92 36
+-95 31
+-96 25
+-98 18
+-99 12
+-99 6
+-99 0
+-99 -6
+-99 -12
+-98 -18
+-96 -24
+-95 -30
+-93 -36
+-90 -42
+-87 -48
+-84 -53
+-81 -58
+-77 -63
+-73 -68
+-68 -72
+-63 -76
+-58 -80
+-53 -84
+-48 -87
+-42 -90
+-37 -92
+-31 -95
+-25 -96
+-18 -98
+-12 -99
+-6 -99
+0 -99
+6 -99
+12 -99
+18 -98
+24 -96
+30 -95
+36 -93
+42 -90
+47 -87
+53 -84
+58 -81
+63 -77
+68 -73
+72 -68
+76 -63
+80 -59
+84 -53
+87 -48
+90 -42
+92 -37
+95 -31
+96 -25
+98 -19
+99 -12
+99 -6
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_017.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_017.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,3 @@
+0
+1
+0 0 1 1
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_018.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_018.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,6 @@
+2
+3 1
+1 3
+1
+0 0
+4 4
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_019.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_019.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,5 @@
+2
+3 2
+2 3
+1
+4 0 0 4
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_020.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_020.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,7 @@
+3
+-2 -2
+-2 4
+-2 10
+1
+0 0
+0 8
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_021.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_021.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,4 @@
+1
+-1 1
+1
+1 0 1 2
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_022.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_022.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,5 @@
+0
+3
+0 0 4 0
+4 0 0 4
+0 4 4 4
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_023.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_023.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,6 @@
+0
+4
+0 0 4 0
+4 0 4 4
+4 4 0 4
+0 4 0 0
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_024.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_024.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,4 @@
+0
+2
+0 0 4 0
+2 2 2 4
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_025.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_025.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,5 @@
+1
+5 6
+2
+0 0 4 0
+2 2 2 4
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_026.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_026.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,6 @@
+2
+0 0
+1 6
+2
+-4 5 5 -1
+3 -11 13 -1
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_027.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_027.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,12 @@
+2
+0 0
+1 6
+8
+-6 5 2 -7
+3 -11 13 -1
+-4 5 5 -1
+4 4 11 4
+4 4 8 10
+11 4 8 10
+8 10 5 13
+8 10 11 13
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_028.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_028.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,5 @@
+0
+3
+0 0 4 2
+4 2 4 -2
+4 -2 0 0
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_029.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_029.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,10 @@
+0
+8
+0 0 0 1
+0 0 1 0
+0 0 -1 0
+0 0 0 -1
+0 0 1 1
+0 0 1 -1
+0 0 -1 1
+0 0 -1 -1
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_030.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_030.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,14 @@
+0
+12
+-1 10 1 10
+10 -1 10 1
+-1 -10 1 -10
+-10 -1 -10 1
+-6 8 -2 11
+-8 6 -11 2
+6 8 2 11
+8 6 11 2
+6 -8 2 -11
+8 -6 11 -2
+-6 -8 -2 -11
+-8 -6 -11 -2
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_031.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_031.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,15 @@
+1
+0 0
+12
+-1 10 1 10
+10 -1 10 1
+-1 -10 1 -10
+-10 -1 -10 1
+-6 8 -2 11
+-8 6 -11 2
+6 8 2 11
+8 6 11 2
+6 -8 2 -11
+8 -6 11 -2
+-6 -8 -2 -11
+-8 -6 -11 -2
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_032.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_032.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,6 @@
+3
+0 -4
+2 8
+-16 15
+1
+7 20 7 -20
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_033.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_033.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,7 @@
+4
+-6 6
+-5 6
+-4 6
+-3 6
+1
+0 0 0 7
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_034.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_034.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,6 @@
+0
+4
+0 -4 2 8
+2 8 -16 15
+0 -4 -16 15
+7 20 7 -20
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_035.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_035.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,22 @@
+0
+20
+100 0 95 30
+95 30 80 58
+80 58 58 80
+58 80 30 95
+30 95 0 99
+0 99 -30 95
+-30 95 -58 80
+-58 80 -80 58
+-80 58 -95 30
+-95 30 -99 0
+-99 0 -95 -30
+-95 -30 -80 -58
+-80 -58 -58 -80
+-58 -80 -30 -95
+-30 -95 0 -99
+0 -99 30 -95
+30 -95 58 -80
+58 -80 80 -58
+80 -58 95 -30
+95 -30 100 0
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_036.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_036.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,102 @@
+0
+100
+100 0 99 6
+99 6 99 12
+99 12 98 18
+98 18 96 24
+96 24 95 30
+95 30 92 36
+92 36 90 42
+90 42 87 48
+87 48 84 53
+84 53 80 58
+80 58 77 63
+77 63 72 68
+72 68 68 72
+68 72 63 77
+63 77 58 80
+58 80 53 84
+53 84 48 87
+48 87 42 90
+42 90 36 92
+36 92 30 95
+30 95 24 96
+24 96 18 98
+18 98 12 99
+12 99 6 99
+6 99 0 99
+0 99 -6 99
+-6 99 -12 99
+-12 99 -18 98
+-18 98 -24 96
+-24 96 -30 95
+-30 95 -36 92
+-36 92 -42 90
+-42 90 -48 87
+-48 87 -53 84
+-53 84 -58 80
+-58 80 -63 77
+-63 77 -68 72
+-68 72 -72 68
+-72 68 -77 63
+-77 63 -80 58
+-80 58 -84 53
+-84 53 -87 48
+-87 48 -90 42
+-90 42 -92 36
+-92 36 -95 30
+-95 30 -96 24
+-96 24 -98 18
+-98 18 -99 12
+-99 12 -99 6
+-99 6 -99 0
+-99 0 -99 -6
+-99 -6 -99 -12
+-99 -12 -98 -18
+-98 -18 -96 -24
+-96 -24 -95 -30
+-95 -30 -92 -36
+-92 -36 -90 -42
+-90 -42 -87 -48
+-87 -48 -84 -53
+-84 -53 -80 -58
+-80 -58 -77 -63
+-77 -63 -72 -68
+-72 -68 -68 -72
+-68 -72 -63 -77
+-63 -77 -58 -80
+-58 -80 -53 -84
+-53 -84 -48 -87
+-48 -87 -42 -90
+-42 -90 -36 -92
+-36 -92 -30 -95
+-30 -95 -24 -96
+-24 -96 -18 -98
+-18 -98 -12 -99
+-12 -99 -6 -99
+-6 -99 0 -99
+0 -99 6 -99
+6 -99 12 -99
+12 -99 18 -98
+18 -98 24 -96
+24 -96 30 -95
+30 -95 36 -92
+36 -92 42 -90
+42 -90 48 -87
+48 -87 53 -84
+53 -84 58 -80
+58 -80 63 -77
+63 -77 68 -72
+68 -72 72 -68
+72 -68 77 -63
+77 -63 80 -58
+80 -58 84 -53
+84 -53 87 -48
+87 -48 90 -42
+90 -42 92 -36
+92 -36 95 -30
+95 -30 96 -24
+96 -24 98 -18
+98 -18 99 -12
+99 -12 99 -6
+99 -6 100 0
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_037.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_037.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,102 @@
+80
+99 6
+99 12
+98 18
+96 24
+92 36
+90 42
+87 48
+84 53
+77 63
+72 68
+68 72
+63 77
+53 84
+48 87
+42 90
+36 92
+24 96
+18 98
+12 99
+6 99
+-6 99
+-12 99
+-18 98
+-24 96
+-36 92
+-42 90
+-48 87
+-53 84
+-63 77
+-68 72
+-72 68
+-77 63
+-84 53
+-87 48
+-90 42
+-92 36
+-96 24
+-98 18
+-99 12
+-99 6
+-99 -6
+-99 -12
+-98 -18
+-96 -24
+-92 -36
+-90 -42
+-87 -48
+-84 -53
+-77 -63
+-72 -68
+-68 -72
+-63 -77
+-53 -84
+-48 -87
+-42 -90
+-36 -92
+-24 -96
+-18 -98
+-12 -99
+-6 -99
+6 -99
+12 -99
+18 -98
+24 -96
+36 -92
+42 -90
+48 -87
+53 -84
+63 -77
+68 -72
+72 -68
+77 -63
+84 -53
+87 -48
+90 -42
+92 -36
+96 -24
+98 -18
+99 -12
+99 -6
+20
+100 0 99 6
+95 30 92 36
+80 58 77 63
+58 80 53 84
+30 95 24 96
+0 99 -6 99
+-30 95 -36 92
+-58 80 -63 77
+-80 58 -84 53
+-95 30 -96 24
+-99 0 -99 -6
+-95 -30 -92 -36
+-80 -58 -77 -63
+-58 -80 -53 -84
+-30 -95 -24 -96
+0 -99 6 -99
+30 -95 36 -92
+58 -80 63 -77
+80 -58 84 -53
+95 -30 96 -24
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_038.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_038.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,222 @@
+0
+220
+0 0 0 10
+0 0 10 0
+0 10 0 20
+0 10 10 10
+0 20 0 30
+0 20 10 20
+0 30 0 40
+0 30 10 30
+0 40 0 50
+0 40 10 40
+0 50 0 60
+0 50 10 50
+0 60 0 70
+0 60 10 60
+0 70 0 80
+0 70 10 70
+0 80 0 90
+0 80 10 80
+0 90 0 100
+0 90 10 90
+0 100 10 100
+10 0 10 10
+10 0 20 0
+10 10 10 20
+10 10 20 10
+10 20 10 30
+10 20 20 20
+10 30 10 40
+10 30 20 30
+10 40 10 50
+10 40 20 40
+10 50 10 60
+10 50 20 50
+10 60 10 70
+10 60 20 60
+10 70 10 80
+10 70 20 70
+10 80 10 90
+10 80 20 80
+10 90 10 100
+10 90 20 90
+10 100 20 100
+20 0 20 10
+20 0 30 0
+20 10 20 20
+20 10 30 10
+20 20 20 30
+20 20 30 20
+20 30 20 40
+20 30 30 30
+20 40 20 50
+20 40 30 40
+20 50 20 60
+20 50 30 50
+20 60 20 70
+20 60 30 60
+20 70 20 80
+20 70 30 70
+20 80 20 90
+20 80 30 80
+20 90 20 100
+20 90 30 90
+20 100 30 100
+30 0 30 10
+30 0 40 0
+30 10 30 20
+30 10 40 10
+30 20 30 30
+30 20 40 20
+30 30 30 40
+30 30 40 30
+30 40 30 50
+30 40 40 40
+30 50 30 60
+30 50 40 50
+30 60 30 70
+30 60 40 60
+30 70 30 80
+30 70 40 70
+30 80 30 90
+30 80 40 80
+30 90 30 100
+30 90 40 90
+30 100 40 100
+40 0 40 10
+40 0 50 0
+40 10 40 20
+40 10 50 10
+40 20 40 30
+40 20 50 20
+40 30 40 40
+40 30 50 30
+40 40 40 50
+40 40 50 40
+40 50 40 60
+40 50 50 50
+40 60 40 70
+40 60 50 60
+40 70 40 80
+40 70 50 70
+40 80 40 90
+40 80 50 80
+40 90 40 100
+40 90 50 90
+40 100 50 100
+50 0 50 10
+50 0 60 0
+50 10 50 20
+50 10 60 10
+50 20 50 30
+50 20 60 20
+50 30 50 40
+50 30 60 30
+50 40 50 50
+50 40 60 40
+50 50 50 60
+50 50 60 50
+50 60 50 70
+50 60 60 60
+50 70 50 80
+50 70 60 70
+50 80 50 90
+50 80 60 80
+50 90 50 100
+50 90 60 90
+50 100 60 100
+60 0 60 10
+60 0 70 0
+60 10 60 20
+60 10 70 10
+60 20 60 30
+60 20 70 20
+60 30 60 40
+60 30 70 30
+60 40 60 50
+60 40 70 40
+60 50 60 60
+60 50 70 50
+60 60 60 70
+60 60 70 60
+60 70 60 80
+60 70 70 70
+60 80 60 90
+60 80 70 80
+60 90 60 100
+60 90 70 90
+60 100 70 100
+70 0 70 10
+70 0 80 0
+70 10 70 20
+70 10 80 10
+70 20 70 30
+70 20 80 20
+70 30 70 40
+70 30 80 30
+70 40 70 50
+70 40 80 40
+70 50 70 60
+70 50 80 50
+70 60 70 70
+70 60 80 60
+70 70 70 80
+70 70 80 70
+70 80 70 90
+70 80 80 80
+70 90 70 100
+70 90 80 90
+70 100 80 100
+80 0 80 10
+80 0 90 0
+80 10 80 20
+80 10 90 10
+80 20 80 30
+80 20 90 20
+80 30 80 40
+80 30 90 30
+80 40 80 50
+80 40 90 40
+80 50 80 60
+80 50 90 50
+80 60 80 70
+80 60 90 60
+80 70 80 80
+80 70 90 70
+80 80 80 90
+80 80 90 80
+80 90 80 100
+80 90 90 90
+80 100 90 100
+90 0 90 10
+90 0 100 0
+90 10 90 20
+90 10 100 10
+90 20 90 30
+90 20 100 20
+90 30 90 40
+90 30 100 30
+90 40 90 50
+90 40 100 40
+90 50 90 60
+90 50 100 50
+90 60 90 70
+90 60 100 60
+90 70 90 80
+90 70 100 70
+90 80 90 90
+90 80 100 80
+90 90 90 100
+90 90 100 90
+90 100 100 100
+100 0 100 10
+100 10 100 20
+100 20 100 30
+100 30 100 40
+100 40 100 50
+100 50 100 60
+100 60 100 70
+100 70 100 80
+100 80 100 90
+100 90 100 100
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_039.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_039.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,322 @@
+100
+5 5
+5 15
+5 25
+5 35
+5 45
+5 55
+5 65
+5 75
+5 85
+5 95
+15 5
+15 15
+15 25
+15 35
+15 45
+15 55
+15 65
+15 75
+15 85
+15 95
+25 5
+25 15
+25 25
+25 35
+25 45
+25 55
+25 65
+25 75
+25 85
+25 95
+35 5
+35 15
+35 25
+35 35
+35 45
+35 55
+35 65
+35 75
+35 85
+35 95
+45 5
+45 15
+45 25
+45 35
+45 45
+45 55
+45 65
+45 75
+45 85
+45 95
+55 5
+55 15
+55 25
+55 35
+55 45
+55 55
+55 65
+55 75
+55 85
+55 95
+65 5
+65 15
+65 25
+65 35
+65 45
+65 55
+65 65
+65 75
+65 85
+65 95
+75 5
+75 15
+75 25
+75 35
+75 45
+75 55
+75 65
+75 75
+75 85
+75 95
+85 5
+85 15
+85 25
+85 35
+85 45
+85 55
+85 65
+85 75
+85 85
+85 95
+95 5
+95 15
+95 25
+95 35
+95 45
+95 55
+95 65
+95 75
+95 85
+95 95
+220
+0 0 0 10
+0 0 10 0
+0 10 0 20
+0 10 10 10
+0 20 0 30
+0 20 10 20
+0 30 0 40
+0 30 10 30
+0 40 0 50
+0 40 10 40
+0 50 0 60
+0 50 10 50
+0 60 0 70
+0 60 10 60
+0 70 0 80
+0 70 10 70
+0 80 0 90
+0 80 10 80
+0 90 0 100
+0 90 10 90
+0 100 10 100
+10 0 10 10
+10 0 20 0
+10 10 10 20
+10 10 20 10
+10 20 10 30
+10 20 20 20
+10 30 10 40
+10 30 20 30
+10 40 10 50
+10 40 20 40
+10 50 10 60
+10 50 20 50
+10 60 10 70
+10 60 20 60
+10 70 10 80
+10 70 20 70
+10 80 10 90
+10 80 20 80
+10 90 10 100
+10 90 20 90
+10 100 20 100
+20 0 20 10
+20 0 30 0
+20 10 20 20
+20 10 30 10
+20 20 20 30
+20 20 30 20
+20 30 20 40
+20 30 30 30
+20 40 20 50
+20 40 30 40
+20 50 20 60
+20 50 30 50
+20 60 20 70
+20 60 30 60
+20 70 20 80
+20 70 30 70
+20 80 20 90
+20 80 30 80
+20 90 20 100
+20 90 30 90
+20 100 30 100
+30 0 30 10
+30 0 40 0
+30 10 30 20
+30 10 40 10
+30 20 30 30
+30 20 40 20
+30 30 30 40
+30 30 40 30
+30 40 30 50
+30 40 40 40
+30 50 30 60
+30 50 40 50
+30 60 30 70
+30 60 40 60
+30 70 30 80
+30 70 40 70
+30 80 30 90
+30 80 40 80
+30 90 30 100
+30 90 40 90
+30 100 40 100
+40 0 40 10
+40 0 50 0
+40 10 40 20
+40 10 50 10
+40 20 40 30
+40 20 50 20
+40 30 40 40
+40 30 50 30
+40 40 40 50
+40 40 50 40
+40 50 40 60
+40 50 50 50
+40 60 40 70
+40 60 50 60
+40 70 40 80
+40 70 50 70
+40 80 40 90
+40 80 50 80
+40 90 40 100
+40 90 50 90
+40 100 50 100
+50 0 50 10
+50 0 60 0
+50 10 50 20
+50 10 60 10
+50 20 50 30
+50 20 60 20
+50 30 50 40
+50 30 60 30
+50 40 50 50
+50 40 60 40
+50 50 50 60
+50 50 60 50
+50 60 50 70
+50 60 60 60
+50 70 50 80
+50 70 60 70
+50 80 50 90
+50 80 60 80
+50 90 50 100
+50 90 60 90
+50 100 60 100
+60 0 60 10
+60 0 70 0
+60 10 60 20
+60 10 70 10
+60 20 60 30
+60 20 70 20
+60 30 60 40
+60 30 70 30
+60 40 60 50
+60 40 70 40
+60 50 60 60
+60 50 70 50
+60 60 60 70
+60 60 70 60
+60 70 60 80
+60 70 70 70
+60 80 60 90
+60 80 70 80
+60 90 60 100
+60 90 70 90
+60 100 70 100
+70 0 70 10
+70 0 80 0
+70 10 70 20
+70 10 80 10
+70 20 70 30
+70 20 80 20
+70 30 70 40
+70 30 80 30
+70 40 70 50
+70 40 80 40
+70 50 70 60
+70 50 80 50
+70 60 70 70
+70 60 80 60
+70 70 70 80
+70 70 80 70
+70 80 70 90
+70 80 80 80
+70 90 70 100
+70 90 80 90
+70 100 80 100
+80 0 80 10
+80 0 90 0
+80 10 80 20
+80 10 90 10
+80 20 80 30
+80 20 90 20
+80 30 80 40
+80 30 90 30
+80 40 80 50
+80 40 90 40
+80 50 80 60
+80 50 90 50
+80 60 80 70
+80 60 90 60
+80 70 80 80
+80 70 90 70
+80 80 80 90
+80 80 90 80
+80 90 80 100
+80 90 90 90
+80 100 90 100
+90 0 90 10
+90 0 100 0
+90 10 90 20
+90 10 100 10
+90 20 90 30
+90 20 100 20
+90 30 90 40
+90 30 100 30
+90 40 90 50
+90 40 100 40
+90 50 90 60
+90 50 100 50
+90 60 90 70
+90 60 100 60
+90 70 90 80
+90 70 100 70
+90 80 90 90
+90 80 100 80
+90 90 90 100
+90 90 100 90
+90 100 100 100
+100 0 100 10
+100 10 100 20
+100 20 100 30
+100 30 100 40
+100 40 100 50
+100 50 100 60
+100 60 100 70
+100 70 100 80
+100 80 100 90
+100 90 100 100
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_040.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_040.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,11 @@
+10
+858993458 1717986916
+-429496729 1288490187
+-2147483645 -1288490187
+-2147483645 -858993458
+-1717986916 858993458
+-2147483645 -429496729
+429496729 -2147483645
+858993458 -429496729
+-429496729 1717986916
+1717986916 -858993458
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_041.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_041.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,8 @@
+0
+6
+0 0 0 10
+-5 0 -1 0
+-6 2 -1 2
+-4 5 -2 5
+-8 8 -1 8
+-7 -2 -7 7
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_042.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_042.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,5 @@
+0
+3
+-6 -1 -5 3
+-1 0 4 -1
+3 0 4 1
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_043.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_043.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,5 @@
+0
+3
+-5 -2 -4 2
+-5 3 -2 2
+-5 5 -2 2
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_044.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_044.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,5 @@
+0
+3
+-9 -8 -4 -3
+-8 -3 -4 -3
+-2 7 -1 3
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_045.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_045.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,5 @@
+0
+3
+14 76 38 29
+37 47 61 50
+39 37 41 35
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_046.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_046.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,5 @@
+2
+2 -5
+3 -3
+1
+0 0 2 -7
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_047.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_047.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,5 @@
+1
+-35 -49
+2
+-48 -29 -46 -78
+-46 -46 -45 -42
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/primary/primary_048.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/primary/primary_048.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,11 @@
+0
+9
+-50 -29 -49 -73
+-48 -29 -46 -78
+-46 -46 -45 -42
+-35 -49 -34 -49
+-30 -2 -29 3
+-43 16 -40 6
+-36 38 -34 49
+-35 39 -31 37
+-28 34 -27 -9
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_001.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_001.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,11 @@
+10
+9 1
+4 3
+9 6
+9 8
+3 9
+6 8
+0 5
+9 5
+3 0
+2 1
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_002.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_002.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,11 @@
+10
+9 9
+2 6
+3 1
+6 4
+9 1
+9 7
+6 2
+2 4
+3 7
+6 7
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_003.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_003.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,11 @@
+10
+4 1
+5 4
+5 5
+2 6
+3 4
+0 7
+2 5
+8 9
+0 4
+2 7
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_004.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_004.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,101 @@
+100
+29 76
+99 94
+74 20
+53 26
+95 55
+94 21
+50 70
+19 93
+31 30
+73 61
+87 23
+60 66
+51 29
+82 51
+74 40
+31 77
+1 82
+43 0
+58 67
+63 32
+19 90
+68 31
+49 63
+76 83
+72 20
+70 11
+80 23
+4 90
+32 56
+63 75
+51 71
+62 10
+80 57
+71 47
+2 8
+67 85
+64 72
+85 6
+53 91
+92 25
+95 79
+24 6
+1 10
+10 85
+11 30
+22 14
+48 55
+82 8
+14 54
+84 60
+33 91
+85 60
+65 81
+60 23
+10 44
+29 32
+21 11
+90 15
+73 71
+41 62
+9 36
+44 80
+27 39
+41 38
+25 23
+86 15
+4 76
+52 6
+39 97
+42 25
+93 93
+97 24
+13 16
+58 62
+48 78
+43 74
+99 85
+13 42
+8 82
+13 9
+51 50
+85 83
+30 11
+58 42
+44 32
+88 74
+37 21
+65 28
+79 94
+50 94
+38 83
+82 13
+30 88
+16 92
+73 66
+24 0
+40 82
+57 25
+55 88
+13 33
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_005.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_005.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,101 @@
+100
+-901943112 1116691472
+2104533928 1889785568
+1030792128 -1288490160
+128849016 -1030792128
+1932735240 214748360
+1889785568 -1245540488
+0 858993440
+-1331439832 1846835896
+-816043768 -858993440
+987842456 472446392
+1589137864 -1159641144
+429496720 687194752
+42949672 -901943112
+1374389504 42949672
+1030792128 -429496720
+-816043768 1159641144
+-2104533928 1374389504
+-300647704 -2147483600
+343597376 730144424
+558345736 -773094096
+-1331439832 1717986880
+773094096 -816043768
+-42949672 558345736
+1116691472 1417339176
+944892784 -1288490160
+858993440 -1675037208
+1288490160 -1159641144
+-1975684912 1717986880
+-773094096 257698032
+558345736 1073741800
+42949672 901943112
+515396064 -1717986880
+1288490160 300647704
+901943112 -128849016
+-2061584256 -1803886224
+730144424 1503238520
+601295408 944892784
+1503238520 -1889785568
+128849016 1760936552
+1803886224 -1073741800
+1932735240 1245540488
+-1116691472 -1889785568
+-2104533928 -1717986880
+-1717986880 1503238520
+-1675037208 -858993440
+-1202590816 -1546188192
+-85899344 214748360
+1374389504 -1803886224
+-1546188192 171798688
+1460288848 429496720
+-730144424 1760936552
+1503238520 429496720
+644245080 1331439832
+429496720 -1159641144
+-1717986880 -257698032
+-901943112 -773094096
+-1245540488 -1675037208
+1717986880 -1503238520
+987842456 901943112
+-386547048 515396064
+-1760936552 -601295408
+-257698032 1288490160
+-987842456 -472446392
+-386547048 -515396064
+-1073741800 -1159641144
+1546188192 -1503238520
+-1975684912 1116691472
+85899344 -1889785568
+-472446392 2018634584
+-343597376 -1073741800
+1846835896 1846835896
+2018634584 -1116691472
+-1589137864 -1460288848
+343597376 515396064
+-85899344 1202590816
+-300647704 1030792128
+2104533928 1503238520
+-1589137864 -343597376
+-1803886224 1374389504
+-1589137864 -1760936552
+42949672 0
+1503238520 1417339176
+-858993440 -1675037208
+343597376 -343597376
+-257698032 -773094096
+1632087536 1030792128
+-558345736 -1245540488
+644245080 -944892784
+1245540488 1889785568
+0 1889785568
+-515396064 1417339176
+1374389504 -1589137864
+-858993440 1632087536
+-1460288848 1803886224
+987842456 687194752
+-1116691472 -2147483600
+-429496720 1374389504
+300647704 -1073741800
+214748360 1632087536
+-1589137864 -730144424
\ No newline at end of file
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_006.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_006.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,6 @@
+0
+4
+-27 -32 5 -21
+-18 41 27 9
+-17 -25 12 9
+27 0 40 -20
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_007.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_007.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,6 @@
+0
+4
+-48 10 -17 19
+-35 -30 -33 -2
+13 -45 18 46
+31 -14 47 18
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_008.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_008.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,6 @@
+0
+4
+-34 7 -21 13
+-9 37 39 10
+7 21 26 -18
+8 45 47 22
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_009.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_009.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,7 @@
+0
+5
+-21 -9 -9 -34
+-20 1 11 43
+-3 -1 21 18
+34 -18 40 15
+47 43 48 -7
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_010.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_010.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,5 @@
+0
+3
+-39 -43 -6 -22
+13 -21 33 38
+24 -42 42 43
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_011.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_011.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,7 @@
+0
+5
+-22 -18 -13 -26
+-16 -36 23 -28
+-12 -11 6 19
+-4 -3 44 -30
+15 -5 47 17
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_012.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_012.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,6 @@
+0
+4
+-27 -24 -20 -45
+-15 29 28 20
+-12 -36 19 -21
+1 -21 3 -1
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_013.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_013.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,6 @@
+0
+4
+-47 11 -25 -20
+-17 2 3 -46
+-13 29 32 -35
+25 -3 42 37
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_014.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_014.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,7 @@
+0
+5
+-36 -8 -18 24
+-17 44 -2 18
+-16 -7 -9 -28
+-14 5 -2 -20
+31 42 33 36
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_015.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_015.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,5 @@
+0
+3
+-24 17 -19 -12
+-21 -40 3 -17
+28 1 38 -38
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_016.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_016.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,8 @@
+0
+6
+-44 -29 -36 -40
+-40 0 -5 -43
+-7 37 -3 -23
+-4 18 14 30
+6 39 38 32
+12 -20 27 -15
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_017.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_017.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,5 @@
+0
+3
+-46 -50 -36 -14
+-5 46 -4 -40
+21 45 49 -45
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_018.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_018.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,7 @@
+0
+5
+-45 44 -36 -29
+-36 41 -32 -14
+-16 44 23 9
+13 -4 19 -29
+18 -3 48 39
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_019.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_019.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,7 @@
+0
+5
+-29 22 -6 18
+-6 -20 18 19
+-5 28 44 22
+9 -48 22 -15
+11 32 11 39
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_020.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_020.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,7 @@
+0
+5
+-14 -43 37 -49
+-12 41 -10 -43
+-7 -20 18 -38
+7 34 47 -38
+23 26 42 -3
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_021.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_021.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,7 @@
+0
+5
+-47 32 0 28
+-20 -22 9 -13
+-13 37 21 30
+-7 47 2 47
+26 47 32 1
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_022.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_022.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,5 @@
+0
+3
+-19 17 -10 9
+-1 -50 25 40
+26 15 48 -3
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_023.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_023.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,8 @@
+0
+6
+-41 -46 -20 -48
+-41 -22 10 -46
+-27 36 28 19
+-10 -10 28 -15
+13 -28 48 -19
+41 -20 47 1
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_024.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_024.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,7 @@
+0
+5
+-29 26 24 -46
+-24 -48 -15 -19
+-15 -20 -2 -23
+-9 -30 0 -42
+3 21 24 43
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_025.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_025.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,4 @@
+0
+2
+-8 -34 29 22
+37 10 48 7
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_026.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_026.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,6 @@
+0
+4
+-35 -28 19 26
+-21 16 -19 -4
+9 -34 27 3
+25 48 47 -31
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_027.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_027.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,8 @@
+0
+6
+-45 46 -24 24
+-37 30 -36 -7
+-18 -47 -4 -14
+-3 -34 40 -33
+5 17 44 -26
+35 -16 45 9
Added: sandbox/gtl/libs/polygon/example/input_data/random/random_028.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/input_data/random/random_028.txt 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,7 @@
+0
+5
+-30 -27 -18 16
+-14 47 0 -46
+-13 42 13 20
+-10 26 7 -42
+-2 22 22 -42
Added: sandbox/gtl/libs/polygon/example/output_data/failure/failure_001.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/polygon/polygon_001.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/polygon/polygon_002.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/polygon/polygon_003.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/polygon/polygon_004.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/polygon/polygon_005.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/polygon/polygon_006.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/polygon/polygon_007.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/polygon/polygon_008.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/polygon/polygon_009.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/polygon/polygon_010.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_001.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_002.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_003.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_004.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_005.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_006.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_007.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_008.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_009.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_010.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_011.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_012.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_013.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_014.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_015.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_016.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_017.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_018.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_019.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_020.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_021.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_022.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_023.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_024.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_025.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_026.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_027.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_028.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_029.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_030.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_031.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_032.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_033.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_034.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_035.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_036.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_037.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_038.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_039.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_040.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_041.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_042.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_043.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_044.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_045.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_046.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_047.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/primary/primary_048.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_001.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_002.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_003.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_004.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_005.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_006.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_007.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_008.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_009.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_010.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_011.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_012.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_013.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_014.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_015.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_016.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_017.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_018.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_019.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_020.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_021.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_022.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_023.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_024.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_025.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_026.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_027.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/output_data/random/random_028.png
==============================================================================
Binary file. No diff available.
Added: sandbox/gtl/libs/polygon/example/voronoi_visualizer.cpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/example/voronoi_visualizer.cpp 2011-10-05 16:04:11 EDT (Wed, 05 Oct 2011)
@@ -0,0 +1,284 @@
+// Boost sweepline library voronoi_visualizer.cpp 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.
+
+#include <iostream>
+
+#include <QtOpenGL/QGLWidget>
+#include <QtGui/QtGui>
+
+#include "boost/polygon/voronoi.hpp"
+using namespace boost::polygon;
+
+class GLWidget : public QGLWidget {
+ Q_OBJECT
+public:
+ GLWidget(QMainWindow *parent = NULL) :
+ QGLWidget(QGLFormat(QGL::SampleBuffers), parent),
+ primary_edges_only_(false) {
+ startTimer(40);
+ }
+
+ QSize sizeHint() const {
+ return QSize(600, 600);
+ }
+
+ void build(QString file_path) {
+ ipoint_set_type point_sites;
+ isegment_set_type segment_sites;
+
+ // Open file.
+ QFile data(file_path);
+ if (!data.open(QFile::ReadOnly))
+ QMessageBox::warning(this, tr("Voronoi Visualizer"),
+ tr("Disable to open file ") + file_path);
+
+ // Read points from the file.
+ QTextStream in_stream(&data);
+ int num_point_sites = 0;
+ int num_edge_sites = 0;
+ int x1, y1, x2, y2;
+ in_stream >> num_point_sites;
+ for (int i = 0; i < num_point_sites; i++) {
+ in_stream >> 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.insert(isegment_type(
+ ipoint_type(x1, y1), ipoint_type(x2, y2)));
+ }
+ in_stream.flush();
+
+ // Build voronoi diagram.
+ construct_voronoi<int>(point_sites, segment_sites, vd_);
+ brect_ = voronoi_helper<coordinate_type>::get_view_rectangle(
+ vd_.bounding_rectangle());
+
+ // Update view.
+ update_view_port();
+ }
+
+ void show_primary_edges_only() {
+ primary_edges_only_ ^= true;
+ }
+
+protected:
+ void initializeGL() {
+ glHint(GL_POINT_SMOOTH_HINT, GL_NICEST);
+ glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
+ glEnable(GL_BLEND);
+ glEnable(GL_POINT_SMOOTH);
+ }
+
+ void paintGL() {
+ qglClearColor(QColor::fromRgb(0, 0, 0));
+ glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
+
+ // Draw voronoi sites.
+ {
+ const voronoi_cells_type &cells = vd_.cell_records();
+ voronoi_cell_const_iterator_type it;
+ glColor3f(0.0f, 0.0f, 1.0f);
+ glPointSize(9);
+ glBegin(GL_POINTS);
+ for (it = cells.begin(); it != cells.end(); it++) {
+ if (!it->contains_segment())
+ glVertex2f(it->point0().x(), it->point0().y());
+ }
+ glEnd();
+ glPointSize(6);
+ glLineWidth(2.7f);
+ glBegin(GL_LINES);
+ for (it = cells.begin(); it != cells.end(); it++) {
+ if (it->contains_segment()) {
+ glVertex2f(it->point0().x(), it->point0().y());
+ glVertex2f(it->point1().x(), it->point1().y());
+ }
+ }
+ glEnd();
+ glLineWidth(1.0);
+ }
+
+ // Draw voronoi vertices.
+ {
+ const voronoi_vertices_type &vertices = vd_.vertex_records();
+ voronoi_vertex_const_iterator_type it;
+ glColor3f(0.0f, 1.0f, 0.0f);
+ glBegin(GL_POINTS);
+ for (it = vertices.begin(); it != vertices.end(); it++)
+ glVertex2f(it->vertex().x(), it->vertex().y());
+ glEnd();
+ }
+
+ // Draw voronoi edges.
+ {
+ const voronoi_edges_type &edges = vd_.edge_records();
+ voronoi_edge_const_iterator_type it;
+ glColor3f(0.0f, 1.0f, 0.0f);
+ glBegin(GL_LINES);
+ for (it = edges.begin(); it != edges.end(); it++) {
+ if (!it->is_primary() && primary_edges_only_)
+ continue;
+ 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());
+ }
+ }
+ glEnd();
+ }
+ }
+
+ void resizeGL(int width, int height) {
+ int side = qMin(width, height);
+ glViewport((width - side) / 2, (height - side) / 2, side, side);
+ }
+
+ void timerEvent(QTimerEvent *) {
+ update();
+ }
+
+private:
+ void update_view_port() {
+ glMatrixMode(GL_PROJECTION);
+ glLoadIdentity();
+ glOrtho(brect_.x_min(), brect_.x_max(), brect_.y_min(), brect_.y_max(), -1.0, 1.0);
+ glMatrixMode(GL_MODELVIEW);
+ }
+
+ typedef double coordinate_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_diagram<coordinate_type>::voronoi_cells_type voronoi_cells_type;
+ typedef voronoi_diagram<coordinate_type>::voronoi_vertices_type voronoi_vertices_type;
+ typedef voronoi_diagram<coordinate_type>::voronoi_edges_type voronoi_edges_type;
+ typedef voronoi_diagram<coordinate_type>::voronoi_cell_const_iterator_type
+ voronoi_cell_const_iterator_type;
+ typedef voronoi_diagram<coordinate_type>::voronoi_vertex_const_iterator_type
+ voronoi_vertex_const_iterator_type;
+ typedef voronoi_diagram<coordinate_type>::voronoi_edge_const_iterator_type
+ voronoi_edge_const_iterator_type;
+ BRect<coordinate_type> brect_;
+ voronoi_diagram<coordinate_type> vd_;
+ bool primary_edges_only_;
+};
+
+class MainWindow : public QWidget {
+ Q_OBJECT
+public:
+ MainWindow() {
+ glWidget_ = new GLWidget();
+ file_dir_ = QDir(QDir::currentPath(), tr("*.txt"));
+ file_name_ = tr("");
+
+ QHBoxLayout *centralLayout = new QHBoxLayout;
+ centralLayout->addWidget(glWidget_);
+ centralLayout->addLayout(create_file_layout());
+ setLayout(centralLayout);
+
+ update_file_list();
+ setWindowTitle(tr("Voronoi Visualizer"));
+ layout()->setSizeConstraint( QLayout::SetFixedSize );
+ }
+
+private slots:
+ void primary_edges_only() {
+ glWidget_->show_primary_edges_only();
+ }
+
+ void browse() {
+ QString new_path = QFileDialog::getExistingDirectory(0, tr("Choose Directory"),
+ file_dir_.absolutePath());
+ if (new_path.isEmpty())
+ return;
+ file_dir_.setPath(new_path);
+ update_file_list();
+ }
+
+ void build() {
+ file_name_ = file_list_->currentItem()->text();
+ QString file_path = file_dir_.filePath(file_name_);
+ message_label_->setText("Building...");
+ glWidget_->build(file_path);
+ message_label_->setText("Double click the item to build voronoi diagram:");
+ setWindowTitle(tr("Voronoi Visualizer - ") + file_path);
+ }
+
+ void print_scr() {
+ if (!file_name_.isEmpty()) {
+ QImage screenshot = glWidget_->grabFrameBuffer(true);
+ QString output_file = file_dir_.absolutePath() + tr("/") +
+ file_name_.left(file_name_.indexOf('.')) + tr(".png");
+ screenshot.save(output_file, 0, -1);
+ }
+ }
+
+private:
+ QGridLayout *create_file_layout() {
+ QGridLayout *file_layout = new QGridLayout;
+
+ message_label_ = new QLabel("Double click item to build voronoi diagram:");
+
+ file_list_ = new QListWidget();
+ file_list_->connect(file_list_, SIGNAL(itemDoubleClicked(QListWidgetItem*)),
+ this, SLOT(build()));
+
+ QCheckBox *primary_checkbox = new QCheckBox("Show primary edges only.");
+ connect(primary_checkbox, SIGNAL(clicked()), this, SLOT(primary_edges_only()));
+
+ QPushButton *browse_button = new QPushButton(tr("Browse Input Directory"));
+ connect(browse_button, SIGNAL(clicked()), this, SLOT(browse()));
+ browse_button->setMinimumHeight(50);
+
+ QPushButton *print_scr_button = new QPushButton(tr("Make Screenshot"));
+ connect(print_scr_button, SIGNAL(clicked()), this, SLOT(print_scr()));
+ print_scr_button->setMinimumHeight(50);
+
+ file_layout->addWidget(message_label_, 0, 0);
+ file_layout->addWidget(file_list_, 1, 0);
+ file_layout->addWidget(primary_checkbox, 2, 0);
+ file_layout->addWidget(browse_button, 3, 0);
+ file_layout->addWidget(print_scr_button, 4, 0);
+
+ return file_layout;
+ }
+
+ void update_file_list() {
+ QFileInfoList list = file_dir_.entryInfoList();
+ file_list_->clear();
+ if (file_dir_.count() == 0)
+ return;
+
+ QFileInfoList::const_iterator it;
+ for (it = list.begin(); it != list.end(); it++)
+ file_list_->addItem(it->fileName());
+ file_list_->setCurrentRow(0);
+ }
+
+ QDir file_dir_;
+ QString file_name_;
+ GLWidget *glWidget_;
+ QListWidget *file_list_;
+ QLabel *message_label_;
+};
+
+int main(int argc, char *argv[])
+{
+ QApplication app(argc, argv);
+ MainWindow window;
+ window.show();
+ return app.exec();
+}
+
+#include "voronoi_visualizer.moc"
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