1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2014-2015, Oracle and/or its affiliates.
5 // Licensed under the Boost Software License version 1.0.
6 // http://www.boost.org/users/license.html
8 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
11 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_TURNS_COMPARE_TURNS_HPP
12 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_TURNS_COMPARE_TURNS_HPP
17 #include <boost/geometry/util/math.hpp>
18 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
21 namespace boost { namespace geometry
24 namespace detail { namespace turns
27 // TURNS SORTING AND SEARCHING
29 // sort turns by G1 - source_index == 0 by:
30 // seg_id -> fraction -> other_id -> operation
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,
37 struct less_seg_fraction_other_op
39 BOOST_STATIC_ASSERT(OpId < 2);
40 static const std::size_t other_op_id = (OpId + 1) % 2;
42 template <typename Op>
43 static inline int order_op(Op const& op)
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;
57 template <typename Op>
58 static inline bool use_operation(Op const& left, Op const& right)
60 return order_op(left) < order_op(right);
63 template <typename Turn>
64 static inline bool use_other_id(Turn const& left, Turn const& right)
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;
69 if ( left_other_seg_id.multi_index != right_other_seg_id.multi_index )
71 return left_other_seg_id.multi_index < right_other_seg_id.multi_index;
73 if ( left_other_seg_id.ring_index != right_other_seg_id.ring_index )
75 return left_other_seg_id.ring_index != right_other_seg_id.ring_index;
77 if ( left_other_seg_id.segment_index != right_other_seg_id.segment_index )
79 return IdLess()(left_other_seg_id.segment_index,
80 right_other_seg_id.segment_index);
82 return use_operation(left.operations[OpId], right.operations[OpId]);
85 template <typename Turn>
86 static inline bool use_fraction(Turn const& left, Turn const& right)
89 geometry::math::equals(left.operations[OpId].fraction,
90 right.operations[OpId].fraction)
92 use_other_id(left, right)
94 (left.operations[OpId].fraction < right.operations[OpId].fraction)
98 template <typename Turn>
99 inline bool operator()(Turn const& left, Turn const& right) const
101 segment_identifier const& sl = left.operations[OpId].seg_id;
102 segment_identifier const& sr = right.operations[OpId].seg_id;
104 return sl < sr || ( sl == sr && use_fraction(left, right) );
112 }} // namespace detail::turns
114 }} // namespace boost::geometry
117 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_TURNS_COMPARE_TURNS_HPP