]>
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 | |
7c673cae FG |
74 | , Geometry1 const& geometry1 |
75 | , Geometry2 const& geometry2 | |
b32b8144 FG |
76 | , RobustPolicy const& robust_policy |
77 | , SideStrategy const& strategy) | |
7c673cae | 78 | : m_turns(turns) |
7c673cae FG |
79 | , m_geometry1(geometry1) |
80 | , m_geometry2(geometry2) | |
81 | , m_robust_policy(robust_policy) | |
b32b8144 | 82 | , m_strategy(strategy) |
7c673cae FG |
83 | { |
84 | } | |
85 | ||
86 | private : | |
87 | ||
88 | Turns const& m_turns; | |
7c673cae FG |
89 | Geometry1 const& m_geometry1; |
90 | Geometry2 const& m_geometry2; | |
91 | RobustPolicy const& m_robust_policy; | |
b32b8144 | 92 | SideStrategy const& m_strategy; |
7c673cae FG |
93 | |
94 | typedef typename geometry::point_type<Geometry1>::type point_type; | |
95 | ||
96 | 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 | ||
102 | 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 | ||
b32b8144 FG |
117 | int const side_rj_p = m_strategy.apply(pi, pj, rj); |
118 | int const side_sj_p = m_strategy.apply(pi, pj, sj); | |
7c673cae FG |
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 | ||
b32b8144 FG |
126 | int const side_sj_r = m_strategy.apply(ri, rj, sj); |
127 | int const side_rj_s = m_strategy.apply(si, sj, rj); | |
7c673cae FG |
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" | |
144 | 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 |