]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | ||
b32b8144 FG |
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 | ||
7c673cae FG |
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 | ||
50 | 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, | |
b32b8144 | 68 | typename SideStrategy, |
7c673cae FG |
69 | bool Reverse1, bool Reverse2 |
70 | > | |
71 | struct less_by_segment_ratio | |
72 | { | |
73 | inline less_by_segment_ratio(Turns const& turns | |
74 | , operation_type for_operation | |
75 | , Geometry1 const& geometry1 | |
76 | , Geometry2 const& geometry2 | |
b32b8144 FG |
77 | , RobustPolicy const& robust_policy |
78 | , SideStrategy const& strategy) | |
7c673cae FG |
79 | : m_turns(turns) |
80 | , m_for_operation(for_operation) | |
81 | , m_geometry1(geometry1) | |
82 | , m_geometry2(geometry2) | |
83 | , m_robust_policy(robust_policy) | |
b32b8144 | 84 | , m_strategy(strategy) |
7c673cae FG |
85 | { |
86 | } | |
87 | ||
88 | private : | |
89 | ||
90 | Turns const& m_turns; | |
91 | operation_type m_for_operation; | |
92 | Geometry1 const& m_geometry1; | |
93 | Geometry2 const& m_geometry2; | |
94 | RobustPolicy const& m_robust_policy; | |
b32b8144 | 95 | SideStrategy const& m_strategy; |
7c673cae FG |
96 | |
97 | typedef typename geometry::point_type<Geometry1>::type point_type; | |
98 | ||
99 | inline bool default_order(Indexed const& left, Indexed const& right) const | |
100 | { | |
101 | // We've nothing to sort on. Take the indexes | |
102 | return left.turn_index < right.turn_index; | |
103 | } | |
104 | ||
105 | inline bool consider_relative_order(Indexed const& left, | |
106 | Indexed const& right) const | |
107 | { | |
108 | point_type pi, pj, ri, rj, si, sj; | |
109 | ||
110 | geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2, | |
111 | left.subject->seg_id, | |
112 | pi, pj); | |
113 | geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2, | |
114 | *left.other_seg_id, | |
115 | ri, rj); | |
116 | geometry::copy_segment_points<Reverse1, Reverse2>(m_geometry1, m_geometry2, | |
117 | *right.other_seg_id, | |
118 | si, sj); | |
119 | ||
b32b8144 FG |
120 | int const side_rj_p = m_strategy.apply(pi, pj, rj); |
121 | int const side_sj_p = m_strategy.apply(pi, pj, sj); | |
7c673cae FG |
122 | |
123 | // Put the one turning left (1; right == -1) as last | |
124 | if (side_rj_p != side_sj_p) | |
125 | { | |
126 | return side_rj_p < side_sj_p; | |
127 | } | |
128 | ||
b32b8144 FG |
129 | int const side_sj_r = m_strategy.apply(ri, rj, sj); |
130 | int const side_rj_s = m_strategy.apply(si, sj, rj); | |
7c673cae FG |
131 | |
132 | // If they both turn left: the most left as last | |
133 | // If they both turn right: this is not relevant, but take also here most left | |
134 | if (side_rj_s != side_sj_r) | |
135 | { | |
136 | return side_rj_s < side_sj_r; | |
137 | } | |
138 | ||
139 | return default_order(left, right); | |
140 | } | |
141 | ||
142 | ||
143 | public : | |
144 | ||
145 | // Note that left/right do NOT correspond to m_geometry1/m_geometry2 | |
146 | // but to the "indexed_turn_operation" | |
147 | inline bool operator()(Indexed const& left, Indexed const& right) const | |
148 | { | |
149 | if (! (left.subject->seg_id == right.subject->seg_id)) | |
150 | { | |
151 | return left.subject->seg_id < right.subject->seg_id; | |
152 | } | |
153 | ||
154 | // Both left and right are located on the SAME segment. | |
155 | ||
156 | if (! (left.subject->fraction == right.subject->fraction)) | |
157 | { | |
158 | return left.subject->fraction < right.subject->fraction; | |
159 | } | |
160 | ||
161 | ||
162 | typedef typename boost::range_value<Turns>::type turn_type; | |
163 | turn_type const& left_turn = m_turns[left.turn_index]; | |
164 | turn_type const& right_turn = m_turns[right.turn_index]; | |
165 | ||
166 | // First check "real" intersection (crosses) | |
167 | // -> distance zero due to precision, solve it by sorting | |
168 | if (left_turn.method == method_crosses | |
169 | && right_turn.method == method_crosses) | |
170 | { | |
171 | return consider_relative_order(left, right); | |
172 | } | |
173 | ||
174 | bool const left_both_xx = left_turn.both(operation_blocked); | |
175 | bool const right_both_xx = right_turn.both(operation_blocked); | |
176 | if (left_both_xx && ! right_both_xx) | |
177 | { | |
178 | return true; | |
179 | } | |
180 | if (! left_both_xx && right_both_xx) | |
181 | { | |
182 | return false; | |
183 | } | |
184 | ||
185 | bool const left_both_uu = left_turn.both(operation_union); | |
186 | bool const right_both_uu = right_turn.both(operation_union); | |
187 | if (left_both_uu && ! right_both_uu) | |
188 | { | |
189 | return true; | |
190 | } | |
191 | if (! left_both_uu && right_both_uu) | |
192 | { | |
193 | return false; | |
194 | } | |
195 | ||
196 | return default_order(left, right); | |
197 | } | |
198 | }; | |
199 | ||
200 | ||
201 | }} // namespace detail::overlay | |
202 | #endif //DOXYGEN_NO_DETAIL | |
203 | ||
204 | ||
205 | }} // namespace boost::geometry | |
206 | ||
207 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SORT_ON_SEGMENT_RATIO_HPP |