| /* |
| Copyright 2008 Intel Corporation |
| |
| Use, modification and distribution are subject to 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). |
| */ |
| |
| #ifndef BOOST_POLYGON_ISOTROPY_HPP |
| #define BOOST_POLYGON_ISOTROPY_HPP |
| |
| //external |
| #include <cmath> |
| #include <cstddef> |
| #include <cstdlib> |
| #include <vector> |
| #include <deque> |
| #include <map> |
| #include <set> |
| #include <list> |
| //#include <iostream> |
| #include <algorithm> |
| #include <limits> |
| #include <iterator> |
| #include <string> |
| |
| #ifndef BOOST_POLYGON_NO_DEPS |
| |
| #include <boost/config.hpp> |
| #ifdef BOOST_MSVC |
| #define BOOST_POLYGON_MSVC |
| #endif |
| #ifdef BOOST_INTEL |
| #define BOOST_POLYGON_ICC |
| #endif |
| #ifdef BOOST_HAS_LONG_LONG |
| #define BOOST_POLYGON_USE_LONG_LONG |
| typedef boost::long_long_type polygon_long_long_type; |
| typedef boost::ulong_long_type polygon_ulong_long_type; |
| //typedef long long polygon_long_long_type; |
| //typedef unsigned long long polygon_ulong_long_type; |
| #endif |
| #include <boost/mpl/size_t.hpp> |
| #include <boost/mpl/protect.hpp> |
| #include <boost/utility/enable_if.hpp> |
| #include <boost/mpl/bool.hpp> |
| #include <boost/mpl/and.hpp> |
| #include <boost/mpl/or.hpp> |
| #else |
| |
| #ifdef _WIN32 |
| #define BOOST_POLYGON_MSVC |
| #endif |
| #ifdef __ICC |
| #define BOOST_POLYGON_ICC |
| #endif |
| #define BOOST_POLYGON_USE_LONG_LONG |
| typedef long long polygon_long_long_type; |
| typedef unsigned long long polygon_ulong_long_type; |
| |
| namespace boost { |
| template <bool B, class T = void> |
| struct enable_if_c { |
| typedef T type; |
| }; |
| |
| template <class T> |
| struct enable_if_c<false, T> {}; |
| |
| template <class Cond, class T = void> |
| struct enable_if : public enable_if_c<Cond::value, T> {}; |
| |
| template <bool B, class T> |
| struct lazy_enable_if_c { |
| typedef typename T::type type; |
| }; |
| |
| template <class T> |
| struct lazy_enable_if_c<false, T> {}; |
| |
| template <class Cond, class T> |
| struct lazy_enable_if : public lazy_enable_if_c<Cond::value, T> {}; |
| |
| |
| template <bool B, class T = void> |
| struct disable_if_c { |
| typedef T type; |
| }; |
| |
| template <class T> |
| struct disable_if_c<true, T> {}; |
| |
| template <class Cond, class T = void> |
| struct disable_if : public disable_if_c<Cond::value, T> {}; |
| |
| template <bool B, class T> |
| struct lazy_disable_if_c { |
| typedef typename T::type type; |
| }; |
| |
| template <class T> |
| struct lazy_disable_if_c<true, T> {}; |
| |
| template <class Cond, class T> |
| struct lazy_disable_if : public lazy_disable_if_c<Cond::value, T> {}; |
| } |
| |
| #endif |
| |
| namespace boost { namespace polygon{ |
| |
| enum GEOMETRY_CONCEPT_ID { |
| COORDINATE_CONCEPT, |
| INTERVAL_CONCEPT, |
| POINT_CONCEPT, |
| POINT_3D_CONCEPT, |
| RECTANGLE_CONCEPT, |
| POLYGON_90_CONCEPT, |
| POLYGON_90_WITH_HOLES_CONCEPT, |
| POLYGON_45_CONCEPT, |
| POLYGON_45_WITH_HOLES_CONCEPT, |
| POLYGON_CONCEPT, |
| POLYGON_WITH_HOLES_CONCEPT, |
| POLYGON_90_SET_CONCEPT, |
| POLYGON_45_SET_CONCEPT, |
| POLYGON_SET_CONCEPT |
| }; |
| |
| struct undefined_concept {}; |
| |
| template <typename T> |
| struct geometry_concept { typedef undefined_concept type; }; |
| |
| template <typename GCT, typename T> |
| struct view_of {}; |
| |
| template <typename T1, typename T2> |
| view_of<T1, T2> view_as(const T2& obj) { return view_of<T1, T2>(obj); } |
| |
| template <typename T> |
| struct coordinate_traits {}; |
| |
| template <typename T> |
| struct high_precision_type { |
| typedef long double type; |
| }; |
| |
| template <typename T> |
| T convert_high_precision_type(const typename high_precision_type<T>::type& v) { |
| return T(v); |
| } |
| |
| template <> |
| struct coordinate_traits<int> { |
| typedef int coordinate_type; |
| typedef long double area_type; |
| #ifdef BOOST_POLYGON_USE_LONG_LONG |
| typedef polygon_long_long_type manhattan_area_type; |
| typedef polygon_ulong_long_type unsigned_area_type; |
| typedef polygon_long_long_type coordinate_difference; |
| #else |
| typedef long manhattan_area_type; |
| typedef unsigned long unsigned_area_type; |
| typedef long coordinate_difference; |
| #endif |
| typedef long double coordinate_distance; |
| }; |
| |
| #ifdef BOOST_POLYGON_USE_LONG_LONG |
| template <> |
| struct coordinate_traits<polygon_long_long_type> { |
| typedef polygon_long_long_type coordinate_type; |
| typedef long double area_type; |
| typedef polygon_long_long_type manhattan_area_type; |
| typedef polygon_ulong_long_type unsigned_area_type; |
| typedef polygon_long_long_type coordinate_difference; |
| typedef long double coordinate_distance; |
| }; |
| #endif |
| |
| template <> |
| struct coordinate_traits<float> { |
| typedef float coordinate_type; |
| typedef float area_type; |
| typedef float manhattan_area_type; |
| typedef float unsigned_area_type; |
| typedef float coordinate_difference; |
| typedef float coordinate_distance; |
| }; |
| |
| template <> |
| struct coordinate_traits<double> { |
| typedef double coordinate_type; |
| typedef double area_type; |
| typedef double manhattan_area_type; |
| typedef double unsigned_area_type; |
| typedef double coordinate_difference; |
| typedef double coordinate_distance; |
| }; |
| |
| template <> |
| struct coordinate_traits<long double> { |
| typedef long double coordinate_type; |
| typedef long double area_type; |
| typedef long double manhattan_area_type; |
| typedef long double unsigned_area_type; |
| typedef long double coordinate_difference; |
| typedef long double coordinate_distance; |
| }; |
| |
| template <typename T> |
| struct scaling_policy { |
| template <typename T2> |
| static inline T round(T2 t2) { |
| return (T)std::floor(t2+0.5); |
| } |
| |
| static inline T round(T t2) { |
| return t2; |
| } |
| }; |
| |
| struct coordinate_concept {}; |
| |
| template <> |
| struct geometry_concept<int> { typedef coordinate_concept type; }; |
| #ifdef BOOST_POLYGON_USE_LONG_LONG |
| template <> |
| struct geometry_concept<polygon_long_long_type> { typedef coordinate_concept type; }; |
| #endif |
| template <> |
| struct geometry_concept<float> { typedef coordinate_concept type; }; |
| template <> |
| struct geometry_concept<double> { typedef coordinate_concept type; }; |
| template <> |
| struct geometry_concept<long double> { typedef coordinate_concept type; }; |
| |
| #ifndef BOOST_POLYGON_NO_DEPS |
| struct gtl_no : mpl::bool_<false> {}; |
| struct gtl_yes : mpl::bool_<true> {}; |
| template <typename T, typename T2> |
| struct gtl_and : mpl::and_<T, T2> {}; |
| template <typename T, typename T2, typename T3> |
| struct gtl_and_3 : mpl::and_<T, T2, T3> {}; |
| template <typename T, typename T2, typename T3, typename T4> |
| struct gtl_and_4 : mpl::and_<T, T2, T3, T4> {}; |
| // template <typename T, typename T2> |
| // struct gtl_or : mpl::or_<T, T2> {}; |
| // template <typename T, typename T2, typename T3> |
| // struct gtl_or_3 : mpl::or_<T, T2, T3> {}; |
| // template <typename T, typename T2, typename T3, typename T4> |
| // struct gtl_or_4 : mpl::or_<T, T2, T3, T4> {}; |
| #else |
| struct gtl_no { static const bool value = false; }; |
| struct gtl_yes { typedef gtl_yes type; |
| static const bool value = true; }; |
| |
| template <bool T, bool T2> |
| struct gtl_and_c { typedef gtl_no type; }; |
| template <> |
| struct gtl_and_c<true, true> { typedef gtl_yes type; }; |
| |
| template <typename T, typename T2> |
| struct gtl_and : gtl_and_c<T::value, T2::value> {}; |
| template <typename T, typename T2, typename T3> |
| struct gtl_and_3 { typedef typename gtl_and< |
| T, typename gtl_and<T2, T3>::type>::type type; }; |
| |
| template <typename T, typename T2, typename T3, typename T4> |
| struct gtl_and_4 { typedef typename gtl_and_3< |
| T, T2, typename gtl_and<T3, T4>::type>::type type; }; |
| #endif |
| template <typename T, typename T2> |
| struct gtl_or { typedef gtl_yes type; }; |
| template <typename T> |
| struct gtl_or<T, T> { typedef T type; }; |
| |
| template <typename T, typename T2, typename T3> |
| struct gtl_or_3 { typedef typename gtl_or< |
| T, typename gtl_or<T2, T3>::type>::type type; }; |
| |
| template <typename T, typename T2, typename T3, typename T4> |
| struct gtl_or_4 { typedef typename gtl_or< |
| T, typename gtl_or_3<T2, T3, T4>::type>::type type; }; |
| |
| template <typename T> |
| struct gtl_not { typedef gtl_no type; }; |
| template <> |
| struct gtl_not<gtl_no> { typedef gtl_yes type; }; |
| |
| template <typename T> |
| struct gtl_if { |
| #ifdef BOOST_POLYGON_MSVC |
| typedef gtl_no type; |
| #endif |
| }; |
| template <> |
| struct gtl_if<gtl_yes> { typedef gtl_yes type; }; |
| |
| template <typename T, typename T2> |
| struct gtl_same_type { typedef gtl_no type; }; |
| template <typename T> |
| struct gtl_same_type<T, T> { typedef gtl_yes type; }; |
| template <typename T, typename T2> |
| struct gtl_different_type { typedef typename gtl_not<typename gtl_same_type<T, T2>::type>::type type; }; |
| |
| struct manhattan_domain {}; |
| struct forty_five_domain {}; |
| struct general_domain {}; |
| |
| template <typename T> |
| struct geometry_domain { typedef general_domain type; }; |
| |
| template <typename domain_type, typename coordinate_type> |
| struct area_type_by_domain { typedef typename coordinate_traits<coordinate_type>::area_type type; }; |
| template <typename coordinate_type> |
| struct area_type_by_domain<manhattan_domain, coordinate_type> { |
| typedef typename coordinate_traits<coordinate_type>::manhattan_area_type type; }; |
| |
| struct y_c_edist : gtl_yes {}; |
| |
| template <typename coordinate_type_1, typename coordinate_type_2> |
| typename enable_if< |
| typename gtl_and_3<y_c_edist, typename gtl_same_type<typename geometry_concept<coordinate_type_1>::type, coordinate_concept>::type, |
| typename gtl_same_type<typename geometry_concept<coordinate_type_1>::type, coordinate_concept>::type>::type, |
| typename coordinate_traits<coordinate_type_1>::coordinate_difference>::type |
| euclidean_distance(const coordinate_type_1& lvalue, const coordinate_type_2& rvalue) { |
| typedef typename coordinate_traits<coordinate_type_1>::coordinate_difference Unit; |
| return (lvalue < rvalue) ? (Unit)rvalue - (Unit)lvalue : (Unit)lvalue - (Unit)rvalue; |
| } |
| |
| |
| |
| // predicated_swap swaps a and b if pred is true |
| |
| // predicated_swap is guarenteed to behave the same as |
| // if(pred){ |
| // T tmp = a; |
| // a = b; |
| // b = tmp; |
| // } |
| // but will not generate a branch instruction. |
| // predicated_swap always creates a temp copy of a, but does not |
| // create more than one temp copy of an input. |
| // predicated_swap can be used to optimize away branch instructions in C++ |
| template <class T> |
| inline bool predicated_swap(const bool& pred, |
| T& a, |
| T& b) { |
| const T tmp = a; |
| const T* input[2] = {&b, &tmp}; |
| a = *input[!pred]; |
| b = *input[pred]; |
| return pred; |
| } |
| |
| enum direction_1d_enum { LOW = 0, HIGH = 1, |
| LEFT = 0, RIGHT = 1, |
| CLOCKWISE = 0, COUNTERCLOCKWISE = 1, |
| REVERSE = 0, FORWARD = 1, |
| NEGATIVE = 0, POSITIVE = 1 }; |
| enum orientation_2d_enum { HORIZONTAL = 0, VERTICAL = 1 }; |
| enum direction_2d_enum { WEST = 0, EAST = 1, SOUTH = 2, NORTH = 3 }; |
| enum orientation_3d_enum { PROXIMAL = 2 }; |
| enum direction_3d_enum { DOWN = 4, UP = 5 }; |
| enum winding_direction { |
| clockwise_winding = 0, |
| counterclockwise_winding = 1, |
| unknown_winding = 2 |
| }; |
| |
| class direction_2d; |
| class direction_3d; |
| class orientation_2d; |
| |
| class direction_1d { |
| private: |
| unsigned int val_; |
| explicit direction_1d(int d); |
| public: |
| inline direction_1d() : val_(LOW) {} |
| inline direction_1d(const direction_1d& that) : val_(that.val_) {} |
| inline direction_1d(const direction_1d_enum val) : val_(val) {} |
| explicit inline direction_1d(const direction_2d& that); |
| explicit inline direction_1d(const direction_3d& that); |
| inline direction_1d& operator = (const direction_1d& d) { |
| val_ = d.val_; return * this; } |
| inline bool operator==(direction_1d d) const { return (val_ == d.val_); } |
| inline bool operator!=(direction_1d d) const { return !((*this) == d); } |
| inline unsigned int to_int(void) const { return val_; } |
| inline direction_1d& backward() { val_ ^= 1; return *this; } |
| inline int get_sign() const { return val_ * 2 - 1; } |
| }; |
| |
| class direction_2d; |
| |
| class orientation_2d { |
| private: |
| unsigned int val_; |
| explicit inline orientation_2d(int o); |
| public: |
| inline orientation_2d() : val_(HORIZONTAL) {} |
| inline orientation_2d(const orientation_2d& ori) : val_(ori.val_) {} |
| inline orientation_2d(const orientation_2d_enum val) : val_(val) {} |
| explicit inline orientation_2d(const direction_2d& that); |
| inline orientation_2d& operator=(const orientation_2d& ori) { |
| val_ = ori.val_; return * this; } |
| inline bool operator==(orientation_2d that) const { return (val_ == that.val_); } |
| inline bool operator!=(orientation_2d that) const { return (val_ != that.val_); } |
| inline unsigned int to_int() const { return (val_); } |
| inline void turn_90() { val_ = val_^ 1; } |
| inline orientation_2d get_perpendicular() const { |
| orientation_2d retval = *this; |
| retval.turn_90(); |
| return retval; |
| } |
| inline direction_2d get_direction(direction_1d dir) const; |
| }; |
| |
| class direction_2d { |
| private: |
| int val_; |
| |
| public: |
| |
| inline direction_2d() : val_(WEST) {} |
| |
| inline direction_2d(const direction_2d& that) : val_(that.val_) {} |
| |
| inline direction_2d(const direction_2d_enum val) : val_(val) {} |
| |
| inline direction_2d& operator=(const direction_2d& d) { |
| val_ = d.val_; |
| return * this; |
| } |
| |
| inline ~direction_2d() { } |
| |
| inline bool operator==(direction_2d d) const { return (val_ == d.val_); } |
| inline bool operator!=(direction_2d d) const { return !((*this) == d); } |
| inline bool operator< (direction_2d d) const { return (val_ < d.val_); } |
| inline bool operator<=(direction_2d d) const { return (val_ <= d.val_); } |
| inline bool operator> (direction_2d d) const { return (val_ > d.val_); } |
| inline bool operator>=(direction_2d d) const { return (val_ >= d.val_); } |
| |
| // Casting to int |
| inline unsigned int to_int(void) const { return val_; } |
| |
| inline direction_2d backward() const { |
| // flip the LSB, toggles 0 - 1 and 2 - 3 |
| return direction_2d(direction_2d_enum(val_ ^ 1)); |
| } |
| |
| // Returns a direction 90 degree left (LOW) or right(HIGH) to this one |
| inline direction_2d turn(direction_1d t) const { |
| return direction_2d(direction_2d_enum(val_ ^ 3 ^ (val_ >> 1) ^ t.to_int())); |
| } |
| |
| // Returns a direction 90 degree left to this one |
| inline direction_2d left() const {return turn(HIGH);} |
| |
| // Returns a direction 90 degree right to this one |
| inline direction_2d right() const {return turn(LOW);} |
| |
| // N, E are positive, S, W are negative |
| inline bool is_positive() const {return (val_ & 1);} |
| inline bool is_negative() const {return !is_positive();} |
| inline int get_sign() const {return ((is_positive()) << 1) -1;} |
| |
| }; |
| |
| direction_1d::direction_1d(const direction_2d& that) : val_(that.to_int() & 1) {} |
| |
| orientation_2d::orientation_2d(const direction_2d& that) : val_(that.to_int() >> 1) {} |
| |
| direction_2d orientation_2d::get_direction(direction_1d dir) const { |
| return direction_2d(direction_2d_enum((val_ << 1) + dir.to_int())); |
| } |
| |
| class orientation_3d { |
| private: |
| unsigned int val_; |
| explicit inline orientation_3d(int o); |
| public: |
| inline orientation_3d() : val_((int)HORIZONTAL) {} |
| inline orientation_3d(const orientation_3d& ori) : val_(ori.val_) {} |
| inline orientation_3d(orientation_2d ori) : val_(ori.to_int()) {} |
| inline orientation_3d(const orientation_3d_enum val) : val_(val) {} |
| explicit inline orientation_3d(const direction_2d& that); |
| explicit inline orientation_3d(const direction_3d& that); |
| inline ~orientation_3d() { } |
| inline orientation_3d& operator=(const orientation_3d& ori) { |
| val_ = ori.val_; return * this; } |
| inline bool operator==(orientation_3d that) const { return (val_ == that.val_); } |
| inline bool operator!=(orientation_3d that) const { return (val_ != that.val_); } |
| inline unsigned int to_int() const { return (val_); } |
| inline direction_3d get_direction(direction_1d dir) const; |
| }; |
| |
| class direction_3d { |
| private: |
| int val_; |
| |
| public: |
| |
| inline direction_3d() : val_(WEST) {} |
| |
| inline direction_3d(direction_2d that) : val_(that.to_int()) {} |
| inline direction_3d(const direction_3d& that) : val_(that.val_) {} |
| |
| inline direction_3d(const direction_2d_enum val) : val_(val) {} |
| inline direction_3d(const direction_3d_enum val) : val_(val) {} |
| |
| inline direction_3d& operator=(direction_3d d) { |
| val_ = d.val_; |
| return * this; |
| } |
| |
| inline ~direction_3d() { } |
| |
| inline bool operator==(direction_3d d) const { return (val_ == d.val_); } |
| inline bool operator!=(direction_3d d) const { return !((*this) == d); } |
| inline bool operator< (direction_3d d) const { return (val_ < d.val_); } |
| inline bool operator<=(direction_3d d) const { return (val_ <= d.val_); } |
| inline bool operator> (direction_3d d) const { return (val_ > d.val_); } |
| inline bool operator>=(direction_3d d) const { return (val_ >= d.val_); } |
| |
| // Casting to int |
| inline unsigned int to_int(void) const { return val_; } |
| |
| inline direction_3d backward() const { |
| // flip the LSB, toggles 0 - 1 and 2 - 3 and 4 - 5 |
| return direction_2d(direction_2d_enum(val_ ^ 1)); |
| } |
| |
| // N, E, U are positive, S, W, D are negative |
| inline bool is_positive() const {return (val_ & 1);} |
| inline bool is_negative() const {return !is_positive();} |
| inline int get_sign() const {return ((is_positive()) << 1) -1;} |
| |
| }; |
| |
| direction_1d::direction_1d(const direction_3d& that) : val_(that.to_int() & 1) {} |
| orientation_3d::orientation_3d(const direction_3d& that) : val_(that.to_int() >> 1) {} |
| orientation_3d::orientation_3d(const direction_2d& that) : val_(that.to_int() >> 1) {} |
| |
| direction_3d orientation_3d::get_direction(direction_1d dir) const { |
| return direction_3d(direction_3d_enum((val_ << 1) + dir.to_int())); |
| } |
| |
| } |
| } |
| #endif |
| |