1 // Boost.Polygon library interval_concept.hpp header file
3 // Copyright (c) Intel Corporation 2008.
4 // Copyright (c) 2008-2012 Simonson Lucanus.
5 // Copyright (c) 2012-2012 Andrii Sydorchuk.
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)
12 #ifndef BOOST_POLYGON_INTERVAL_CONCEPT_HPP
13 #define BOOST_POLYGON_INTERVAL_CONCEPT_HPP
15 #include "isotropy.hpp"
16 #include "interval_traits.hpp"
21 struct interval_concept {};
23 template <typename ConceptType>
24 struct is_interval_concept {
29 struct is_interval_concept<interval_concept> {
33 template <typename ConceptType>
34 struct is_mutable_interval_concept {
39 struct is_mutable_interval_concept<interval_concept> {
43 template <typename GeometryType, typename BoolType>
44 struct interval_coordinate_type_by_concept {
48 template <typename GeometryType>
49 struct interval_coordinate_type_by_concept<GeometryType, gtl_yes> {
50 typedef typename interval_traits<GeometryType>::coordinate_type type;
53 template <typename GeometryType>
54 struct interval_coordinate_type {
55 typedef typename interval_coordinate_type_by_concept<
57 typename is_interval_concept<
58 typename geometry_concept<GeometryType>::type
63 template <typename GeometryType, typename BoolType>
64 struct interval_difference_type_by_concept {
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;
75 template <typename GeometryType>
76 struct interval_difference_type {
77 typedef typename interval_difference_type_by_concept<
79 typename is_interval_concept<
80 typename geometry_concept<GeometryType>::type
85 struct y_i_get : gtl_yes {};
87 template <typename IntervalType>
91 typename is_interval_concept<
92 typename geometry_concept<IntervalType>::type
95 typename interval_coordinate_type<IntervalType>::type
96 >::type get(const IntervalType& interval, direction_1d dir) {
97 return interval_traits<IntervalType>::get(interval, dir);
100 struct y_i_set : gtl_yes {};
102 template <typename IntervalType>
106 typename is_mutable_interval_concept<
107 typename geometry_concept<IntervalType>::type
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);
116 struct y_i_construct : gtl_yes {};
118 template <typename IntervalType>
122 typename is_mutable_interval_concept<
123 typename geometry_concept<IntervalType>::type
128 typename interval_mutable_traits<IntervalType>::coordinate_type low,
129 typename interval_mutable_traits<IntervalType>::coordinate_type high) {
131 (std::swap)(low, high);
133 return interval_mutable_traits<IntervalType>::construct(low, high);
136 struct y_i_copy_construct : gtl_yes {};
138 template <typename IntervalType1, typename IntervalType2>
142 typename is_mutable_interval_concept<
143 typename geometry_concept<IntervalType1>::type
145 typename is_interval_concept<
146 typename geometry_concept<IntervalType2>::type
150 >::type copy_construct(const IntervalType2& interval) {
151 return construct<IntervalType1>(get(interval, LOW), get(interval, HIGH));
154 struct y_i_assign : gtl_yes {};
156 template <typename IntervalType1, typename IntervalType2>
160 typename is_mutable_interval_concept<
161 typename geometry_concept<IntervalType1>::type
163 typename is_interval_concept<
164 typename geometry_concept<IntervalType2>::type
168 >::type& assign(IntervalType1& lvalue, const IntervalType2& rvalue) {
169 set(lvalue, LOW, get(rvalue, LOW));
170 set(lvalue, HIGH, get(rvalue, HIGH));
174 struct y_i_low : gtl_yes {};
176 template <typename IntervalType>
180 typename is_interval_concept<
181 typename geometry_concept<IntervalType>::type
184 typename interval_coordinate_type<IntervalType>::type
185 >::type low(const IntervalType& interval) {
186 return get(interval, LOW);
189 struct y_i_high : gtl_yes {};
191 template <typename IntervalType>
195 typename is_interval_concept<
196 typename geometry_concept<IntervalType>::type
199 typename interval_coordinate_type<IntervalType>::type
200 >::type high(const IntervalType& interval) {
201 return get(interval, HIGH);
204 struct y_i_low2 : gtl_yes {};
206 template <typename IntervalType>
210 typename is_mutable_interval_concept<
211 typename geometry_concept<IntervalType>::type
215 >::type low(IntervalType& interval,
216 typename interval_mutable_traits<IntervalType>::coordinate_type value) {
217 set(interval, LOW, value);
220 struct y_i_high2 : gtl_yes {};
222 template <typename IntervalType>
226 typename is_mutable_interval_concept<
227 typename geometry_concept<IntervalType>::type
231 >::type high(IntervalType& interval,
232 typename interval_mutable_traits<IntervalType>::coordinate_type value) {
233 set(interval, HIGH, value);
236 struct y_i_equivalence : gtl_yes {};
238 template <typename IntervalType1, typename IntervalType2>
242 typename is_interval_concept<
243 typename geometry_concept<IntervalType1>::type
245 typename is_interval_concept<
246 typename geometry_concept<IntervalType2>::type
251 const IntervalType1& interval1,
252 const IntervalType2& interval2) {
253 return (get(interval1, LOW) == get(interval2, LOW)) &&
254 (get(interval1, HIGH) == get(interval2, HIGH));
257 struct y_i_contains : gtl_yes {};
259 template <typename IntervalType>
263 typename is_interval_concept<
264 typename geometry_concept<IntervalType>::type
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);
275 return value < high(interval) && value > low(interval);
279 struct y_i_contains2 : gtl_yes {};
281 template <typename IntervalType1, typename IntervalType2>
285 typename is_interval_concept<
286 typename geometry_concept<IntervalType1>::type
288 typename is_interval_concept<
289 typename geometry_concept<IntervalType2>::type
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);
301 struct y_i_center : gtl_yes {};
303 template <typename IntervalType>
307 typename is_interval_concept<
308 typename geometry_concept<IntervalType>::type
311 typename interval_coordinate_type<IntervalType>::type
312 >::type center(const IntervalType& interval) {
313 return (high(interval) + low(interval)) / 2;
316 struct y_i_delta : gtl_yes {};
318 template <typename IntervalType>
322 typename is_interval_concept<
323 typename geometry_concept<IntervalType>::type
326 typename interval_difference_type<IntervalType>::type
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));
333 struct y_i_flip : gtl_yes {};
335 template <typename IntervalType>
339 typename is_mutable_interval_concept<
340 typename geometry_concept<IntervalType>::type
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);
354 struct y_i_scale_up : gtl_yes {};
356 template <typename IntervalType>
360 typename is_mutable_interval_concept<
361 typename geometry_concept<IntervalType>::type
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));
375 struct y_i_scale_down : gtl_yes {};
377 template <typename IntervalType>
381 typename is_mutable_interval_concept<
382 typename geometry_concept<IntervalType>::type
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));
396 // TODO(asydorchuk): Deprecated.
397 struct y_i_scale : gtl_yes {};
399 template <typename IntervalType>
403 typename is_mutable_interval_concept<
404 typename geometry_concept<IntervalType>::type
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));
418 struct y_i_move : gtl_yes {};
420 template <typename IntervalType>
424 typename is_mutable_interval_concept<
425 typename geometry_concept<IntervalType>::type
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));
441 struct y_i_convolve : gtl_yes {};
443 template <typename IntervalType>
447 typename is_mutable_interval_concept<
448 typename geometry_concept<IntervalType>::type
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);
463 struct y_i_deconvolve : gtl_yes {};
465 template <typename IntervalType>
469 typename is_mutable_interval_concept<
470 typename geometry_concept<IntervalType>::type
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);
485 struct y_i_convolve2 : gtl_yes {};
487 template <typename IntervalType1, typename IntervalType2>
491 typename is_mutable_interval_concept<
492 typename geometry_concept<IntervalType1>::type
494 typename is_interval_concept<
495 typename geometry_concept<IntervalType2>::type
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);
504 high(lvalue, newHigh);
508 struct y_i_deconvolve2 : gtl_yes {};
510 template <typename IntervalType1, typename IntervalType2>
514 typename is_mutable_interval_concept<
515 typename geometry_concept<IntervalType1>::type
517 typename is_interval_concept<
518 typename geometry_concept<IntervalType2>::type
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);
527 high(lvalue, newHigh);
531 struct y_i_reconvolve : gtl_yes {};
533 template <typename IntervalType1, typename IntervalType2>
537 typename is_mutable_interval_concept<
538 typename geometry_concept<IntervalType1>::type
540 typename is_interval_concept<
541 typename geometry_concept<IntervalType2>::type
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);
552 high(lvalue, newHigh);
556 struct y_i_redeconvolve : gtl_yes {};
558 template <typename IntervalType1, typename IntervalType2>
562 typename is_mutable_interval_concept<
563 typename geometry_concept<IntervalType1>::type
565 typename is_interval_concept<
566 typename geometry_concept<IntervalType2>::type
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);
577 high(lvalue, newHigh);
581 struct y_i_e_dist1 : gtl_yes {};
583 template <typename IntervalType>
585 typename gtl_and<y_i_e_dist1,
586 typename is_interval_concept<
587 typename geometry_concept<IntervalType>::type
590 typename interval_difference_type<IntervalType>::type
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;
597 (Unit)low(interval) - (Unit)position,
598 (Unit)position - (Unit)high(interval)
600 return dist[(dist[1] > 0) + ((dist[2] > 0) << 1)];
603 struct y_i_e_dist2 : gtl_yes {};
605 template <typename IntervalType1, typename IntervalType2>
609 typename is_interval_concept<
610 typename geometry_concept<IntervalType1>::type
612 typename is_interval_concept<
613 typename geometry_concept<IntervalType2>::type
616 typename interval_difference_type<IntervalType1>::type
617 >::type euclidean_distance(
618 const IntervalType1& interval1,
619 const IntervalType2& interval2) {
620 typedef typename interval_difference_type<IntervalType1>::type Unit;
623 (Unit)low(interval1) - (Unit)high(interval2),
624 (Unit)low(interval2) - (Unit)high(interval1)
626 return dist[(dist[1] > 0) + ((dist[2] > 0) << 1)];
629 struct y_i_e_intersects : gtl_yes {};
631 template <typename IntervalType1, typename IntervalType2>
635 typename is_interval_concept<
636 typename geometry_concept<IntervalType1>::type
638 typename is_interval_concept<
639 typename geometry_concept<IntervalType2>::type
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));
654 struct y_i_e_bintersect : gtl_yes {};
656 template <typename IntervalType1, typename IntervalType2>
660 typename is_interval_concept<
661 typename geometry_concept<IntervalType1>::type
663 typename is_interval_concept<
664 typename geometry_concept<IntervalType2>::type
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));
678 struct y_i_intersect : gtl_yes {};
680 template <typename IntervalType1, typename IntervalType2>
684 typename is_mutable_interval_concept<
685 typename geometry_concept<IntervalType1>::type
687 typename is_interval_concept<
688 typename geometry_concept<IntervalType2>::type
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;
702 high(lvalue, highVal);
707 struct y_i_g_intersect : gtl_yes {};
709 // TODO(asydorchuk): Deprecated.
710 template <typename IntervalType1, typename IntervalType2>
714 typename is_mutable_interval_concept<
715 typename geometry_concept<IntervalType1>::type
717 typename is_interval_concept<
718 typename geometry_concept<IntervalType2>::type
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]);
735 struct y_i_abuts1 : gtl_yes {};
737 template <typename IntervalType1, typename IntervalType2>
741 typename is_interval_concept<
742 typename geometry_concept<IntervalType1>::type
744 typename is_interval_concept<
745 typename geometry_concept<IntervalType2>::type
750 const IntervalType1& interval1,
751 const IntervalType2& interval2,
753 return dir.to_int() ? low(interval2) == high(interval1) :
754 low(interval1) == high(interval2);
757 struct y_i_abuts2 : gtl_yes {};
759 template <typename IntervalType1, typename IntervalType2>
763 typename is_interval_concept<
764 typename geometry_concept<IntervalType1>::type
766 typename is_interval_concept<
767 typename geometry_concept<IntervalType2>::type
772 const IntervalType1& interval1,
773 const IntervalType2& interval2) {
774 return abuts(interval1, interval2, HIGH) ||
775 abuts(interval1, interval2, LOW);
778 struct y_i_bloat : gtl_yes {};
780 template <typename IntervalType>
784 typename is_mutable_interval_concept<
785 typename geometry_concept<IntervalType>::type
790 IntervalType& interval,
791 typename interval_coordinate_type<IntervalType>::type bloating) {
792 low(interval, low(interval) - bloating);
793 high(interval, high(interval) + bloating);
797 struct y_i_bloat2 : gtl_yes {};
799 template <typename IntervalType>
803 typename is_mutable_interval_concept<
804 typename geometry_concept<IntervalType>::type
809 IntervalType& interval,
811 typename interval_coordinate_type<IntervalType>::type bloating) {
812 set(interval, dir, get(interval, dir) + dir.get_sign() * bloating);
816 struct y_i_shrink : gtl_yes {};
818 template <typename IntervalType>
822 typename is_mutable_interval_concept<
823 typename geometry_concept<IntervalType>::type
828 IntervalType& interval,
829 typename interval_coordinate_type<IntervalType>::type shrinking) {
830 return bloat(interval, -shrinking);
833 struct y_i_shrink2 : gtl_yes {};
835 template <typename IntervalType>
839 typename is_mutable_interval_concept<
840 typename geometry_concept<IntervalType>::type
845 IntervalType& interval,
847 typename interval_coordinate_type<IntervalType>::type shrinking) {
848 return bloat(interval, dir, -shrinking);
851 struct y_i_encompass : gtl_yes {};
853 template <typename IntervalType1, typename IntervalType2>
857 typename is_mutable_interval_concept<
858 typename geometry_concept<IntervalType1>::type
860 typename is_interval_concept<
861 typename geometry_concept<IntervalType2>::type
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)));
872 struct y_i_encompass2 : gtl_yes {};
874 template <typename IntervalType>
878 typename is_mutable_interval_concept<
879 typename geometry_concept<IntervalType>::type
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));
892 struct y_i_get_half : gtl_yes {};
894 template <typename IntervalType>
898 typename is_mutable_interval_concept<
899 typename geometry_concept<IntervalType>::type
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));
911 struct y_i_join_with : gtl_yes {};
913 template <typename IntervalType1, typename IntervalType2>
917 typename is_mutable_interval_concept<
918 typename geometry_concept<IntervalType1>::type
920 typename is_interval_concept<
921 typename geometry_concept<IntervalType2>::type
924 >::type join_with(IntervalType1& interval1, const IntervalType2& interval2) {
925 if (abuts(interval1, interval2)) {
926 encompass(interval1, interval2);
934 #endif // BOOST_POLYGON_INTERVAL_CONCEPT_HPP