1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2014-2015, Oracle and/or its affiliates. 4 5 // Licensed under the Boost Software License version 1.0. 6 // http://www.boost.org/users/license.html 7 8 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle 9 10 11 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_TURNS_COMPARE_TURNS_HPP 12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_TURNS_COMPARE_TURNS_HPP 13 14 #include <cstddef> 15 #include <functional> 16 17 #include <boost/geometry/util/math.hpp> 18 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> 19 20 21 namespace boost { namespace geometry 22 { 23 24 namespace detail { namespace turns 25 { 26 27 // TURNS SORTING AND SEARCHING 28 29 // sort turns by G1 - source_index == 0 by: 30 // seg_id -> fraction -> other_id -> operation 31 template 32 < 33 typename IdLess = std::less<signed_size_type>, 34 int N = 0, int U = 1, int I = 2, int B = 3, int C = 4, int O = 0, 35 std::size_t OpId = 0 36 > 37 struct less_seg_fraction_other_op 38 { 39 BOOST_STATIC_ASSERT(OpId < 2); 40 static const std::size_t other_op_id = (OpId + 1) % 2; 41 42 template <typename Op> order_opboost::geometry::detail::turns::less_seg_fraction_other_op43 static inline int order_op(Op const& op) 44 { 45 switch (op.operation) 46 { 47 case detail::overlay::operation_none : return N; 48 case detail::overlay::operation_union : return U; 49 case detail::overlay::operation_intersection : return I; 50 case detail::overlay::operation_blocked : return B; 51 case detail::overlay::operation_continue : return C; 52 case detail::overlay::operation_opposite : return O; 53 } 54 return -1; 55 } 56 57 template <typename Op> use_operationboost::geometry::detail::turns::less_seg_fraction_other_op58 static inline bool use_operation(Op const& left, Op const& right) 59 { 60 return order_op(left) < order_op(right); 61 } 62 63 template <typename Turn> use_other_idboost::geometry::detail::turns::less_seg_fraction_other_op64 static inline bool use_other_id(Turn const& left, Turn const& right) 65 { 66 segment_identifier const& left_other_seg_id = left.operations[other_op_id].seg_id; 67 segment_identifier const& right_other_seg_id = right.operations[other_op_id].seg_id; 68 69 if ( left_other_seg_id.multi_index != right_other_seg_id.multi_index ) 70 { 71 return left_other_seg_id.multi_index < right_other_seg_id.multi_index; 72 } 73 if ( left_other_seg_id.ring_index != right_other_seg_id.ring_index ) 74 { 75 return left_other_seg_id.ring_index != right_other_seg_id.ring_index; 76 } 77 if ( left_other_seg_id.segment_index != right_other_seg_id.segment_index ) 78 { 79 return IdLess()(left_other_seg_id.segment_index, 80 right_other_seg_id.segment_index); 81 } 82 return use_operation(left.operations[OpId], right.operations[OpId]); 83 } 84 85 template <typename Turn> use_fractionboost::geometry::detail::turns::less_seg_fraction_other_op86 static inline bool use_fraction(Turn const& left, Turn const& right) 87 { 88 return 89 geometry::math::equals(left.operations[OpId].fraction, 90 right.operations[OpId].fraction) 91 ? 92 use_other_id(left, right) 93 : 94 (left.operations[OpId].fraction < right.operations[OpId].fraction) 95 ; 96 } 97 98 template <typename Turn> operator ()boost::geometry::detail::turns::less_seg_fraction_other_op99 inline bool operator()(Turn const& left, Turn const& right) const 100 { 101 segment_identifier const& sl = left.operations[OpId].seg_id; 102 segment_identifier const& sr = right.operations[OpId].seg_id; 103 104 return sl < sr || ( sl == sr && use_fraction(left, right) ); 105 } 106 }; 107 108 109 110 111 112 }} // namespace detail::turns 113 114 }} // namespace boost::geometry 115 116 117 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_TURNS_COMPARE_TURNS_HPP 118