strategies/spherical/distance_cross_track_box_box.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2016-2020 Oracle and/or its affiliates.
0004 // Contributed and/or modified by Vissarion Fisikopoulos, on behalf of Oracle
0005 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0006
0007 // Use, modification and distribution is subject to the Boost Software License,
0008 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0009 // http://www.boost.org/LICENSE_1_0.txt)
0010
0011 #ifndef BOOST_GEOMETRY_STRATEGIES_SPHERICAL_DISTANCE_CROSS_TRACK_BOX_BOX_HPP
0012 #define BOOST_GEOMETRY_STRATEGIES_SPHERICAL_DISTANCE_CROSS_TRACK_BOX_BOX_HPP
0013
0014
0015 #include <type_traits>
0016
0017 #include <boost/config.hpp>
0018 #include <boost/concept_check.hpp>
0019
0020 #include <boost/geometry/core/access.hpp>
0021 #include <boost/geometry/core/assert.hpp>
0022 #include <boost/geometry/core/point_type.hpp>
0023 #include <boost/geometry/core/radian_access.hpp>
0024 #include <boost/geometry/core/tags.hpp>
0025
0026 #include <boost/geometry/strategies/distance.hpp>
0027 #include <boost/geometry/strategies/concepts/distance_concept.hpp>
0028 #include <boost/geometry/strategies/spherical/distance_cross_track.hpp>
0029
0030 #include <boost/geometry/util/math.hpp>
0031 #include <boost/geometry/algorithms/detail/assign_box_corners.hpp>
0032
0033
0034 namespace boost { namespace geometry
0035 {
0036
0037 namespace strategy { namespace distance
0038 {
0039
0040 namespace details
0041 {
0042
0043 template <typename ReturnType>
0044 class cross_track_box_box_generic
0045 {
0046 public :
0047
0048     template <typename Point, typename PPStrategy, typename PSStrategy>
0049     ReturnType static inline diagonal_case(Point topA,
0050                                            Point topB,
0051                                            Point bottomA,
0052                                            Point bottomB,
0053                                            bool north_shortest,
0054                                            bool non_overlap,
0055                                            PPStrategy pp_strategy,
0056                                            PSStrategy ps_strategy)
0057     {
0058         if (north_shortest && non_overlap)
0059         {
0060             return pp_strategy.apply(topA, bottomB);
0061         }
0062         if (north_shortest && !non_overlap)
0063         {
0064             return ps_strategy.apply(topA, topB, bottomB);
0065         }
0066         if (!north_shortest && non_overlap)
0067         {
0068             return pp_strategy.apply(bottomA, topB);
0069         }
0070         return ps_strategy.apply(bottomA, topB, bottomB);
0071     }
0072
0073
0074     template
0075     <
0076             typename Box1,
0077             typename Box2,
0078             typename PPStrategy,
0079             typename PSStrategy
0080     >
0081     ReturnType static inline apply (Box1 const& box1,
0082                                     Box2 const& box2,
0083                                     PPStrategy pp_strategy,
0084                                     PSStrategy ps_strategy)
0085     {
0086
0087         // this method assumes that the coordinates of the point and
0088         // the box are normalized
0089
0090         typedef typename point_type<Box1>::type box_point_type1;
0091         typedef typename point_type<Box2>::type box_point_type2;
0092
0093         box_point_type1 bottom_left1, bottom_right1, top_left1, top_right1;
0094         geometry::detail::assign_box_corners(box1,
0095                                              bottom_left1, bottom_right1,
0096                                              top_left1, top_right1);
0097
0098         box_point_type2 bottom_left2, bottom_right2, top_left2, top_right2;
0099         geometry::detail::assign_box_corners(box2,
0100                                              bottom_left2, bottom_right2,
0101                                              top_left2, top_right2);
0102
0103         ReturnType lon_min1 = geometry::get_as_radian<0>(bottom_left1);
0104         ReturnType const lat_min1 = geometry::get_as_radian<1>(bottom_left1);
0105         ReturnType lon_max1 = geometry::get_as_radian<0>(top_right1);
0106         ReturnType const lat_max1 = geometry::get_as_radian<1>(top_right1);
0107
0108         ReturnType lon_min2 = geometry::get_as_radian<0>(bottom_left2);
0109         ReturnType const lat_min2 = geometry::get_as_radian<1>(bottom_left2);
0110         ReturnType lon_max2 = geometry::get_as_radian<0>(top_right2);
0111         ReturnType const lat_max2 = geometry::get_as_radian<1>(top_right2);
0112
0113         ReturnType const two_pi = math::two_pi<ReturnType>();
0114
0115         // Test which sides of the boxes are closer and if boxes cross
0116         // antimeridian
0117         bool right_wrap;
0118
0119         if (lon_min2 > 0 && lon_max2 < 0) // box2 crosses antimeridian
0120         {
0121 #ifdef BOOST_GEOMETRY_DEBUG_CROSS_TRACK_BOX_BOX
0122             std::cout << "(box2 crosses antimeridian)";
0123 #endif
0124             right_wrap = lon_min2 - lon_max1 < lon_min1 - lon_max2;
0125             lon_max2 += two_pi;
0126             if (lon_min1 > 0 && lon_max1 < 0) // both boxes crosses antimeridian
0127             {
0128                 lon_max1 += two_pi;
0129             }
0130         }
0131         else if (lon_min1 > 0 && lon_max1 < 0) // only box1 crosses antimeridian
0132         {
0133 #ifdef BOOST_GEOMETRY_DEBUG_CROSS_TRACK_BOX_BOX
0134             std::cout << "(box1 crosses antimeridian)";
0135 #endif
0136             return apply(box2, box1, pp_strategy, ps_strategy);
0137         }
0138         else
0139         {
0140             right_wrap = lon_max1 <= lon_min2
0141                          ? lon_min2 - lon_max1 < two_pi - (lon_max2 - lon_min1)
0142                          : lon_min1 - lon_max2 > two_pi - (lon_max1 - lon_min2);
0143
0144         }
0145
0146         // Check1: if box2 crosses the band defined by the
0147         // minimum and maximum longitude of box1; if yes, determine
0148         // if the box2 is above, below or intersects/is inside box1 and compute
0149         // the distance (easy in this case)
0150
0151         bool lon_min12 = lon_min1 <= lon_min2;
0152         bool right = lon_max1 <= lon_min2;
0153         bool left = lon_min1 >= lon_max2;
0154         bool lon_max12 = lon_max1 <= lon_max2;
0155
0156         if ((lon_min12 && !right)
0157                 || (!left && !lon_max12)
0158                 || (!lon_min12 && lon_max12))
0159         {
0160 #ifdef BOOST_GEOMETRY_DEBUG_CROSS_TRACK_BOX_BOX
0161             std::cout << "(up-down)\n";
0162 #endif
0163             if (lat_min1 > lat_max2)
0164             {
0165                 return geometry::strategy::distance::services::result_from_distance
0166                     <
0167                         PSStrategy, box_point_type1, box_point_type2
0168                     >::apply(ps_strategy, ps_strategy
0169                                .vertical_or_meridian(lat_min1, lat_max2));
0170             }
0171             else if (lat_max1 < lat_min2)
0172             {
0173                 return geometry::strategy::distance::services::result_from_distance
0174                     <
0175                         PSStrategy, box_point_type1, box_point_type2
0176                     >::apply(ps_strategy, ps_strategy
0177                              .vertical_or_meridian(lat_min2, lat_max1));
0178             }
0179             else
0180             {
0181                 //BOOST_GEOMETRY_ASSERT(plat >= lat_min && plat <= lat_max);
0182                 return ReturnType(0);
0183             }
0184         }
0185
0186         // Check2: if box2 is right/left of box1
0187         // the max lat of box2 should be less than the max lat of box1
0188         bool bottom_max;
0189
0190         ReturnType top_common = (std::min)(lat_max1, lat_max2);
0191         ReturnType bottom_common = (std::max)(lat_min1, lat_min2);
0192
0193         // true if the closest points are on northern hemisphere
0194         bool north_shortest = top_common + bottom_common > 0;
0195         // true if box bands do not overlap
0196         bool non_overlap = top_common < bottom_common;
0197
0198         if (north_shortest)
0199         {
0200             bottom_max = lat_max1 >= lat_max2;
0201         }
0202         else
0203         {
0204             bottom_max = lat_min1 <= lat_min2;
0205         }
0206
0207 #ifdef BOOST_GEOMETRY_DEBUG_CROSS_TRACK_BOX_BOX
0208         std::cout << "(diagonal)";
0209 #endif
0210         if (bottom_max && !right_wrap)
0211         {
0212 #ifdef BOOST_GEOMETRY_DEBUG_CROSS_TRACK_BOX_BOX
0213             std::cout << "(bottom left)";
0214 #endif
0215             return diagonal_case(top_right2, top_left1,
0216                                  bottom_right2, bottom_left1,
0217                                  north_shortest, non_overlap,
0218                                  pp_strategy, ps_strategy);
0219         }
0220         if (bottom_max && right_wrap)
0221         {
0222 #ifdef BOOST_GEOMETRY_DEBUG_CROSS_TRACK_BOX_BOX
0223             std::cout << "(bottom right)";
0224 #endif
0225             return diagonal_case(top_left2, top_right1,
0226                                  bottom_left2, bottom_right1,
0227                                  north_shortest, non_overlap,
0228                                  pp_strategy, ps_strategy);
0229         }
0230         if (!bottom_max && !right_wrap)
0231         {
0232 #ifdef BOOST_GEOMETRY_DEBUG_CROSS_TRACK_BOX_BOX
0233             std::cout << "(top left)";
0234 #endif
0235             return diagonal_case(top_left1, top_right2,
0236                                  bottom_left1, bottom_right2,
0237                                  north_shortest, non_overlap,
0238                                  pp_strategy, ps_strategy);
0239         }
0240         if (!bottom_max && right_wrap)
0241         {
0242 #ifdef BOOST_GEOMETRY_DEBUG_CROSS_TRACK_BOX_BOX
0243             std::cout << "(top right)";
0244 #endif
0245             return diagonal_case(top_right1, top_left2,
0246                                  bottom_right1, bottom_left2,
0247                                  north_shortest, non_overlap,
0248                                  pp_strategy, ps_strategy);
0249         }
0250         return ReturnType(0);
0251     }
0252 };
0253
0254 } //namespace details
0255
0256 /*!
0257 \brief Strategy functor for distance box to box calculation
0258 \ingroup strategies
0259 \details Class which calculates the distance of a box to a box, for
0260 boxes on a sphere or globe
0261 \tparam CalculationType \tparam_calculation
0262 \tparam Strategy underlying point-segment distance strategy, defaults
0263 to cross track
0264 \qbk{
0265 [heading See also]
0266 [link geometry.reference.algorithms.distance.distance_3_with_strategy distance (with strategy)]
0267 }
0268 */
0269 template
0270 <
0271     typename CalculationType = void,
0272     typename Strategy = haversine<double, CalculationType>
0273 >
0274 class cross_track_box_box
0275 {
0276 public:
0277     template <typename Box1, typename Box2>
0278     struct return_type
0279         : services::return_type<Strategy,
0280                                 typename point_type<Box1>::type,
0281                                 typename point_type<Box2>::type>
0282     {};
0283
0284     typedef typename Strategy::radius_type radius_type;
0285
0286     // strategy getters
0287
0288     // point-segment strategy getters
0289     struct distance_ps_strategy
0290     {
0291         typedef cross_track<CalculationType, Strategy> type;
0292     };
0293
0294     typedef typename strategy::distance::services::comparable_type
0295         <
0296             Strategy
0297         >::type pp_comparable_strategy;
0298
0299     typedef std::conditional_t
0300         <
0301             std::is_same
0302                 <
0303                     pp_comparable_strategy,
0304                     Strategy
0305                 >::value,
0306             typename strategy::distance::services::comparable_type
0307                 <
0308                     typename distance_ps_strategy::type
0309                 >::type,
0310             typename distance_ps_strategy::type
0311         > ps_strategy_type;
0312
0313     // constructors
0314
0315     inline cross_track_box_box()
0316     {}
0317
0318     explicit inline cross_track_box_box(typename Strategy::radius_type const& r)
0319         : m_strategy(r)
0320     {}
0321
0322     inline cross_track_box_box(Strategy const& s)
0323         : m_strategy(s)
0324     {}
0325
0326
0327     // It might be useful in the future
0328     // to overload constructor with strategy info.
0329     // crosstrack(...) {}
0330
0331     template <typename Box1, typename Box2>
0332     inline typename return_type<Box1, Box2>::type
0333     apply(Box1 const& box1, Box2 const& box2) const
0334     {
0335 #if !defined(BOOST_MSVC)
0336         BOOST_CONCEPT_ASSERT
0337             (
0338                 (concepts::PointDistanceStrategy
0339                     <
0340                         Strategy,
0341                         typename point_type<Box1>::type,
0342                         typename point_type<Box2>::type
0343                     >)
0344             );
0345 #endif
0346         typedef typename return_type<Box1, Box2>::type return_type;
0347         return details::cross_track_box_box_generic
0348                                 <return_type>::apply(box1, box2,
0349                                                      m_strategy,
0350                                                      ps_strategy_type(m_strategy));
0351     }
0352
0353     inline typename Strategy::radius_type radius() const
0354     {
0355         return m_strategy.radius();
0356     }
0357
0358 private:
0359     Strategy m_strategy;
0360 };
0361
0362
0363
0364 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
0365 namespace services
0366 {
0367
0368 template <typename CalculationType, typename Strategy>
0369 struct tag<cross_track_box_box<CalculationType, Strategy> >
0370 {
0371     typedef strategy_tag_distance_box_box type;
0372 };
0373
0374
0375 template <typename CalculationType, typename Strategy, typename Box1, typename Box2>
0376 struct return_type<cross_track_box_box<CalculationType, Strategy>, Box1, Box2>
0377     : cross_track_box_box
0378         <
0379             CalculationType, Strategy
0380         >::template return_type<Box1, Box2>
0381 {};
0382
0383
0384 template <typename CalculationType, typename Strategy>
0385 struct comparable_type<cross_track_box_box<CalculationType, Strategy> >
0386 {
0387     typedef cross_track_box_box
0388         <
0389             CalculationType, typename comparable_type<Strategy>::type
0390         > type;
0391 };
0392
0393
0394 template <typename CalculationType, typename Strategy>
0395 struct get_comparable<cross_track_box_box<CalculationType, Strategy> >
0396 {
0397     typedef cross_track_box_box<CalculationType, Strategy> this_strategy;
0398     typedef typename comparable_type<this_strategy>::type comparable_type;
0399
0400 public:
0401     static inline comparable_type apply(this_strategy const& strategy)
0402     {
0403         return comparable_type(strategy.radius());
0404     }
0405 };
0406
0407
0408 template <typename CalculationType, typename Strategy, typename Box1, typename Box2>
0409 struct result_from_distance
0410     <
0411         cross_track_box_box<CalculationType, Strategy>, Box1, Box2
0412     >
0413 {
0414 private:
0415     typedef cross_track_box_box<CalculationType, Strategy> this_strategy;
0416
0417     typedef typename this_strategy::template return_type
0418         <
0419             Box1, Box2
0420         >::type return_type;
0421
0422 public:
0423     template <typename T>
0424     static inline return_type apply(this_strategy const& strategy,
0425                                     T const& distance)
0426     {
0427         Strategy s(strategy.radius());
0428
0429         return result_from_distance
0430             <
0431                 Strategy,
0432                 typename point_type<Box1>::type,
0433                 typename point_type<Box2>::type
0434             >::apply(s, distance);
0435     }
0436 };
0437
0438
0439 // define cross_track_box_box<default_point_segment_strategy> as
0440 // default box-box strategy for the spherical equatorial coordinate system
0441 template <typename Box1, typename Box2, typename Strategy>
0442 struct default_strategy
0443     <
0444         box_tag, box_tag, Box1, Box2,
0445         spherical_equatorial_tag, spherical_equatorial_tag,
0446         Strategy
0447     >
0448 {
0449     typedef cross_track_box_box
0450         <
0451             void,
0452             std::conditional_t
0453                 <
0454                     std::is_void<Strategy>::value,
0455                     typename default_strategy
0456                         <
0457                             point_tag, point_tag,
0458                             typename point_type<Box1>::type, typename point_type<Box2>::type,
0459                             spherical_equatorial_tag, spherical_equatorial_tag
0460                         >::type,
0461                     Strategy
0462                 >
0463         > type;
0464 };
0465
0466 } // namespace services
0467 #endif // DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
0468
0469
0470 }} // namespace strategy::distance
0471
0472
0473 }} // namespace boost::geometry
0474
0475 #endif // BOOST_GEOMETRY_STRATEGIES_SPHERICAL_DISTANCE_CROSS_TRACK_BOX_BOX_HPP