detail/closest_points/segment_to_segment.hpp

0001 // Boost.Geometry
0002
0003 // Copyright (c) 2021-2023, Oracle and/or its affiliates.
0004
0005 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0006
0007 // Licensed under the Boost Software License version 1.0.
0008 // http://www.boost.org/users/license.html
0009
0010 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_POINTS_SEGMENT_TO_SEGMENT_HPP
0011 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_POINTS_SEGMENT_TO_SEGMENT_HPP
0012
0013 #include <algorithm>
0014 #include <iterator>
0015
0016 #include <boost/core/addressof.hpp>
0017
0018 #include <boost/geometry/algorithms/assign.hpp>
0019 #include <boost/geometry/algorithms/detail/closest_points/utilities.hpp>
0020 #include <boost/geometry/algorithms/detail/distance/is_comparable.hpp>
0021 #include <boost/geometry/algorithms/detail/distance/strategy_utils.hpp>
0022 #include <boost/geometry/algorithms/dispatch/closest_points.hpp>
0023 #include <boost/geometry/algorithms/dispatch/distance.hpp>
0024 #include <boost/geometry/algorithms/intersects.hpp>
0025
0026 #include <boost/geometry/core/point_type.hpp>
0027 #include <boost/geometry/core/tags.hpp>
0028
0029 #include <boost/geometry/strategies/distance.hpp>
0030 #include <boost/geometry/strategies/tags.hpp>
0031
0032 #include <boost/geometry/util/condition.hpp>
0033
0034
0035 namespace boost { namespace geometry
0036 {
0037
0038
0039 #ifndef DOXYGEN_NO_DETAIL
0040 namespace detail { namespace closest_points
0041 {
0042
0043
0044
0045 // compute segment-segment closest-points
0046 class segment_to_segment
0047 {
0048 public:
0049
0050     template <typename Segment1, typename Segment2, typename OutputSegment, typename Strategies>
0051     static inline void apply(Segment1 const& segment1, Segment2 const& segment2,
0052                              OutputSegment& shortest_seg,
0053                              Strategies const& strategies)
0054     {
0055         using intersection_return_type = segment_intersection_points
0056             <
0057                 typename point_type<Segment1>::type
0058             >;
0059
0060         using intersection_policy = policies::relate::segments_intersection_points
0061             <
0062                 intersection_return_type
0063             >;
0064
0065         detail::segment_as_subrange<Segment1> sub_range1(segment1);
0066         detail::segment_as_subrange<Segment2> sub_range2(segment2);
0067         auto is = strategies.relate().apply(sub_range1, sub_range2,
0068                                             intersection_policy());
0069         if (is.count > 0)
0070         {
0071             set_segment_from_points::apply(is.intersections[0],
0072                                            is.intersections[0],
0073                                            shortest_seg);
0074             return;
0075         }
0076
0077         typename point_type<Segment1>::type p[2];
0078         detail::assign_point_from_index<0>(segment1, p[0]);
0079         detail::assign_point_from_index<1>(segment1, p[1]);
0080
0081         typename point_type<Segment2>::type q[2];
0082         detail::assign_point_from_index<0>(segment2, q[0]);
0083         detail::assign_point_from_index<1>(segment2, q[1]);
0084
0085         auto cp0 = strategies.closest_points(q[0], segment1).apply(q[0], p[0], p[1]);
0086         auto cp1 = strategies.closest_points(q[1], segment1).apply(q[1], p[0], p[1]);
0087         auto cp2 = strategies.closest_points(p[0], segment2).apply(p[0], q[0], q[1]);
0088         auto cp3 = strategies.closest_points(p[1], segment2).apply(p[1], q[0], q[1]);
0089
0090         closest_points::creturn_t<Segment1, Segment2, Strategies> d[4];
0091
0092         auto const cds = strategies::distance::detail::make_comparable(strategies)
0093             .distance(detail::dummy_point(), detail::dummy_point());
0094
0095         d[0] = cds.apply(cp0, q[0]);
0096         d[1] = cds.apply(cp1, q[1]);
0097         d[2] = cds.apply(p[0], cp2);
0098         d[3] = cds.apply(p[1], cp3);
0099
0100         std::size_t imin = std::distance(boost::addressof(d[0]), std::min_element(d, d + 4));
0101
0102         switch (imin)
0103         {
0104         case 0:
0105             set_segment_from_points::apply(cp0, q[0], shortest_seg);
0106             return;
0107         case 1:
0108             set_segment_from_points::apply(cp1, q[1], shortest_seg);
0109             return;
0110         case 2:
0111             set_segment_from_points::apply(p[0], cp2, shortest_seg);
0112             return;
0113         default:
0114             set_segment_from_points::apply(p[1], cp3, shortest_seg);
0115             return;
0116         }
0117     }
0118 };
0119
0120
0121 }} // namespace detail::closest_points
0122 #endif // DOXYGEN_NO_DETAIL
0123
0124
0125 #ifndef DOXYGEN_NO_DISPATCH
0126 namespace dispatch
0127 {
0128
0129
0130 // segment-segment
0131 template <typename Segment1, typename Segment2>
0132 struct closest_points
0133     <
0134         Segment1, Segment2, segment_tag, segment_tag, false
0135     > : detail::closest_points::segment_to_segment
0136 {};
0137
0138 } // namespace dispatch
0139 #endif // DOXYGEN_NO_DISPATCH
0140
0141
0142 }} // namespace boost::geometry
0143
0144
0145 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_CLOSEST_POINTS_SEGMENT_TO_SEGMENT_HPP