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
38typedef boost::long_long_type polygon_long_long_type;
39typedef 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
58typedef long long polygon_long_long_type;
59typedef 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
110namespace 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, bool /*enable*/ = true>
141 struct coordinate_traits {};
142
143 //used to override long double with an infinite precision datatype
144 template <typename T>
145 struct high_precision_type {
146 typedef long double type;
147 };
148
149 template <typename T>
150 T convert_high_precision_type(const typename high_precision_type<T>::type& v) {
151 return T(v);
152 }
153
154 //used to override std::sort with an alternative (parallel) algorithm
155 template <typename iter_type>
156 void polygon_sort(iter_type _b_, iter_type _e_);
157
158 template <typename iter_type, typename pred_type>
159 void polygon_sort(iter_type _b_, iter_type _e_, const pred_type& _pred_);
160
161
162 template <>
163 struct coordinate_traits<int> {
164 typedef int coordinate_type;
165 typedef long double area_type;
166#ifdef BOOST_POLYGON_USE_LONG_LONG
167 typedef polygon_long_long_type manhattan_area_type;
168 typedef polygon_ulong_long_type unsigned_area_type;
169 typedef polygon_long_long_type coordinate_difference;
170#else
171 typedef long manhattan_area_type;
172 typedef unsigned long unsigned_area_type;
173 typedef long coordinate_difference;
174#endif
175 typedef long double coordinate_distance;
176 };
177
178 template<>
179 struct coordinate_traits<long, sizeof(long) == sizeof(int)> {
180 typedef coordinate_traits<int> cT_;
181 typedef cT_::coordinate_type coordinate_type;
182 typedef cT_::area_type area_type;
183 typedef cT_::manhattan_area_type manhattan_area_type;
184 typedef cT_::unsigned_area_type unsigned_area_type;
185 typedef cT_::coordinate_difference coordinate_difference;
186 typedef cT_::coordinate_distance coordinate_distance;
187 };
188
189#ifdef BOOST_POLYGON_USE_LONG_LONG
190 template <>
191 struct coordinate_traits<polygon_long_long_type> {
192 typedef polygon_long_long_type coordinate_type;
193 typedef long double area_type;
194 typedef polygon_long_long_type manhattan_area_type;
195 typedef polygon_ulong_long_type unsigned_area_type;
196 typedef polygon_long_long_type coordinate_difference;
197 typedef long double coordinate_distance;
198 };
199
200 template<>
201 struct coordinate_traits<long, sizeof(long) == sizeof(polygon_long_long_type)> {
202 typedef coordinate_traits<polygon_long_long_type> cT_;
203 typedef cT_::coordinate_type coordinate_type;
204 typedef cT_::area_type area_type;
205 typedef cT_::manhattan_area_type manhattan_area_type;
206 typedef cT_::unsigned_area_type unsigned_area_type;
207 typedef cT_::coordinate_difference coordinate_difference;
208 typedef cT_::coordinate_distance coordinate_distance;
209 };
210#endif
211
212 template <>
213 struct coordinate_traits<float> {
214 typedef float coordinate_type;
215 typedef float area_type;
216 typedef float manhattan_area_type;
217 typedef float unsigned_area_type;
218 typedef float coordinate_difference;
219 typedef float coordinate_distance;
220 };
221
222 template <>
223 struct coordinate_traits<double> {
224 typedef double coordinate_type;
225 typedef double area_type;
226 typedef double manhattan_area_type;
227 typedef double unsigned_area_type;
228 typedef double coordinate_difference;
229 typedef double coordinate_distance;
230 };
231
232 template <>
233 struct coordinate_traits<long double> {
234 typedef long double coordinate_type;
235 typedef long double area_type;
236 typedef long double manhattan_area_type;
237 typedef long double unsigned_area_type;
238 typedef long double coordinate_difference;
239 typedef long double coordinate_distance;
240 };
241
242 template <typename T>
243 struct scaling_policy {
244 template <typename T2>
245 static inline T round(T2 t2) {
246 return (T)std::floor(t2+0.5);
247 }
248
249 static inline T round(T t2) {
250 return t2;
251 }
252 };
253
254 struct coordinate_concept {};
255
256 template <>
257 struct geometry_concept<int> { typedef coordinate_concept type; };
258#ifdef BOOST_POLYGON_USE_LONG_LONG
259 template <>
260 struct geometry_concept<polygon_long_long_type> { typedef coordinate_concept type; };
261#endif
262 template <>
263 struct geometry_concept<float> { typedef coordinate_concept type; };
264 template <>
265 struct geometry_concept<double> { typedef coordinate_concept type; };
266 template <>
267 struct geometry_concept<long double> { typedef coordinate_concept type; };
268
269#ifndef BOOST_POLYGON_NO_DEPS
270 struct gtl_no : mpl::bool_<false> {};
271 struct gtl_yes : mpl::bool_<true> {};
272 template <typename T, typename T2>
273 struct gtl_and : mpl::and_<T, T2> {};
274 template <typename T, typename T2, typename T3>
275 struct gtl_and_3 : mpl::and_<T, T2, T3> {};
276 template <typename T, typename T2, typename T3, typename T4>
277 struct gtl_and_4 : mpl::and_<T, T2, T3, T4> {};
278// template <typename T, typename T2>
279// struct gtl_or : mpl::or_<T, T2> {};
280// template <typename T, typename T2, typename T3>
281// struct gtl_or_3 : mpl::or_<T, T2, T3> {};
282// template <typename T, typename T2, typename T3, typename T4>
283// struct gtl_or_4 : mpl::or_<T, T2, T3, T4> {};
284#else
285 struct gtl_no { static const bool value = false; };
286 struct gtl_yes { typedef gtl_yes type;
287 static const bool value = true; };
288
289 template <bool T, bool T2>
290 struct gtl_and_c { typedef gtl_no type; };
291 template <>
292 struct gtl_and_c<true, true> { typedef gtl_yes type; };
293
294 template <typename T, typename T2>
295 struct gtl_and : gtl_and_c<T::value, T2::value> {};
296 template <typename T, typename T2, typename T3>
297 struct gtl_and_3 { typedef typename gtl_and<
298 T, typename gtl_and<T2, T3>::type>::type type; };
299
300 template <typename T, typename T2, typename T3, typename T4>
301 struct gtl_and_4 { typedef typename gtl_and_3<
302 T, T2, typename gtl_and<T3, T4>::type>::type type; };
303#endif
304 template <typename T, typename T2>
305 struct gtl_or { typedef gtl_yes type; };
306 template <typename T>
307 struct gtl_or<T, T> { typedef T type; };
308
309 template <typename T, typename T2, typename T3>
310 struct gtl_or_3 { typedef typename gtl_or<
311 T, typename gtl_or<T2, T3>::type>::type type; };
312
313 template <typename T, typename T2, typename T3, typename T4>
314 struct gtl_or_4 { typedef typename gtl_or<
315 T, typename gtl_or_3<T2, T3, T4>::type>::type type; };
316
317 template <typename T>
318 struct gtl_not { typedef gtl_no type; };
319 template <>
320 struct gtl_not<gtl_no> { typedef gtl_yes type; };
321
322 template <typename T>
323 struct gtl_if {
324#ifdef BOOST_POLYGON_MSVC
325 typedef gtl_no type;
326#endif
327 };
328 template <>
329 struct gtl_if<gtl_yes> { typedef gtl_yes type; };
330
331 template <typename T, typename T2>
332 struct gtl_same_type { typedef gtl_no type; };
333 template <typename T>
334 struct gtl_same_type<T, T> { typedef gtl_yes type; };
335 template <typename T, typename T2>
336 struct gtl_different_type { typedef typename gtl_not<typename gtl_same_type<T, T2>::type>::type type; };
337
338 struct manhattan_domain {};
339 struct forty_five_domain {};
340 struct general_domain {};
341
342 template <typename T>
343 struct geometry_domain { typedef general_domain type; };
344
345 template <typename domain_type, typename coordinate_type>
346 struct area_type_by_domain { typedef typename coordinate_traits<coordinate_type>::area_type type; };
347 template <typename coordinate_type>
348 struct area_type_by_domain<manhattan_domain, coordinate_type> {
349 typedef typename coordinate_traits<coordinate_type>::manhattan_area_type type; };
350
351 struct y_c_edist : gtl_yes {};
352
353 template <typename coordinate_type_1, typename coordinate_type_2>
354 typename enable_if<
355 typename gtl_and_3<y_c_edist, typename gtl_same_type<typename geometry_concept<coordinate_type_1>::type, coordinate_concept>::type,
356 typename gtl_same_type<typename geometry_concept<coordinate_type_1>::type, coordinate_concept>::type>::type,
357 typename coordinate_traits<coordinate_type_1>::coordinate_difference>::type
358 euclidean_distance(const coordinate_type_1& lvalue, const coordinate_type_2& rvalue) {
359 typedef typename coordinate_traits<coordinate_type_1>::coordinate_difference Unit;
360 return (lvalue < rvalue) ? (Unit)rvalue - (Unit)lvalue : (Unit)lvalue - (Unit)rvalue;
361 }
362
363
364
365 // predicated_swap swaps a and b if pred is true
366
367 // predicated_swap is guarenteed to behave the same as
368 // if(pred){
369 // T tmp = a;
370 // a = b;
371 // b = tmp;
372 // }
373 // but will not generate a branch instruction.
374 // predicated_swap always creates a temp copy of a, but does not
375 // create more than one temp copy of an input.
376 // predicated_swap can be used to optimize away branch instructions in C++
377 template <class T>
378 inline bool predicated_swap(const bool& pred,
379 T& a,
380 T& b) {
381 const T tmp = a;
382 const T* input[2] = {&b, &tmp};
383 a = *input[!pred];
384 b = *input[pred];
385 return pred;
386 }
387
388 enum direction_1d_enum { LOW = 0, HIGH = 1,
389 LEFT = 0, RIGHT = 1,
390 CLOCKWISE = 0, COUNTERCLOCKWISE = 1,
391 REVERSE = 0, FORWARD = 1,
392 NEGATIVE = 0, POSITIVE = 1 };
393 enum orientation_2d_enum { HORIZONTAL = 0, VERTICAL = 1 };
394 enum direction_2d_enum { WEST = 0, EAST = 1, SOUTH = 2, NORTH = 3 };
395 enum orientation_3d_enum { PROXIMAL = 2 };
396 enum direction_3d_enum { DOWN = 4, UP = 5 };
397 enum winding_direction {
398 clockwise_winding = 0,
399 counterclockwise_winding = 1,
400 unknown_winding = 2
401 };
402
403 class direction_2d;
404 class direction_3d;
405 class orientation_2d;
406
407 class direction_1d {
408 private:
409 unsigned int val_;
410 explicit direction_1d(int d);
411 public:
412 inline direction_1d() : val_(LOW) {}
413 inline direction_1d(const direction_1d& that) : val_(that.val_) {}
414 inline direction_1d(const direction_1d_enum val) : val_(val) {}
415 explicit inline direction_1d(const direction_2d& that);
416 explicit inline direction_1d(const direction_3d& that);
417 inline direction_1d& operator = (const direction_1d& d) {
418 val_ = d.val_; return * this; }
419 inline bool operator==(direction_1d d) const { return (val_ == d.val_); }
420 inline bool operator!=(direction_1d d) const { return !((*this) == d); }
421 inline unsigned int to_int(void) const { return val_; }
422 inline direction_1d& backward() { val_ ^= 1; return *this; }
423 inline int get_sign() const { return val_ * 2 - 1; }
424 };
425
426 class direction_2d;
427
428 class orientation_2d {
429 private:
430 unsigned int val_;
431 explicit inline orientation_2d(int o);
432 public:
433 inline orientation_2d() : val_(HORIZONTAL) {}
434 inline orientation_2d(const orientation_2d& ori) : val_(ori.val_) {}
435 inline orientation_2d(const orientation_2d_enum val) : val_(val) {}
436 explicit inline orientation_2d(const direction_2d& that);
437 inline orientation_2d& operator=(const orientation_2d& ori) {
438 val_ = ori.val_; return * this; }
439 inline bool operator==(orientation_2d that) const { return (val_ == that.val_); }
440 inline bool operator!=(orientation_2d that) const { return (val_ != that.val_); }
441 inline unsigned int to_int() const { return (val_); }
442 inline void turn_90() { val_ = val_^ 1; }
443 inline orientation_2d get_perpendicular() const {
444 orientation_2d retval = *this;
445 retval.turn_90();
446 return retval;
447 }
448 inline direction_2d get_direction(direction_1d dir) const;
449 };
450
451 class direction_2d {
452 private:
453 int val_;
454
455 public:
456
457 inline direction_2d() : val_(WEST) {}
458
459 inline direction_2d(const direction_2d& that) : val_(that.val_) {}
460
461 inline direction_2d(const direction_2d_enum val) : val_(val) {}
462
463 inline direction_2d& operator=(const direction_2d& d) {
464 val_ = d.val_;
465 return * this;
466 }
467
468 inline ~direction_2d() { }
469
470 inline bool operator==(direction_2d d) const { return (val_ == d.val_); }
471 inline bool operator!=(direction_2d d) const { return !((*this) == d); }
472 inline bool operator< (direction_2d d) const { return (val_ < d.val_); }
473 inline bool operator<=(direction_2d d) const { return (val_ <= d.val_); }
474 inline bool operator> (direction_2d d) const { return (val_ > d.val_); }
475 inline bool operator>=(direction_2d d) const { return (val_ >= d.val_); }
476
477 // Casting to int
478 inline unsigned int to_int(void) const { return val_; }
479
480 inline direction_2d backward() const {
481 // flip the LSB, toggles 0 - 1 and 2 - 3
482 return direction_2d(direction_2d_enum(val_ ^ 1));
483 }
484
485 // Returns a direction 90 degree left (LOW) or right(HIGH) to this one
486 inline direction_2d turn(direction_1d t) const {
487 return direction_2d(direction_2d_enum(val_ ^ 3 ^ (val_ >> 1) ^ t.to_int()));
488 }
489
490 // Returns a direction 90 degree left to this one
491 inline direction_2d left() const {return turn(t: HIGH);}
492
493 // Returns a direction 90 degree right to this one
494 inline direction_2d right() const {return turn(t: LOW);}
495
496 // N, E are positive, S, W are negative
497 inline bool is_positive() const {return (val_ & 1);}
498 inline bool is_negative() const {return !is_positive();}
499 inline int get_sign() const {return ((is_positive()) << 1) -1;}
500
501 };
502
503 direction_1d::direction_1d(const direction_2d& that) : val_(that.to_int() & 1) {}
504
505 orientation_2d::orientation_2d(const direction_2d& that) : val_(that.to_int() >> 1) {}
506
507 direction_2d orientation_2d::get_direction(direction_1d dir) const {
508 return direction_2d(direction_2d_enum((val_ << 1) + dir.to_int()));
509 }
510
511 class orientation_3d {
512 private:
513 unsigned int val_;
514 explicit inline orientation_3d(int o);
515 public:
516 inline orientation_3d() : val_((int)HORIZONTAL) {}
517 inline orientation_3d(const orientation_3d& ori) : val_(ori.val_) {}
518 inline orientation_3d(orientation_2d ori) : val_(ori.to_int()) {}
519 inline orientation_3d(const orientation_3d_enum val) : val_(val) {}
520 explicit inline orientation_3d(const direction_2d& that);
521 explicit inline orientation_3d(const direction_3d& that);
522 inline ~orientation_3d() { }
523 inline orientation_3d& operator=(const orientation_3d& ori) {
524 val_ = ori.val_; return * this; }
525 inline bool operator==(orientation_3d that) const { return (val_ == that.val_); }
526 inline bool operator!=(orientation_3d that) const { return (val_ != that.val_); }
527 inline unsigned int to_int() const { return (val_); }
528 inline direction_3d get_direction(direction_1d dir) const;
529 };
530
531 class direction_3d {
532 private:
533 int val_;
534
535 public:
536
537 inline direction_3d() : val_(WEST) {}
538
539 inline direction_3d(direction_2d that) : val_(that.to_int()) {}
540 inline direction_3d(const direction_3d& that) : val_(that.val_) {}
541
542 inline direction_3d(const direction_2d_enum val) : val_(val) {}
543 inline direction_3d(const direction_3d_enum val) : val_(val) {}
544
545 inline direction_3d& operator=(direction_3d d) {
546 val_ = d.val_;
547 return * this;
548 }
549
550 inline ~direction_3d() { }
551
552 inline bool operator==(direction_3d d) const { return (val_ == d.val_); }
553 inline bool operator!=(direction_3d d) const { return !((*this) == d); }
554 inline bool operator< (direction_3d d) const { return (val_ < d.val_); }
555 inline bool operator<=(direction_3d d) const { return (val_ <= d.val_); }
556 inline bool operator> (direction_3d d) const { return (val_ > d.val_); }
557 inline bool operator>=(direction_3d d) const { return (val_ >= d.val_); }
558
559 // Casting to int
560 inline unsigned int to_int(void) const { return val_; }
561
562 inline direction_3d backward() const {
563 // flip the LSB, toggles 0 - 1 and 2 - 3 and 4 - 5
564 return direction_2d(direction_2d_enum(val_ ^ 1));
565 }
566
567 // N, E, U are positive, S, W, D are negative
568 inline bool is_positive() const {return (val_ & 1);}
569 inline bool is_negative() const {return !is_positive();}
570 inline int get_sign() const {return ((is_positive()) << 1) -1;}
571
572 };
573
574 direction_1d::direction_1d(const direction_3d& that) : val_(that.to_int() & 1) {}
575 orientation_3d::orientation_3d(const direction_3d& that) : val_(that.to_int() >> 1) {}
576 orientation_3d::orientation_3d(const direction_2d& that) : val_(that.to_int() >> 1) {}
577
578 direction_3d orientation_3d::get_direction(direction_1d dir) const {
579 return direction_3d(direction_3d_enum((val_ << 1) + dir.to_int()));
580 }
581
582}
583}
584#endif
585

source code of boost/boost/polygon/isotropy.hpp