1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. 4 5 // This file was modified by Oracle on 2017. 6 // Modifications copyright (c) 2017 Oracle and/or its affiliates. 7 8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 9 10 // Use, modification and distribution is subject to the Boost Software License, 11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 12 // http://www.boost.org/LICENSE_1_0.txt) 13 14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP 15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP 16 17 #include <cstddef> 18 #include <algorithm> 19 #include <map> 20 #include <set> 21 #include <vector> 22 23 #include <boost/range.hpp> 24 25 #include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp> 26 #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp> 27 #include <boost/geometry/strategies/side.hpp> 28 29 namespace boost { namespace geometry 30 { 31 32 #ifndef DOXYGEN_NO_DETAIL 33 namespace detail { namespace overlay 34 { 35 36 // Wraps "turn_operation" from turn_info.hpp, 37 // giving it extra information, necessary for sorting 38 template <typename TurnOperation> 39 struct indexed_turn_operation 40 { 41 typedef TurnOperation type; 42 43 std::size_t turn_index; 44 std::size_t operation_index; 45 bool skip; 46 // use pointers to avoid copies, const& is not possible because of usage in vector 47 segment_identifier const* other_seg_id; // segment id of other segment of intersection of two segments 48 TurnOperation const* subject; 49 indexed_turn_operationboost::geometry::detail::overlay::indexed_turn_operation50 inline indexed_turn_operation(std::size_t ti, std::size_t oi, 51 TurnOperation const& sub, 52 segment_identifier const& oid) 53 : turn_index(ti) 54 , operation_index(oi) 55 , skip(false) 56 , other_seg_id(&oid) 57 , subject(boost::addressof(sub)) 58 {} 59 60 }; 61 62 template 63 < 64 typename Turns, 65 typename Indexed, 66 typename Geometry1, typename Geometry2, 67 typename RobustPolicy, 68 typename SideStrategy, 69 bool Reverse1, bool Reverse2 70 > 71 struct less_by_segment_ratio 72 { less_by_segment_ratioboost::geometry::detail::overlay::less_by_segment_ratio73 inline less_by_segment_ratio(Turns const& turns 74 , Geometry1 const& geometry1 75 , Geometry2 const& geometry2 76 , RobustPolicy const& robust_policy 77 , SideStrategy const& strategy) 78 : m_turns(turns) 79 , m_geometry1(geometry1) 80 , m_geometry2(geometry2) 81 , m_robust_policy(robust_policy) 82 , m_strategy(strategy) 83 { 84 } 85 86 private : 87 88 Turns const& m_turns; 89 Geometry1 const& m_geometry1; 90 Geometry2 const& m_geometry2; 91 RobustPolicy const& m_robust_policy; 92 SideStrategy const& m_strategy; 93 94 typedef typename geometry::point_type<Geometry1>::type point_type; 95 default_orderboost::geometry::detail::overlay::less_by_segment_ratio96 inline bool default_order(Indexed const& left, Indexed const& right) const 97 { 98 // We've nothing to sort on. Take the indexes 99 return left.turn_index < right.turn_index; 100 } 101 consider_relative_orderboost::geometry::detail::overlay::less_by_segment_ratio102 inline bool consider_relative_order(Indexed const& left, 103 Indexed const& right) const 104 { 105 point_type pi, pj, ri, rj, si, sj; 106 107 geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2, 108 left.subject->seg_id, 109 pi, pj); 110 geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2, 111 *left.other_seg_id, 112 ri, rj); 113 geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2, 114 *right.other_seg_id, 115 si, sj); 116 117 int const side_rj_p = m_strategy.apply(pi, pj, rj); 118 int const side_sj_p = m_strategy.apply(pi, pj, sj); 119 120 // Put the one turning left (1; right == -1) as last 121 if (side_rj_p != side_sj_p) 122 { 123 return side_rj_p < side_sj_p; 124 } 125 126 int const side_sj_r = m_strategy.apply(ri, rj, sj); 127 int const side_rj_s = m_strategy.apply(si, sj, rj); 128 129 // If they both turn left: the most left as last 130 // If they both turn right: this is not relevant, but take also here most left 131 if (side_rj_s != side_sj_r) 132 { 133 return side_rj_s < side_sj_r; 134 } 135 136 return default_order(left, right); 137 } 138 139 140 public : 141 142 // Note that left/right do NOT correspond to m_geometry1/m_geometry2 143 // but to the "indexed_turn_operation" operator ()boost::geometry::detail::overlay::less_by_segment_ratio144 inline bool operator()(Indexed const& left, Indexed const& right) const 145 { 146 if (! (left.subject->seg_id == right.subject->seg_id)) 147 { 148 return left.subject->seg_id < right.subject->seg_id; 149 } 150 151 // Both left and right are located on the SAME segment. 152 153 if (! (left.subject->fraction == right.subject->fraction)) 154 { 155 return left.subject->fraction < right.subject->fraction; 156 } 157 158 159 typedef typename boost::range_value<Turns>::type turn_type; 160 turn_type const& left_turn = m_turns[left.turn_index]; 161 turn_type const& right_turn = m_turns[right.turn_index]; 162 163 // First check "real" intersection (crosses) 164 // -> distance zero due to precision, solve it by sorting 165 if (left_turn.method == method_crosses 166 && right_turn.method == method_crosses) 167 { 168 return consider_relative_order(left, right); 169 } 170 171 bool const left_both_xx = left_turn.both(operation_blocked); 172 bool const right_both_xx = right_turn.both(operation_blocked); 173 if (left_both_xx && ! right_both_xx) 174 { 175 return true; 176 } 177 if (! left_both_xx && right_both_xx) 178 { 179 return false; 180 } 181 182 bool const left_both_uu = left_turn.both(operation_union); 183 bool const right_both_uu = right_turn.both(operation_union); 184 if (left_both_uu && ! right_both_uu) 185 { 186 return true; 187 } 188 if (! left_both_uu && right_both_uu) 189 { 190 return false; 191 } 192 193 return default_order(left, right); 194 } 195 }; 196 197 198 }} // namespace detail::overlay 199 #endif //DOXYGEN_NO_DETAIL 200 201 202 }} // namespace boost::geometry 203 204 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP 205