boost/polygon/interval_concept.hpp

0001 // Boost.Polygon library interval_concept.hpp header file
0002
0003 // Copyright (c) Intel Corporation 2008.
0004 // Copyright (c) 2008-2012 Simonson Lucanus.
0005 // Copyright (c) 2012-2012 Andrii Sydorchuk.
0006
0007 // See http://www.boost.org for updates, documentation, and revision history.
0008 // Use, modification and distribution is subject to the Boost Software License,
0009 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0010 // http://www.boost.org/LICENSE_1_0.txt)
0011
0012 #ifndef BOOST_POLYGON_INTERVAL_CONCEPT_HPP
0013 #define BOOST_POLYGON_INTERVAL_CONCEPT_HPP
0014
0015 #include "isotropy.hpp"
0016 #include "interval_traits.hpp"
0017
0018 namespace boost {
0019 namespace polygon {
0020
0021 struct interval_concept {};
0022
0023 template <typename ConceptType>
0024 struct is_interval_concept {
0025   typedef gtl_no type;
0026 };
0027
0028 template <>
0029 struct is_interval_concept<interval_concept> {
0030   typedef gtl_yes type;
0031 };
0032
0033 template <typename ConceptType>
0034 struct is_mutable_interval_concept {
0035   typedef gtl_no type;
0036 };
0037
0038 template <>
0039 struct is_mutable_interval_concept<interval_concept> {
0040   typedef gtl_yes type;
0041 };
0042
0043 template <typename GeometryType, typename BoolType>
0044 struct interval_coordinate_type_by_concept {
0045   typedef void type;
0046 };
0047
0048 template <typename GeometryType>
0049 struct interval_coordinate_type_by_concept<GeometryType, gtl_yes> {
0050   typedef typename interval_traits<GeometryType>::coordinate_type type;
0051 };
0052
0053 template <typename GeometryType>
0054 struct interval_coordinate_type {
0055   typedef typename interval_coordinate_type_by_concept<
0056     GeometryType,
0057     typename is_interval_concept<
0058       typename geometry_concept<GeometryType>::type
0059     >::type
0060   >::type type;
0061 };
0062
0063 template <typename GeometryType, typename BoolType>
0064 struct interval_difference_type_by_concept {
0065   typedef void type;
0066 };
0067
0068 template <typename GeometryType>
0069 struct interval_difference_type_by_concept<GeometryType, gtl_yes> {
0070   typedef typename coordinate_traits<
0071     typename interval_traits<GeometryType>::coordinate_type
0072   >::coordinate_difference type;
0073 };
0074
0075 template <typename GeometryType>
0076 struct interval_difference_type {
0077   typedef typename interval_difference_type_by_concept<
0078     GeometryType,
0079     typename is_interval_concept<
0080       typename geometry_concept<GeometryType>::type
0081     >::type
0082   >::type type;
0083 };
0084
0085 struct y_i_get : gtl_yes {};
0086
0087 template <typename IntervalType>
0088 typename enable_if<
0089   typename gtl_and<
0090     y_i_get,
0091     typename is_interval_concept<
0092       typename geometry_concept<IntervalType>::type
0093     >::type
0094   >::type,
0095   typename interval_coordinate_type<IntervalType>::type
0096 >::type get(const IntervalType& interval, direction_1d dir) {
0097   return interval_traits<IntervalType>::get(interval, dir);
0098 }
0099
0100 struct y_i_set : gtl_yes {};
0101
0102 template <typename IntervalType>
0103 typename enable_if<
0104   typename gtl_and<
0105     y_i_set,
0106     typename is_mutable_interval_concept<
0107       typename geometry_concept<IntervalType>::type
0108     >::type
0109   >::type,
0110   void
0111 >::type set(IntervalType& interval, direction_1d dir,
0112     typename interval_mutable_traits<IntervalType>::coordinate_type value) {
0113   interval_mutable_traits<IntervalType>::set(interval, dir, value);
0114 }
0115
0116 struct y_i_construct : gtl_yes {};
0117
0118 template <typename IntervalType>
0119 typename enable_if<
0120   typename gtl_and<
0121     y_i_construct,
0122     typename is_mutable_interval_concept<
0123       typename geometry_concept<IntervalType>::type
0124     >::type
0125   >::type,
0126   IntervalType
0127 >::type construct(
0128     typename interval_mutable_traits<IntervalType>::coordinate_type low,
0129     typename interval_mutable_traits<IntervalType>::coordinate_type high) {
0130   if (low > high) {
0131     (std::swap)(low, high);
0132   }
0133   return interval_mutable_traits<IntervalType>::construct(low, high);
0134 }
0135
0136 struct y_i_copy_construct : gtl_yes {};
0137
0138 template <typename IntervalType1, typename IntervalType2>
0139 typename enable_if<
0140   typename gtl_and_3<
0141     y_i_copy_construct,
0142     typename is_mutable_interval_concept<
0143       typename geometry_concept<IntervalType1>::type
0144     >::type,
0145     typename is_interval_concept<
0146       typename geometry_concept<IntervalType2>::type
0147     >::type
0148   >::type,
0149   IntervalType1
0150 >::type copy_construct(const IntervalType2& interval) {
0151   return construct<IntervalType1>(get(interval, LOW), get(interval, HIGH));
0152 }
0153
0154 struct y_i_assign : gtl_yes {};
0155
0156 template <typename IntervalType1, typename IntervalType2>
0157 typename enable_if<
0158   typename gtl_and_3<
0159     y_i_assign,
0160     typename is_mutable_interval_concept<
0161       typename geometry_concept<IntervalType1>::type
0162     >::type,
0163     typename is_interval_concept<
0164       typename geometry_concept<IntervalType2>::type
0165     >::type
0166   >::type,
0167   IntervalType1
0168 >::type& assign(IntervalType1& lvalue, const IntervalType2& rvalue) {
0169   set(lvalue, LOW, get(rvalue, LOW));
0170   set(lvalue, HIGH, get(rvalue, HIGH));
0171   return lvalue;
0172 }
0173
0174 struct y_i_low : gtl_yes {};
0175
0176 template <typename IntervalType>
0177 typename enable_if<
0178   typename gtl_and<
0179     y_i_low,
0180     typename is_interval_concept<
0181       typename geometry_concept<IntervalType>::type
0182     >::type
0183   >::type,
0184   typename interval_coordinate_type<IntervalType>::type
0185 >::type low(const IntervalType& interval) {
0186   return get(interval, LOW);
0187 }
0188
0189 struct y_i_high : gtl_yes {};
0190
0191 template <typename IntervalType>
0192 typename enable_if<
0193   typename gtl_and<
0194     y_i_high,
0195     typename is_interval_concept<
0196       typename geometry_concept<IntervalType>::type
0197     >::type
0198   >::type,
0199   typename interval_coordinate_type<IntervalType>::type
0200 >::type high(const IntervalType& interval) {
0201   return get(interval, HIGH);
0202 }
0203
0204 struct y_i_low2 : gtl_yes {};
0205
0206 template <typename IntervalType>
0207 typename enable_if<
0208   typename gtl_and<
0209     y_i_low2,
0210     typename is_mutable_interval_concept<
0211       typename geometry_concept<IntervalType>::type
0212     >::type
0213   >::type,
0214   void
0215 >::type low(IntervalType& interval,
0216     typename interval_mutable_traits<IntervalType>::coordinate_type value) {
0217   set(interval, LOW, value);
0218 }
0219
0220 struct y_i_high2 : gtl_yes {};
0221
0222 template <typename IntervalType>
0223 typename enable_if<
0224   typename gtl_and<
0225     y_i_high2,
0226     typename is_mutable_interval_concept<
0227       typename geometry_concept<IntervalType>::type
0228     >::type
0229   >::type,
0230   void
0231 >::type high(IntervalType& interval,
0232     typename interval_mutable_traits<IntervalType>::coordinate_type value) {
0233   set(interval, HIGH, value);
0234 }
0235
0236 struct y_i_equivalence : gtl_yes {};
0237
0238 template <typename IntervalType1, typename IntervalType2>
0239 typename enable_if<
0240   typename gtl_and_3<
0241     y_i_equivalence,
0242     typename is_interval_concept<
0243       typename geometry_concept<IntervalType1>::type
0244     >::type,
0245     typename is_interval_concept<
0246       typename geometry_concept<IntervalType2>::type
0247     >::type
0248   >::type,
0249   bool
0250 >::type equivalence(
0251     const IntervalType1& interval1,
0252     const IntervalType2& interval2) {
0253   return (get(interval1, LOW) == get(interval2, LOW)) &&
0254          (get(interval1, HIGH) == get(interval2, HIGH));
0255 }
0256
0257 struct y_i_contains : gtl_yes {};
0258
0259 template <typename IntervalType>
0260 typename enable_if<
0261   typename gtl_and<
0262     y_i_contains,
0263     typename is_interval_concept<
0264       typename geometry_concept<IntervalType>::type
0265     >::type
0266   >::type,
0267   bool
0268 >::type contains(
0269     const IntervalType& interval,
0270     typename interval_coordinate_type<IntervalType>::type value,
0271     bool consider_touch = true ) {
0272   if (consider_touch) {
0273     return value <= high(interval) && value >= low(interval);
0274   } else {
0275     return value < high(interval) && value > low(interval);
0276   }
0277 }
0278
0279 struct y_i_contains2 : gtl_yes {};
0280
0281 template <typename IntervalType1, typename IntervalType2>
0282 typename enable_if<
0283   typename gtl_and_3<
0284     y_i_contains2,
0285     typename is_interval_concept<
0286       typename geometry_concept<IntervalType1>::type
0287     >::type,
0288     typename is_interval_concept<
0289       typename geometry_concept<IntervalType2>::type
0290     >::type
0291   >::type,
0292   bool
0293 >::type contains(
0294     const IntervalType1& interval1,
0295     const IntervalType2& interval2,
0296     bool consider_touch = true) {
0297   return contains(interval1, get(interval2, LOW), consider_touch) &&
0298          contains(interval1, get(interval2, HIGH), consider_touch);
0299 }
0300
0301 struct y_i_center : gtl_yes {};
0302
0303 template <typename IntervalType>
0304 typename enable_if<
0305   typename gtl_and<
0306     y_i_center,
0307     typename is_interval_concept<
0308       typename geometry_concept<IntervalType>::type
0309     >::type
0310   >::type,
0311   typename interval_coordinate_type<IntervalType>::type
0312 >::type center(const IntervalType& interval) {
0313   return (high(interval) + low(interval)) / 2;
0314 }
0315
0316 struct y_i_delta : gtl_yes {};
0317
0318 template <typename IntervalType>
0319 typename enable_if<
0320   typename gtl_and<
0321     y_i_delta,
0322     typename is_interval_concept<
0323       typename geometry_concept<IntervalType>::type
0324     >::type
0325   >::type,
0326   typename interval_difference_type<IntervalType>::type
0327 >::type delta(const IntervalType& interval) {
0328   typedef typename interval_difference_type<IntervalType>::type diff_type;
0329   return static_cast<diff_type>(high(interval)) -
0330          static_cast<diff_type>(low(interval));
0331 }
0332
0333 struct y_i_flip : gtl_yes {};
0334
0335 template <typename IntervalType>
0336 typename enable_if<
0337   typename gtl_and<
0338     y_i_flip,
0339     typename is_mutable_interval_concept<
0340       typename geometry_concept<IntervalType>::type
0341     >::type
0342   >::type,
0343 IntervalType>::type& flip(
0344     IntervalType& interval,
0345     typename interval_coordinate_type<IntervalType>::type axis = 0) {
0346   typename interval_coordinate_type<IntervalType>::type newLow, newHigh;
0347   newLow  = 2 * axis - high(interval);
0348   newHigh = 2 * axis - low(interval);
0349   low(interval, newLow);
0350   high(interval, newHigh);
0351   return interval;
0352 }
0353
0354 struct y_i_scale_up : gtl_yes {};
0355
0356 template <typename IntervalType>
0357 typename enable_if<
0358   typename gtl_and<
0359     y_i_scale_up,
0360     typename is_mutable_interval_concept<
0361       typename geometry_concept<IntervalType>::type
0362     >::type
0363   >::type,
0364   IntervalType
0365 >::type& scale_up(
0366     IntervalType& interval,
0367     typename interval_coordinate_type<IntervalType>::type factor) {
0368   typename interval_coordinate_type<IntervalType>::type newHigh =
0369       high(interval) * factor;
0370   low(interval, low(interval) * factor);
0371   high(interval, (newHigh));
0372   return interval;
0373 }
0374
0375 struct y_i_scale_down : gtl_yes {};
0376
0377 template <typename IntervalType>
0378 typename enable_if<
0379   typename gtl_and<
0380     y_i_scale_down,
0381     typename is_mutable_interval_concept<
0382       typename geometry_concept<IntervalType>::type
0383     >::type
0384   >::type,
0385   IntervalType
0386 >::type& scale_down(
0387     IntervalType& interval,
0388     typename interval_coordinate_type<IntervalType>::type factor) {
0389   typename interval_coordinate_type<IntervalType>::type newHigh =
0390       high(interval) / factor;
0391   low(interval, low(interval) / factor);
0392   high(interval, (newHigh));
0393   return interval;
0394 }
0395
0396 // TODO(asydorchuk): Deprecated.
0397 struct y_i_scale : gtl_yes {};
0398
0399 template <typename IntervalType>
0400 typename enable_if<
0401   typename gtl_and<
0402     y_i_scale,
0403     typename is_mutable_interval_concept<
0404       typename geometry_concept<IntervalType>::type
0405     >::type
0406   >::type,
0407   IntervalType
0408 >::type& scale(IntervalType& interval, double factor) {
0409   typedef typename interval_coordinate_type<IntervalType>::type Unit;
0410   Unit newHigh = scaling_policy<Unit>::round(
0411       static_cast<double>(high(interval)) * factor);
0412   low(interval, scaling_policy<Unit>::round(
0413       static_cast<double>(low(interval)) * factor));
0414   high(interval, (newHigh));
0415   return interval;
0416 }
0417
0418 struct y_i_move : gtl_yes {};
0419
0420 template <typename IntervalType>
0421 typename enable_if<
0422   typename gtl_and<
0423     y_i_move,
0424     typename is_mutable_interval_concept<
0425       typename geometry_concept<IntervalType>::type
0426     >::type
0427   >::type,
0428   IntervalType
0429 >::type& move(
0430     IntervalType& interval,
0431     typename interval_difference_type<IntervalType>::type displacement) {
0432   typedef typename interval_coordinate_type<IntervalType>::type ctype;
0433   typedef typename coordinate_traits<ctype>::coordinate_difference Unit;
0434   low(interval, static_cast<ctype>(
0435       static_cast<Unit>(low(interval)) + displacement));
0436   high(interval, static_cast<ctype>(
0437       static_cast<Unit>(high(interval)) + displacement));
0438   return interval;
0439 }
0440
0441 struct y_i_convolve : gtl_yes {};
0442
0443 template <typename IntervalType>
0444 typename enable_if<
0445   typename gtl_and<
0446     y_i_convolve,
0447     typename is_mutable_interval_concept<
0448       typename geometry_concept<IntervalType>::type
0449     >::type
0450   >::type,
0451   IntervalType
0452 >::type& convolve(
0453     IntervalType& interval,
0454     typename interval_coordinate_type<IntervalType>::type value) {
0455     typedef typename interval_coordinate_type<IntervalType>::type Unit;
0456   Unit newLow  = low(interval) + value;
0457   Unit newHigh = high(interval) + value;
0458   low(interval, newLow);
0459   high(interval, newHigh);
0460   return interval;
0461 }
0462
0463 struct y_i_deconvolve : gtl_yes {};
0464
0465 template <typename IntervalType>
0466 typename enable_if<
0467   typename gtl_and<
0468     y_i_deconvolve,
0469     typename is_mutable_interval_concept<
0470       typename geometry_concept<IntervalType>::type
0471     >::type
0472   >::type,
0473   IntervalType
0474 >::type& deconvolve(
0475     IntervalType& interval,
0476     typename interval_coordinate_type<IntervalType>::type value) {
0477     typedef typename interval_coordinate_type<IntervalType>::type Unit;
0478   Unit newLow  = low(interval) - value;
0479   Unit newHigh = high(interval) - value;
0480   low(interval, newLow);
0481   high(interval, newHigh);
0482   return interval;
0483 }
0484
0485 struct y_i_convolve2 : gtl_yes {};
0486
0487 template <typename IntervalType1, typename IntervalType2>
0488 typename enable_if<
0489   typename gtl_and_3<
0490     y_i_convolve2,
0491     typename is_mutable_interval_concept<
0492       typename geometry_concept<IntervalType1>::type
0493     >::type,
0494     typename is_interval_concept<
0495       typename geometry_concept<IntervalType2>::type
0496     >::type
0497   >::type,
0498   IntervalType1
0499 >::type& convolve(IntervalType1& lvalue, const IntervalType2& rvalue) {
0500   typedef typename interval_coordinate_type<IntervalType1>::type Unit;
0501   Unit newLow  = low(lvalue) + low(rvalue);
0502   Unit newHigh = high(lvalue) + high(rvalue);
0503   low(lvalue, newLow);
0504   high(lvalue, newHigh);
0505   return lvalue;
0506 }
0507
0508 struct y_i_deconvolve2 : gtl_yes {};
0509
0510 template <typename IntervalType1, typename IntervalType2>
0511 typename enable_if<
0512   typename gtl_and_3<
0513     y_i_deconvolve2,
0514     typename is_mutable_interval_concept<
0515       typename geometry_concept<IntervalType1>::type
0516     >::type,
0517     typename is_interval_concept<
0518       typename geometry_concept<IntervalType2>::type
0519     >::type
0520   >::type,
0521   IntervalType1
0522 >::type& deconvolve(IntervalType1& lvalue, const IntervalType2& rvalue) {
0523   typedef typename interval_coordinate_type<IntervalType1>::type Unit;
0524   Unit newLow  = low(lvalue) - low(rvalue);
0525   Unit newHigh = high(lvalue) - high(rvalue);
0526   low(lvalue, newLow);
0527   high(lvalue, newHigh);
0528   return lvalue;
0529 }
0530
0531 struct y_i_reconvolve : gtl_yes {};
0532
0533 template <typename IntervalType1, typename IntervalType2>
0534 typename enable_if<
0535   typename gtl_and_3<
0536     y_i_reconvolve,
0537     typename is_mutable_interval_concept<
0538       typename geometry_concept<IntervalType1>::type
0539     >::type,
0540     typename is_interval_concept<
0541       typename geometry_concept<IntervalType2>::type
0542     >::type
0543   >::type,
0544   IntervalType1
0545 >::type& reflected_convolve(
0546     IntervalType1& lvalue,
0547     const IntervalType2& rvalue) {
0548   typedef typename interval_coordinate_type<IntervalType1>::type Unit;
0549   Unit newLow  = low(lvalue) - high(rvalue);
0550   Unit newHigh = high(lvalue) - low(rvalue);
0551   low(lvalue, newLow);
0552   high(lvalue, newHigh);
0553   return lvalue;
0554 }
0555
0556 struct y_i_redeconvolve : gtl_yes {};
0557
0558 template <typename IntervalType1, typename IntervalType2>
0559 typename enable_if<
0560   typename gtl_and_3<
0561     y_i_redeconvolve,
0562     typename is_mutable_interval_concept<
0563       typename geometry_concept<IntervalType1>::type
0564     >::type,
0565     typename is_interval_concept<
0566       typename geometry_concept<IntervalType2>::type
0567     >::type
0568   >::type,
0569   IntervalType1
0570 >::type& reflected_deconvolve(
0571     IntervalType1& lvalue,
0572     const IntervalType2& rvalue) {
0573   typedef typename interval_coordinate_type<IntervalType1>::type Unit;
0574   Unit newLow  = low(lvalue)  + high(rvalue);
0575   Unit newHigh = high(lvalue) + low(rvalue);
0576   low(lvalue, newLow);
0577   high(lvalue, newHigh);
0578   return lvalue;
0579 }
0580
0581 struct y_i_e_dist1 : gtl_yes {};
0582
0583 template <typename IntervalType>
0584 typename enable_if<
0585   typename gtl_and<y_i_e_dist1,
0586     typename is_interval_concept<
0587       typename geometry_concept<IntervalType>::type
0588     >::type
0589   >::type,
0590   typename interval_difference_type<IntervalType>::type
0591 >::type euclidean_distance(
0592     const IntervalType& interval,
0593     typename interval_coordinate_type<IntervalType>::type position) {
0594   typedef typename interval_difference_type<IntervalType>::type Unit;
0595   Unit dist[3] = {
0596       0,
0597       (Unit)low(interval) - (Unit)position,
0598       (Unit)position - (Unit)high(interval)
0599   };
0600   return dist[(dist[1] > 0) + ((dist[2] > 0) << 1)];
0601 }
0602
0603 struct y_i_e_dist2 : gtl_yes {};
0604
0605 template <typename IntervalType1, typename IntervalType2>
0606 typename enable_if<
0607   typename gtl_and_3<
0608     y_i_e_dist2,
0609     typename is_interval_concept<
0610       typename geometry_concept<IntervalType1>::type
0611     >::type,
0612     typename is_interval_concept<
0613       typename geometry_concept<IntervalType2>::type
0614     >::type
0615   >::type,
0616   typename interval_difference_type<IntervalType1>::type
0617 >::type euclidean_distance(
0618     const IntervalType1& interval1,
0619     const IntervalType2& interval2) {
0620   typedef typename interval_difference_type<IntervalType1>::type Unit;
0621   Unit dist[3] = {
0622       0,
0623       (Unit)low(interval1) - (Unit)high(interval2),
0624       (Unit)low(interval2) - (Unit)high(interval1)
0625   };
0626   return dist[(dist[1] > 0) + ((dist[2] > 0) << 1)];
0627 }
0628
0629 struct y_i_e_intersects : gtl_yes {};
0630
0631 template <typename IntervalType1, typename IntervalType2>
0632 typename enable_if<
0633   typename gtl_and_3<
0634     y_i_e_intersects,
0635     typename is_interval_concept<
0636       typename geometry_concept<IntervalType1>::type
0637     >::type,
0638     typename is_interval_concept<
0639       typename geometry_concept<IntervalType2>::type
0640     >::type
0641   >::type,
0642   bool
0643 >::type intersects(
0644     const IntervalType1& interval1,
0645     const IntervalType2& interval2,
0646     bool consider_touch = true) {
0647   return consider_touch ?
0648       (low(interval1) <= high(interval2)) &&
0649       (high(interval1) >= low(interval2)) :
0650       (low(interval1) < high(interval2)) &&
0651       (high(interval1) > low(interval2));
0652 }
0653
0654 struct y_i_e_bintersect : gtl_yes {};
0655
0656 template <typename IntervalType1, typename IntervalType2>
0657 typename enable_if<
0658   typename gtl_and_3<
0659     y_i_e_bintersect,
0660     typename is_interval_concept<
0661       typename geometry_concept<IntervalType1>::type
0662     >::type,
0663     typename is_interval_concept<
0664       typename geometry_concept<IntervalType2>::type
0665     >::type
0666   >::type,
0667   bool
0668 >::type boundaries_intersect(
0669     const IntervalType1& interval1,
0670     const IntervalType2& interval2,
0671     bool consider_touch = true) {
0672   return (contains(interval1, low(interval2), consider_touch) ||
0673           contains(interval1, high(interval2), consider_touch)) &&
0674          (contains(interval2, low(interval1), consider_touch) ||
0675           contains(interval2, high(interval1), consider_touch));
0676 }
0677
0678 struct y_i_intersect : gtl_yes {};
0679
0680 template <typename IntervalType1, typename IntervalType2>
0681 typename enable_if<
0682   typename gtl_and_3<
0683     y_i_intersect,
0684     typename is_mutable_interval_concept<
0685       typename geometry_concept<IntervalType1>::type
0686     >::type,
0687     typename is_interval_concept<
0688       typename geometry_concept<IntervalType2>::type
0689     >::type
0690   >::type,
0691   bool
0692 >::type intersect(
0693     IntervalType1& lvalue,
0694     const IntervalType2& rvalue,
0695     bool consider_touch = true) {
0696   typedef typename interval_coordinate_type<IntervalType1>::type Unit;
0697   Unit lowVal = (std::max)(low(lvalue), low(rvalue));
0698   Unit highVal = (std::min)(high(lvalue), high(rvalue));
0699   bool valid = consider_touch ? lowVal <= highVal : lowVal < highVal;
0700   if (valid) {
0701     low(lvalue, lowVal);
0702     high(lvalue, highVal);
0703   }
0704   return valid;
0705 }
0706
0707 struct y_i_g_intersect : gtl_yes {};
0708
0709 // TODO(asydorchuk): Deprecated.
0710 template <typename IntervalType1, typename IntervalType2>
0711 typename enable_if<
0712   typename gtl_and_3<
0713     y_i_g_intersect,
0714     typename is_mutable_interval_concept<
0715       typename geometry_concept<IntervalType1>::type
0716     >::type,
0717     typename is_interval_concept<
0718       typename geometry_concept<IntervalType2>::type
0719     >::type
0720   >::type,
0721   IntervalType1
0722 >::type& generalized_intersect(
0723     IntervalType1& lvalue,
0724     const IntervalType2& rvalue) {
0725   typedef typename interval_coordinate_type<IntervalType1>::type Unit;
0726   Unit coords[4] = {low(lvalue), high(lvalue), low(rvalue), high(rvalue)};
0727   // TODO(asydorchuk): consider implementing faster sorting of small
0728   // fixed length range.
0729   polygon_sort(coords, coords+4);
0730   low(lvalue, coords[1]);
0731   high(lvalue, coords[2]);
0732   return lvalue;
0733 }
0734
0735 struct y_i_abuts1 : gtl_yes {};
0736
0737 template <typename IntervalType1, typename IntervalType2>
0738 typename enable_if<
0739   typename gtl_and_3<
0740     y_i_abuts1,
0741     typename is_interval_concept<
0742       typename geometry_concept<IntervalType1>::type
0743     >::type,
0744     typename is_interval_concept<
0745       typename geometry_concept<IntervalType2>::type
0746     >::type
0747   >::type,
0748   bool
0749 >::type abuts(
0750     const IntervalType1& interval1,
0751     const IntervalType2& interval2,
0752     direction_1d dir) {
0753   return dir.to_int() ? low(interval2) == high(interval1) :
0754                         low(interval1) == high(interval2);
0755 }
0756
0757 struct y_i_abuts2 : gtl_yes {};
0758
0759 template <typename IntervalType1, typename IntervalType2>
0760 typename enable_if<
0761   typename gtl_and_3<
0762     y_i_abuts2,
0763     typename is_interval_concept<
0764       typename geometry_concept<IntervalType1>::type
0765     >::type,
0766     typename is_interval_concept<
0767       typename geometry_concept<IntervalType2>::type
0768     >::type
0769   >::type,
0770   bool
0771 >::type abuts(
0772     const IntervalType1& interval1,
0773     const IntervalType2& interval2) {
0774   return abuts(interval1, interval2, HIGH) ||
0775          abuts(interval1, interval2, LOW);
0776 }
0777
0778 struct y_i_bloat : gtl_yes {};
0779
0780 template <typename IntervalType>
0781 typename enable_if<
0782   typename gtl_and<
0783     y_i_bloat,
0784     typename is_mutable_interval_concept<
0785       typename geometry_concept<IntervalType>::type
0786     >::type
0787   >::type,
0788   IntervalType
0789 >::type& bloat(
0790     IntervalType& interval,
0791     typename interval_coordinate_type<IntervalType>::type bloating) {
0792   low(interval, low(interval) - bloating);
0793   high(interval, high(interval) + bloating);
0794   return interval;
0795 }
0796
0797 struct y_i_bloat2 : gtl_yes {};
0798
0799 template <typename IntervalType>
0800 typename enable_if<
0801   typename gtl_and<
0802     y_i_bloat2,
0803     typename is_mutable_interval_concept<
0804       typename geometry_concept<IntervalType>::type
0805     >::type
0806   >::type,
0807   IntervalType
0808 >::type& bloat(
0809     IntervalType& interval,
0810     direction_1d dir,
0811     typename interval_coordinate_type<IntervalType>::type bloating) {
0812   set(interval, dir, get(interval, dir) + dir.get_sign() * bloating);
0813   return interval;
0814 }
0815
0816 struct y_i_shrink : gtl_yes {};
0817
0818 template <typename IntervalType>
0819 typename enable_if<
0820   typename gtl_and<
0821     y_i_shrink,
0822     typename is_mutable_interval_concept<
0823       typename geometry_concept<IntervalType>::type
0824     >::type
0825   >::type,
0826   IntervalType
0827 >::type& shrink(
0828     IntervalType& interval,
0829     typename interval_coordinate_type<IntervalType>::type shrinking) {
0830   return bloat(interval, -shrinking);
0831 }
0832
0833 struct y_i_shrink2 : gtl_yes {};
0834
0835 template <typename IntervalType>
0836 typename enable_if<
0837   typename gtl_and<
0838     y_i_shrink2,
0839     typename is_mutable_interval_concept<
0840       typename geometry_concept<IntervalType>::type
0841     >::type
0842   >::type,
0843   IntervalType
0844 >::type& shrink(
0845     IntervalType& interval,
0846     direction_1d dir,
0847     typename interval_coordinate_type<IntervalType>::type shrinking) {
0848   return bloat(interval, dir, -shrinking);
0849 }
0850
0851 struct y_i_encompass : gtl_yes {};
0852
0853 template <typename IntervalType1, typename IntervalType2>
0854 typename enable_if<
0855   typename gtl_and_3<
0856     y_i_encompass,
0857     typename is_mutable_interval_concept<
0858       typename geometry_concept<IntervalType1>::type
0859     >::type,
0860     typename is_interval_concept<
0861       typename geometry_concept<IntervalType2>::type
0862     >::type
0863   >::type,
0864   bool
0865 >::type encompass(IntervalType1& interval1, const IntervalType2& interval2) {
0866   bool retval = !contains(interval1, interval2, true);
0867   low(interval1, (std::min)(low(interval1), low(interval2)));
0868   high(interval1, (std::max)(high(interval1), high(interval2)));
0869   return retval;
0870 }
0871
0872 struct y_i_encompass2 : gtl_yes {};
0873
0874 template <typename IntervalType>
0875 typename enable_if<
0876   typename gtl_and<
0877     y_i_encompass2,
0878     typename is_mutable_interval_concept<
0879       typename geometry_concept<IntervalType>::type
0880     >::type
0881   >::type,
0882   bool
0883 >::type encompass(
0884     IntervalType& interval,
0885     typename interval_coordinate_type<IntervalType>::type value) {
0886   bool retval = !contains(interval, value, true);
0887   low(interval, (std::min)(low(interval), value));
0888   high(interval, (std::max)(high(interval), value));
0889   return retval;
0890 }
0891
0892 struct y_i_get_half : gtl_yes {};
0893
0894 template <typename IntervalType>
0895 typename enable_if<
0896   typename gtl_and<
0897     y_i_get_half,
0898     typename is_mutable_interval_concept<
0899       typename geometry_concept<IntervalType>::type
0900     >::type
0901   >::type,
0902   IntervalType
0903 >::type get_half(const IntervalType& interval, direction_1d dir) {
0904   typedef typename interval_coordinate_type<IntervalType>::type Unit;
0905   Unit c = (get(interval, LOW) + get(interval, HIGH)) / 2;
0906   return construct<IntervalType>(
0907       (dir == LOW) ? get(interval, LOW) : c,
0908       (dir == LOW) ? c : get(interval, HIGH));
0909 }
0910
0911 struct y_i_join_with : gtl_yes {};
0912
0913 template <typename IntervalType1, typename IntervalType2>
0914 typename enable_if<
0915   typename gtl_and_3<
0916     y_i_join_with,
0917     typename is_mutable_interval_concept<
0918       typename geometry_concept<IntervalType1>::type
0919     >::type,
0920     typename is_interval_concept<
0921       typename geometry_concept<IntervalType2>::type
0922     >::type>::type,
0923   bool
0924 >::type join_with(IntervalType1& interval1, const IntervalType2& interval2) {
0925   if (abuts(interval1, interval2)) {
0926     encompass(interval1, interval2);
0927     return true;
0928   }
0929   return false;
0930 }
0931 }  // polygon
0932 }  // boost
0933
0934 #endif  // BOOST_POLYGON_INTERVAL_CONCEPT_HPP