]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | |
7c673cae FG |
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; | |
7c673cae FG |
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> | |
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> | |
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> | |
191 | static inline T round(T2 t2) { | |
192 | return (T)std::floor(t2+0.5); | |
193 | } | |
194 | ||
195 | 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 | ||
7c673cae FG |
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; }; | |
7c673cae FG |
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 | ||
92f5a8d4 TL |
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 | ||
7c673cae FG |
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 | |
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> | |
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: | |
353 | inline direction_1d() : val_(LOW) {} | |
354 | inline direction_1d(const direction_1d& that) : val_(that.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); | |
358 | inline direction_1d& operator = (const direction_1d& d) { | |
359 | val_ = d.val_; return * this; } | |
360 | inline bool operator==(direction_1d d) const { return (val_ == d.val_); } | |
361 | inline bool operator!=(direction_1d d) const { return !((*this) == d); } | |
362 | inline unsigned int to_int(void) const { return val_; } | |
363 | inline direction_1d& backward() { val_ ^= 1; return *this; } | |
364 | 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: | |
374 | inline orientation_2d() : val_(HORIZONTAL) {} | |
375 | inline orientation_2d(const orientation_2d& ori) : val_(ori.val_) {} | |
376 | inline orientation_2d(const orientation_2d_enum val) : val_(val) {} | |
377 | explicit inline orientation_2d(const direction_2d& that); | |
378 | inline orientation_2d& operator=(const orientation_2d& ori) { | |
379 | val_ = ori.val_; return * this; } | |
380 | inline bool operator==(orientation_2d that) const { return (val_ == that.val_); } | |
381 | inline bool operator!=(orientation_2d that) const { return (val_ != that.val_); } | |
382 | inline unsigned int to_int() const { return (val_); } | |
383 | inline void turn_90() { val_ = val_^ 1; } | |
384 | 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 | ||
398 | inline direction_2d() : val_(WEST) {} | |
399 | ||
400 | inline direction_2d(const direction_2d& that) : val_(that.val_) {} | |
401 | ||
402 | inline direction_2d(const direction_2d_enum val) : val_(val) {} | |
403 | ||
404 | inline direction_2d& operator=(const direction_2d& d) { | |
405 | val_ = d.val_; | |
406 | return * this; | |
407 | } | |
408 | ||
409 | inline ~direction_2d() { } | |
410 | ||
411 | inline bool operator==(direction_2d d) const { return (val_ == d.val_); } | |
412 | inline bool operator!=(direction_2d d) const { return !((*this) == d); } | |
413 | inline bool operator< (direction_2d d) const { return (val_ < d.val_); } | |
414 | inline bool operator<=(direction_2d d) const { return (val_ <= d.val_); } | |
415 | inline bool operator> (direction_2d d) const { return (val_ > d.val_); } | |
416 | inline bool operator>=(direction_2d d) const { return (val_ >= d.val_); } | |
417 | ||
418 | // Casting to int | |
419 | inline unsigned int to_int(void) const { return val_; } | |
420 | ||
421 | 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 | |
427 | 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 | |
432 | inline direction_2d left() const {return turn(HIGH);} | |
433 | ||
434 | // Returns a direction 90 degree right to this one | |
435 | inline direction_2d right() const {return turn(LOW);} | |
436 | ||
437 | // N, E are positive, S, W are negative | |
438 | inline bool is_positive() const {return (val_ & 1);} | |
439 | inline bool is_negative() const {return !is_positive();} | |
440 | inline int get_sign() const {return ((is_positive()) << 1) -1;} | |
441 | ||
442 | }; | |
443 | ||
444 | direction_1d::direction_1d(const direction_2d& that) : val_(that.to_int() & 1) {} | |
445 | ||
446 | orientation_2d::orientation_2d(const direction_2d& that) : val_(that.to_int() >> 1) {} | |
447 | ||
448 | 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: | |
457 | inline orientation_3d() : val_((int)HORIZONTAL) {} | |
458 | inline orientation_3d(const orientation_3d& ori) : val_(ori.val_) {} | |
459 | inline orientation_3d(orientation_2d ori) : val_(ori.to_int()) {} | |
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); | |
463 | inline ~orientation_3d() { } | |
464 | inline orientation_3d& operator=(const orientation_3d& ori) { | |
465 | val_ = ori.val_; return * this; } | |
466 | inline bool operator==(orientation_3d that) const { return (val_ == that.val_); } | |
467 | inline bool operator!=(orientation_3d that) const { return (val_ != that.val_); } | |
468 | 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 | ||
478 | inline direction_3d() : val_(WEST) {} | |
479 | ||
480 | inline direction_3d(direction_2d that) : val_(that.to_int()) {} | |
481 | inline direction_3d(const direction_3d& that) : val_(that.val_) {} | |
482 | ||
483 | inline direction_3d(const direction_2d_enum val) : val_(val) {} | |
484 | inline direction_3d(const direction_3d_enum val) : val_(val) {} | |
485 | ||
486 | inline direction_3d& operator=(direction_3d d) { | |
487 | val_ = d.val_; | |
488 | return * this; | |
489 | } | |
490 | ||
491 | inline ~direction_3d() { } | |
492 | ||
493 | inline bool operator==(direction_3d d) const { return (val_ == d.val_); } | |
494 | inline bool operator!=(direction_3d d) const { return !((*this) == d); } | |
495 | inline bool operator< (direction_3d d) const { return (val_ < d.val_); } | |
496 | inline bool operator<=(direction_3d d) const { return (val_ <= d.val_); } | |
497 | inline bool operator> (direction_3d d) const { return (val_ > d.val_); } | |
498 | inline bool operator>=(direction_3d d) const { return (val_ >= d.val_); } | |
499 | ||
500 | // Casting to int | |
501 | inline unsigned int to_int(void) const { return val_; } | |
502 | ||
503 | 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 | |
509 | inline bool is_positive() const {return (val_ & 1);} | |
510 | inline bool is_negative() const {return !is_positive();} | |
511 | inline int get_sign() const {return ((is_positive()) << 1) -1;} | |
512 | ||
513 | }; | |
514 | ||
515 | direction_1d::direction_1d(const direction_3d& that) : val_(that.to_int() & 1) {} | |
516 | orientation_3d::orientation_3d(const direction_3d& that) : val_(that.to_int() >> 1) {} | |
517 | orientation_3d::orientation_3d(const direction_2d& that) : val_(that.to_int() >> 1) {} | |
518 | ||
519 | 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 |