1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
5 // This file was modified by Oracle on 2017-2020.
6 // Modifications copyright (c) 2017-2020 Oracle and/or its affiliates.
8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
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)
14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP
15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP
23 #include <boost/core/addressof.hpp>
24 #include <boost/range/value_type.hpp>
26 #include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp>
27 #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
28 #include <boost/geometry/strategies/side.hpp>
30 namespace boost { namespace geometry
33 #ifndef DOXYGEN_NO_DETAIL
34 namespace detail { namespace overlay
37 // Wraps "turn_operation" from turn_info.hpp,
38 // giving it extra information, necessary for sorting
39 template <typename TurnOperation>
40 struct indexed_turn_operation
42 typedef TurnOperation type;
44 std::size_t turn_index;
45 std::size_t operation_index;
47 // use pointers to avoid copies, const& is not possible because of usage in vector
48 segment_identifier const* other_seg_id; // segment id of other segment of intersection of two segments
49 TurnOperation const* subject;
51 inline indexed_turn_operation(std::size_t ti, std::size_t oi,
52 TurnOperation const& sub,
53 segment_identifier const& oid)
58 , subject(boost::addressof(sub))
67 typename Geometry1, typename Geometry2,
68 typename RobustPolicy,
69 typename SideStrategy,
70 bool Reverse1, bool Reverse2
72 struct less_by_segment_ratio
74 inline less_by_segment_ratio(Turns const& turns
75 , Geometry1 const& geometry1
76 , Geometry2 const& geometry2
77 , RobustPolicy const& robust_policy
78 , SideStrategy const& strategy)
80 , m_geometry1(geometry1)
81 , m_geometry2(geometry2)
82 , m_robust_policy(robust_policy)
83 , m_strategy(strategy)
90 Geometry1 const& m_geometry1;
91 Geometry2 const& m_geometry2;
92 RobustPolicy const& m_robust_policy;
93 SideStrategy const& m_strategy;
95 typedef typename geometry::point_type<Geometry1>::type point_type;
97 inline bool default_order(Indexed const& left, Indexed const& right) const
99 // We've nothing to sort on. Take the indexes
100 return left.turn_index < right.turn_index;
103 inline bool consider_relative_order(Indexed const& left,
104 Indexed const& right) const
106 point_type pi, pj, ri, rj, si, sj;
108 geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2,
109 left.subject->seg_id,
111 geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2,
114 geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2,
118 int const side_rj_p = m_strategy.apply(pi, pj, rj);
119 int const side_sj_p = m_strategy.apply(pi, pj, sj);
121 // Put the one turning left (1; right == -1) as last
122 if (side_rj_p != side_sj_p)
124 return side_rj_p < side_sj_p;
127 int const side_sj_r = m_strategy.apply(ri, rj, sj);
128 int const side_rj_s = m_strategy.apply(si, sj, rj);
130 // If they both turn left: the most left as last
131 // If they both turn right: this is not relevant, but take also here most left
132 if (side_rj_s != side_sj_r)
134 return side_rj_s < side_sj_r;
137 return default_order(left, right);
143 // Note that left/right do NOT correspond to m_geometry1/m_geometry2
144 // but to the "indexed_turn_operation"
145 inline bool operator()(Indexed const& left, Indexed const& right) const
147 if (! (left.subject->seg_id == right.subject->seg_id))
149 return left.subject->seg_id < right.subject->seg_id;
152 // Both left and right are located on the SAME segment.
154 if (! (left.subject->fraction == right.subject->fraction))
156 return left.subject->fraction < right.subject->fraction;
160 typedef typename boost::range_value<Turns>::type turn_type;
161 turn_type const& left_turn = m_turns[left.turn_index];
162 turn_type const& right_turn = m_turns[right.turn_index];
164 // First check "real" intersection (crosses)
165 // -> distance zero due to precision, solve it by sorting
166 if (left_turn.method == method_crosses
167 && right_turn.method == method_crosses)
169 return consider_relative_order(left, right);
172 bool const left_both_xx = left_turn.both(operation_blocked);
173 bool const right_both_xx = right_turn.both(operation_blocked);
174 if (left_both_xx && ! right_both_xx)
178 if (! left_both_xx && right_both_xx)
183 bool const left_both_uu = left_turn.both(operation_union);
184 bool const right_both_uu = right_turn.both(operation_union);
185 if (left_both_uu && ! right_both_uu)
189 if (! left_both_uu && right_both_uu)
194 return default_order(left, right);
199 }} // namespace detail::overlay
200 #endif //DOXYGEN_NO_DETAIL
203 }} // namespace boost::geometry
205 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP