boost/polygon/isotropy.hpp

   1 /*
   2   Copyright 2008 Intel Corporation
   3
   4   Use, modification and distribution are subject to the Boost Software License,
   5   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6   http://www.boost.org/LICENSE_1_0.txt).
   7 */
   8
   9 #ifndef BOOST_POLYGON_ISOTROPY_HPP
  10 #define BOOST_POLYGON_ISOTROPY_HPP
  11
  12 //external
  13 #include <cmath>
  14 #include <cstddef>
  15 #include <cstdlib>
  16 #include <vector>
  17 #include <deque>
  18 #include <map>
  19 #include <set>
  20 #include <list>
  21 //#include <iostream>
  22 #include <algorithm>
  23 #include <limits>
  24 #include <iterator>
  25 #include <string>
  26
  27 #ifndef BOOST_POLYGON_NO_DEPS
  28
  29 #include <boost/config.hpp>
  30 #ifdef BOOST_MSVC
  31 #define BOOST_POLYGON_MSVC
  32 #endif
  33 #ifdef BOOST_INTEL
  34 #define BOOST_POLYGON_ICC
  35 #endif
  36 #ifdef BOOST_HAS_LONG_LONG
  37 #define BOOST_POLYGON_USE_LONG_LONG
  38 typedef boost::long_long_type polygon_long_long_type;
  39 typedef boost::ulong_long_type polygon_ulong_long_type;
  40 //typedef long long polygon_long_long_type;
  41 //typedef unsigned long long polygon_ulong_long_type;
  42 #endif
  43 #include <boost/mpl/size_t.hpp>
  44 #include <boost/mpl/protect.hpp>
  45 #include <boost/utility/enable_if.hpp>
  46 #include <boost/mpl/bool.hpp>
  47 #include <boost/mpl/and.hpp>
  48 #include <boost/mpl/or.hpp>
  49 #else
  50
  51 #ifdef _WIN32
  52 #define BOOST_POLYGON_MSVC
  53 #endif
  54 #ifdef __ICC
  55 #define BOOST_POLYGON_ICC
  56 #endif
  57 #define BOOST_POLYGON_USE_LONG_LONG
  58 typedef long long polygon_long_long_type;
  59 typedef unsigned long long polygon_ulong_long_type;
  60
  61   namespace boost {
  62     template <bool B, class T   = void>
  63     struct enable_if_c {
  64       typedef T type;
  65     };
  66
  67     template <class T>
  68     struct enable_if_c<false, T> {};
  69
  70     template <class Cond, class T = void>
  71     struct enable_if : public enable_if_c<Cond::value, T> {};
  72
  73     template <bool B, class T>
  74     struct lazy_enable_if_c {
  75       typedef typename T::type type;
  76     };
  77
  78     template <class T>
  79     struct lazy_enable_if_c<false, T> {};
  80
  81     template <class Cond, class T>
  82     struct lazy_enable_if : public lazy_enable_if_c<Cond::value, T> {};
  83
  84
  85     template <bool B, class T = void>
  86     struct disable_if_c {
  87       typedef T type;
  88     };
  89
  90     template <class T>
  91     struct disable_if_c<true, T> {};
  92
  93     template <class Cond, class T = void>
  94     struct disable_if : public disable_if_c<Cond::value, T> {};
  95
  96     template <bool B, class T>
  97     struct lazy_disable_if_c {
  98       typedef typename T::type type;
  99     };
 100
 101     template <class T>
 102     struct lazy_disable_if_c<true, T> {};
 103
 104     template <class Cond, class T>
 105     struct lazy_disable_if : public lazy_disable_if_c<Cond::value, T> {};
 106   }
 107
 108 #endif
 109
 110 namespace boost { namespace polygon{
 111
 112   enum GEOMETRY_CONCEPT_ID {
 113     COORDINATE_CONCEPT,
 114     INTERVAL_CONCEPT,
 115     POINT_CONCEPT,
 116     POINT_3D_CONCEPT,
 117     RECTANGLE_CONCEPT,
 118     POLYGON_90_CONCEPT,
 119     POLYGON_90_WITH_HOLES_CONCEPT,
 120     POLYGON_45_CONCEPT,
 121     POLYGON_45_WITH_HOLES_CONCEPT,
 122     POLYGON_CONCEPT,
 123     POLYGON_WITH_HOLES_CONCEPT,
 124     POLYGON_90_SET_CONCEPT,
 125     POLYGON_45_SET_CONCEPT,
 126     POLYGON_SET_CONCEPT
 127   };
 128
 129   struct undefined_concept {};
 130
 131   template <typename T>
 132   struct geometry_concept { typedef undefined_concept type; };
 133
 134   template <typename GCT, typename T>
 135   struct view_of {};
 136
 137   template <typename T1, typename T2>
 138   view_of<T1, T2> view_as(const T2& obj) { return view_of<T1, T2>(obj); }
 139
 140   template <typename T>
 141   struct coordinate_traits {};
 142
 143   template <typename T>
 144   struct high_precision_type {
 145     typedef long double type;
 146   };
 147
 148   template <typename T>
 149   T convert_high_precision_type(const typename high_precision_type<T>::type& v) {
 150     return T(v);
 151   }
 152
 153   template <>
 154   struct coordinate_traits<int> {
 155     typedef int coordinate_type;
 156     typedef long double area_type;
 157 #ifdef BOOST_POLYGON_USE_LONG_LONG
 158     typedef polygon_long_long_type manhattan_area_type;
 159     typedef polygon_ulong_long_type unsigned_area_type;
 160     typedef polygon_long_long_type coordinate_difference;
 161 #else
 162     typedef long manhattan_area_type;
 163     typedef unsigned long unsigned_area_type;
 164     typedef long coordinate_difference;
 165 #endif
 166     typedef long double coordinate_distance;
 167   };
 168
 169 #ifdef BOOST_POLYGON_USE_LONG_LONG
 170   template <>
 171   struct coordinate_traits<polygon_long_long_type> {
 172     typedef polygon_long_long_type coordinate_type;
 173     typedef long double area_type;
 174     typedef polygon_long_long_type manhattan_area_type;
 175     typedef polygon_ulong_long_type unsigned_area_type;
 176     typedef polygon_long_long_type coordinate_difference;
 177     typedef long double coordinate_distance;
 178   };
 179 #endif
 180
 181   template <>
 182   struct coordinate_traits<float> {
 183     typedef float coordinate_type;
 184     typedef float area_type;
 185     typedef float manhattan_area_type;
 186     typedef float unsigned_area_type;
 187     typedef float coordinate_difference;
 188     typedef float coordinate_distance;
 189   };
 190
 191   template <>
 192   struct coordinate_traits<double> {
 193     typedef double coordinate_type;
 194     typedef double area_type;
 195     typedef double manhattan_area_type;
 196     typedef double unsigned_area_type;
 197     typedef double coordinate_difference;
 198     typedef double coordinate_distance;
 199   };
 200
 201   template <>
 202   struct coordinate_traits<long double> {
 203     typedef long double coordinate_type;
 204     typedef long double area_type;
 205     typedef long double manhattan_area_type;
 206     typedef long double unsigned_area_type;
 207     typedef long double coordinate_difference;
 208     typedef long double coordinate_distance;
 209   };
 210
 211   template <typename T>
 212   struct scaling_policy {
 213     template <typename T2>
 214     static inline T round(T2 t2) {
 215       return (T)std::floor(t2+0.5);
 216     }
 217
 218     static inline T round(T t2) {
 219       return t2;
 220     }
 221   };
 222
 223   struct coordinate_concept {};
 224
 225   template <>
 226   struct geometry_concept<int> { typedef coordinate_concept type; };
 227 #ifdef BOOST_POLYGON_USE_LONG_LONG
 228   template <>
 229   struct geometry_concept<polygon_long_long_type> { typedef coordinate_concept type; };
 230 #endif
 231   template <>
 232   struct geometry_concept<float> { typedef coordinate_concept type; };
 233   template <>
 234   struct geometry_concept<double> { typedef coordinate_concept type; };
 235   template <>
 236   struct geometry_concept<long double> { typedef coordinate_concept type; };
 237
 238 #ifndef BOOST_POLYGON_NO_DEPS
 239   struct gtl_no : mpl::bool_<false> {};
 240   struct gtl_yes : mpl::bool_<true> {};
 241   template <typename T, typename T2>
 242   struct gtl_and : mpl::and_<T, T2> {};
 243   template <typename T, typename T2, typename T3>
 244   struct gtl_and_3 : mpl::and_<T, T2, T3> {};
 245   template <typename T, typename T2, typename T3, typename T4>
 246   struct gtl_and_4 : mpl::and_<T, T2, T3, T4> {};
 247 //  template <typename T, typename T2>
 248 //  struct gtl_or : mpl::or_<T, T2> {};
 249 //  template <typename T, typename T2, typename T3>
 250 //  struct gtl_or_3 : mpl::or_<T, T2, T3> {};
 251 //  template <typename T, typename T2, typename T3, typename T4>
 252 //  struct gtl_or_4 : mpl::or_<T, T2, T3, T4> {};
 253 #else
 254   struct gtl_no { static const bool value = false; };
 255   struct gtl_yes { typedef gtl_yes type;
 256     static const bool value = true; };
 257
 258   template <bool T, bool T2>
 259   struct gtl_and_c { typedef gtl_no type; };
 260   template <>
 261   struct gtl_and_c<true, true> { typedef gtl_yes type; };
 262
 263   template <typename T, typename T2>
 264   struct gtl_and : gtl_and_c<T::value, T2::value> {};
 265   template <typename T, typename T2, typename T3>
 266   struct gtl_and_3 { typedef typename gtl_and<
 267                        T, typename gtl_and<T2, T3>::type>::type type; };
 268
 269   template <typename T, typename T2, typename T3, typename T4>
 270   struct gtl_and_4 { typedef typename gtl_and_3<
 271                        T, T2, typename gtl_and<T3, T4>::type>::type type; };
 272 #endif
 273   template <typename T, typename T2>
 274   struct gtl_or { typedef gtl_yes type; };
 275   template <typename T>
 276   struct gtl_or<T, T> { typedef T type; };
 277
 278   template <typename T, typename T2, typename T3>
 279   struct gtl_or_3 { typedef typename gtl_or<
 280                       T, typename gtl_or<T2, T3>::type>::type type; };
 281
 282   template <typename T, typename T2, typename T3, typename T4>
 283   struct gtl_or_4 { typedef typename gtl_or<
 284                       T, typename gtl_or_3<T2, T3, T4>::type>::type type; };
 285
 286   template <typename T>
 287   struct gtl_not { typedef gtl_no type; };
 288   template <>
 289   struct gtl_not<gtl_no> { typedef gtl_yes type; };
 290
 291   template <typename T>
 292   struct gtl_if {
 293 #ifdef BOOST_POLYGON_MSVC
 294     typedef gtl_no type;
 295 #endif
 296   };
 297   template <>
 298   struct gtl_if<gtl_yes> { typedef gtl_yes type; };
 299
 300   template <typename T, typename T2>
 301   struct gtl_same_type { typedef gtl_no type; };
 302   template <typename T>
 303   struct gtl_same_type<T, T> { typedef gtl_yes type; };
 304   template <typename T, typename T2>
 305   struct gtl_different_type { typedef typename gtl_not<typename gtl_same_type<T, T2>::type>::type type; };
 306
 307   struct manhattan_domain {};
 308   struct forty_five_domain {};
 309   struct general_domain {};
 310
 311   template <typename T>
 312   struct geometry_domain { typedef general_domain type; };
 313
 314   template <typename domain_type, typename coordinate_type>
 315   struct area_type_by_domain { typedef typename coordinate_traits<coordinate_type>::area_type type; };
 316   template <typename coordinate_type>
 317   struct area_type_by_domain<manhattan_domain, coordinate_type> {
 318     typedef typename coordinate_traits<coordinate_type>::manhattan_area_type type; };
 319
 320   struct y_c_edist : gtl_yes {};
 321
 322   template <typename coordinate_type_1, typename coordinate_type_2>
 323     typename enable_if<
 324     typename gtl_and_3<y_c_edist, typename gtl_same_type<typename geometry_concept<coordinate_type_1>::type, coordinate_concept>::type,
 325                        typename gtl_same_type<typename geometry_concept<coordinate_type_1>::type, coordinate_concept>::type>::type,
 326     typename coordinate_traits<coordinate_type_1>::coordinate_difference>::type
 327   euclidean_distance(const coordinate_type_1& lvalue, const coordinate_type_2& rvalue) {
 328     typedef typename coordinate_traits<coordinate_type_1>::coordinate_difference Unit;
 329     return (lvalue < rvalue) ? (Unit)rvalue - (Unit)lvalue : (Unit)lvalue - (Unit)rvalue;
 330   }
 331
 332
 333
 334   // predicated_swap swaps a and b if pred is true
 335
 336   // predicated_swap is guarenteed to behave the same as
 337   // if(pred){
 338   //   T tmp = a;
 339   //   a = b;
 340   //   b = tmp;
 341   // }
 342   // but will not generate a branch instruction.
 343   // predicated_swap always creates a temp copy of a, but does not
 344   // create more than one temp copy of an input.
 345   // predicated_swap can be used to optimize away branch instructions in C++
 346   template <class T>
 347   inline bool predicated_swap(const bool& pred,
 348                               T& a,
 349                               T& b) {
 350     const T tmp = a;
 351     const T* input[2] = {&b, &tmp};
 352     a = *input[!pred];
 353     b = *input[pred];
 354     return pred;
 355   }
 356
 357   enum direction_1d_enum { LOW = 0, HIGH = 1,
 358                            LEFT = 0, RIGHT = 1,
 359                            CLOCKWISE = 0, COUNTERCLOCKWISE = 1,
 360                            REVERSE = 0, FORWARD = 1,
 361                            NEGATIVE = 0, POSITIVE = 1 };
 362   enum orientation_2d_enum { HORIZONTAL = 0, VERTICAL = 1 };
 363   enum direction_2d_enum { WEST = 0, EAST = 1, SOUTH = 2, NORTH = 3 };
 364   enum orientation_3d_enum { PROXIMAL = 2 };
 365   enum direction_3d_enum { DOWN = 4, UP = 5 };
 366   enum winding_direction {
 367     clockwise_winding = 0,
 368     counterclockwise_winding = 1,
 369     unknown_winding = 2
 370   };
 371
 372   class direction_2d;
 373   class direction_3d;
 374   class orientation_2d;
 375
 376   class direction_1d {
 377   private:
 378     unsigned int val_;
 379     explicit direction_1d(int d);
 380   public:
 381     inline direction_1d() : val_(LOW) {}
 382     inline direction_1d(const direction_1d& that) : val_(that.val_) {}
 383     inline direction_1d(const direction_1d_enum val) : val_(val) {}
 384     explicit inline direction_1d(const direction_2d& that);
 385     explicit inline direction_1d(const direction_3d& that);
 386     inline direction_1d& operator = (const direction_1d& d) {
 387       val_ = d.val_; return * this; }
 388     inline bool operator==(direction_1d d) const { return (val_ == d.val_); }
 389     inline bool operator!=(direction_1d d) const { return !((*this) == d); }
 390     inline unsigned int to_int(void) const { return val_; }
 391     inline direction_1d& backward() { val_ ^= 1; return *this; }
 392     inline int get_sign() const { return val_ * 2 - 1; }
 393   };
 394
 395   class direction_2d;
 396
 397   class orientation_2d {
 398   private:
 399     unsigned int val_;
 400     explicit inline orientation_2d(int o);
 401   public:
 402     inline orientation_2d() : val_(HORIZONTAL) {}
 403     inline orientation_2d(const orientation_2d& ori) : val_(ori.val_) {}
 404     inline orientation_2d(const orientation_2d_enum val) : val_(val) {}
 405     explicit inline orientation_2d(const direction_2d& that);
 406     inline orientation_2d& operator=(const orientation_2d& ori) {
 407       val_ = ori.val_; return * this; }
 408     inline bool operator==(orientation_2d that) const { return (val_ == that.val_); }
 409     inline bool operator!=(orientation_2d that) const { return (val_ != that.val_); }
 410     inline unsigned int to_int() const { return (val_); }
 411     inline void turn_90() { val_ = val_^ 1; }
 412     inline orientation_2d get_perpendicular() const {
 413       orientation_2d retval = *this;
 414       retval.turn_90();
 415       return retval;
 416     }
 417     inline direction_2d get_direction(direction_1d dir) const;
 418   };
 419
 420   class direction_2d {
 421   private:
 422     int val_;
 423
 424   public:
 425
 426     inline direction_2d() : val_(WEST) {}
 427
 428     inline direction_2d(const direction_2d& that) : val_(that.val_) {}
 429
 430     inline direction_2d(const direction_2d_enum val) : val_(val) {}
 431
 432     inline direction_2d& operator=(const direction_2d& d) {
 433       val_ = d.val_;
 434       return * this;
 435     }
 436
 437     inline ~direction_2d() { }
 438
 439     inline bool operator==(direction_2d d) const { return (val_ == d.val_); }
 440     inline bool operator!=(direction_2d d) const { return !((*this) == d); }
 441     inline bool operator< (direction_2d d) const { return (val_ < d.val_); }
 442     inline bool operator<=(direction_2d d) const { return (val_ <= d.val_); }
 443     inline bool operator> (direction_2d d) const { return (val_ > d.val_); }
 444     inline bool operator>=(direction_2d d) const { return (val_ >= d.val_); }
 445
 446     // Casting to int
 447     inline unsigned int to_int(void) const { return val_; }
 448
 449     inline direction_2d backward() const {
 450       // flip the LSB, toggles 0 - 1   and 2 - 3
 451       return direction_2d(direction_2d_enum(val_ ^ 1));
 452     }
 453
 454     // Returns a direction 90 degree left (LOW) or right(HIGH) to this one
 455     inline direction_2d turn(direction_1d t) const {
 456       return direction_2d(direction_2d_enum(val_ ^ 3 ^ (val_ >> 1) ^ t.to_int()));
 457     }
 458
 459     // Returns a direction 90 degree left to this one
 460     inline direction_2d left() const {return turn(HIGH);}
 461
 462     // Returns a direction 90 degree right to this one
 463     inline direction_2d right() const {return turn(LOW);}
 464
 465     // N, E are positive, S, W are negative
 466     inline bool is_positive() const {return (val_ & 1);}
 467     inline bool is_negative() const {return !is_positive();}
 468     inline int get_sign() const {return ((is_positive()) << 1) -1;}
 469
 470   };
 471
 472   direction_1d::direction_1d(const direction_2d& that) : val_(that.to_int() & 1) {}
 473
 474   orientation_2d::orientation_2d(const direction_2d& that) : val_(that.to_int() >> 1) {}
 475
 476   direction_2d orientation_2d::get_direction(direction_1d dir) const {
 477     return direction_2d(direction_2d_enum((val_ << 1) + dir.to_int()));
 478   }
 479
 480   class orientation_3d {
 481   private:
 482     unsigned int val_;
 483     explicit inline orientation_3d(int o);
 484   public:
 485     inline orientation_3d() : val_((int)HORIZONTAL) {}
 486     inline orientation_3d(const orientation_3d& ori) : val_(ori.val_) {}
 487     inline orientation_3d(orientation_2d ori) : val_(ori.to_int()) {}
 488     inline orientation_3d(const orientation_3d_enum val) : val_(val) {}
 489     explicit inline orientation_3d(const direction_2d& that);
 490     explicit inline orientation_3d(const direction_3d& that);
 491     inline ~orientation_3d() {  }
 492     inline orientation_3d& operator=(const orientation_3d& ori) {
 493       val_ = ori.val_; return * this; }
 494     inline bool operator==(orientation_3d that) const { return (val_ == that.val_); }
 495     inline bool operator!=(orientation_3d that) const { return (val_ != that.val_); }
 496     inline unsigned int to_int() const { return (val_); }
 497     inline direction_3d get_direction(direction_1d dir) const;
 498   };
 499
 500   class direction_3d {
 501   private:
 502     int val_;
 503
 504   public:
 505
 506     inline direction_3d() : val_(WEST) {}
 507
 508     inline direction_3d(direction_2d that) : val_(that.to_int()) {}
 509     inline direction_3d(const direction_3d& that) : val_(that.val_) {}
 510
 511     inline direction_3d(const direction_2d_enum val) : val_(val) {}
 512     inline direction_3d(const direction_3d_enum val) : val_(val) {}
 513
 514     inline direction_3d& operator=(direction_3d d) {
 515       val_ = d.val_;
 516       return * this;
 517     }
 518
 519     inline ~direction_3d() { }
 520
 521     inline bool operator==(direction_3d d) const { return (val_ == d.val_); }
 522     inline bool operator!=(direction_3d d) const { return !((*this) == d); }
 523     inline bool operator< (direction_3d d) const { return (val_ < d.val_); }
 524     inline bool operator<=(direction_3d d) const { return (val_ <= d.val_); }
 525     inline bool operator> (direction_3d d) const { return (val_ > d.val_); }
 526     inline bool operator>=(direction_3d d) const { return (val_ >= d.val_); }
 527
 528     // Casting to int
 529     inline unsigned int to_int(void) const { return val_; }
 530
 531     inline direction_3d backward() const {
 532       // flip the LSB, toggles 0 - 1   and 2 - 3 and 4 - 5
 533       return direction_2d(direction_2d_enum(val_ ^ 1));
 534     }
 535
 536     // N, E, U are positive, S, W, D are negative
 537     inline bool is_positive() const {return (val_ & 1);}
 538     inline bool is_negative() const {return !is_positive();}
 539     inline int get_sign() const {return ((is_positive()) << 1) -1;}
 540
 541   };
 542
 543   direction_1d::direction_1d(const direction_3d& that) : val_(that.to_int() & 1) {}
 544   orientation_3d::orientation_3d(const direction_3d& that) : val_(that.to_int() >> 1) {}
 545   orientation_3d::orientation_3d(const direction_2d& that) : val_(that.to_int() >> 1) {}
 546
 547   direction_3d orientation_3d::get_direction(direction_1d dir) const {
 548     return direction_3d(direction_3d_enum((val_ << 1) + dir.to_int()));
 549   }
 550
 551 }
 552 }
 553 #endif
 554