]>
Commit | Line | Data |
---|---|---|
b32b8144 FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2017 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | ||
5 | // Use, modification and distribution is subject to the Boost Software License, | |
6 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
7 | // http://www.boost.org/LICENSE_1_0.txt) | |
8 | ||
9 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP | |
10 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP | |
11 | ||
12 | #include <boost/range.hpp> | |
13 | ||
14 | #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp> | |
15 | #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp> | |
16 | #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> | |
17 | #include <boost/geometry/algorithms/within.hpp> | |
18 | ||
19 | namespace boost { namespace geometry | |
20 | { | |
21 | ||
22 | #ifndef DOXYGEN_NO_DETAIL | |
23 | namespace detail { namespace overlay | |
24 | { | |
25 | ||
26 | struct discard_turns | |
27 | { | |
28 | template <typename Turns, typename Clusters, typename Geometry0, typename Geometry1> | |
29 | static inline | |
30 | void apply(Turns& , Clusters const& , Geometry0 const& , Geometry1 const& ) | |
31 | {} | |
32 | }; | |
33 | ||
34 | template <overlay_type OverlayType, operation_type OperationType> | |
35 | struct discard_closed_turns : discard_turns {}; | |
36 | ||
37 | // It is only implemented for operation_union, not in buffer | |
38 | template <> | |
39 | struct discard_closed_turns<overlay_union, operation_union> | |
40 | { | |
41 | ||
42 | template <typename Turns, typename Clusters, typename Geometry0, typename Geometry1> | |
43 | static inline | |
44 | void apply(Turns& turns, Clusters const& clusters, | |
45 | Geometry0 const& geometry0, Geometry1 const& geometry1) | |
46 | { | |
47 | typedef typename boost::range_value<Turns>::type turn_type; | |
48 | ||
49 | for (typename boost::range_iterator<Turns>::type | |
50 | it = boost::begin(turns); | |
51 | it != boost::end(turns); | |
52 | ++it) | |
53 | { | |
54 | turn_type& turn = *it; | |
55 | ||
56 | if (turn.discarded || ! is_self_turn<overlay_union>(turn)) | |
57 | { | |
58 | continue; | |
59 | } | |
60 | ||
61 | bool const within = | |
62 | turn.operations[0].seg_id.source_index == 0 | |
63 | ? geometry::within(turn.point, geometry1) | |
64 | : geometry::within(turn.point, geometry0); | |
65 | ||
66 | if (within) | |
67 | { | |
68 | // It is in the interior of the other geometry | |
69 | turn.discarded = true; | |
70 | } | |
71 | } | |
72 | } | |
73 | }; | |
74 | ||
75 | struct discard_self_intersection_turns | |
76 | { | |
77 | private : | |
78 | ||
79 | template <typename Turns, typename Clusters> | |
80 | static inline | |
81 | bool any_blocked(signed_size_type cluster_id, | |
82 | const Turns& turns, Clusters const& clusters) | |
83 | { | |
84 | typename Clusters::const_iterator cit = clusters.find(cluster_id); | |
85 | if (cit == clusters.end()) | |
86 | { | |
87 | return false; | |
88 | } | |
89 | cluster_info const& cinfo = cit->second; | |
90 | for (std::set<signed_size_type>::const_iterator it | |
91 | = cinfo.turn_indices.begin(); | |
92 | it != cinfo.turn_indices.end(); ++it) | |
93 | { | |
94 | typename boost::range_value<Turns>::type const& turn = turns[*it]; | |
95 | if (turn.any_blocked()) | |
96 | { | |
97 | return true; | |
98 | } | |
99 | } | |
100 | return false; | |
101 | } | |
102 | ||
103 | template <typename Turns, typename Clusters> | |
104 | static inline | |
105 | bool is_self_cluster(signed_size_type cluster_id, | |
106 | const Turns& turns, Clusters const& clusters) | |
107 | { | |
108 | typename Clusters::const_iterator cit = clusters.find(cluster_id); | |
109 | if (cit == clusters.end()) | |
110 | { | |
111 | return false; | |
112 | } | |
113 | ||
114 | cluster_info const& cinfo = cit->second; | |
115 | for (std::set<signed_size_type>::const_iterator it | |
116 | = cinfo.turn_indices.begin(); | |
117 | it != cinfo.turn_indices.end(); ++it) | |
118 | { | |
119 | if (! is_self_turn<overlay_intersection>(turns[*it])) | |
120 | { | |
121 | return false; | |
122 | } | |
123 | } | |
124 | ||
125 | return true; | |
126 | } | |
127 | ||
128 | template <typename Turn, typename Geometry0, typename Geometry1> | |
129 | static inline | |
130 | bool within(Turn const& turn, Geometry0 const& geometry0, | |
131 | Geometry1 const& geometry1) | |
132 | { | |
133 | return turn.operations[0].seg_id.source_index == 0 | |
134 | ? geometry::within(turn.point, geometry1) | |
135 | : geometry::within(turn.point, geometry0); | |
136 | } | |
137 | ||
138 | template <typename Turns, typename Clusters, | |
139 | typename Geometry0, typename Geometry1> | |
140 | static inline | |
141 | void discard_clusters(Turns& turns, Clusters const& clusters, | |
142 | Geometry0 const& geometry0, Geometry1 const& geometry1) | |
143 | { | |
144 | for (typename Clusters::const_iterator cit = clusters.begin(); | |
145 | cit != clusters.end(); ++cit) | |
146 | { | |
147 | signed_size_type cluster_id = cit->first; | |
148 | ||
149 | // If there are only self-turns in the cluster, the cluster should | |
150 | // be located within the other geometry, for intersection | |
151 | if (is_self_cluster(cluster_id, turns, clusters)) | |
152 | { | |
153 | cluster_info const& cinfo = cit->second; | |
154 | if (! within(turns[*cinfo.turn_indices.begin()], geometry0, geometry1)) | |
155 | { | |
156 | // Discard all turns in cluster | |
157 | for (std::set<signed_size_type>::const_iterator sit = cinfo.turn_indices.begin(); | |
158 | sit != cinfo.turn_indices.end(); ++sit) | |
159 | { | |
160 | turns[*sit].discarded = true; | |
161 | } | |
162 | } | |
163 | } | |
164 | } | |
165 | } | |
166 | ||
167 | public : | |
168 | ||
169 | template <typename Turns, typename Clusters, | |
170 | typename Geometry0, typename Geometry1> | |
171 | static inline | |
172 | void apply(Turns& turns, Clusters const& clusters, | |
173 | Geometry0 const& geometry0, Geometry1 const& geometry1) | |
174 | { | |
175 | discard_clusters(turns, clusters, geometry0, geometry1); | |
176 | ||
177 | typedef typename boost::range_value<Turns>::type turn_type; | |
178 | ||
179 | for (typename boost::range_iterator<Turns>::type | |
180 | it = boost::begin(turns); | |
181 | it != boost::end(turns); | |
182 | ++it) | |
183 | { | |
184 | turn_type& turn = *it; | |
185 | ||
186 | if (turn.discarded || ! is_self_turn<overlay_intersection>(turn)) | |
187 | { | |
188 | continue; | |
189 | } | |
190 | ||
191 | segment_identifier const& id0 = turn.operations[0].seg_id; | |
192 | segment_identifier const& id1 = turn.operations[1].seg_id; | |
193 | if (id0.multi_index != id1.multi_index | |
194 | || (id0.ring_index == -1 && id1.ring_index == -1) | |
195 | || (id0.ring_index >= 0 && id1.ring_index >= 0)) | |
196 | { | |
197 | // Not an ii ring (int/ext) on same ring | |
198 | continue; | |
199 | } | |
200 | ||
201 | if (turn.is_clustered() && turn.has_colocated_both) | |
202 | { | |
203 | // Don't delete a self-ii-turn colocated with another ii-turn | |
204 | // (for example #case_recursive_boxes_70) | |
205 | // But for some cases (#case_58_iet) they should be deleted, | |
206 | // there are many self-turns there and also blocked turns there | |
207 | if (! any_blocked(turn.cluster_id, turns, clusters)) | |
208 | { | |
209 | continue; | |
210 | } | |
211 | } | |
212 | ||
213 | // It is a ii self-turn | |
214 | // Check if it is within the other geometry | |
215 | // If not, it can be ignored | |
216 | if (! within(turn, geometry0, geometry1)) | |
217 | { | |
218 | // It is not within another geometry, discard the turn | |
219 | turn.discarded = true; | |
220 | } | |
221 | } | |
222 | } | |
223 | }; | |
224 | ||
225 | template <overlay_type OverlayType, operation_type OperationType> | |
226 | struct discard_open_turns : discard_turns {}; | |
227 | ||
228 | // Handler it for intersection | |
229 | template <> | |
230 | struct discard_open_turns<overlay_intersection, operation_intersection> | |
231 | : discard_self_intersection_turns {}; | |
232 | ||
233 | // For difference, it should be done in a different way (TODO) | |
234 | ||
235 | ||
236 | template <overlay_type OverlayType, typename Turns> | |
237 | inline void discard_self_turns_which_loop(Turns& turns) | |
238 | { | |
239 | if (operation_from_overlay<OverlayType>::value == operation_union) | |
240 | { | |
241 | // For union, self-turn i/u traveling to itself are allowed to form | |
242 | // holes. #case_recursive_boxes_37 | |
243 | // TODO: this can be finetuned by inspecting the cluster too, | |
244 | // and if there are non-self-turns the polygons on their sides can | |
245 | // be checked | |
246 | return; | |
247 | } | |
248 | ||
249 | typedef typename boost::range_value<Turns>::type turn_type; | |
250 | typedef typename turn_type::turn_operation_type op_type; | |
251 | ||
252 | signed_size_type turn_index = 0; | |
253 | for (typename boost::range_iterator<Turns>::type | |
254 | it = boost::begin(turns); | |
255 | it != boost::end(turns); | |
256 | ++it, ++turn_index) | |
257 | { | |
258 | turn_type& turn = *it; | |
259 | ||
260 | if (! is_self_turn<OverlayType>(turn)) | |
261 | { | |
262 | continue; | |
263 | } | |
264 | if (! turn.combination(operation_intersection, operation_union)) | |
265 | { | |
266 | // ii may travel to itself | |
267 | continue; | |
268 | } | |
269 | ||
270 | for (int i = 0; i < 2; i++) | |
271 | { | |
272 | op_type& op = turn.operations[i]; | |
273 | ||
274 | if (op.enriched.startable | |
275 | && op.operation == operation_intersection | |
276 | && op.enriched.get_next_turn_index() == turn_index) | |
277 | { | |
278 | // Self-turn i/u, i part traveling to itself. Discard it. | |
279 | // (alternatively it might be made unstartable - but the | |
280 | // intersection-operation may not be traveled anyway, and the | |
281 | // union-operation is not traveled at all in intersections | |
282 | // #case_recursive_boxes_77 | |
283 | turn.discarded = true; | |
284 | } | |
285 | } | |
286 | } | |
287 | ||
288 | } | |
289 | ||
290 | }} // namespace detail::overlay | |
291 | #endif //DOXYGEN_NO_DETAIL | |
292 | ||
293 | ||
294 | }} // namespace boost::geometry | |
295 | ||
296 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP |