]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2015 Barend Gehrels, Amsterdam, the Netherlands. | |
11fdf7f2 | 4 | // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. |
7c673cae | 5 | |
b32b8144 FG |
6 | // This file was modified by Oracle on 2017. |
7 | // Modifications copyright (c) 2017 Oracle and/or its affiliates. | |
8 | ||
9 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
10 | ||
7c673cae FG |
11 | // Use, modification and distribution is subject to the Boost Software License, |
12 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
13 | // http://www.boost.org/LICENSE_1_0.txt) | |
14 | ||
15 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP | |
16 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP | |
17 | ||
18 | #include <cstddef> | |
19 | #include <algorithm> | |
20 | #include <map> | |
21 | #include <vector> | |
22 | ||
b32b8144 | 23 | #include <boost/core/ignore_unused.hpp> |
7c673cae | 24 | #include <boost/range.hpp> |
92f5a8d4 | 25 | #include <boost/geometry/core/assert.hpp> |
7c673cae FG |
26 | #include <boost/geometry/core/point_order.hpp> |
27 | #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp> | |
28 | #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp> | |
92f5a8d4 | 29 | #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp> |
b32b8144 | 30 | #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp> |
7c673cae FG |
31 | #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> |
32 | #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp> | |
33 | #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> | |
34 | #include <boost/geometry/algorithms/detail/ring_identifier.hpp> | |
35 | #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp> | |
11fdf7f2 | 36 | #include <boost/geometry/util/condition.hpp> |
7c673cae FG |
37 | |
38 | #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS) | |
39 | # include <iostream> | |
40 | # include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp> | |
41 | # include <boost/geometry/io/wkt/wkt.hpp> | |
42 | # define BOOST_GEOMETRY_DEBUG_IDENTIFIER | |
43 | #endif | |
44 | ||
45 | namespace boost { namespace geometry | |
46 | { | |
47 | ||
48 | #ifndef DOXYGEN_NO_DETAIL | |
49 | namespace detail { namespace overlay | |
50 | { | |
51 | ||
52 | template <typename SegmentRatio> | |
53 | struct segment_fraction | |
54 | { | |
55 | segment_identifier seg_id; | |
56 | SegmentRatio fraction; | |
57 | ||
58 | segment_fraction(segment_identifier const& id, SegmentRatio const& fr) | |
59 | : seg_id(id) | |
60 | , fraction(fr) | |
61 | {} | |
62 | ||
63 | segment_fraction() | |
64 | {} | |
65 | ||
66 | bool operator<(segment_fraction<SegmentRatio> const& other) const | |
67 | { | |
68 | return seg_id == other.seg_id | |
69 | ? fraction < other.fraction | |
70 | : seg_id < other.seg_id; | |
71 | } | |
72 | ||
73 | }; | |
74 | ||
75 | struct turn_operation_index | |
76 | { | |
77 | turn_operation_index(signed_size_type ti = -1, | |
78 | signed_size_type oi = -1) | |
79 | : turn_index(ti) | |
80 | , op_index(oi) | |
81 | {} | |
82 | ||
83 | signed_size_type turn_index; | |
84 | signed_size_type op_index; // only 0,1 | |
85 | }; | |
86 | ||
7c673cae FG |
87 | template <typename Turns> |
88 | struct less_by_fraction_and_type | |
89 | { | |
90 | inline less_by_fraction_and_type(Turns const& turns) | |
91 | : m_turns(turns) | |
92 | { | |
93 | } | |
94 | ||
95 | inline bool operator()(turn_operation_index const& left, | |
96 | turn_operation_index const& right) const | |
97 | { | |
98 | typedef typename boost::range_value<Turns>::type turn_type; | |
99 | typedef typename turn_type::turn_operation_type turn_operation_type; | |
100 | ||
101 | turn_type const& left_turn = m_turns[left.turn_index]; | |
102 | turn_type const& right_turn = m_turns[right.turn_index]; | |
103 | turn_operation_type const& left_op | |
104 | = left_turn.operations[left.op_index]; | |
105 | ||
106 | turn_operation_type const& right_op | |
107 | = right_turn.operations[right.op_index]; | |
108 | ||
109 | if (! (left_op.fraction == right_op.fraction)) | |
110 | { | |
111 | return left_op.fraction < right_op.fraction; | |
112 | } | |
113 | ||
114 | // Order xx first - used to discard any following colocated turn | |
115 | bool const left_both_xx = left_turn.both(operation_blocked); | |
116 | bool const right_both_xx = right_turn.both(operation_blocked); | |
117 | if (left_both_xx && ! right_both_xx) | |
118 | { | |
119 | return true; | |
120 | } | |
121 | if (! left_both_xx && right_both_xx) | |
122 | { | |
123 | return false; | |
124 | } | |
125 | ||
126 | bool const left_both_uu = left_turn.both(operation_union); | |
127 | bool const right_both_uu = right_turn.both(operation_union); | |
128 | if (left_both_uu && ! right_both_uu) | |
129 | { | |
130 | return true; | |
131 | } | |
132 | if (! left_both_uu && right_both_uu) | |
133 | { | |
134 | return false; | |
135 | } | |
136 | ||
137 | turn_operation_type const& left_other_op | |
138 | = left_turn.operations[1 - left.op_index]; | |
139 | ||
140 | turn_operation_type const& right_other_op | |
141 | = right_turn.operations[1 - right.op_index]; | |
142 | ||
143 | // Fraction is the same, now sort on ring id, first outer ring, | |
144 | // then interior rings | |
145 | return left_other_op.seg_id < right_other_op.seg_id; | |
146 | } | |
147 | ||
148 | private: | |
149 | Turns const& m_turns; | |
150 | }; | |
151 | ||
152 | template <typename Operation, typename ClusterPerSegment> | |
153 | inline signed_size_type get_cluster_id(Operation const& op, ClusterPerSegment const& cluster_per_segment) | |
154 | { | |
155 | typedef typename ClusterPerSegment::key_type segment_fraction_type; | |
156 | ||
157 | segment_fraction_type seg_frac(op.seg_id, op.fraction); | |
158 | typename ClusterPerSegment::const_iterator it | |
159 | = cluster_per_segment.find(seg_frac); | |
160 | ||
161 | if (it == cluster_per_segment.end()) | |
162 | { | |
163 | return -1; | |
164 | } | |
165 | return it->second; | |
166 | } | |
167 | ||
168 | template <typename Operation, typename ClusterPerSegment> | |
169 | inline void add_cluster_id(Operation const& op, | |
170 | ClusterPerSegment& cluster_per_segment, signed_size_type id) | |
171 | { | |
172 | typedef typename ClusterPerSegment::key_type segment_fraction_type; | |
173 | ||
174 | segment_fraction_type seg_frac(op.seg_id, op.fraction); | |
175 | ||
176 | cluster_per_segment[seg_frac] = id; | |
177 | } | |
178 | ||
179 | template <typename Turn, typename ClusterPerSegment> | |
180 | inline signed_size_type add_turn_to_cluster(Turn const& turn, | |
181 | ClusterPerSegment& cluster_per_segment, signed_size_type& cluster_id) | |
182 | { | |
183 | signed_size_type cid0 = get_cluster_id(turn.operations[0], cluster_per_segment); | |
184 | signed_size_type cid1 = get_cluster_id(turn.operations[1], cluster_per_segment); | |
185 | ||
186 | if (cid0 == -1 && cid1 == -1) | |
187 | { | |
b32b8144 | 188 | // Because of this, first cluster ID will be 1 |
7c673cae FG |
189 | ++cluster_id; |
190 | add_cluster_id(turn.operations[0], cluster_per_segment, cluster_id); | |
191 | add_cluster_id(turn.operations[1], cluster_per_segment, cluster_id); | |
192 | return cluster_id; | |
193 | } | |
194 | else if (cid0 == -1 && cid1 != -1) | |
195 | { | |
196 | add_cluster_id(turn.operations[0], cluster_per_segment, cid1); | |
197 | return cid1; | |
198 | } | |
199 | else if (cid0 != -1 && cid1 == -1) | |
200 | { | |
201 | add_cluster_id(turn.operations[1], cluster_per_segment, cid0); | |
202 | return cid0; | |
203 | } | |
204 | else if (cid0 == cid1) | |
205 | { | |
206 | // Both already added to same cluster, no action | |
207 | return cid0; | |
208 | } | |
209 | ||
210 | // Both operations.seg_id/fraction were already part of any cluster, and | |
211 | // these clusters are not the same. Merge of two clusters is necessary | |
b32b8144 | 212 | #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS) |
7c673cae | 213 | std::cout << " TODO: merge " << cid0 << " and " << cid1 << std::endl; |
b32b8144 | 214 | #endif |
7c673cae FG |
215 | return cid0; |
216 | } | |
217 | ||
218 | template | |
219 | < | |
220 | typename Turns, | |
221 | typename ClusterPerSegment, | |
222 | typename Operations, | |
223 | typename Geometry1, | |
224 | typename Geometry2 | |
225 | > | |
226 | inline void handle_colocation_cluster(Turns& turns, | |
227 | signed_size_type& cluster_id, | |
228 | ClusterPerSegment& cluster_per_segment, | |
229 | Operations const& operations, | |
230 | Geometry1 const& /*geometry1*/, Geometry2 const& /*geometry2*/) | |
231 | { | |
232 | typedef typename boost::range_value<Turns>::type turn_type; | |
233 | typedef typename turn_type::turn_operation_type turn_operation_type; | |
234 | ||
235 | std::vector<turn_operation_index>::const_iterator vit = operations.begin(); | |
236 | ||
237 | turn_operation_index ref_toi = *vit; | |
238 | signed_size_type ref_id = -1; | |
239 | ||
240 | for (++vit; vit != operations.end(); ++vit) | |
241 | { | |
242 | turn_type& ref_turn = turns[ref_toi.turn_index]; | |
243 | turn_operation_type const& ref_op | |
244 | = ref_turn.operations[ref_toi.op_index]; | |
245 | ||
246 | turn_operation_index const& toi = *vit; | |
247 | turn_type& turn = turns[toi.turn_index]; | |
248 | turn_operation_type const& op = turn.operations[toi.op_index]; | |
249 | ||
92f5a8d4 | 250 | BOOST_GEOMETRY_ASSERT(ref_op.seg_id == op.seg_id); |
7c673cae FG |
251 | |
252 | if (ref_op.fraction == op.fraction) | |
253 | { | |
254 | turn_operation_type const& other_op = turn.operations[1 - toi.op_index]; | |
255 | ||
256 | if (ref_id == -1) | |
257 | { | |
258 | ref_id = add_turn_to_cluster(ref_turn, cluster_per_segment, cluster_id); | |
259 | } | |
92f5a8d4 | 260 | BOOST_GEOMETRY_ASSERT(ref_id != -1); |
7c673cae FG |
261 | |
262 | // ref_turn (both operations) are already added to cluster, | |
263 | // so also "op" is already added to cluster, | |
264 | // We only need to add other_op | |
265 | signed_size_type id = get_cluster_id(other_op, cluster_per_segment); | |
266 | if (id != -1 && id != ref_id) | |
267 | { | |
268 | } | |
269 | else if (id == -1) | |
270 | { | |
271 | // Add to same cluster | |
272 | add_cluster_id(other_op, cluster_per_segment, ref_id); | |
273 | id = ref_id; | |
274 | } | |
7c673cae FG |
275 | } |
276 | else | |
277 | { | |
278 | // Not on same fraction on this segment | |
279 | // assign for next | |
280 | ref_toi = toi; | |
281 | ref_id = -1; | |
282 | } | |
283 | } | |
284 | } | |
285 | ||
286 | template | |
287 | < | |
288 | typename Turns, | |
289 | typename Clusters, | |
290 | typename ClusterPerSegment | |
291 | > | |
292 | inline void assign_cluster_to_turns(Turns& turns, | |
293 | Clusters& clusters, | |
294 | ClusterPerSegment const& cluster_per_segment) | |
295 | { | |
296 | typedef typename boost::range_value<Turns>::type turn_type; | |
297 | typedef typename turn_type::turn_operation_type turn_operation_type; | |
298 | typedef typename ClusterPerSegment::key_type segment_fraction_type; | |
299 | ||
300 | signed_size_type turn_index = 0; | |
301 | for (typename boost::range_iterator<Turns>::type it = turns.begin(); | |
302 | it != turns.end(); ++it, ++turn_index) | |
303 | { | |
304 | turn_type& turn = *it; | |
305 | ||
306 | if (turn.discarded) | |
307 | { | |
308 | // They were processed (to create proper map) but will not be added | |
309 | // This might leave a cluster with only 1 turn, which will be fixed | |
310 | // afterwards | |
311 | continue; | |
312 | } | |
313 | ||
314 | for (int i = 0; i < 2; i++) | |
315 | { | |
316 | turn_operation_type const& op = turn.operations[i]; | |
317 | segment_fraction_type seg_frac(op.seg_id, op.fraction); | |
11fdf7f2 TL |
318 | typename ClusterPerSegment::const_iterator cit = cluster_per_segment.find(seg_frac); |
319 | if (cit != cluster_per_segment.end()) | |
7c673cae | 320 | { |
b32b8144 FG |
321 | #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS) |
322 | if (turn.is_clustered() | |
11fdf7f2 | 323 | && turn.cluster_id != cit->second) |
7c673cae FG |
324 | { |
325 | std::cout << " CONFLICT " << std::endl; | |
326 | } | |
b32b8144 | 327 | #endif |
11fdf7f2 | 328 | turn.cluster_id = cit->second; |
7c673cae FG |
329 | clusters[turn.cluster_id].turn_indices.insert(turn_index); |
330 | } | |
331 | } | |
332 | } | |
333 | } | |
334 | ||
b32b8144 | 335 | template <typename Turns, typename Clusters> |
7c673cae FG |
336 | inline void remove_clusters(Turns& turns, Clusters& clusters) |
337 | { | |
338 | typename Clusters::iterator it = clusters.begin(); | |
339 | while (it != clusters.end()) | |
340 | { | |
341 | // Hold iterator and increase. We can erase cit, this keeps the | |
342 | // iterator valid (cf The standard associative-container erase idiom) | |
343 | typename Clusters::iterator current_it = it; | |
344 | ++it; | |
345 | ||
346 | std::set<signed_size_type> const& turn_indices | |
347 | = current_it->second.turn_indices; | |
348 | if (turn_indices.size() == 1) | |
349 | { | |
b32b8144 | 350 | signed_size_type const turn_index = *turn_indices.begin(); |
7c673cae FG |
351 | turns[turn_index].cluster_id = -1; |
352 | clusters.erase(current_it); | |
353 | } | |
354 | } | |
355 | } | |
356 | ||
b32b8144 FG |
357 | template <typename Turns, typename Clusters> |
358 | inline void cleanup_clusters(Turns& turns, Clusters& clusters) | |
359 | { | |
360 | // Removes discarded turns from clusters | |
361 | for (typename Clusters::iterator mit = clusters.begin(); | |
362 | mit != clusters.end(); ++mit) | |
363 | { | |
364 | cluster_info& cinfo = mit->second; | |
365 | std::set<signed_size_type>& ids = cinfo.turn_indices; | |
366 | for (std::set<signed_size_type>::iterator sit = ids.begin(); | |
367 | sit != ids.end(); /* no increment */) | |
368 | { | |
369 | std::set<signed_size_type>::iterator current_it = sit; | |
370 | ++sit; | |
371 | ||
372 | signed_size_type const turn_index = *current_it; | |
373 | if (turns[turn_index].discarded) | |
374 | { | |
375 | ids.erase(current_it); | |
376 | } | |
377 | } | |
378 | } | |
379 | ||
380 | remove_clusters(turns, clusters); | |
381 | } | |
382 | ||
7c673cae FG |
383 | template <typename Turn, typename IdSet> |
384 | inline void discard_ie_turn(Turn& turn, IdSet& ids, signed_size_type id) | |
385 | { | |
386 | turn.discarded = true; | |
b32b8144 | 387 | // Set cluster id to -1, but don't clear colocated flags |
7c673cae FG |
388 | turn.cluster_id = -1; |
389 | // To remove it later from clusters | |
390 | ids.insert(id); | |
391 | } | |
392 | ||
393 | template <bool Reverse> | |
394 | inline bool is_interior(segment_identifier const& seg_id) | |
395 | { | |
396 | return Reverse ? seg_id.ring_index == -1 : seg_id.ring_index >= 0; | |
397 | } | |
398 | ||
399 | template <bool Reverse0, bool Reverse1> | |
400 | inline bool is_ie_turn(segment_identifier const& ext_seg_0, | |
401 | segment_identifier const& ext_seg_1, | |
402 | segment_identifier const& int_seg_0, | |
403 | segment_identifier const& other_seg_1) | |
404 | { | |
b32b8144 FG |
405 | if (ext_seg_0.source_index == ext_seg_1.source_index) |
406 | { | |
407 | // External turn is a self-turn, dont discard internal turn for this | |
408 | return false; | |
409 | } | |
410 | ||
411 | ||
7c673cae FG |
412 | // Compares two segment identifiers from two turns (external / one internal) |
413 | ||
414 | // From first turn [0], both are from same polygon (multi_index), | |
415 | // one is exterior (-1), the other is interior (>= 0), | |
416 | // and the second turn [1] handles the same ring | |
417 | ||
418 | // For difference, where the rings are processed in reversal, all interior | |
419 | // rings become exterior and vice versa. But also the multi property changes: | |
420 | // rings originally from the same multi should now be considered as from | |
421 | // different multi polygons. | |
422 | // But this is not always the case, and at this point hard to figure out | |
423 | // (not yet implemented, TODO) | |
424 | ||
425 | bool const same_multi0 = ! Reverse0 | |
426 | && ext_seg_0.multi_index == int_seg_0.multi_index; | |
427 | ||
428 | bool const same_multi1 = ! Reverse1 | |
429 | && ext_seg_1.multi_index == other_seg_1.multi_index; | |
430 | ||
b32b8144 FG |
431 | boost::ignore_unused(same_multi1); |
432 | ||
7c673cae FG |
433 | return same_multi0 |
434 | && same_multi1 | |
435 | && ! is_interior<Reverse0>(ext_seg_0) | |
436 | && is_interior<Reverse0>(int_seg_0) | |
437 | && ext_seg_1.ring_index == other_seg_1.ring_index; | |
438 | ||
439 | // The other way round is tested in another call | |
440 | } | |
441 | ||
442 | template | |
443 | < | |
444 | bool Reverse0, bool Reverse1, // Reverse interpretation interior/exterior | |
445 | typename Turns, | |
446 | typename Clusters | |
447 | > | |
448 | inline void discard_interior_exterior_turns(Turns& turns, Clusters& clusters) | |
449 | { | |
450 | typedef std::set<signed_size_type>::const_iterator set_iterator; | |
451 | typedef typename boost::range_value<Turns>::type turn_type; | |
452 | ||
453 | std::set<signed_size_type> ids_to_remove; | |
454 | ||
455 | for (typename Clusters::iterator cit = clusters.begin(); | |
456 | cit != clusters.end(); ++cit) | |
457 | { | |
458 | cluster_info& cinfo = cit->second; | |
459 | std::set<signed_size_type>& ids = cinfo.turn_indices; | |
460 | ||
461 | ids_to_remove.clear(); | |
462 | ||
463 | for (set_iterator it = ids.begin(); it != ids.end(); ++it) | |
464 | { | |
465 | turn_type& turn = turns[*it]; | |
466 | segment_identifier const& seg_0 = turn.operations[0].seg_id; | |
467 | segment_identifier const& seg_1 = turn.operations[1].seg_id; | |
468 | ||
7c673cae FG |
469 | if (! (turn.both(operation_union) |
470 | || turn.combination(operation_union, operation_blocked))) | |
471 | { | |
472 | // Not a uu/ux, so cannot be colocated with a iu turn | |
473 | continue; | |
474 | } | |
475 | ||
476 | for (set_iterator int_it = ids.begin(); int_it != ids.end(); ++int_it) | |
477 | { | |
478 | if (*it == *int_it) | |
479 | { | |
480 | continue; | |
481 | } | |
482 | ||
483 | // Turn with, possibly, an interior ring involved | |
484 | turn_type& int_turn = turns[*int_it]; | |
485 | segment_identifier const& int_seg_0 = int_turn.operations[0].seg_id; | |
486 | segment_identifier const& int_seg_1 = int_turn.operations[1].seg_id; | |
487 | ||
488 | if (is_ie_turn<Reverse0, Reverse1>(seg_0, seg_1, int_seg_0, int_seg_1)) | |
489 | { | |
490 | discard_ie_turn(int_turn, ids_to_remove, *int_it); | |
491 | } | |
492 | if (is_ie_turn<Reverse1, Reverse0>(seg_1, seg_0, int_seg_1, int_seg_0)) | |
493 | { | |
494 | discard_ie_turn(int_turn, ids_to_remove, *int_it); | |
495 | } | |
496 | } | |
497 | } | |
498 | ||
499 | // Erase from the ids (which cannot be done above) | |
500 | for (set_iterator sit = ids_to_remove.begin(); | |
501 | sit != ids_to_remove.end(); ++sit) | |
502 | { | |
503 | ids.erase(*sit); | |
504 | } | |
505 | } | |
506 | } | |
507 | ||
92f5a8d4 TL |
508 | template <typename Geometry0, typename Geometry1> |
509 | inline segment_identifier get_preceding_segment_id(segment_identifier const& id, | |
510 | Geometry0 const& geometry0, Geometry1 const& geometry1) | |
511 | { | |
512 | segment_identifier result = id; | |
513 | ||
514 | if (result.segment_index == 0) | |
515 | { | |
516 | // Assign to segment_count before decrement | |
517 | result.segment_index | |
518 | = id.source_index == 0 | |
519 | ? segment_count_on_ring(geometry0, id) | |
520 | : segment_count_on_ring(geometry1, id); | |
521 | } | |
522 | ||
523 | result.segment_index--; | |
524 | ||
525 | return result; | |
526 | } | |
527 | ||
b32b8144 FG |
528 | template |
529 | < | |
530 | overlay_type OverlayType, | |
531 | typename Turns, | |
532 | typename Clusters | |
533 | > | |
534 | inline void set_colocation(Turns& turns, Clusters const& clusters) | |
535 | { | |
536 | typedef std::set<signed_size_type>::const_iterator set_iterator; | |
537 | typedef typename boost::range_value<Turns>::type turn_type; | |
538 | ||
539 | for (typename Clusters::const_iterator cit = clusters.begin(); | |
540 | cit != clusters.end(); ++cit) | |
541 | { | |
542 | cluster_info const& cinfo = cit->second; | |
543 | std::set<signed_size_type> const& ids = cinfo.turn_indices; | |
544 | ||
545 | bool both_target = false; | |
546 | for (set_iterator it = ids.begin(); it != ids.end(); ++it) | |
547 | { | |
548 | turn_type const& turn = turns[*it]; | |
549 | if (turn.both(operation_from_overlay<OverlayType>::value)) | |
550 | { | |
551 | both_target = true; | |
552 | break; | |
553 | } | |
554 | } | |
555 | ||
556 | if (both_target) | |
557 | { | |
558 | for (set_iterator it = ids.begin(); it != ids.end(); ++it) | |
559 | { | |
560 | turn_type& turn = turns[*it]; | |
92f5a8d4 | 561 | turn.has_colocated_both = true; |
b32b8144 FG |
562 | } |
563 | } | |
564 | } | |
565 | } | |
566 | ||
567 | template | |
568 | < | |
569 | typename Turns, | |
570 | typename Clusters | |
571 | > | |
572 | inline void check_colocation(bool& has_blocked, | |
11fdf7f2 | 573 | signed_size_type cluster_id, Turns const& turns, Clusters const& clusters) |
b32b8144 FG |
574 | { |
575 | typedef typename boost::range_value<Turns>::type turn_type; | |
576 | ||
577 | has_blocked = false; | |
578 | ||
579 | typename Clusters::const_iterator mit = clusters.find(cluster_id); | |
580 | if (mit == clusters.end()) | |
581 | { | |
582 | return; | |
583 | } | |
584 | ||
585 | cluster_info const& cinfo = mit->second; | |
586 | ||
587 | for (std::set<signed_size_type>::const_iterator it | |
588 | = cinfo.turn_indices.begin(); | |
589 | it != cinfo.turn_indices.end(); ++it) | |
590 | { | |
591 | turn_type const& turn = turns[*it]; | |
592 | if (turn.any_blocked()) | |
593 | { | |
594 | has_blocked = true; | |
595 | } | |
596 | } | |
597 | } | |
598 | ||
7c673cae FG |
599 | |
600 | // Checks colocated turns and flags combinations of uu/other, possibly a | |
601 | // combination of a ring touching another geometry's interior ring which is | |
602 | // tangential to the exterior ring | |
603 | ||
604 | // This function can be extended to replace handle_tangencies: at each | |
605 | // colocation incoming and outgoing vectors should be inspected | |
606 | ||
607 | template | |
608 | < | |
609 | bool Reverse1, bool Reverse2, | |
b32b8144 | 610 | overlay_type OverlayType, |
7c673cae FG |
611 | typename Turns, |
612 | typename Clusters, | |
613 | typename Geometry1, | |
614 | typename Geometry2 | |
615 | > | |
616 | inline bool handle_colocations(Turns& turns, Clusters& clusters, | |
617 | Geometry1 const& geometry1, Geometry2 const& geometry2) | |
618 | { | |
11fdf7f2 TL |
619 | static const detail::overlay::operation_type target_operation |
620 | = detail::overlay::operation_from_overlay<OverlayType>::value; | |
7c673cae FG |
621 | typedef std::map |
622 | < | |
623 | segment_identifier, | |
624 | std::vector<turn_operation_index> | |
625 | > map_type; | |
626 | ||
627 | // Create and fill map on segment-identifier Map is sorted on seg_id, | |
628 | // meaning it is sorted on ring_identifier too. This means that exterior | |
629 | // rings are handled first. If there is a colocation on the exterior ring, | |
630 | // that information can be used for the interior ring too | |
631 | map_type map; | |
632 | ||
11fdf7f2 | 633 | signed_size_type index = 0; |
7c673cae FG |
634 | for (typename boost::range_iterator<Turns>::type |
635 | it = boost::begin(turns); | |
636 | it != boost::end(turns); | |
637 | ++it, ++index) | |
638 | { | |
639 | map[it->operations[0].seg_id].push_back(turn_operation_index(index, 0)); | |
640 | map[it->operations[1].seg_id].push_back(turn_operation_index(index, 1)); | |
641 | } | |
642 | ||
643 | // Check if there are multiple turns on one or more segments, | |
644 | // if not then nothing is to be done | |
645 | bool colocations = 0; | |
646 | for (typename map_type::const_iterator it = map.begin(); | |
647 | it != map.end(); | |
648 | ++it) | |
649 | { | |
650 | if (it->second.size() > 1u) | |
651 | { | |
652 | colocations = true; | |
653 | break; | |
654 | } | |
655 | } | |
656 | ||
657 | if (! colocations) | |
658 | { | |
659 | return false; | |
660 | } | |
661 | ||
662 | // Sort all vectors, per same segment | |
663 | less_by_fraction_and_type<Turns> less(turns); | |
664 | for (typename map_type::iterator it = map.begin(); | |
665 | it != map.end(); ++it) | |
666 | { | |
667 | std::sort(it->second.begin(), it->second.end(), less); | |
668 | } | |
669 | ||
670 | typedef typename boost::range_value<Turns>::type turn_type; | |
671 | typedef typename turn_type::segment_ratio_type segment_ratio_type; | |
672 | ||
673 | typedef std::map | |
674 | < | |
675 | segment_fraction<segment_ratio_type>, | |
676 | signed_size_type | |
677 | > cluster_per_segment_type; | |
678 | ||
679 | cluster_per_segment_type cluster_per_segment; | |
b32b8144 FG |
680 | |
681 | // Assign to zero, because of pre-increment later the cluster_id | |
682 | // effectively starts with 1 | |
683 | // (and can later be negated to use uniquely with turn_index) | |
7c673cae FG |
684 | signed_size_type cluster_id = 0; |
685 | ||
686 | for (typename map_type::const_iterator it = map.begin(); | |
687 | it != map.end(); ++it) | |
688 | { | |
689 | if (it->second.size() > 1u) | |
690 | { | |
691 | handle_colocation_cluster(turns, cluster_id, cluster_per_segment, | |
692 | it->second, geometry1, geometry2); | |
693 | } | |
694 | } | |
695 | ||
696 | assign_cluster_to_turns(turns, clusters, cluster_per_segment); | |
b32b8144 FG |
697 | // Get colocated information here and not later, to keep information |
698 | // on turns which are discarded afterwards | |
699 | set_colocation<OverlayType>(turns, clusters); | |
11fdf7f2 TL |
700 | |
701 | if (BOOST_GEOMETRY_CONDITION(target_operation == operation_intersection)) | |
702 | { | |
703 | discard_interior_exterior_turns | |
704 | < | |
705 | do_reverse<geometry::point_order<Geometry1>::value>::value != Reverse1, | |
706 | do_reverse<geometry::point_order<Geometry2>::value>::value != Reverse2 | |
707 | >(turns, clusters); | |
708 | } | |
7c673cae FG |
709 | |
710 | #if defined(BOOST_GEOMETRY_DEBUG_HANDLE_COLOCATIONS) | |
711 | std::cout << "*** Colocations " << map.size() << std::endl; | |
712 | for (typename map_type::const_iterator it = map.begin(); | |
713 | it != map.end(); ++it) | |
714 | { | |
715 | std::cout << it->first << std::endl; | |
716 | for (std::vector<turn_operation_index>::const_iterator vit | |
717 | = it->second.begin(); vit != it->second.end(); ++vit) | |
718 | { | |
719 | turn_operation_index const& toi = *vit; | |
720 | std::cout << geometry::wkt(turns[toi.turn_index].point) | |
721 | << std::boolalpha | |
722 | << " discarded=" << turns[toi.turn_index].discarded | |
b32b8144 FG |
723 | << " colocated(uu)=" << turns[toi.turn_index].colocated_uu |
724 | << " colocated(ii)=" << turns[toi.turn_index].colocated_ii | |
7c673cae FG |
725 | << " " << operation_char(turns[toi.turn_index].operations[0].operation) |
726 | << " " << turns[toi.turn_index].operations[0].seg_id | |
727 | << " " << turns[toi.turn_index].operations[0].fraction | |
728 | << " // " << operation_char(turns[toi.turn_index].operations[1].operation) | |
729 | << " " << turns[toi.turn_index].operations[1].seg_id | |
730 | << " " << turns[toi.turn_index].operations[1].fraction | |
731 | << std::endl; | |
732 | } | |
733 | } | |
734 | #endif // DEBUG | |
735 | ||
736 | return true; | |
737 | } | |
738 | ||
739 | ||
740 | struct is_turn_index | |
741 | { | |
742 | is_turn_index(signed_size_type index) | |
743 | : m_index(index) | |
744 | {} | |
745 | ||
746 | template <typename Indexed> | |
747 | inline bool operator()(Indexed const& indexed) const | |
748 | { | |
749 | // Indexed is a indexed_turn_operation<Operation> | |
750 | return indexed.turn_index == m_index; | |
751 | } | |
752 | ||
92f5a8d4 | 753 | signed_size_type m_index; |
7c673cae FG |
754 | }; |
755 | ||
756 | ||
757 | template | |
758 | < | |
759 | bool Reverse1, bool Reverse2, | |
b32b8144 | 760 | overlay_type OverlayType, |
7c673cae FG |
761 | typename Turns, |
762 | typename Clusters, | |
763 | typename Geometry1, | |
b32b8144 FG |
764 | typename Geometry2, |
765 | typename SideStrategy | |
7c673cae FG |
766 | > |
767 | inline void gather_cluster_properties(Clusters& clusters, Turns& turns, | |
768 | operation_type for_operation, | |
b32b8144 FG |
769 | Geometry1 const& geometry1, Geometry2 const& geometry2, |
770 | SideStrategy const& strategy) | |
7c673cae FG |
771 | { |
772 | typedef typename boost::range_value<Turns>::type turn_type; | |
773 | typedef typename turn_type::point_type point_type; | |
774 | typedef typename turn_type::turn_operation_type turn_operation_type; | |
775 | ||
776 | // Define sorter, sorting counter-clockwise such that polygons are on the | |
777 | // right side | |
778 | typedef sort_by_side::side_sorter | |
779 | < | |
b32b8144 | 780 | Reverse1, Reverse2, OverlayType, point_type, SideStrategy, std::less<int> |
7c673cae FG |
781 | > sbs_type; |
782 | ||
783 | for (typename Clusters::iterator mit = clusters.begin(); | |
784 | mit != clusters.end(); ++mit) | |
785 | { | |
786 | cluster_info& cinfo = mit->second; | |
787 | std::set<signed_size_type> const& ids = cinfo.turn_indices; | |
788 | if (ids.empty()) | |
789 | { | |
790 | continue; | |
791 | } | |
792 | ||
b32b8144 | 793 | sbs_type sbs(strategy); |
7c673cae FG |
794 | point_type turn_point; // should be all the same for all turns in cluster |
795 | ||
796 | bool first = true; | |
b32b8144 | 797 | for (std::set<signed_size_type>::const_iterator sit = ids.begin(); |
7c673cae FG |
798 | sit != ids.end(); ++sit) |
799 | { | |
800 | signed_size_type turn_index = *sit; | |
801 | turn_type const& turn = turns[turn_index]; | |
802 | if (first) | |
803 | { | |
804 | turn_point = turn.point; | |
805 | } | |
806 | for (int i = 0; i < 2; i++) | |
807 | { | |
808 | turn_operation_type const& op = turn.operations[i]; | |
809 | sbs.add(op, turn_index, i, geometry1, geometry2, first); | |
810 | first = false; | |
811 | } | |
812 | } | |
813 | sbs.apply(turn_point); | |
814 | ||
815 | sbs.find_open(); | |
b32b8144 FG |
816 | sbs.assign_zones(for_operation); |
817 | ||
818 | cinfo.open_count = sbs.open_count(for_operation); | |
7c673cae | 819 | |
11fdf7f2 | 820 | bool const set_startable = OverlayType != overlay_dissolve; |
b32b8144 FG |
821 | |
822 | // Unset the startable flag for all 'closed' zones. This does not | |
823 | // apply for self-turns, because those counts are not from both | |
824 | // polygons | |
7c673cae FG |
825 | for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++) |
826 | { | |
827 | const typename sbs_type::rp& ranked = sbs.m_ranked_points[i]; | |
828 | turn_type& turn = turns[ranked.turn_index]; | |
829 | turn_operation_type& op = turn.operations[ranked.operation_index]; | |
830 | ||
b32b8144 FG |
831 | if (set_startable |
832 | && for_operation == operation_union && cinfo.open_count == 0) | |
833 | { | |
834 | op.enriched.startable = false; | |
835 | } | |
836 | ||
7c673cae FG |
837 | if (ranked.direction != sort_by_side::dir_to) |
838 | { | |
839 | continue; | |
840 | } | |
841 | ||
842 | op.enriched.count_left = ranked.count_left; | |
843 | op.enriched.count_right = ranked.count_right; | |
b32b8144 | 844 | op.enriched.rank = ranked.rank; |
7c673cae FG |
845 | op.enriched.zone = ranked.zone; |
846 | ||
b32b8144 FG |
847 | if (! set_startable) |
848 | { | |
849 | continue; | |
850 | } | |
851 | ||
92f5a8d4 | 852 | if (BOOST_GEOMETRY_CONDITION(OverlayType != overlay_difference) |
b32b8144 FG |
853 | && is_self_turn<OverlayType>(turn)) |
854 | { | |
855 | // Difference needs the self-turns, TODO: investigate | |
856 | continue; | |
857 | } | |
858 | ||
7c673cae FG |
859 | if ((for_operation == operation_union |
860 | && ranked.count_left != 0) | |
861 | || (for_operation == operation_intersection | |
862 | && ranked.count_right != 2)) | |
863 | { | |
864 | op.enriched.startable = false; | |
865 | } | |
866 | } | |
867 | ||
7c673cae FG |
868 | } |
869 | } | |
870 | ||
871 | ||
872 | }} // namespace detail::overlay | |
873 | #endif //DOXYGEN_NO_DETAIL | |
874 | ||
875 | ||
876 | }} // namespace boost::geometry | |
877 | ||
878 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_COLOCATIONS_HPP |