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 #else 44 45 #ifdef _WIN32 46 #define BOOST_POLYGON_MSVC 47 #endif 48 #ifdef __ICC 49 #define BOOST_POLYGON_ICC 50 #endif 51 #define BOOST_POLYGON_USE_LONG_LONG 52 typedef long long polygon_long_long_type; 53 typedef unsigned long long polygon_ulong_long_type; 54 #endif 55 56 namespace boost { namespace polygon{ 57 58 enum GEOMETRY_CONCEPT_ID { 59 COORDINATE_CONCEPT, 60 INTERVAL_CONCEPT, 61 POINT_CONCEPT, 62 POINT_3D_CONCEPT, 63 RECTANGLE_CONCEPT, 64 POLYGON_90_CONCEPT, 65 POLYGON_90_WITH_HOLES_CONCEPT, 66 POLYGON_45_CONCEPT, 67 POLYGON_45_WITH_HOLES_CONCEPT, 68 POLYGON_CONCEPT, 69 POLYGON_WITH_HOLES_CONCEPT, 70 POLYGON_90_SET_CONCEPT, 71 POLYGON_45_SET_CONCEPT, 72 POLYGON_SET_CONCEPT 73 }; 74 75 struct undefined_concept {}; 76 77 template <typename T> 78 struct geometry_concept { typedef undefined_concept type; }; 79 80 template <typename GCT, typename T> 81 struct view_of {}; 82 83 template <typename T1, typename T2> view_as(const T2 & obj)84 view_of<T1, T2> view_as(const T2& obj) { return view_of<T1, T2>(obj); } 85 86 template <typename T, bool /*enable*/ = true> 87 struct coordinate_traits {}; 88 89 //used to override long double with an infinite precision datatype 90 template <typename T> 91 struct high_precision_type { 92 typedef long double type; 93 }; 94 95 template <typename T> convert_high_precision_type(const typename high_precision_type<T>::type & v)96 T convert_high_precision_type(const typename high_precision_type<T>::type& v) { 97 return T(v); 98 } 99 100 //used to override std::sort with an alternative (parallel) algorithm 101 template <typename iter_type> 102 void polygon_sort(iter_type _b_, iter_type _e_); 103 104 template <typename iter_type, typename pred_type> 105 void polygon_sort(iter_type _b_, iter_type _e_, const pred_type& _pred_); 106 107 108 template <> 109 struct coordinate_traits<int> { 110 typedef int coordinate_type; 111 typedef long double area_type; 112 #ifdef BOOST_POLYGON_USE_LONG_LONG 113 typedef polygon_long_long_type manhattan_area_type; 114 typedef polygon_ulong_long_type unsigned_area_type; 115 typedef polygon_long_long_type coordinate_difference; 116 #else 117 typedef long manhattan_area_type; 118 typedef unsigned long unsigned_area_type; 119 typedef long coordinate_difference; 120 #endif 121 typedef long double coordinate_distance; 122 }; 123 124 template<> 125 struct coordinate_traits<long, sizeof(long) == sizeof(int)> { 126 typedef coordinate_traits<int> cT_; 127 typedef cT_::coordinate_type coordinate_type; 128 typedef cT_::area_type area_type; 129 typedef cT_::manhattan_area_type manhattan_area_type; 130 typedef cT_::unsigned_area_type unsigned_area_type; 131 typedef cT_::coordinate_difference coordinate_difference; 132 typedef cT_::coordinate_distance coordinate_distance; 133 }; 134 135 #ifdef BOOST_POLYGON_USE_LONG_LONG 136 template <> 137 struct coordinate_traits<polygon_long_long_type> { 138 typedef polygon_long_long_type coordinate_type; 139 typedef long double area_type; 140 typedef polygon_long_long_type manhattan_area_type; 141 typedef polygon_ulong_long_type unsigned_area_type; 142 typedef polygon_long_long_type coordinate_difference; 143 typedef long double coordinate_distance; 144 }; 145 146 template<> 147 struct coordinate_traits<long, sizeof(long) == sizeof(polygon_long_long_type)> { 148 typedef coordinate_traits<polygon_long_long_type> cT_; 149 typedef cT_::coordinate_type coordinate_type; 150 typedef cT_::area_type area_type; 151 typedef cT_::manhattan_area_type manhattan_area_type; 152 typedef cT_::unsigned_area_type unsigned_area_type; 153 typedef cT_::coordinate_difference coordinate_difference; 154 typedef cT_::coordinate_distance coordinate_distance; 155 }; 156 #endif 157 158 template <> 159 struct coordinate_traits<float> { 160 typedef float coordinate_type; 161 typedef float area_type; 162 typedef float manhattan_area_type; 163 typedef float unsigned_area_type; 164 typedef float coordinate_difference; 165 typedef float coordinate_distance; 166 }; 167 168 template <> 169 struct coordinate_traits<double> { 170 typedef double coordinate_type; 171 typedef double area_type; 172 typedef double manhattan_area_type; 173 typedef double unsigned_area_type; 174 typedef double coordinate_difference; 175 typedef double coordinate_distance; 176 }; 177 178 template <> 179 struct coordinate_traits<long double> { 180 typedef long double coordinate_type; 181 typedef long double area_type; 182 typedef long double manhattan_area_type; 183 typedef long double unsigned_area_type; 184 typedef long double coordinate_difference; 185 typedef long double coordinate_distance; 186 }; 187 188 template <typename T> 189 struct scaling_policy { 190 template <typename T2> roundboost::polygon::scaling_policy191 static inline T round(T2 t2) { 192 return (T)std::floor(t2+0.5); 193 } 194 roundboost::polygon::scaling_policy195 static inline T round(T t2) { 196 return t2; 197 } 198 }; 199 200 struct coordinate_concept {}; 201 202 template <> 203 struct geometry_concept<int> { typedef coordinate_concept type; }; 204 #ifdef BOOST_POLYGON_USE_LONG_LONG 205 template <> 206 struct geometry_concept<polygon_long_long_type> { typedef coordinate_concept type; }; 207 #endif 208 template <> 209 struct geometry_concept<float> { typedef coordinate_concept type; }; 210 template <> 211 struct geometry_concept<double> { typedef coordinate_concept type; }; 212 template <> 213 struct geometry_concept<long double> { typedef coordinate_concept type; }; 214 215 struct gtl_no { static const bool value = false; }; 216 struct gtl_yes { typedef gtl_yes type; 217 static const bool value = true; }; 218 219 template <bool T, bool T2> 220 struct gtl_and_c { typedef gtl_no type; }; 221 template <> 222 struct gtl_and_c<true, true> { typedef gtl_yes type; }; 223 224 template <typename T, typename T2> 225 struct gtl_and : gtl_and_c<T::value, T2::value> {}; 226 template <typename T, typename T2, typename T3> 227 struct gtl_and_3 { typedef typename gtl_and< 228 T, typename gtl_and<T2, T3>::type>::type type; }; 229 230 template <typename T, typename T2, typename T3, typename T4> 231 struct gtl_and_4 { typedef typename gtl_and_3< 232 T, T2, typename gtl_and<T3, T4>::type>::type type; }; 233 template <typename T, typename T2> 234 struct gtl_or { typedef gtl_yes type; }; 235 template <typename T> 236 struct gtl_or<T, T> { typedef T type; }; 237 238 template <typename T, typename T2, typename T3> 239 struct gtl_or_3 { typedef typename gtl_or< 240 T, typename gtl_or<T2, T3>::type>::type type; }; 241 242 template <typename T, typename T2, typename T3, typename T4> 243 struct gtl_or_4 { typedef typename gtl_or< 244 T, typename gtl_or_3<T2, T3, T4>::type>::type type; }; 245 246 template <typename T> 247 struct gtl_not { typedef gtl_no type; }; 248 template <> 249 struct gtl_not<gtl_no> { typedef gtl_yes type; }; 250 251 template <typename T> 252 struct gtl_if { 253 #ifdef BOOST_POLYGON_MSVC 254 typedef gtl_no type; 255 #endif 256 }; 257 template <> 258 struct gtl_if<gtl_yes> { typedef gtl_yes type; }; 259 260 template <typename T, typename T2> 261 struct gtl_same_type { typedef gtl_no type; }; 262 template <typename T> 263 struct gtl_same_type<T, T> { typedef gtl_yes type; }; 264 template <typename T, typename T2> 265 struct gtl_different_type { typedef typename gtl_not<typename gtl_same_type<T, T2>::type>::type type; }; 266 267 struct manhattan_domain {}; 268 struct forty_five_domain {}; 269 struct general_domain {}; 270 271 template <typename T> 272 struct geometry_domain { typedef general_domain type; }; 273 274 template <typename domain_type, typename coordinate_type> 275 struct area_type_by_domain { typedef typename coordinate_traits<coordinate_type>::area_type type; }; 276 template <typename coordinate_type> 277 struct area_type_by_domain<manhattan_domain, coordinate_type> { 278 typedef typename coordinate_traits<coordinate_type>::manhattan_area_type type; }; 279 280 template<bool E, class R = void> 281 struct enable_if_ { 282 typedef R type; 283 }; 284 285 template<class R> 286 struct enable_if_<false, R> { }; 287 288 template<class E, class R = void> 289 struct enable_if 290 : enable_if_<E::value, R> { }; 291 292 struct y_c_edist : gtl_yes {}; 293 294 template <typename coordinate_type_1, typename coordinate_type_2> 295 typename enable_if< 296 typename gtl_and_3<y_c_edist, typename gtl_same_type<typename geometry_concept<coordinate_type_1>::type, coordinate_concept>::type, 297 typename gtl_same_type<typename geometry_concept<coordinate_type_1>::type, coordinate_concept>::type>::type, 298 typename coordinate_traits<coordinate_type_1>::coordinate_difference>::type euclidean_distance(const coordinate_type_1 & lvalue,const coordinate_type_2 & rvalue)299 euclidean_distance(const coordinate_type_1& lvalue, const coordinate_type_2& rvalue) { 300 typedef typename coordinate_traits<coordinate_type_1>::coordinate_difference Unit; 301 return (lvalue < rvalue) ? (Unit)rvalue - (Unit)lvalue : (Unit)lvalue - (Unit)rvalue; 302 } 303 304 305 306 // predicated_swap swaps a and b if pred is true 307 308 // predicated_swap is guarenteed to behave the same as 309 // if(pred){ 310 // T tmp = a; 311 // a = b; 312 // b = tmp; 313 // } 314 // but will not generate a branch instruction. 315 // predicated_swap always creates a temp copy of a, but does not 316 // create more than one temp copy of an input. 317 // predicated_swap can be used to optimize away branch instructions in C++ 318 template <class T> predicated_swap(const bool & pred,T & a,T & b)319 inline bool predicated_swap(const bool& pred, 320 T& a, 321 T& b) { 322 const T tmp = a; 323 const T* input[2] = {&b, &tmp}; 324 a = *input[!pred]; 325 b = *input[pred]; 326 return pred; 327 } 328 329 enum direction_1d_enum { LOW = 0, HIGH = 1, 330 LEFT = 0, RIGHT = 1, 331 CLOCKWISE = 0, COUNTERCLOCKWISE = 1, 332 REVERSE = 0, FORWARD = 1, 333 NEGATIVE = 0, POSITIVE = 1 }; 334 enum orientation_2d_enum { HORIZONTAL = 0, VERTICAL = 1 }; 335 enum direction_2d_enum { WEST = 0, EAST = 1, SOUTH = 2, NORTH = 3 }; 336 enum orientation_3d_enum { PROXIMAL = 2 }; 337 enum direction_3d_enum { DOWN = 4, UP = 5 }; 338 enum winding_direction { 339 clockwise_winding = 0, 340 counterclockwise_winding = 1, 341 unknown_winding = 2 342 }; 343 344 class direction_2d; 345 class direction_3d; 346 class orientation_2d; 347 348 class direction_1d { 349 private: 350 unsigned int val_; 351 explicit direction_1d(int d); 352 public: direction_1d()353 inline direction_1d() : val_(LOW) {} direction_1d(const direction_1d & that)354 inline direction_1d(const direction_1d& that) : val_(that.val_) {} direction_1d(const direction_1d_enum val)355 inline direction_1d(const direction_1d_enum val) : val_(val) {} 356 explicit inline direction_1d(const direction_2d& that); 357 explicit inline direction_1d(const direction_3d& that); operator =(const direction_1d & d)358 inline direction_1d& operator = (const direction_1d& d) { 359 val_ = d.val_; return * this; } operator ==(direction_1d d) const360 inline bool operator==(direction_1d d) const { return (val_ == d.val_); } operator !=(direction_1d d) const361 inline bool operator!=(direction_1d d) const { return !((*this) == d); } to_int(void) const362 inline unsigned int to_int(void) const { return val_; } backward()363 inline direction_1d& backward() { val_ ^= 1; return *this; } get_sign() const364 inline int get_sign() const { return val_ * 2 - 1; } 365 }; 366 367 class direction_2d; 368 369 class orientation_2d { 370 private: 371 unsigned int val_; 372 explicit inline orientation_2d(int o); 373 public: orientation_2d()374 inline orientation_2d() : val_(HORIZONTAL) {} orientation_2d(const orientation_2d & ori)375 inline orientation_2d(const orientation_2d& ori) : val_(ori.val_) {} orientation_2d(const orientation_2d_enum val)376 inline orientation_2d(const orientation_2d_enum val) : val_(val) {} 377 explicit inline orientation_2d(const direction_2d& that); operator =(const orientation_2d & ori)378 inline orientation_2d& operator=(const orientation_2d& ori) { 379 val_ = ori.val_; return * this; } operator ==(orientation_2d that) const380 inline bool operator==(orientation_2d that) const { return (val_ == that.val_); } operator !=(orientation_2d that) const381 inline bool operator!=(orientation_2d that) const { return (val_ != that.val_); } to_int() const382 inline unsigned int to_int() const { return (val_); } turn_90()383 inline void turn_90() { val_ = val_^ 1; } get_perpendicular() const384 inline orientation_2d get_perpendicular() const { 385 orientation_2d retval = *this; 386 retval.turn_90(); 387 return retval; 388 } 389 inline direction_2d get_direction(direction_1d dir) const; 390 }; 391 392 class direction_2d { 393 private: 394 int val_; 395 396 public: 397 direction_2d()398 inline direction_2d() : val_(WEST) {} 399 direction_2d(const direction_2d & that)400 inline direction_2d(const direction_2d& that) : val_(that.val_) {} 401 direction_2d(const direction_2d_enum val)402 inline direction_2d(const direction_2d_enum val) : val_(val) {} 403 operator =(const direction_2d & d)404 inline direction_2d& operator=(const direction_2d& d) { 405 val_ = d.val_; 406 return * this; 407 } 408 ~direction_2d()409 inline ~direction_2d() { } 410 operator ==(direction_2d d) const411 inline bool operator==(direction_2d d) const { return (val_ == d.val_); } operator !=(direction_2d d) const412 inline bool operator!=(direction_2d d) const { return !((*this) == d); } operator <(direction_2d d) const413 inline bool operator< (direction_2d d) const { return (val_ < d.val_); } operator <=(direction_2d d) const414 inline bool operator<=(direction_2d d) const { return (val_ <= d.val_); } operator >(direction_2d d) const415 inline bool operator> (direction_2d d) const { return (val_ > d.val_); } operator >=(direction_2d d) const416 inline bool operator>=(direction_2d d) const { return (val_ >= d.val_); } 417 418 // Casting to int to_int(void) const419 inline unsigned int to_int(void) const { return val_; } 420 backward() const421 inline direction_2d backward() const { 422 // flip the LSB, toggles 0 - 1 and 2 - 3 423 return direction_2d(direction_2d_enum(val_ ^ 1)); 424 } 425 426 // Returns a direction 90 degree left (LOW) or right(HIGH) to this one turn(direction_1d t) const427 inline direction_2d turn(direction_1d t) const { 428 return direction_2d(direction_2d_enum(val_ ^ 3 ^ (val_ >> 1) ^ t.to_int())); 429 } 430 431 // Returns a direction 90 degree left to this one left() const432 inline direction_2d left() const {return turn(HIGH);} 433 434 // Returns a direction 90 degree right to this one right() const435 inline direction_2d right() const {return turn(LOW);} 436 437 // N, E are positive, S, W are negative is_positive() const438 inline bool is_positive() const {return (val_ & 1);} is_negative() const439 inline bool is_negative() const {return !is_positive();} get_sign() const440 inline int get_sign() const {return ((is_positive()) << 1) -1;} 441 442 }; 443 direction_1d(const direction_2d & that)444 direction_1d::direction_1d(const direction_2d& that) : val_(that.to_int() & 1) {} 445 orientation_2d(const direction_2d & that)446 orientation_2d::orientation_2d(const direction_2d& that) : val_(that.to_int() >> 1) {} 447 get_direction(direction_1d dir) const448 direction_2d orientation_2d::get_direction(direction_1d dir) const { 449 return direction_2d(direction_2d_enum((val_ << 1) + dir.to_int())); 450 } 451 452 class orientation_3d { 453 private: 454 unsigned int val_; 455 explicit inline orientation_3d(int o); 456 public: orientation_3d()457 inline orientation_3d() : val_((int)HORIZONTAL) {} orientation_3d(const orientation_3d & ori)458 inline orientation_3d(const orientation_3d& ori) : val_(ori.val_) {} orientation_3d(orientation_2d ori)459 inline orientation_3d(orientation_2d ori) : val_(ori.to_int()) {} orientation_3d(const orientation_3d_enum val)460 inline orientation_3d(const orientation_3d_enum val) : val_(val) {} 461 explicit inline orientation_3d(const direction_2d& that); 462 explicit inline orientation_3d(const direction_3d& that); ~orientation_3d()463 inline ~orientation_3d() { } operator =(const orientation_3d & ori)464 inline orientation_3d& operator=(const orientation_3d& ori) { 465 val_ = ori.val_; return * this; } operator ==(orientation_3d that) const466 inline bool operator==(orientation_3d that) const { return (val_ == that.val_); } operator !=(orientation_3d that) const467 inline bool operator!=(orientation_3d that) const { return (val_ != that.val_); } to_int() const468 inline unsigned int to_int() const { return (val_); } 469 inline direction_3d get_direction(direction_1d dir) const; 470 }; 471 472 class direction_3d { 473 private: 474 int val_; 475 476 public: 477 direction_3d()478 inline direction_3d() : val_(WEST) {} 479 direction_3d(direction_2d that)480 inline direction_3d(direction_2d that) : val_(that.to_int()) {} direction_3d(const direction_3d & that)481 inline direction_3d(const direction_3d& that) : val_(that.val_) {} 482 direction_3d(const direction_2d_enum val)483 inline direction_3d(const direction_2d_enum val) : val_(val) {} direction_3d(const direction_3d_enum val)484 inline direction_3d(const direction_3d_enum val) : val_(val) {} 485 operator =(direction_3d d)486 inline direction_3d& operator=(direction_3d d) { 487 val_ = d.val_; 488 return * this; 489 } 490 ~direction_3d()491 inline ~direction_3d() { } 492 operator ==(direction_3d d) const493 inline bool operator==(direction_3d d) const { return (val_ == d.val_); } operator !=(direction_3d d) const494 inline bool operator!=(direction_3d d) const { return !((*this) == d); } operator <(direction_3d d) const495 inline bool operator< (direction_3d d) const { return (val_ < d.val_); } operator <=(direction_3d d) const496 inline bool operator<=(direction_3d d) const { return (val_ <= d.val_); } operator >(direction_3d d) const497 inline bool operator> (direction_3d d) const { return (val_ > d.val_); } operator >=(direction_3d d) const498 inline bool operator>=(direction_3d d) const { return (val_ >= d.val_); } 499 500 // Casting to int to_int(void) const501 inline unsigned int to_int(void) const { return val_; } 502 backward() const503 inline direction_3d backward() const { 504 // flip the LSB, toggles 0 - 1 and 2 - 3 and 4 - 5 505 return direction_2d(direction_2d_enum(val_ ^ 1)); 506 } 507 508 // N, E, U are positive, S, W, D are negative is_positive() const509 inline bool is_positive() const {return (val_ & 1);} is_negative() const510 inline bool is_negative() const {return !is_positive();} get_sign() const511 inline int get_sign() const {return ((is_positive()) << 1) -1;} 512 513 }; 514 direction_1d(const direction_3d & that)515 direction_1d::direction_1d(const direction_3d& that) : val_(that.to_int() & 1) {} orientation_3d(const direction_3d & that)516 orientation_3d::orientation_3d(const direction_3d& that) : val_(that.to_int() >> 1) {} orientation_3d(const direction_2d & that)517 orientation_3d::orientation_3d(const direction_2d& that) : val_(that.to_int() >> 1) {} 518 get_direction(direction_1d dir) const519 direction_3d orientation_3d::get_direction(direction_1d dir) const { 520 return direction_3d(direction_3d_enum((val_ << 1) + dir.to_int())); 521 } 522 523 } 524 } 525 #endif 526