Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-30 09:55:21 

0001 /*
0002   Copyright 2008 Intel Corporation
0003 
0004   Use, modification and distribution are subject to the Boost Software License,
0005   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0006   http://www.boost.org/LICENSE_1_0.txt).
0007 */
0008 
0009 #ifndef BOOST_POLYGON_ISOTROPY_HPP
0010 #define BOOST_POLYGON_ISOTROPY_HPP
0011 
0012 //external
0013 #include <cmath>
0014 #include <cstddef>
0015 #include <cstdlib>
0016 #include <vector>
0017 #include <deque>
0018 #include <map>
0019 #include <set>
0020 #include <list>
0021 //#include <iostream>
0022 #include <algorithm>
0023 #include <limits>
0024 #include <iterator>
0025 #include <string>
0026 
0027 #ifndef BOOST_POLYGON_NO_DEPS
0028 
0029 #include <boost/config.hpp>
0030 #ifdef BOOST_MSVC
0031 #define BOOST_POLYGON_MSVC
0032 #endif
0033 #ifdef BOOST_INTEL
0034 #define BOOST_POLYGON_ICC
0035 #endif
0036 #ifdef BOOST_HAS_LONG_LONG
0037 #define BOOST_POLYGON_USE_LONG_LONG
0038 typedef boost::long_long_type polygon_long_long_type;
0039 typedef boost::ulong_long_type polygon_ulong_long_type;
0040 //typedef long long polygon_long_long_type;
0041 //typedef unsigned long long polygon_ulong_long_type;
0042 #endif
0043 #else
0044 
0045 #ifdef _WIN32
0046 #define BOOST_POLYGON_MSVC
0047 #endif
0048 #ifdef __ICC
0049 #define BOOST_POLYGON_ICC
0050 #endif
0051 #define BOOST_POLYGON_USE_LONG_LONG
0052 typedef long long polygon_long_long_type;
0053 typedef unsigned long long polygon_ulong_long_type;
0054 #endif
0055 
0056 namespace boost { namespace polygon{
0057 
0058   enum GEOMETRY_CONCEPT_ID {
0059     COORDINATE_CONCEPT,
0060     INTERVAL_CONCEPT,
0061     POINT_CONCEPT,
0062     POINT_3D_CONCEPT,
0063     RECTANGLE_CONCEPT,
0064     POLYGON_90_CONCEPT,
0065     POLYGON_90_WITH_HOLES_CONCEPT,
0066     POLYGON_45_CONCEPT,
0067     POLYGON_45_WITH_HOLES_CONCEPT,
0068     POLYGON_CONCEPT,
0069     POLYGON_WITH_HOLES_CONCEPT,
0070     POLYGON_90_SET_CONCEPT,
0071     POLYGON_45_SET_CONCEPT,
0072     POLYGON_SET_CONCEPT
0073   };
0074 
0075   struct undefined_concept {};
0076 
0077   template <typename T>
0078   struct geometry_concept { typedef undefined_concept type; };
0079 
0080   template <typename GCT, typename T>
0081   struct view_of {};
0082 
0083   template <typename T1, typename T2>
0084   view_of<T1, T2> view_as(const T2& obj) { return view_of<T1, T2>(obj); }
0085 
0086   template <typename T, bool /*enable*/ = true>
0087   struct coordinate_traits {};
0088 
0089   //used to override long double with an infinite precision datatype
0090   template <typename T>
0091   struct high_precision_type {
0092     typedef long double type;
0093   };
0094 
0095   template <typename T>
0096   T convert_high_precision_type(const typename high_precision_type<T>::type& v) {
0097     return T(v);
0098   }
0099 
0100   //used to override std::sort with an alternative (parallel) algorithm
0101   template <typename iter_type>
0102   void polygon_sort(iter_type _b_, iter_type _e_);
0103 
0104   template <typename iter_type, typename pred_type>
0105   void polygon_sort(iter_type _b_, iter_type _e_, const pred_type& _pred_);
0106 
0107 
0108   template <>
0109   struct coordinate_traits<int> {
0110     typedef int coordinate_type;
0111     typedef long double area_type;
0112 #ifdef BOOST_POLYGON_USE_LONG_LONG
0113     typedef polygon_long_long_type manhattan_area_type;
0114     typedef polygon_ulong_long_type unsigned_area_type;
0115     typedef polygon_long_long_type coordinate_difference;
0116 #else
0117     typedef long manhattan_area_type;
0118     typedef unsigned long unsigned_area_type;
0119     typedef long coordinate_difference;
0120 #endif
0121     typedef long double coordinate_distance;
0122   };
0123 
0124   template<>
0125   struct coordinate_traits<long, sizeof(long) == sizeof(int)> {
0126     typedef coordinate_traits<int> cT_;
0127     typedef cT_::coordinate_type coordinate_type;
0128     typedef cT_::area_type area_type;
0129     typedef cT_::manhattan_area_type manhattan_area_type;
0130     typedef cT_::unsigned_area_type unsigned_area_type;
0131     typedef cT_::coordinate_difference coordinate_difference;
0132     typedef cT_::coordinate_distance coordinate_distance;
0133   };
0134 
0135 #ifdef BOOST_POLYGON_USE_LONG_LONG
0136   template <>
0137   struct coordinate_traits<polygon_long_long_type> {
0138     typedef polygon_long_long_type coordinate_type;
0139     typedef long double area_type;
0140     typedef polygon_long_long_type manhattan_area_type;
0141     typedef polygon_ulong_long_type unsigned_area_type;
0142     typedef polygon_long_long_type coordinate_difference;
0143     typedef long double coordinate_distance;
0144   };
0145 
0146   template<>
0147   struct coordinate_traits<long, sizeof(long) == sizeof(polygon_long_long_type)> {
0148     typedef coordinate_traits<polygon_long_long_type> cT_;
0149     typedef cT_::coordinate_type coordinate_type;
0150     typedef cT_::area_type area_type;
0151     typedef cT_::manhattan_area_type manhattan_area_type;
0152     typedef cT_::unsigned_area_type unsigned_area_type;
0153     typedef cT_::coordinate_difference coordinate_difference;
0154     typedef cT_::coordinate_distance coordinate_distance;
0155   };
0156 #endif
0157 
0158   template <>
0159   struct coordinate_traits<float> {
0160     typedef float coordinate_type;
0161     typedef float area_type;
0162     typedef float manhattan_area_type;
0163     typedef float unsigned_area_type;
0164     typedef float coordinate_difference;
0165     typedef float coordinate_distance;
0166   };
0167 
0168   template <>
0169   struct coordinate_traits<double> {
0170     typedef double coordinate_type;
0171     typedef double area_type;
0172     typedef double manhattan_area_type;
0173     typedef double unsigned_area_type;
0174     typedef double coordinate_difference;
0175     typedef double coordinate_distance;
0176   };
0177 
0178   template <>
0179   struct coordinate_traits<long double> {
0180     typedef long double coordinate_type;
0181     typedef long double area_type;
0182     typedef long double manhattan_area_type;
0183     typedef long double unsigned_area_type;
0184     typedef long double coordinate_difference;
0185     typedef long double coordinate_distance;
0186   };
0187 
0188   template <typename T>
0189   struct scaling_policy {
0190     template <typename T2>
0191     static inline T round(T2 t2) {
0192       return (T)std::floor(t2+0.5);
0193     }
0194 
0195     static inline T round(T t2) {
0196       return t2;
0197     }
0198   };
0199 
0200   struct coordinate_concept {};
0201 
0202   template <>
0203   struct geometry_concept<int> { typedef coordinate_concept type; };
0204 #ifdef BOOST_POLYGON_USE_LONG_LONG
0205   template <>
0206   struct geometry_concept<polygon_long_long_type> { typedef coordinate_concept type; };
0207 #endif
0208   template <>
0209   struct geometry_concept<float> { typedef coordinate_concept type; };
0210   template <>
0211   struct geometry_concept<double> { typedef coordinate_concept type; };
0212   template <>
0213   struct geometry_concept<long double> { typedef coordinate_concept type; };
0214 
0215   struct gtl_no { static const bool value = false; };
0216   struct gtl_yes { typedef gtl_yes type;
0217     static const bool value = true; };
0218 
0219   template <bool T, bool T2>
0220   struct gtl_and_c { typedef gtl_no type; };
0221   template <>
0222   struct gtl_and_c<true, true> { typedef gtl_yes type; };
0223 
0224   template <typename T, typename T2>
0225   struct gtl_and : gtl_and_c<T::value, T2::value> {};
0226   template <typename T, typename T2, typename T3>
0227   struct gtl_and_3 { typedef typename gtl_and<
0228                        T, typename gtl_and<T2, T3>::type>::type type; };
0229 
0230   template <typename T, typename T2, typename T3, typename T4>
0231   struct gtl_and_4 { typedef typename gtl_and_3<
0232                        T, T2, typename gtl_and<T3, T4>::type>::type type; };
0233   template <typename T, typename T2>
0234   struct gtl_or { typedef gtl_yes type; };
0235   template <typename T>
0236   struct gtl_or<T, T> { typedef T type; };
0237 
0238   template <typename T, typename T2, typename T3>
0239   struct gtl_or_3 { typedef typename gtl_or<
0240                       T, typename gtl_or<T2, T3>::type>::type type; };
0241 
0242   template <typename T, typename T2, typename T3, typename T4>
0243   struct gtl_or_4 { typedef typename gtl_or<
0244                       T, typename gtl_or_3<T2, T3, T4>::type>::type type; };
0245 
0246   template <typename T>
0247   struct gtl_not { typedef gtl_no type; };
0248   template <>
0249   struct gtl_not<gtl_no> { typedef gtl_yes type; };
0250 
0251   template <typename T>
0252   struct gtl_if {
0253 #ifdef BOOST_POLYGON_MSVC
0254     typedef gtl_no type;
0255 #endif
0256   };
0257   template <>
0258   struct gtl_if<gtl_yes> { typedef gtl_yes type; };
0259 
0260   template <typename T, typename T2>
0261   struct gtl_same_type { typedef gtl_no type; };
0262   template <typename T>
0263   struct gtl_same_type<T, T> { typedef gtl_yes type; };
0264   template <typename T, typename T2>
0265   struct gtl_different_type { typedef typename gtl_not<typename gtl_same_type<T, T2>::type>::type type; };
0266 
0267   struct manhattan_domain {};
0268   struct forty_five_domain {};
0269   struct general_domain {};
0270 
0271   template <typename T>
0272   struct geometry_domain { typedef general_domain type; };
0273 
0274   template <typename domain_type, typename coordinate_type>
0275   struct area_type_by_domain { typedef typename coordinate_traits<coordinate_type>::area_type type; };
0276   template <typename coordinate_type>
0277   struct area_type_by_domain<manhattan_domain, coordinate_type> {
0278     typedef typename coordinate_traits<coordinate_type>::manhattan_area_type type; };
0279 
0280   template<bool E, class R = void>
0281   struct enable_if_ {
0282       typedef R type;
0283   };
0284 
0285   template<class R>
0286   struct enable_if_<false, R> { };
0287 
0288   template<class E, class R = void>
0289   struct enable_if
0290       : enable_if_<E::value, R> { };
0291 
0292   struct y_c_edist : gtl_yes {};
0293 
0294   template <typename coordinate_type_1, typename coordinate_type_2>
0295     typename enable_if<
0296     typename gtl_and_3<y_c_edist, typename gtl_same_type<typename geometry_concept<coordinate_type_1>::type, coordinate_concept>::type,
0297                        typename gtl_same_type<typename geometry_concept<coordinate_type_1>::type, coordinate_concept>::type>::type,
0298     typename coordinate_traits<coordinate_type_1>::coordinate_difference>::type
0299   euclidean_distance(const coordinate_type_1& lvalue, const coordinate_type_2& rvalue) {
0300     typedef typename coordinate_traits<coordinate_type_1>::coordinate_difference Unit;
0301     return (lvalue < rvalue) ? (Unit)rvalue - (Unit)lvalue : (Unit)lvalue - (Unit)rvalue;
0302   }
0303 
0304 
0305 
0306   // predicated_swap swaps a and b if pred is true
0307 
0308   // predicated_swap is guarenteed to behave the same as
0309   // if(pred){
0310   //   T tmp = a;
0311   //   a = b;
0312   //   b = tmp;
0313   // }
0314   // but will not generate a branch instruction.
0315   // predicated_swap always creates a temp copy of a, but does not
0316   // create more than one temp copy of an input.
0317   // predicated_swap can be used to optimize away branch instructions in C++
0318   template <class T>
0319   inline bool predicated_swap(const bool& pred,
0320                               T& a,
0321                               T& b) {
0322     const T tmp = a;
0323     const T* input[2] = {&b, &tmp};
0324     a = *input[!pred];
0325     b = *input[pred];
0326     return pred;
0327   }
0328 
0329   enum direction_1d_enum { LOW = 0, HIGH = 1,
0330                            LEFT = 0, RIGHT = 1,
0331                            CLOCKWISE = 0, COUNTERCLOCKWISE = 1,
0332                            REVERSE = 0, FORWARD = 1,
0333                            NEGATIVE = 0, POSITIVE = 1 };
0334   enum orientation_2d_enum { HORIZONTAL = 0, VERTICAL = 1 };
0335   enum direction_2d_enum { WEST = 0, EAST = 1, SOUTH = 2, NORTH = 3 };
0336   enum orientation_3d_enum { PROXIMAL = 2 };
0337   enum direction_3d_enum { DOWN = 4, UP = 5 };
0338   enum winding_direction {
0339     clockwise_winding = 0,
0340     counterclockwise_winding = 1,
0341     unknown_winding = 2
0342   };
0343 
0344   class direction_2d;
0345   class direction_3d;
0346   class orientation_2d;
0347 
0348   class direction_1d {
0349   private:
0350     unsigned int val_;
0351     explicit direction_1d(int d);
0352   public:
0353     inline direction_1d() : val_(LOW) {}
0354     inline direction_1d(const direction_1d& that) : val_(that.val_) {}
0355     inline direction_1d(const direction_1d_enum val) : val_(val) {}
0356     explicit inline direction_1d(const direction_2d& that);
0357     explicit inline direction_1d(const direction_3d& that);
0358     inline direction_1d& operator = (const direction_1d& d) {
0359       val_ = d.val_; return * this; }
0360     inline bool operator==(direction_1d d) const { return (val_ == d.val_); }
0361     inline bool operator!=(direction_1d d) const { return !((*this) == d); }
0362     inline unsigned int to_int(void) const { return val_; }
0363     inline direction_1d& backward() { val_ ^= 1; return *this; }
0364     inline int get_sign() const { return val_ * 2 - 1; }
0365   };
0366 
0367   class direction_2d;
0368 
0369   class orientation_2d {
0370   private:
0371     unsigned int val_;
0372     explicit inline orientation_2d(int o);
0373   public:
0374     inline orientation_2d() : val_(HORIZONTAL) {}
0375     inline orientation_2d(const orientation_2d& ori) : val_(ori.val_) {}
0376     inline orientation_2d(const orientation_2d_enum val) : val_(val) {}
0377     explicit inline orientation_2d(const direction_2d& that);
0378     inline orientation_2d& operator=(const orientation_2d& ori) {
0379       val_ = ori.val_; return * this; }
0380     inline bool operator==(orientation_2d that) const { return (val_ == that.val_); }
0381     inline bool operator!=(orientation_2d that) const { return (val_ != that.val_); }
0382     inline unsigned int to_int() const { return (val_); }
0383     inline void turn_90() { val_ = val_^ 1; }
0384     inline orientation_2d get_perpendicular() const {
0385       orientation_2d retval = *this;
0386       retval.turn_90();
0387       return retval;
0388     }
0389     inline direction_2d get_direction(direction_1d dir) const;
0390   };
0391 
0392   class direction_2d {
0393   private:
0394     int val_;
0395 
0396   public:
0397 
0398     inline direction_2d() : val_(WEST) {}
0399 
0400     inline direction_2d(const direction_2d& that) : val_(that.val_) {}
0401 
0402     inline direction_2d(const direction_2d_enum val) : val_(val) {}
0403 
0404     inline direction_2d& operator=(const direction_2d& d) {
0405       val_ = d.val_;
0406       return * this;
0407     }
0408 
0409     inline ~direction_2d() { }
0410 
0411     inline bool operator==(direction_2d d) const { return (val_ == d.val_); }
0412     inline bool operator!=(direction_2d d) const { return !((*this) == d); }
0413     inline bool operator< (direction_2d d) const { return (val_ < d.val_); }
0414     inline bool operator<=(direction_2d d) const { return (val_ <= d.val_); }
0415     inline bool operator> (direction_2d d) const { return (val_ > d.val_); }
0416     inline bool operator>=(direction_2d d) const { return (val_ >= d.val_); }
0417 
0418     // Casting to int
0419     inline unsigned int to_int(void) const { return val_; }
0420 
0421     inline direction_2d backward() const {
0422       // flip the LSB, toggles 0 - 1   and 2 - 3
0423       return direction_2d(direction_2d_enum(val_ ^ 1));
0424     }
0425 
0426     // Returns a direction 90 degree left (LOW) or right(HIGH) to this one
0427     inline direction_2d turn(direction_1d t) const {
0428       return direction_2d(direction_2d_enum(val_ ^ 3 ^ (val_ >> 1) ^ t.to_int()));
0429     }
0430 
0431     // Returns a direction 90 degree left to this one
0432     inline direction_2d left() const {return turn(HIGH);}
0433 
0434     // Returns a direction 90 degree right to this one
0435     inline direction_2d right() const {return turn(LOW);}
0436 
0437     // N, E are positive, S, W are negative
0438     inline bool is_positive() const {return (val_ & 1);}
0439     inline bool is_negative() const {return !is_positive();}
0440     inline int get_sign() const {return ((is_positive()) << 1) -1;}
0441 
0442   };
0443 
0444   direction_1d::direction_1d(const direction_2d& that) : val_(that.to_int() & 1) {}
0445 
0446   orientation_2d::orientation_2d(const direction_2d& that) : val_(that.to_int() >> 1) {}
0447 
0448   direction_2d orientation_2d::get_direction(direction_1d dir) const {
0449     return direction_2d(direction_2d_enum((val_ << 1) + dir.to_int()));
0450   }
0451 
0452   class orientation_3d {
0453   private:
0454     unsigned int val_;
0455     explicit inline orientation_3d(int o);
0456   public:
0457     inline orientation_3d() : val_((int)HORIZONTAL) {}
0458     inline orientation_3d(const orientation_3d& ori) : val_(ori.val_) {}
0459     inline orientation_3d(orientation_2d ori) : val_(ori.to_int()) {}
0460     inline orientation_3d(const orientation_3d_enum val) : val_(val) {}
0461     explicit inline orientation_3d(const direction_2d& that);
0462     explicit inline orientation_3d(const direction_3d& that);
0463     inline ~orientation_3d() {  }
0464     inline orientation_3d& operator=(const orientation_3d& ori) {
0465       val_ = ori.val_; return * this; }
0466     inline bool operator==(orientation_3d that) const { return (val_ == that.val_); }
0467     inline bool operator!=(orientation_3d that) const { return (val_ != that.val_); }
0468     inline unsigned int to_int() const { return (val_); }
0469     inline direction_3d get_direction(direction_1d dir) const;
0470   };
0471 
0472   class direction_3d {
0473   private:
0474     int val_;
0475 
0476   public:
0477 
0478     inline direction_3d() : val_(WEST) {}
0479 
0480     inline direction_3d(direction_2d that) : val_(that.to_int()) {}
0481     inline direction_3d(const direction_3d& that) : val_(that.val_) {}
0482 
0483     inline direction_3d(const direction_2d_enum val) : val_(val) {}
0484     inline direction_3d(const direction_3d_enum val) : val_(val) {}
0485 
0486     inline direction_3d& operator=(direction_3d d) {
0487       val_ = d.val_;
0488       return * this;
0489     }
0490 
0491     inline ~direction_3d() { }
0492 
0493     inline bool operator==(direction_3d d) const { return (val_ == d.val_); }
0494     inline bool operator!=(direction_3d d) const { return !((*this) == d); }
0495     inline bool operator< (direction_3d d) const { return (val_ < d.val_); }
0496     inline bool operator<=(direction_3d d) const { return (val_ <= d.val_); }
0497     inline bool operator> (direction_3d d) const { return (val_ > d.val_); }
0498     inline bool operator>=(direction_3d d) const { return (val_ >= d.val_); }
0499 
0500     // Casting to int
0501     inline unsigned int to_int(void) const { return val_; }
0502 
0503     inline direction_3d backward() const {
0504       // flip the LSB, toggles 0 - 1   and 2 - 3 and 4 - 5
0505       return direction_2d(direction_2d_enum(val_ ^ 1));
0506     }
0507 
0508     // N, E, U are positive, S, W, D are negative
0509     inline bool is_positive() const {return (val_ & 1);}
0510     inline bool is_negative() const {return !is_positive();}
0511     inline int get_sign() const {return ((is_positive()) << 1) -1;}
0512 
0513   };
0514 
0515   direction_1d::direction_1d(const direction_3d& that) : val_(that.to_int() & 1) {}
0516   orientation_3d::orientation_3d(const direction_3d& that) : val_(that.to_int() >> 1) {}
0517   orientation_3d::orientation_3d(const direction_2d& that) : val_(that.to_int() >> 1) {}
0518 
0519   direction_3d orientation_3d::get_direction(direction_1d dir) const {
0520     return direction_3d(direction_3d_enum((val_ << 1) + dir.to_int()));
0521   }
0522 
0523 }
0524 }
0525 #endif
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!