strategies/cartesian/closest_points_pt_seg.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_STRATEGIES_CARTESIAN_CLOSEST_POINTS_PT_SEG_HPP
0011 #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_CLOSEST_POINTS_PT_SEG_HPP
0012
0013 #include <boost/geometry/algorithms/convert.hpp>
0014
0015 #include <boost/geometry/core/coordinate_promotion.hpp>
0016
0017 #include <boost/geometry/geometries/point.hpp>
0018
0019 #include <boost/geometry/strategies/cartesian/distance_pythagoras.hpp>
0020 #include <boost/geometry/strategies/closest_points/services.hpp>
0021
0022 namespace boost { namespace geometry
0023 {
0024
0025 namespace strategy { namespace closest_points
0026 {
0027
0028 #ifndef DOXYGEN_NO_DETAIL
0029 namespace detail
0030 {
0031
0032 template <typename CalculationType>
0033 struct compute_closest_point_to_segment
0034 {
0035     template <typename Point, typename PointOfSegment>
0036     static inline auto
0037     apply(Point const& p, PointOfSegment const& p1, PointOfSegment const& p2)
0038     {
0039         // A projected point of points in Integer coordinates must be able to be
0040         // represented in FP.
0041         using fp_point_type = model::point
0042             <
0043                 CalculationType,
0044                 dimension<PointOfSegment>::value,
0045                 typename coordinate_system<PointOfSegment>::type
0046             >;
0047
0048         // For convenience
0049         using fp_vector_type = fp_point_type;
0050
0051         /*
0052             Algorithm [p: (px,py), p1: (x1,y1), p2: (x2,y2)]
0053             VECTOR v(x2 - x1, y2 - y1)
0054             VECTOR w(px - x1, py - y1)
0055             c1 = w . v
0056             c2 = v . v
0057             b = c1 / c2
0058             RETURN POINT(x1 + b * vx, y1 + b * vy)
0059         */
0060
0061         // v is multiplied below with a (possibly) FP-value, so should be in FP
0062         // For consistency we define w also in FP
0063         fp_vector_type v, w, projected;
0064
0065         geometry::convert(p2, v);
0066         geometry::convert(p, w);
0067         geometry::convert(p1, projected);
0068         subtract_point(v, projected);
0069         subtract_point(w, projected);
0070
0071         CalculationType const zero = CalculationType();
0072         CalculationType const c1 = dot_product(w, v);
0073         if (c1 <= zero)
0074         {
0075             fp_vector_type fp_p1;
0076             geometry::convert(p1, fp_p1);
0077             return fp_p1;
0078         }
0079         CalculationType const c2 = dot_product(v, v);
0080         if (c2 <= c1)
0081         {
0082             fp_vector_type fp_p2;
0083             geometry::convert(p2, fp_p2);
0084             return fp_p2;
0085         }
0086
0087         // See above, c1 > 0 AND c2 > c1 so: c2 != 0
0088         CalculationType const b = c1 / c2;
0089
0090         multiply_value(v, b);
0091         add_point(projected, v);
0092
0093         return projected;
0094     }
0095 };
0096
0097 }
0098 #endif // DOXYGEN_NO_DETAIL
0099
0100 template
0101 <
0102     typename CalculationType = void
0103 >
0104 class projected_point
0105 {
0106 public:
0107     // The three typedefs below are necessary to calculate distances
0108     // from segments defined in integer coordinates.
0109
0110     // Integer coordinates can still result in FP distances.
0111     // There is a division, which must be represented in FP.
0112     // So promote.
0113
0114     template <typename Point, typename PointOfSegment>
0115     struct calculation_type
0116         : promote_floating_point
0117           <
0118             typename select_most_precise
0119                 <
0120                     typename coordinate_type<Point>::type,
0121                     typename coordinate_type<PointOfSegment>::type,
0122                     CalculationType
0123                 >::type
0124           >
0125     {};
0126
0127     template <typename Point, typename PointOfSegment>
0128     inline auto
0129     apply(Point const& p, PointOfSegment const& p1, PointOfSegment const& p2) const
0130     {
0131         assert_dimension_equal<Point, PointOfSegment>();
0132
0133         using calculation_type = typename calculation_type<Point, PointOfSegment>::type;
0134
0135         return detail::compute_closest_point_to_segment<calculation_type>::apply(p, p1, p2);
0136     }
0137
0138 };
0139
0140 }} // namespace strategy::closest_points
0141
0142
0143 }} // namespace boost::geometry
0144
0145
0146 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_CLOSEST_POINTS_PT_SEG_HPP