strategies/spherical/distance_cross_track_box_box.hpp

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