1 // Boost.Polygon library interval_concept.hpp header file
2 
3 // Copyright (c) Intel Corporation 2008.
4 // Copyright (c) 2008-2012 Simonson Lucanus.
5 // Copyright (c) 2012-2012 Andrii Sydorchuk.
6 
7 // See http://www.boost.org for updates, documentation, and revision history.
8 // Use, modification and distribution is subject to the Boost Software License,
9 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
10 // http://www.boost.org/LICENSE_1_0.txt)
11 
12 #ifndef BOOST_POLYGON_INTERVAL_CONCEPT_HPP
13 #define BOOST_POLYGON_INTERVAL_CONCEPT_HPP
14 
15 #include "isotropy.hpp"
16 #include "interval_traits.hpp"
17 
18 namespace boost {
19 namespace polygon {
20 
21 struct interval_concept {};
22 
23 template <typename ConceptType>
24 struct is_interval_concept {
25   typedef gtl_no type;
26 };
27 
28 template <>
29 struct is_interval_concept<interval_concept> {
30   typedef gtl_yes type;
31 };
32 
33 template <typename ConceptType>
34 struct is_mutable_interval_concept {
35   typedef gtl_no type;
36 };
37 
38 template <>
39 struct is_mutable_interval_concept<interval_concept> {
40   typedef gtl_yes type;
41 };
42 
43 template <typename GeometryType, typename BoolType>
44 struct interval_coordinate_type_by_concept {
45   typedef void type;
46 };
47 
48 template <typename GeometryType>
49 struct interval_coordinate_type_by_concept<GeometryType, gtl_yes> {
50   typedef typename interval_traits<GeometryType>::coordinate_type type;
51 };
52 
53 template <typename GeometryType>
54 struct interval_coordinate_type {
55   typedef typename interval_coordinate_type_by_concept<
56     GeometryType,
57     typename is_interval_concept<
58       typename geometry_concept<GeometryType>::type
59     >::type
60   >::type type;
61 };
62 
63 template <typename GeometryType, typename BoolType>
64 struct interval_difference_type_by_concept {
65   typedef void type;
66 };
67 
68 template <typename GeometryType>
69 struct interval_difference_type_by_concept<GeometryType, gtl_yes> {
70   typedef typename coordinate_traits<
71     typename interval_traits<GeometryType>::coordinate_type
72   >::coordinate_difference type;
73 };
74 
75 template <typename GeometryType>
76 struct interval_difference_type {
77   typedef typename interval_difference_type_by_concept<
78     GeometryType,
79     typename is_interval_concept<
80       typename geometry_concept<GeometryType>::type
81     >::type
82   >::type type;
83 };
84 
85 struct y_i_get : gtl_yes {};
86 
87 template <typename IntervalType>
88 typename enable_if<
89   typename gtl_and<
90     y_i_get,
91     typename is_interval_concept<
92       typename geometry_concept<IntervalType>::type
93     >::type
94   >::type,
95   typename interval_coordinate_type<IntervalType>::type
get(const IntervalType & interval,direction_1d dir)96 >::type get(const IntervalType& interval, direction_1d dir) {
97   return interval_traits<IntervalType>::get(interval, dir);
98 }
99 
100 struct y_i_set : gtl_yes {};
101 
102 template <typename IntervalType>
103 typename enable_if<
104   typename gtl_and<
105     y_i_set,
106     typename is_mutable_interval_concept<
107       typename geometry_concept<IntervalType>::type
108     >::type
109   >::type,
110   void
set(IntervalType & interval,direction_1d dir,typename interval_mutable_traits<IntervalType>::coordinate_type value)111 >::type set(IntervalType& interval, direction_1d dir,
112     typename interval_mutable_traits<IntervalType>::coordinate_type value) {
113   interval_mutable_traits<IntervalType>::set(interval, dir, value);
114 }
115 
116 struct y_i_construct : gtl_yes {};
117 
118 template <typename IntervalType>
119 typename enable_if<
120   typename gtl_and<
121     y_i_construct,
122     typename is_mutable_interval_concept<
123       typename geometry_concept<IntervalType>::type
124     >::type
125   >::type,
126   IntervalType
construct(typename interval_mutable_traits<IntervalType>::coordinate_type low,typename interval_mutable_traits<IntervalType>::coordinate_type high)127 >::type construct(
128     typename interval_mutable_traits<IntervalType>::coordinate_type low,
129     typename interval_mutable_traits<IntervalType>::coordinate_type high) {
130   if (low > high) {
131     (std::swap)(low, high);
132   }
133   return interval_mutable_traits<IntervalType>::construct(low, high);
134 }
135 
136 struct y_i_copy_construct : gtl_yes {};
137 
138 template <typename IntervalType1, typename IntervalType2>
139 typename enable_if<
140   typename gtl_and_3<
141     y_i_copy_construct,
142     typename is_mutable_interval_concept<
143       typename geometry_concept<IntervalType1>::type
144     >::type,
145     typename is_interval_concept<
146       typename geometry_concept<IntervalType2>::type
147     >::type
148   >::type,
149   IntervalType1
copy_construct(const IntervalType2 & interval)150 >::type copy_construct(const IntervalType2& interval) {
151   return construct<IntervalType1>(get(interval, LOW), get(interval, HIGH));
152 }
153 
154 struct y_i_assign : gtl_yes {};
155 
156 template <typename IntervalType1, typename IntervalType2>
157 typename enable_if<
158   typename gtl_and_3<
159     y_i_assign,
160     typename is_mutable_interval_concept<
161       typename geometry_concept<IntervalType1>::type
162     >::type,
163     typename is_interval_concept<
164       typename geometry_concept<IntervalType2>::type
165     >::type
166   >::type,
167   IntervalType1
assign(IntervalType1 & lvalue,const IntervalType2 & rvalue)168 >::type& assign(IntervalType1& lvalue, const IntervalType2& rvalue) {
169   set(lvalue, LOW, get(rvalue, LOW));
170   set(lvalue, HIGH, get(rvalue, HIGH));
171   return lvalue;
172 }
173 
174 struct y_i_low : gtl_yes {};
175 
176 template <typename IntervalType>
177 typename enable_if<
178   typename gtl_and<
179     y_i_low,
180     typename is_interval_concept<
181       typename geometry_concept<IntervalType>::type
182     >::type
183   >::type,
184   typename interval_coordinate_type<IntervalType>::type
low(const IntervalType & interval)185 >::type low(const IntervalType& interval) {
186   return get(interval, LOW);
187 }
188 
189 struct y_i_high : gtl_yes {};
190 
191 template <typename IntervalType>
192 typename enable_if<
193   typename gtl_and<
194     y_i_high,
195     typename is_interval_concept<
196       typename geometry_concept<IntervalType>::type
197     >::type
198   >::type,
199   typename interval_coordinate_type<IntervalType>::type
high(const IntervalType & interval)200 >::type high(const IntervalType& interval) {
201   return get(interval, HIGH);
202 }
203 
204 struct y_i_low2 : gtl_yes {};
205 
206 template <typename IntervalType>
207 typename enable_if<
208   typename gtl_and<
209     y_i_low2,
210     typename is_mutable_interval_concept<
211       typename geometry_concept<IntervalType>::type
212     >::type
213   >::type,
214   void
low(IntervalType & interval,typename interval_mutable_traits<IntervalType>::coordinate_type value)215 >::type low(IntervalType& interval,
216     typename interval_mutable_traits<IntervalType>::coordinate_type value) {
217   set(interval, LOW, value);
218 }
219 
220 struct y_i_high2 : gtl_yes {};
221 
222 template <typename IntervalType>
223 typename enable_if<
224   typename gtl_and<
225     y_i_high2,
226     typename is_mutable_interval_concept<
227       typename geometry_concept<IntervalType>::type
228     >::type
229   >::type,
230   void
high(IntervalType & interval,typename interval_mutable_traits<IntervalType>::coordinate_type value)231 >::type high(IntervalType& interval,
232     typename interval_mutable_traits<IntervalType>::coordinate_type value) {
233   set(interval, HIGH, value);
234 }
235 
236 struct y_i_equivalence : gtl_yes {};
237 
238 template <typename IntervalType1, typename IntervalType2>
239 typename enable_if<
240   typename gtl_and_3<
241     y_i_equivalence,
242     typename is_interval_concept<
243       typename geometry_concept<IntervalType1>::type
244     >::type,
245     typename is_interval_concept<
246       typename geometry_concept<IntervalType2>::type
247     >::type
248   >::type,
249   bool
equivalence(const IntervalType1 & interval1,const IntervalType2 & interval2)250 >::type equivalence(
251     const IntervalType1& interval1,
252     const IntervalType2& interval2) {
253   return (get(interval1, LOW) == get(interval2, LOW)) &&
254          (get(interval1, HIGH) == get(interval2, HIGH));
255 }
256 
257 struct y_i_contains : gtl_yes {};
258 
259 template <typename IntervalType>
260 typename enable_if<
261   typename gtl_and<
262     y_i_contains,
263     typename is_interval_concept<
264       typename geometry_concept<IntervalType>::type
265     >::type
266   >::type,
267   bool
contains(const IntervalType & interval,typename interval_coordinate_type<IntervalType>::type value,bool consider_touch=true)268 >::type contains(
269     const IntervalType& interval,
270     typename interval_coordinate_type<IntervalType>::type value,
271     bool consider_touch = true ) {
272   if (consider_touch) {
273     return value <= high(interval) && value >= low(interval);
274   } else {
275     return value < high(interval) && value > low(interval);
276   }
277 }
278 
279 struct y_i_contains2 : gtl_yes {};
280 
281 template <typename IntervalType1, typename IntervalType2>
282 typename enable_if<
283   typename gtl_and_3<
284     y_i_contains2,
285     typename is_interval_concept<
286       typename geometry_concept<IntervalType1>::type
287     >::type,
288     typename is_interval_concept<
289       typename geometry_concept<IntervalType2>::type
290     >::type
291   >::type,
292   bool
contains(const IntervalType1 & interval1,const IntervalType2 & interval2,bool consider_touch=true)293 >::type contains(
294     const IntervalType1& interval1,
295     const IntervalType2& interval2,
296     bool consider_touch = true) {
297   return contains(interval1, get(interval2, LOW), consider_touch) &&
298          contains(interval1, get(interval2, HIGH), consider_touch);
299 }
300 
301 struct y_i_center : gtl_yes {};
302 
303 template <typename IntervalType>
304 typename enable_if<
305   typename gtl_and<
306     y_i_center,
307     typename is_interval_concept<
308       typename geometry_concept<IntervalType>::type
309     >::type
310   >::type,
311   typename interval_coordinate_type<IntervalType>::type
center(const IntervalType & interval)312 >::type center(const IntervalType& interval) {
313   return (high(interval) + low(interval)) / 2;
314 }
315 
316 struct y_i_delta : gtl_yes {};
317 
318 template <typename IntervalType>
319 typename enable_if<
320   typename gtl_and<
321     y_i_delta,
322     typename is_interval_concept<
323       typename geometry_concept<IntervalType>::type
324     >::type
325   >::type,
326   typename interval_difference_type<IntervalType>::type
delta(const IntervalType & interval)327 >::type delta(const IntervalType& interval) {
328   typedef typename interval_difference_type<IntervalType>::type diff_type;
329   return static_cast<diff_type>(high(interval)) -
330          static_cast<diff_type>(low(interval));
331 }
332 
333 struct y_i_flip : gtl_yes {};
334 
335 template <typename IntervalType>
336 typename enable_if<
337   typename gtl_and<
338     y_i_flip,
339     typename is_mutable_interval_concept<
340       typename geometry_concept<IntervalType>::type
341     >::type
342   >::type,
flip(IntervalType & interval,typename interval_coordinate_type<IntervalType>::type axis=0)343 IntervalType>::type& flip(
344     IntervalType& interval,
345     typename interval_coordinate_type<IntervalType>::type axis = 0) {
346   typename interval_coordinate_type<IntervalType>::type newLow, newHigh;
347   newLow  = 2 * axis - high(interval);
348   newHigh = 2 * axis - low(interval);
349   low(interval, newLow);
350   high(interval, newHigh);
351   return interval;
352 }
353 
354 struct y_i_scale_up : gtl_yes {};
355 
356 template <typename IntervalType>
357 typename enable_if<
358   typename gtl_and<
359     y_i_scale_up,
360     typename is_mutable_interval_concept<
361       typename geometry_concept<IntervalType>::type
362     >::type
363   >::type,
364   IntervalType
scale_up(IntervalType & interval,typename interval_coordinate_type<IntervalType>::type factor)365 >::type& scale_up(
366     IntervalType& interval,
367     typename interval_coordinate_type<IntervalType>::type factor) {
368   typename interval_coordinate_type<IntervalType>::type newHigh =
369       high(interval) * factor;
370   low(interval, low(interval) * factor);
371   high(interval, (newHigh));
372   return interval;
373 }
374 
375 struct y_i_scale_down : gtl_yes {};
376 
377 template <typename IntervalType>
378 typename enable_if<
379   typename gtl_and<
380     y_i_scale_down,
381     typename is_mutable_interval_concept<
382       typename geometry_concept<IntervalType>::type
383     >::type
384   >::type,
385   IntervalType
scale_down(IntervalType & interval,typename interval_coordinate_type<IntervalType>::type factor)386 >::type& scale_down(
387     IntervalType& interval,
388     typename interval_coordinate_type<IntervalType>::type factor) {
389   typename interval_coordinate_type<IntervalType>::type newHigh =
390       high(interval) / factor;
391   low(interval, low(interval) / factor);
392   high(interval, (newHigh));
393   return interval;
394 }
395 
396 // TODO(asydorchuk): Deprecated.
397 struct y_i_scale : gtl_yes {};
398 
399 template <typename IntervalType>
400 typename enable_if<
401   typename gtl_and<
402     y_i_scale,
403     typename is_mutable_interval_concept<
404       typename geometry_concept<IntervalType>::type
405     >::type
406   >::type,
407   IntervalType
scale(IntervalType & interval,double factor)408 >::type& scale(IntervalType& interval, double factor) {
409   typedef typename interval_coordinate_type<IntervalType>::type Unit;
410   Unit newHigh = scaling_policy<Unit>::round(
411       static_cast<double>(high(interval)) * factor);
412   low(interval, scaling_policy<Unit>::round(
413       static_cast<double>(low(interval)) * factor));
414   high(interval, (newHigh));
415   return interval;
416 }
417 
418 struct y_i_move : gtl_yes {};
419 
420 template <typename IntervalType>
421 typename enable_if<
422   typename gtl_and<
423     y_i_move,
424     typename is_mutable_interval_concept<
425       typename geometry_concept<IntervalType>::type
426     >::type
427   >::type,
428   IntervalType
move(IntervalType & interval,typename interval_difference_type<IntervalType>::type displacement)429 >::type& move(
430     IntervalType& interval,
431     typename interval_difference_type<IntervalType>::type displacement) {
432   typedef typename interval_coordinate_type<IntervalType>::type ctype;
433   typedef typename coordinate_traits<ctype>::coordinate_difference Unit;
434   low(interval, static_cast<ctype>(
435       static_cast<Unit>(low(interval)) + displacement));
436   high(interval, static_cast<ctype>(
437       static_cast<Unit>(high(interval)) + displacement));
438   return interval;
439 }
440 
441 struct y_i_convolve : gtl_yes {};
442 
443 template <typename IntervalType>
444 typename enable_if<
445   typename gtl_and<
446     y_i_convolve,
447     typename is_mutable_interval_concept<
448       typename geometry_concept<IntervalType>::type
449     >::type
450   >::type,
451   IntervalType
convolve(IntervalType & interval,typename interval_coordinate_type<IntervalType>::type value)452 >::type& convolve(
453     IntervalType& interval,
454     typename interval_coordinate_type<IntervalType>::type value) {
455     typedef typename interval_coordinate_type<IntervalType>::type Unit;
456   Unit newLow  = low(interval) + value;
457   Unit newHigh = high(interval) + value;
458   low(interval, newLow);
459   high(interval, newHigh);
460   return interval;
461 }
462 
463 struct y_i_deconvolve : gtl_yes {};
464 
465 template <typename IntervalType>
466 typename enable_if<
467   typename gtl_and<
468     y_i_deconvolve,
469     typename is_mutable_interval_concept<
470       typename geometry_concept<IntervalType>::type
471     >::type
472   >::type,
473   IntervalType
deconvolve(IntervalType & interval,typename interval_coordinate_type<IntervalType>::type value)474 >::type& deconvolve(
475     IntervalType& interval,
476     typename interval_coordinate_type<IntervalType>::type value) {
477     typedef typename interval_coordinate_type<IntervalType>::type Unit;
478   Unit newLow  = low(interval) - value;
479   Unit newHigh = high(interval) - value;
480   low(interval, newLow);
481   high(interval, newHigh);
482   return interval;
483 }
484 
485 struct y_i_convolve2 : gtl_yes {};
486 
487 template <typename IntervalType1, typename IntervalType2>
488 typename enable_if<
489   typename gtl_and_3<
490     y_i_convolve2,
491     typename is_mutable_interval_concept<
492       typename geometry_concept<IntervalType1>::type
493     >::type,
494     typename is_interval_concept<
495       typename geometry_concept<IntervalType2>::type
496     >::type
497   >::type,
498   IntervalType1
convolve(IntervalType1 & lvalue,const IntervalType2 & rvalue)499 >::type& convolve(IntervalType1& lvalue, const IntervalType2& rvalue) {
500   typedef typename interval_coordinate_type<IntervalType1>::type Unit;
501   Unit newLow  = low(lvalue) + low(rvalue);
502   Unit newHigh = high(lvalue) + high(rvalue);
503   low(lvalue, newLow);
504   high(lvalue, newHigh);
505   return lvalue;
506 }
507 
508 struct y_i_deconvolve2 : gtl_yes {};
509 
510 template <typename IntervalType1, typename IntervalType2>
511 typename enable_if<
512   typename gtl_and_3<
513     y_i_deconvolve2,
514     typename is_mutable_interval_concept<
515       typename geometry_concept<IntervalType1>::type
516     >::type,
517     typename is_interval_concept<
518       typename geometry_concept<IntervalType2>::type
519     >::type
520   >::type,
521   IntervalType1
deconvolve(IntervalType1 & lvalue,const IntervalType2 & rvalue)522 >::type& deconvolve(IntervalType1& lvalue, const IntervalType2& rvalue) {
523   typedef typename interval_coordinate_type<IntervalType1>::type Unit;
524   Unit newLow  = low(lvalue) - low(rvalue);
525   Unit newHigh = high(lvalue) - high(rvalue);
526   low(lvalue, newLow);
527   high(lvalue, newHigh);
528   return lvalue;
529 }
530 
531 struct y_i_reconvolve : gtl_yes {};
532 
533 template <typename IntervalType1, typename IntervalType2>
534 typename enable_if<
535   typename gtl_and_3<
536     y_i_reconvolve,
537     typename is_mutable_interval_concept<
538       typename geometry_concept<IntervalType1>::type
539     >::type,
540     typename is_interval_concept<
541       typename geometry_concept<IntervalType2>::type
542     >::type
543   >::type,
544   IntervalType1
reflected_convolve(IntervalType1 & lvalue,const IntervalType2 & rvalue)545 >::type& reflected_convolve(
546     IntervalType1& lvalue,
547     const IntervalType2& rvalue) {
548   typedef typename interval_coordinate_type<IntervalType1>::type Unit;
549   Unit newLow  = low(lvalue) - high(rvalue);
550   Unit newHigh = high(lvalue) - low(rvalue);
551   low(lvalue, newLow);
552   high(lvalue, newHigh);
553   return lvalue;
554 }
555 
556 struct y_i_redeconvolve : gtl_yes {};
557 
558 template <typename IntervalType1, typename IntervalType2>
559 typename enable_if<
560   typename gtl_and_3<
561     y_i_redeconvolve,
562     typename is_mutable_interval_concept<
563       typename geometry_concept<IntervalType1>::type
564     >::type,
565     typename is_interval_concept<
566       typename geometry_concept<IntervalType2>::type
567     >::type
568   >::type,
569   IntervalType1
reflected_deconvolve(IntervalType1 & lvalue,const IntervalType2 & rvalue)570 >::type& reflected_deconvolve(
571     IntervalType1& lvalue,
572     const IntervalType2& rvalue) {
573   typedef typename interval_coordinate_type<IntervalType1>::type Unit;
574   Unit newLow  = low(lvalue)  + high(rvalue);
575   Unit newHigh = high(lvalue) + low(rvalue);
576   low(lvalue, newLow);
577   high(lvalue, newHigh);
578   return lvalue;
579 }
580 
581 struct y_i_e_dist1 : gtl_yes {};
582 
583 template <typename IntervalType>
584 typename enable_if<
585   typename gtl_and<y_i_e_dist1,
586     typename is_interval_concept<
587       typename geometry_concept<IntervalType>::type
588     >::type
589   >::type,
590   typename interval_difference_type<IntervalType>::type
euclidean_distance(const IntervalType & interval,typename interval_coordinate_type<IntervalType>::type position)591 >::type euclidean_distance(
592     const IntervalType& interval,
593     typename interval_coordinate_type<IntervalType>::type position) {
594   typedef typename interval_difference_type<IntervalType>::type Unit;
595   Unit dist[3] = {
596       0,
597       (Unit)low(interval) - (Unit)position,
598       (Unit)position - (Unit)high(interval)
599   };
600   return dist[(dist[1] > 0) + ((dist[2] > 0) << 1)];
601 }
602 
603 struct y_i_e_dist2 : gtl_yes {};
604 
605 template <typename IntervalType1, typename IntervalType2>
606 typename enable_if<
607   typename gtl_and_3<
608     y_i_e_dist2,
609     typename is_interval_concept<
610       typename geometry_concept<IntervalType1>::type
611     >::type,
612     typename is_interval_concept<
613       typename geometry_concept<IntervalType2>::type
614     >::type
615   >::type,
616   typename interval_difference_type<IntervalType1>::type
euclidean_distance(const IntervalType1 & interval1,const IntervalType2 & interval2)617 >::type euclidean_distance(
618     const IntervalType1& interval1,
619     const IntervalType2& interval2) {
620   typedef typename interval_difference_type<IntervalType1>::type Unit;
621   Unit dist[3] = {
622       0,
623       (Unit)low(interval1) - (Unit)high(interval2),
624       (Unit)low(interval2) - (Unit)high(interval1)
625   };
626   return dist[(dist[1] > 0) + ((dist[2] > 0) << 1)];
627 }
628 
629 struct y_i_e_intersects : gtl_yes {};
630 
631 template <typename IntervalType1, typename IntervalType2>
632 typename enable_if<
633   typename gtl_and_3<
634     y_i_e_intersects,
635     typename is_interval_concept<
636       typename geometry_concept<IntervalType1>::type
637     >::type,
638     typename is_interval_concept<
639       typename geometry_concept<IntervalType2>::type
640     >::type
641   >::type,
642   bool
intersects(const IntervalType1 & interval1,const IntervalType2 & interval2,bool consider_touch=true)643 >::type intersects(
644     const IntervalType1& interval1,
645     const IntervalType2& interval2,
646     bool consider_touch = true) {
647   return consider_touch ?
648       (low(interval1) <= high(interval2)) &&
649       (high(interval1) >= low(interval2)) :
650       (low(interval1) < high(interval2)) &&
651       (high(interval1) > low(interval2));
652 }
653 
654 struct y_i_e_bintersect : gtl_yes {};
655 
656 template <typename IntervalType1, typename IntervalType2>
657 typename enable_if<
658   typename gtl_and_3<
659     y_i_e_bintersect,
660     typename is_interval_concept<
661       typename geometry_concept<IntervalType1>::type
662     >::type,
663     typename is_interval_concept<
664       typename geometry_concept<IntervalType2>::type
665     >::type
666   >::type,
667   bool
boundaries_intersect(const IntervalType1 & interval1,const IntervalType2 & interval2,bool consider_touch=true)668 >::type boundaries_intersect(
669     const IntervalType1& interval1,
670     const IntervalType2& interval2,
671     bool consider_touch = true) {
672   return (contains(interval1, low(interval2), consider_touch) ||
673           contains(interval1, high(interval2), consider_touch)) &&
674          (contains(interval2, low(interval1), consider_touch) ||
675           contains(interval2, high(interval1), consider_touch));
676 }
677 
678 struct y_i_intersect : gtl_yes {};
679 
680 template <typename IntervalType1, typename IntervalType2>
681 typename enable_if<
682   typename gtl_and_3<
683     y_i_intersect,
684     typename is_mutable_interval_concept<
685       typename geometry_concept<IntervalType1>::type
686     >::type,
687     typename is_interval_concept<
688       typename geometry_concept<IntervalType2>::type
689     >::type
690   >::type,
691   bool
intersect(IntervalType1 & lvalue,const IntervalType2 & rvalue,bool consider_touch=true)692 >::type intersect(
693     IntervalType1& lvalue,
694     const IntervalType2& rvalue,
695     bool consider_touch = true) {
696   typedef typename interval_coordinate_type<IntervalType1>::type Unit;
697   Unit lowVal = (std::max)(low(lvalue), low(rvalue));
698   Unit highVal = (std::min)(high(lvalue), high(rvalue));
699   bool valid = consider_touch ? lowVal <= highVal : lowVal < highVal;
700   if (valid) {
701     low(lvalue, lowVal);
702     high(lvalue, highVal);
703   }
704   return valid;
705 }
706 
707 struct y_i_g_intersect : gtl_yes {};
708 
709 // TODO(asydorchuk): Deprecated.
710 template <typename IntervalType1, typename IntervalType2>
711 typename enable_if<
712   typename gtl_and_3<
713     y_i_g_intersect,
714     typename is_mutable_interval_concept<
715       typename geometry_concept<IntervalType1>::type
716     >::type,
717     typename is_interval_concept<
718       typename geometry_concept<IntervalType2>::type
719     >::type
720   >::type,
721   IntervalType1
generalized_intersect(IntervalType1 & lvalue,const IntervalType2 & rvalue)722 >::type& generalized_intersect(
723     IntervalType1& lvalue,
724     const IntervalType2& rvalue) {
725   typedef typename interval_coordinate_type<IntervalType1>::type Unit;
726   Unit coords[4] = {low(lvalue), high(lvalue), low(rvalue), high(rvalue)};
727   // TODO(asydorchuk): consider implementing faster sorting of small
728   // fixed length range.
729   polygon_sort(coords, coords+4);
730   low(lvalue, coords[1]);
731   high(lvalue, coords[2]);
732   return lvalue;
733 }
734 
735 struct y_i_abuts1 : gtl_yes {};
736 
737 template <typename IntervalType1, typename IntervalType2>
738 typename enable_if<
739   typename gtl_and_3<
740     y_i_abuts1,
741     typename is_interval_concept<
742       typename geometry_concept<IntervalType1>::type
743     >::type,
744     typename is_interval_concept<
745       typename geometry_concept<IntervalType2>::type
746     >::type
747   >::type,
748   bool
abuts(const IntervalType1 & interval1,const IntervalType2 & interval2,direction_1d dir)749 >::type abuts(
750     const IntervalType1& interval1,
751     const IntervalType2& interval2,
752     direction_1d dir) {
753   return dir.to_int() ? low(interval2) == high(interval1) :
754                         low(interval1) == high(interval2);
755 }
756 
757 struct y_i_abuts2 : gtl_yes {};
758 
759 template <typename IntervalType1, typename IntervalType2>
760 typename enable_if<
761   typename gtl_and_3<
762     y_i_abuts2,
763     typename is_interval_concept<
764       typename geometry_concept<IntervalType1>::type
765     >::type,
766     typename is_interval_concept<
767       typename geometry_concept<IntervalType2>::type
768     >::type
769   >::type,
770   bool
abuts(const IntervalType1 & interval1,const IntervalType2 & interval2)771 >::type abuts(
772     const IntervalType1& interval1,
773     const IntervalType2& interval2) {
774   return abuts(interval1, interval2, HIGH) ||
775          abuts(interval1, interval2, LOW);
776 }
777 
778 struct y_i_bloat : gtl_yes {};
779 
780 template <typename IntervalType>
781 typename enable_if<
782   typename gtl_and<
783     y_i_bloat,
784     typename is_mutable_interval_concept<
785       typename geometry_concept<IntervalType>::type
786     >::type
787   >::type,
788   IntervalType
bloat(IntervalType & interval,typename interval_coordinate_type<IntervalType>::type bloating)789 >::type& bloat(
790     IntervalType& interval,
791     typename interval_coordinate_type<IntervalType>::type bloating) {
792   low(interval, low(interval) - bloating);
793   high(interval, high(interval) + bloating);
794   return interval;
795 }
796 
797 struct y_i_bloat2 : gtl_yes {};
798 
799 template <typename IntervalType>
800 typename enable_if<
801   typename gtl_and<
802     y_i_bloat2,
803     typename is_mutable_interval_concept<
804       typename geometry_concept<IntervalType>::type
805     >::type
806   >::type,
807   IntervalType
bloat(IntervalType & interval,direction_1d dir,typename interval_coordinate_type<IntervalType>::type bloating)808 >::type& bloat(
809     IntervalType& interval,
810     direction_1d dir,
811     typename interval_coordinate_type<IntervalType>::type bloating) {
812   set(interval, dir, get(interval, dir) + dir.get_sign() * bloating);
813   return interval;
814 }
815 
816 struct y_i_shrink : gtl_yes {};
817 
818 template <typename IntervalType>
819 typename enable_if<
820   typename gtl_and<
821     y_i_shrink,
822     typename is_mutable_interval_concept<
823       typename geometry_concept<IntervalType>::type
824     >::type
825   >::type,
826   IntervalType
shrink(IntervalType & interval,typename interval_coordinate_type<IntervalType>::type shrinking)827 >::type& shrink(
828     IntervalType& interval,
829     typename interval_coordinate_type<IntervalType>::type shrinking) {
830   return bloat(interval, -shrinking);
831 }
832 
833 struct y_i_shrink2 : gtl_yes {};
834 
835 template <typename IntervalType>
836 typename enable_if<
837   typename gtl_and<
838     y_i_shrink2,
839     typename is_mutable_interval_concept<
840       typename geometry_concept<IntervalType>::type
841     >::type
842   >::type,
843   IntervalType
shrink(IntervalType & interval,direction_1d dir,typename interval_coordinate_type<IntervalType>::type shrinking)844 >::type& shrink(
845     IntervalType& interval,
846     direction_1d dir,
847     typename interval_coordinate_type<IntervalType>::type shrinking) {
848   return bloat(interval, dir, -shrinking);
849 }
850 
851 struct y_i_encompass : gtl_yes {};
852 
853 template <typename IntervalType1, typename IntervalType2>
854 typename enable_if<
855   typename gtl_and_3<
856     y_i_encompass,
857     typename is_mutable_interval_concept<
858       typename geometry_concept<IntervalType1>::type
859     >::type,
860     typename is_interval_concept<
861       typename geometry_concept<IntervalType2>::type
862     >::type
863   >::type,
864   bool
encompass(IntervalType1 & interval1,const IntervalType2 & interval2)865 >::type encompass(IntervalType1& interval1, const IntervalType2& interval2) {
866   bool retval = !contains(interval1, interval2, true);
867   low(interval1, (std::min)(low(interval1), low(interval2)));
868   high(interval1, (std::max)(high(interval1), high(interval2)));
869   return retval;
870 }
871 
872 struct y_i_encompass2 : gtl_yes {};
873 
874 template <typename IntervalType>
875 typename enable_if<
876   typename gtl_and<
877     y_i_encompass2,
878     typename is_mutable_interval_concept<
879       typename geometry_concept<IntervalType>::type
880     >::type
881   >::type,
882   bool
encompass(IntervalType & interval,typename interval_coordinate_type<IntervalType>::type value)883 >::type encompass(
884     IntervalType& interval,
885     typename interval_coordinate_type<IntervalType>::type value) {
886   bool retval = !contains(interval, value, true);
887   low(interval, (std::min)(low(interval), value));
888   high(interval, (std::max)(high(interval), value));
889   return retval;
890 }
891 
892 struct y_i_get_half : gtl_yes {};
893 
894 template <typename IntervalType>
895 typename enable_if<
896   typename gtl_and<
897     y_i_get_half,
898     typename is_mutable_interval_concept<
899       typename geometry_concept<IntervalType>::type
900     >::type
901   >::type,
902   IntervalType
get_half(const IntervalType & interval,direction_1d dir)903 >::type get_half(const IntervalType& interval, direction_1d dir) {
904   typedef typename interval_coordinate_type<IntervalType>::type Unit;
905   Unit c = (get(interval, LOW) + get(interval, HIGH)) / 2;
906   return construct<IntervalType>(
907       (dir == LOW) ? get(interval, LOW) : c,
908       (dir == LOW) ? c : get(interval, HIGH));
909 }
910 
911 struct y_i_join_with : gtl_yes {};
912 
913 template <typename IntervalType1, typename IntervalType2>
914 typename enable_if<
915   typename gtl_and_3<
916     y_i_join_with,
917     typename is_mutable_interval_concept<
918       typename geometry_concept<IntervalType1>::type
919     >::type,
920     typename is_interval_concept<
921       typename geometry_concept<IntervalType2>::type
922     >::type>::type,
923   bool
join_with(IntervalType1 & interval1,const IntervalType2 & interval2)924 >::type join_with(IntervalType1& interval1, const IntervalType2& interval2) {
925   if (abuts(interval1, interval2)) {
926     encompass(interval1, interval2);
927     return true;
928   }
929   return false;
930 }
931 }  // polygon
932 }  // boost
933 
934 #endif  // BOOST_POLYGON_INTERVAL_CONCEPT_HPP
935