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/detail/assign_indexed_point.hpp>
0022 #include <boost/geometry/core/access.hpp>
0023 #include <boost/geometry/core/assert.hpp>
0024 #include <boost/geometry/strategies/side_info.hpp>
0025
0026 namespace boost { namespace geometry
0027 {
0028
0029 namespace policies { namespace relate
0030 {
0031
0032
0033 /*!
0034 \brief Policy calculating the intersection points themselves
0035  */
0036 template
0037 <
0038     typename ReturnType
0039 >
0040 struct segments_intersection_points
0041 {
0042     typedef ReturnType return_type;
0043
0044     template
0045     <
0046         typename Segment1,
0047         typename Segment2,
0048         typename SegmentIntersectionInfo
0049     >
0050     static inline return_type segments_crosses(side_info const&,
0051                     SegmentIntersectionInfo const& sinfo,
0052                     Segment1 const& s1, Segment2 const& s2)
0053     {
0054         return_type result;
0055         result.count = 1;
0056         sinfo.calculate(result.intersections[0], s1, s2);
0057
0058         // Temporary - this should go later
0059         result.fractions[0].assign(sinfo);
0060
0061         return result;
0062     }
0063
0064     template <typename Segment1, typename Segment2, typename Ratio>
0065     static inline return_type segments_collinear(
0066         Segment1 const& a, Segment2 const& b, bool /*opposite*/,
0067         int a1_wrt_b, int a2_wrt_b, int b1_wrt_a, int b2_wrt_a,
0068         Ratio const& ra_from_wrt_b, Ratio const& ra_to_wrt_b,
0069         Ratio const& rb_from_wrt_a, Ratio const& rb_to_wrt_a)
0070     {
0071         return_type result;
0072         unsigned int index = 0;
0073         Ratio on_a[2];
0074
0075         // The conditions "index < 2" are necessary for non-robust handling,
0076         // if index would be 2 this indicate an (currently uncatched) error
0077
0078         // IMPORTANT: the order of conditions is different as in direction.hpp
0079         if (a1_wrt_b >= 1 && a1_wrt_b <= 3 // ra_from_wrt_b.on_segment()
0080             && index < 2)
0081         {
0082             //     a1--------->a2
0083             // b1----->b2
0084             //
0085             // ra1 (relative to b) is between 0/1:
0086             // -> First point of A is intersection point
0087             detail::assign_point_from_index<0>(a, result.intersections[index]);
0088             result.fractions[index].assign(Ratio::zero(), ra_from_wrt_b);
0089             on_a[index] = Ratio::zero();
0090             index++;
0091         }
0092         if (b1_wrt_a == 2 //rb_from_wrt_a.in_segment()
0093             && index < 2)
0094         {
0095             // We take the first intersection point of B
0096             // a1--------->a2
0097             //         b1----->b2
0098             // But only if it is not located on A
0099             // a1--------->a2
0100             // b1----->b2      rb_from_wrt_a == 0/1 -> a already taken
0101
0102             detail::assign_point_from_index<0>(b, result.intersections[index]);
0103             result.fractions[index].assign(rb_from_wrt_a, Ratio::zero());
0104             on_a[index] = rb_from_wrt_a;
0105             index++;
0106         }
0107
0108         if (a2_wrt_b >= 1 && a2_wrt_b <= 3 //ra_to_wrt_b.on_segment()
0109             && index < 2)
0110         {
0111             // Similarly, second IP (here a2)
0112             // a1--------->a2
0113             //         b1----->b2
0114             detail::assign_point_from_index<1>(a, result.intersections[index]);
0115             result.fractions[index].assign(Ratio::one(), ra_to_wrt_b);
0116             on_a[index] = Ratio::one();
0117             index++;
0118         }
0119         if (b2_wrt_a == 2 // rb_to_wrt_a.in_segment()
0120             && index < 2)
0121         {
0122             detail::assign_point_from_index<1>(b, result.intersections[index]);
0123             result.fractions[index].assign(rb_to_wrt_a, Ratio::one());
0124             on_a[index] = rb_to_wrt_a;
0125             index++;
0126         }
0127
0128         // TEMPORARY
0129         // If both are from b, and b is reversed w.r.t. a, we swap IP's
0130         // to align them w.r.t. a
0131         // get_turn_info still relies on some order (in some collinear cases)
0132         if (index == 2 && on_a[1] < on_a[0])
0133         {
0134             std::swap(result.fractions[0], result.fractions[1]);
0135             std::swap(result.intersections[0], result.intersections[1]);
0136         }
0137
0138         result.count = index;
0139
0140         return result;
0141     }
0142
0143     static inline return_type disjoint()
0144     {
0145         return return_type();
0146     }
0147     static inline return_type error(std::string const&)
0148     {
0149         return return_type();
0150     }
0151
0152     // Both degenerate
0153     template <typename Segment>
0154     static inline return_type degenerate(Segment const& segment, bool)
0155     {
0156         return_type result;
0157         result.count = 1;
0158         set<0>(result.intersections[0], get<0, 0>(segment));
0159         set<1>(result.intersections[0], get<0, 1>(segment));
0160         return result;
0161     }
0162
0163     // One degenerate
0164     template <typename Segment, typename Ratio>
0165     static inline return_type one_degenerate(Segment const& degenerate_segment,
0166             Ratio const& ratio, bool a_degenerate)
0167     {
0168         return_type result;
0169         result.count = 1;
0170         set<0>(result.intersections[0], get<0, 0>(degenerate_segment));
0171         set<1>(result.intersections[0], get<0, 1>(degenerate_segment));
0172         if (a_degenerate)
0173         {
0174             // IP lies on ratio w.r.t. segment b
0175             result.fractions[0].assign(Ratio::zero(), ratio);
0176         }
0177         else
0178         {
0179             result.fractions[0].assign(ratio, Ratio::zero());
0180         }
0181         return result;
0182     }
0183 };
0184
0185
0186 }} // namespace policies::relate
0187
0188 }} // namespace boost::geometry
0189
0190 #endif // BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_INTERSECTION_POINTS_HPP