1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. 4 5 // This file was modified by Oracle on 2016. 6 // Modifications copyright (c) 2016 Oracle and/or its affiliates. 7 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 8 9 // Use, modification and distribution is subject to the Boost Software License, 10 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 11 // http://www.boost.org/LICENSE_1_0.txt) 12 13 #ifndef BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_INTERSECTION_POINTS_HPP 14 #define BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_INTERSECTION_POINTS_HPP 15 16 17 #include <algorithm> 18 #include <string> 19 20 #include <boost/geometry/algorithms/detail/assign_indexed_point.hpp> 21 #include <boost/geometry/core/access.hpp> 22 #include <boost/geometry/core/assert.hpp> 23 #include <boost/geometry/strategies/side_info.hpp> 24 25 namespace boost { namespace geometry 26 { 27 28 namespace policies { namespace relate 29 { 30 31 32 /*! 33 \brief Policy calculating the intersection points themselves 34 */ 35 template 36 < 37 typename ReturnType 38 > 39 struct segments_intersection_points 40 { 41 typedef ReturnType return_type; 42 43 template 44 < 45 typename Segment1, 46 typename Segment2, 47 typename SegmentIntersectionInfo 48 > segments_crossesboost::geometry::policies::relate::segments_intersection_points49 static inline return_type segments_crosses(side_info const&, 50 SegmentIntersectionInfo const& sinfo, 51 Segment1 const& s1, Segment2 const& s2) 52 { 53 return_type result; 54 result.count = 1; 55 sinfo.calculate(result.intersections[0], s1, s2); 56 57 // Temporary - this should go later 58 result.fractions[0].assign(sinfo); 59 60 return result; 61 } 62 63 template <typename Segment1, typename Segment2, typename Ratio> segments_collinearboost::geometry::policies::relate::segments_intersection_points64 static inline return_type segments_collinear( 65 Segment1 const& a, Segment2 const& b, bool /*opposite*/, 66 int a1_wrt_b, int a2_wrt_b, int b1_wrt_a, int b2_wrt_a, 67 Ratio const& ra_from_wrt_b, Ratio const& ra_to_wrt_b, 68 Ratio const& rb_from_wrt_a, Ratio const& rb_to_wrt_a) 69 { 70 return_type result; 71 unsigned int index = 0, count_a = 0, count_b = 0; 72 Ratio on_a[2]; 73 74 // The conditions "index < 2" are necessary for non-robust handling, 75 // if index would be 2 this indicate an (currently uncatched) error 76 77 // IMPORTANT: the order of conditions is different as in direction.hpp 78 if (a1_wrt_b >= 1 && a1_wrt_b <= 3 // ra_from_wrt_b.on_segment() 79 && index < 2) 80 { 81 // a1--------->a2 82 // b1----->b2 83 // 84 // ra1 (relative to b) is between 0/1: 85 // -> First point of A is intersection point 86 detail::assign_point_from_index<0>(a, result.intersections[index]); 87 result.fractions[index].assign(Ratio::zero(), ra_from_wrt_b); 88 on_a[index] = Ratio::zero(); 89 index++; 90 count_a++; 91 } 92 if (b1_wrt_a == 2 //rb_from_wrt_a.in_segment() 93 && index < 2) 94 { 95 // We take the first intersection point of B 96 // a1--------->a2 97 // b1----->b2 98 // But only if it is not located on A 99 // a1--------->a2 100 // b1----->b2 rb_from_wrt_a == 0/1 -> a already taken 101 102 detail::assign_point_from_index<0>(b, result.intersections[index]); 103 result.fractions[index].assign(rb_from_wrt_a, Ratio::zero()); 104 on_a[index] = rb_from_wrt_a; 105 index++; 106 count_b++; 107 } 108 109 if (a2_wrt_b >= 1 && a2_wrt_b <= 3 //ra_to_wrt_b.on_segment() 110 && index < 2) 111 { 112 // Similarly, second IP (here a2) 113 // a1--------->a2 114 // b1----->b2 115 detail::assign_point_from_index<1>(a, result.intersections[index]); 116 result.fractions[index].assign(Ratio::one(), ra_to_wrt_b); 117 on_a[index] = Ratio::one(); 118 index++; 119 count_a++; 120 } 121 if (b2_wrt_a == 2 // rb_to_wrt_a.in_segment() 122 && index < 2) 123 { 124 detail::assign_point_from_index<1>(b, result.intersections[index]); 125 result.fractions[index].assign(rb_to_wrt_a, Ratio::one()); 126 on_a[index] = rb_to_wrt_a; 127 index++; 128 count_b++; 129 } 130 131 // TEMPORARY 132 // If both are from b, and b is reversed w.r.t. a, we swap IP's 133 // to align them w.r.t. a 134 // get_turn_info still relies on some order (in some collinear cases) 135 if (index == 2 && on_a[1] < on_a[0]) 136 { 137 std::swap(result.fractions[0], result.fractions[1]); 138 std::swap(result.intersections[0], result.intersections[1]); 139 } 140 141 result.count = index; 142 143 return result; 144 } 145 disjointboost::geometry::policies::relate::segments_intersection_points146 static inline return_type disjoint() 147 { 148 return return_type(); 149 } errorboost::geometry::policies::relate::segments_intersection_points150 static inline return_type error(std::string const&) 151 { 152 return return_type(); 153 } 154 155 // Both degenerate 156 template <typename Segment> degenerateboost::geometry::policies::relate::segments_intersection_points157 static inline return_type degenerate(Segment const& segment, bool) 158 { 159 return_type result; 160 result.count = 1; 161 set<0>(result.intersections[0], get<0, 0>(segment)); 162 set<1>(result.intersections[0], get<0, 1>(segment)); 163 return result; 164 } 165 166 // One degenerate 167 template <typename Segment, typename Ratio> one_degenerateboost::geometry::policies::relate::segments_intersection_points168 static inline return_type one_degenerate(Segment const& degenerate_segment, 169 Ratio const& ratio, bool a_degenerate) 170 { 171 return_type result; 172 result.count = 1; 173 set<0>(result.intersections[0], get<0, 0>(degenerate_segment)); 174 set<1>(result.intersections[0], get<0, 1>(degenerate_segment)); 175 if (a_degenerate) 176 { 177 // IP lies on ratio w.r.t. segment b 178 result.fractions[0].assign(Ratio::zero(), ratio); 179 } 180 else 181 { 182 result.fractions[0].assign(ratio, Ratio::zero()); 183 } 184 return result; 185 } 186 }; 187 188 189 }} // namespace policies::relate 190 191 }} // namespace boost::geometry 192 193 #endif // BOOST_GEOMETRY_GEOMETRY_POLICIES_RELATE_INTERSECTION_POINTS_HPP 194