9
3

isotropy.hpp 17 KB

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