policies/relate/intersection_points.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
0004
0005 // This file was modified by Oracle on 2016, 2022.
0006 // Modifications copyright (c) 2016-2022 Oracle and/or its affiliates.
0007 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0008 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0009
0010 // Use, modification and distribution is subject to the Boost Software License,
0011 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0012 // http://www.boost.org/LICENSE_1_0.txt)
0013
0014 #ifndef BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_INTERSECTION_POINTS_HPP
0015 #define BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_INTERSECTION_POINTS_HPP
0016
0017
0018 #include <algorithm>
0019 #include <string>
0020
0021 #include <boost/geometry/algorithms/assign.hpp>
0022 #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp>
0023 #include <boost/geometry/core/access.hpp>
0024 #include <boost/geometry/core/assert.hpp>
0025 #include <boost/geometry/strategies/side_info.hpp>
0026
0027 namespace boost { namespace geometry
0028 {
0029
0030 namespace policies { namespace relate
0031 {
0032
0033
0034 /*!
0035 \brief Policy calculating the intersection points themselves
0036  */
0037 template
0038 <
0039     typename ReturnType
0040 >
0041 struct segments_intersection_points
0042 {
0043     typedef ReturnType return_type;
0044
0045     template
0046     <
0047         typename Segment1,
0048         typename Segment2,
0049         typename SegmentIntersectionInfo
0050     >
0051     static inline return_type segments_crosses(side_info const&,
0052                     SegmentIntersectionInfo const& sinfo,
0053                     Segment1 const& s1, Segment2 const& s2)
0054     {
0055         return_type result;
0056         result.count = 1;
0057         sinfo.calculate(result.intersections[0], s1, s2);
0058
0059         // Temporary - this should go later
0060         result.fractions[0].assign(sinfo);
0061
0062         return result;
0063     }
0064
0065     template<typename SegmentIntersectionInfo, typename Point>
0066     static inline return_type
0067     segments_share_common_point(side_info const&, SegmentIntersectionInfo const& sinfo,
0068                                 Point const& p)
0069     {
0070         return_type result;
0071         result.count = 1;
0072         boost::geometry::assign(result.intersections[0], p);
0073
0074         // Temporary - this should go later
0075         result.fractions[0].assign(sinfo);
0076
0077         return result;
0078     }
0079
0080     template <typename Segment1, typename Segment2, typename Ratio>
0081     static inline return_type segments_collinear(
0082         Segment1 const& a, Segment2 const& b, bool /*opposite*/,
0083         int a1_wrt_b, int a2_wrt_b, int b1_wrt_a, int b2_wrt_a,
0084         Ratio const& ra_from_wrt_b, Ratio const& ra_to_wrt_b,
0085         Ratio const& rb_from_wrt_a, Ratio const& rb_to_wrt_a)
0086     {
0087         return_type result;
0088         unsigned int index = 0;
0089         Ratio on_a[2];
0090
0091         // The conditions "index < 2" are necessary for non-robust handling,
0092         // if index would be 2 this indicate an (currently uncatched) error
0093
0094         // IMPORTANT: the order of conditions is different as in direction.hpp
0095         if (a1_wrt_b >= 1 && a1_wrt_b <= 3 // ra_from_wrt_b.on_segment()
0096             && index < 2)
0097         {
0098             //     a1--------->a2
0099             // b1----->b2
0100             //
0101             // ra1 (relative to b) is between 0/1:
0102             // -> First point of A is intersection point
0103             detail::assign_point_from_index<0>(a, result.intersections[index]);
0104             result.fractions[index].assign(Ratio::zero(), ra_from_wrt_b);
0105             on_a[index] = Ratio::zero();
0106             index++;
0107         }
0108         if (b1_wrt_a == 2 //rb_from_wrt_a.in_segment()
0109             && index < 2)
0110         {
0111             // We take the first intersection point of B
0112             // a1--------->a2
0113             //         b1----->b2
0114             // But only if it is not located on A
0115             // a1--------->a2
0116             // b1----->b2      rb_from_wrt_a == 0/1 -> a already taken
0117
0118             detail::assign_point_from_index<0>(b, result.intersections[index]);
0119             result.fractions[index].assign(rb_from_wrt_a, Ratio::zero());
0120             on_a[index] = rb_from_wrt_a;
0121             index++;
0122         }
0123
0124         if (a2_wrt_b >= 1 && a2_wrt_b <= 3 //ra_to_wrt_b.on_segment()
0125             && index < 2)
0126         {
0127             // Similarly, second IP (here a2)
0128             // a1--------->a2
0129             //         b1----->b2
0130             detail::assign_point_from_index<1>(a, result.intersections[index]);
0131             result.fractions[index].assign(Ratio::one(), ra_to_wrt_b);
0132             on_a[index] = Ratio::one();
0133             index++;
0134         }
0135         if (b2_wrt_a == 2 // rb_to_wrt_a.in_segment()
0136             && index < 2)
0137         {
0138             detail::assign_point_from_index<1>(b, result.intersections[index]);
0139             result.fractions[index].assign(rb_to_wrt_a, Ratio::one());
0140             on_a[index] = rb_to_wrt_a;
0141             index++;
0142         }
0143
0144         // TEMPORARY
0145         // If both are from b, and b is reversed w.r.t. a, we swap IP's
0146         // to align them w.r.t. a
0147         // get_turn_info still relies on some order (in some collinear cases)
0148         if (index == 2 && on_a[1] < on_a[0])
0149         {
0150             std::swap(result.fractions[0], result.fractions[1]);
0151             std::swap(result.intersections[0], result.intersections[1]);
0152         }
0153
0154         result.count = index;
0155
0156         return result;
0157     }
0158
0159     static inline return_type disjoint()
0160     {
0161         return return_type();
0162     }
0163     static inline return_type error(std::string const&)
0164     {
0165         return return_type();
0166     }
0167
0168     // Both degenerate
0169     template <typename Segment>
0170     static inline return_type degenerate(Segment const& segment, bool)
0171     {
0172         return_type result;
0173         result.count = 1;
0174         set<0>(result.intersections[0], get<0, 0>(segment));
0175         set<1>(result.intersections[0], get<0, 1>(segment));
0176         return result;
0177     }
0178
0179     // One degenerate
0180     template <typename Segment, typename Ratio>
0181     static inline return_type one_degenerate(Segment const& degenerate_segment,
0182             Ratio const& ratio, bool a_degenerate)
0183     {
0184         return_type result;
0185         result.count = 1;
0186         set<0>(result.intersections[0], get<0, 0>(degenerate_segment));
0187         set<1>(result.intersections[0], get<0, 1>(degenerate_segment));
0188         if (a_degenerate)
0189         {
0190             // IP lies on ratio w.r.t. segment b
0191             result.fractions[0].assign(Ratio::zero(), ratio);
0192         }
0193         else
0194         {
0195             result.fractions[0].assign(ratio, Ratio::zero());
0196         }
0197         return result;
0198     }
0199 };
0200
0201
0202 }} // namespace policies::relate
0203
0204 }} // namespace boost::geometry
0205
0206 #endif // BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_INTERSECTION_POINTS_HPP