]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | ||
5 | // This file was modified by Oracle on 2016. | |
6 | // Modifications copyright (c) 2016 Oracle and/or its affiliates. | |
7 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
8 | ||
9 | // Use, modification and distribution is subject to the Boost Software License, | |
10 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
11 | // http://www.boost.org/LICENSE_1_0.txt) | |
12 | ||
13 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP | |
14 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP | |
15 | ||
16 | #include <algorithm> | |
17 | #include <cstddef> | |
18 | #include <set> | |
19 | ||
20 | #include <boost/core/ignore_unused.hpp> | |
21 | #include <boost/range.hpp> | |
22 | ||
23 | #include <boost/geometry/core/assert.hpp> | |
24 | #include <boost/geometry/core/coordinate_type.hpp> | |
25 | #include <boost/geometry/core/point_type.hpp> | |
26 | ||
27 | #include <boost/geometry/algorithms/comparable_distance.hpp> | |
28 | #include <boost/geometry/algorithms/covered_by.hpp> | |
29 | #include <boost/geometry/algorithms/envelope.hpp> | |
30 | #include <boost/geometry/algorithms/is_convex.hpp> | |
31 | ||
32 | #include <boost/geometry/strategies/buffer.hpp> | |
33 | ||
34 | #include <boost/geometry/geometries/ring.hpp> | |
35 | ||
36 | #include <boost/geometry/algorithms/detail/buffer/buffered_ring.hpp> | |
37 | #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp> | |
38 | #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp> | |
39 | #include <boost/geometry/algorithms/detail/buffer/get_piece_turns.hpp> | |
40 | #include <boost/geometry/algorithms/detail/buffer/turn_in_piece_visitor.hpp> | |
41 | #include <boost/geometry/algorithms/detail/buffer/turn_in_original_visitor.hpp> | |
42 | ||
43 | #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp> | |
44 | #include <boost/geometry/algorithms/detail/overlay/add_rings.hpp> | |
45 | #include <boost/geometry/algorithms/detail/overlay/assign_parents.hpp> | |
46 | #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp> | |
47 | #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp> | |
48 | #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp> | |
49 | #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp> | |
50 | #include <boost/geometry/algorithms/detail/overlay/traverse.hpp> | |
51 | #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> | |
52 | #include <boost/geometry/algorithms/detail/occupation_info.hpp> | |
53 | #include <boost/geometry/algorithms/detail/partition.hpp> | |
54 | #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp> | |
55 | #include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp> | |
56 | ||
57 | #include <boost/geometry/util/range.hpp> | |
58 | ||
59 | ||
60 | namespace boost { namespace geometry | |
61 | { | |
62 | ||
63 | ||
64 | #ifndef DOXYGEN_NO_DETAIL | |
65 | namespace detail { namespace buffer | |
66 | { | |
67 | ||
68 | enum segment_relation_code | |
69 | { | |
70 | segment_relation_on_left, | |
71 | segment_relation_on_right, | |
72 | segment_relation_within, | |
73 | segment_relation_disjoint | |
74 | }; | |
75 | ||
76 | /* | |
77 | * Terminology | |
78 | * | |
79 | * Suppose we make a buffer (using blocked corners) of this rectangle: | |
80 | * | |
81 | * +-------+ | |
82 | * | | | |
83 | * | rect | | |
84 | * | | | |
85 | * +-------+ | |
86 | * | |
87 | * For the sides we get these four buffered side-pieces (marked with s) | |
88 | * and four buffered corner pieces (marked with c) | |
89 | * | |
90 | * c---+---s---+---c | |
91 | * | | piece | | <- see below for details of the middle top-side-piece | |
92 | * +---+-------+---+ | |
93 | * | | | | | |
94 | * s | rect | s <- two side pieces left/right of rect | |
95 | * | | | | | |
96 | * +---+-------+---+ | |
97 | * | | piece | | <- one side-piece below, and two corner pieces | |
98 | * c---+---s---+---c | |
99 | * | |
100 | * The outer part of the picture above, using all pieces, | |
101 | * form together the offsetted ring (marked with o below) | |
102 | * The 8 pieces are part of the piece collection and use for inside-checks | |
103 | * The inner parts form (using 1 or 2 points per piece, often co-located) | |
104 | * form together the robust_polygons (marked with r below) | |
105 | * The remaining piece-segments are helper-segments (marked with h) | |
106 | * | |
107 | * ooooooooooooooooo | |
108 | * o h h o | |
109 | * ohhhrrrrrrrrrhhho | |
110 | * o r r o | |
111 | * o r r o | |
112 | * o r r o | |
113 | * ohhhrrrrrrrrrhhho | |
114 | * o h h o | |
115 | * ooooooooooooooooo | |
116 | * | |
117 | */ | |
118 | ||
119 | ||
120 | template <typename Ring, typename RobustPolicy> | |
121 | struct buffered_piece_collection | |
122 | { | |
123 | typedef buffered_piece_collection<Ring, RobustPolicy> this_type; | |
124 | ||
125 | typedef typename geometry::point_type<Ring>::type point_type; | |
126 | typedef typename geometry::coordinate_type<Ring>::type coordinate_type; | |
127 | typedef typename geometry::robust_point_type | |
128 | < | |
129 | point_type, | |
130 | RobustPolicy | |
131 | >::type robust_point_type; | |
132 | ||
133 | // Robust ring/polygon type, always clockwise | |
134 | typedef geometry::model::ring<robust_point_type> robust_ring_type; | |
135 | typedef geometry::model::box<robust_point_type> robust_box_type; | |
136 | ||
137 | typedef typename default_comparable_distance_result | |
138 | < | |
139 | robust_point_type | |
140 | >::type robust_comparable_radius_type; | |
141 | ||
142 | typedef typename strategy::side::services::default_strategy | |
143 | < | |
144 | typename cs_tag<point_type>::type | |
145 | >::type side_strategy; | |
146 | ||
147 | typedef typename geometry::rescale_policy_type | |
148 | < | |
149 | typename geometry::point_type<Ring>::type | |
150 | >::type rescale_policy_type; | |
151 | ||
152 | typedef typename geometry::segment_ratio_type | |
153 | < | |
154 | point_type, | |
155 | RobustPolicy | |
156 | >::type segment_ratio_type; | |
157 | ||
158 | typedef buffer_turn_info | |
159 | < | |
160 | point_type, | |
161 | robust_point_type, | |
162 | segment_ratio_type | |
163 | > buffer_turn_info_type; | |
164 | ||
165 | typedef buffer_turn_operation | |
166 | < | |
167 | point_type, | |
168 | segment_ratio_type | |
169 | > buffer_turn_operation_type; | |
170 | ||
171 | typedef std::vector<buffer_turn_info_type> turn_vector_type; | |
172 | ||
173 | struct robust_turn | |
174 | { | |
175 | std::size_t turn_index; | |
176 | int operation_index; | |
177 | robust_point_type point; | |
178 | segment_identifier seg_id; | |
179 | segment_ratio_type fraction; | |
180 | }; | |
181 | ||
182 | struct piece | |
183 | { | |
184 | typedef robust_ring_type piece_robust_ring_type; | |
185 | typedef geometry::section<robust_box_type, 1> section_type; | |
186 | ||
187 | strategy::buffer::piece_type type; | |
188 | signed_size_type index; | |
189 | ||
190 | signed_size_type left_index; // points to previous piece of same ring | |
191 | signed_size_type right_index; // points to next piece of same ring | |
192 | ||
193 | // The next two members (1, 2) form together a complete clockwise ring | |
194 | // for each piece (with one dupped point) | |
195 | // The complete clockwise ring is also included as a robust ring (3) | |
196 | ||
197 | // 1: half, part of offsetted_rings | |
198 | segment_identifier first_seg_id; | |
199 | signed_size_type last_segment_index; // no segment-identifier - it is the same as first_seg_id | |
200 | signed_size_type offsetted_count; // part in robust_ring which is part of offsetted ring | |
201 | ||
202 | #if defined(BOOST_GEOMETRY_BUFFER_USE_HELPER_POINTS) | |
203 | // 2: half, not part of offsetted rings - part of robust ring | |
204 | std::vector<point_type> helper_points; // 4 points for side, 3 points for join - 0 points for flat-end | |
205 | #endif | |
206 | ||
207 | bool is_convex; | |
208 | bool is_monotonic_increasing[2]; // 0=x, 1=y | |
209 | bool is_monotonic_decreasing[2]; // 0=x, 1=y | |
210 | ||
211 | // Monotonic sections of pieces around points | |
212 | std::vector<section_type> sections; | |
213 | ||
214 | // Robust representations | |
215 | // 3: complete ring | |
216 | robust_ring_type robust_ring; | |
217 | ||
218 | robust_box_type robust_envelope; | |
219 | robust_box_type robust_offsetted_envelope; | |
220 | ||
221 | std::vector<robust_turn> robust_turns; // Used only in insert_rescaled_piece_turns - we might use a map instead | |
222 | ||
223 | robust_point_type robust_center; | |
224 | robust_comparable_radius_type robust_min_comparable_radius; | |
225 | robust_comparable_radius_type robust_max_comparable_radius; | |
226 | ||
227 | piece() | |
228 | : type(strategy::buffer::piece_type_unknown) | |
229 | , index(-1) | |
230 | , left_index(-1) | |
231 | , right_index(-1) | |
232 | , last_segment_index(-1) | |
233 | , offsetted_count(-1) | |
234 | , is_convex(false) | |
235 | , robust_min_comparable_radius(0) | |
236 | , robust_max_comparable_radius(0) | |
237 | { | |
238 | is_monotonic_increasing[0] = false; | |
239 | is_monotonic_increasing[1] = false; | |
240 | is_monotonic_decreasing[0] = false; | |
241 | is_monotonic_decreasing[1] = false; | |
242 | } | |
243 | }; | |
244 | ||
245 | struct robust_original | |
246 | { | |
247 | typedef robust_ring_type original_robust_ring_type; | |
248 | typedef geometry::sections<robust_box_type, 1> sections_type; | |
249 | ||
250 | inline robust_original() | |
251 | : m_is_interior(false) | |
252 | , m_has_interiors(true) | |
253 | {} | |
254 | ||
255 | inline robust_original(robust_ring_type const& ring, | |
256 | bool is_interior, bool has_interiors) | |
257 | : m_ring(ring) | |
258 | , m_is_interior(is_interior) | |
259 | , m_has_interiors(has_interiors) | |
260 | { | |
261 | geometry::envelope(m_ring, m_box); | |
262 | ||
263 | // create monotonic sections in x-dimension | |
264 | // The dimension is critical because the direction is later used | |
265 | // in the optimization for within checks using winding strategy | |
266 | // and this strategy is scanning in x direction. | |
267 | typedef boost::mpl::vector_c<std::size_t, 0> dimensions; | |
268 | geometry::sectionalize<false, dimensions>(m_ring, | |
269 | detail::no_rescale_policy(), m_sections); | |
270 | } | |
271 | ||
272 | robust_ring_type m_ring; | |
273 | robust_box_type m_box; | |
274 | sections_type m_sections; | |
275 | ||
276 | bool m_is_interior; | |
277 | bool m_has_interiors; | |
278 | }; | |
279 | ||
280 | typedef std::vector<piece> piece_vector_type; | |
281 | ||
282 | piece_vector_type m_pieces; | |
283 | turn_vector_type m_turns; | |
284 | signed_size_type m_first_piece_index; | |
285 | ||
286 | buffered_ring_collection<buffered_ring<Ring> > offsetted_rings; // indexed by multi_index | |
287 | std::vector<robust_original> robust_originals; // robust representation of the original(s) | |
288 | robust_ring_type current_robust_ring; | |
289 | buffered_ring_collection<Ring> traversed_rings; | |
290 | segment_identifier current_segment_id; | |
291 | ||
292 | // Specificly for offsetted rings around points | |
293 | // but also for large joins with many points | |
294 | typedef geometry::sections<robust_box_type, 2> sections_type; | |
295 | sections_type monotonic_sections; | |
296 | ||
297 | // Define the clusters, mapping cluster_id -> turns | |
298 | typedef std::map | |
299 | < | |
300 | signed_size_type, | |
301 | detail::overlay::cluster_info | |
302 | > cluster_type; | |
303 | ||
304 | cluster_type m_clusters; | |
305 | ||
306 | ||
307 | RobustPolicy const& m_robust_policy; | |
308 | ||
309 | struct redundant_turn | |
310 | { | |
311 | inline bool operator()(buffer_turn_info_type const& turn) const | |
312 | { | |
313 | return turn.remove_on_multi; | |
314 | } | |
315 | }; | |
316 | ||
317 | buffered_piece_collection(RobustPolicy const& robust_policy) | |
318 | : m_first_piece_index(-1) | |
319 | , m_robust_policy(robust_policy) | |
320 | {} | |
321 | ||
322 | ||
323 | #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS) | |
324 | // Will (most probably) be removed later | |
325 | template <typename OccupationMap> | |
326 | inline void adapt_mapped_robust_point(OccupationMap const& map, | |
327 | buffer_turn_info_type& turn, int distance) const | |
328 | { | |
329 | for (int x = -distance; x <= distance; x++) | |
330 | { | |
331 | for (int y = -distance; y <= distance; y++) | |
332 | { | |
333 | robust_point_type rp = turn.robust_point; | |
334 | geometry::set<0>(rp, geometry::get<0>(rp) + x); | |
335 | geometry::set<1>(rp, geometry::get<1>(rp) + y); | |
336 | if (map.find(rp) != map.end()) | |
337 | { | |
338 | turn.mapped_robust_point = rp; | |
339 | return; | |
340 | } | |
341 | } | |
342 | } | |
343 | } | |
344 | #endif | |
345 | ||
346 | inline void get_occupation( | |
347 | #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS) | |
348 | int distance = 0 | |
349 | #endif | |
350 | ) | |
351 | { | |
352 | typedef occupation_info<angle_info<robust_point_type, coordinate_type> > | |
353 | buffer_occupation_info; | |
354 | ||
355 | typedef std::map | |
356 | < | |
357 | robust_point_type, | |
358 | buffer_occupation_info, | |
359 | geometry::less<robust_point_type> | |
360 | > occupation_map_type; | |
361 | ||
362 | occupation_map_type occupation_map; | |
363 | ||
364 | // 1: Add all intersection points to occupation map | |
365 | typedef typename boost::range_iterator<turn_vector_type>::type | |
366 | iterator_type; | |
367 | ||
368 | for (iterator_type it = boost::begin(m_turns); | |
369 | it != boost::end(m_turns); | |
370 | ++it) | |
371 | { | |
372 | if (it->location == location_ok) | |
373 | { | |
374 | #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS) | |
375 | if (distance > 0 && ! occupation_map.empty()) | |
376 | { | |
377 | adapt_mapped_robust_point(occupation_map, *it, distance); | |
378 | } | |
379 | #endif | |
380 | occupation_map[it->get_robust_point()].count++; | |
381 | } | |
382 | } | |
383 | ||
384 | // Remove all points with one or more u/u points from the map | |
385 | // (Alternatively, we could NOT do this here and change all u/u | |
386 | // behaviour in overlay. Currently nothing is done: each polygon is | |
387 | // just followed there. We could also always switch polygons there. For | |
388 | // buffer behaviour, where 3 pieces might meet of which 2 (or more) form | |
389 | // a u/u turn, this last option would have been better, probably). | |
390 | for (iterator_type it = boost::begin(m_turns); | |
391 | it != boost::end(m_turns); | |
392 | ++it) | |
393 | { | |
394 | if (it->both(detail::overlay::operation_union)) | |
395 | { | |
396 | typename occupation_map_type::iterator mit = | |
397 | occupation_map.find(it->get_robust_point()); | |
398 | ||
399 | if (mit != occupation_map.end()) | |
400 | { | |
401 | occupation_map.erase(mit); | |
402 | } | |
403 | } | |
404 | } | |
405 | ||
406 | // 2: Remove all points from map which has only one | |
407 | typename occupation_map_type::iterator it = occupation_map.begin(); | |
408 | while (it != occupation_map.end()) | |
409 | { | |
410 | if (it->second.count <= 1) | |
411 | { | |
412 | typename occupation_map_type::iterator to_erase = it; | |
413 | ++it; | |
414 | occupation_map.erase(to_erase); | |
415 | } | |
416 | else | |
417 | { | |
418 | ++it; | |
419 | } | |
420 | } | |
421 | ||
422 | if (occupation_map.empty()) | |
423 | { | |
424 | return; | |
425 | } | |
426 | ||
427 | // 3: Add vectors (incoming->intersection-point, | |
428 | // intersection-point -> outgoing) | |
429 | // for all (co-located) points still present in the map | |
430 | ||
431 | for (iterator_type it = boost::begin(m_turns); | |
432 | it != boost::end(m_turns); | |
433 | ++it) | |
434 | { | |
435 | typename occupation_map_type::iterator mit = | |
436 | occupation_map.find(it->get_robust_point()); | |
437 | ||
438 | if (mit != occupation_map.end()) | |
439 | { | |
440 | buffer_occupation_info& info = mit->second; | |
441 | for (int i = 0; i < 2; i++) | |
442 | { | |
443 | add_incoming_and_outgoing_angles(it->get_robust_point(), *it, | |
444 | m_pieces, | |
445 | i, it->operations[i].seg_id, | |
446 | info); | |
447 | } | |
448 | ||
449 | it->count_on_multi++; | |
450 | } | |
451 | } | |
452 | ||
453 | #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS) | |
454 | // X: Check rounding issues | |
455 | if (distance == 0) | |
456 | { | |
457 | for (typename occupation_map_type::const_iterator it = occupation_map.begin(); | |
458 | it != occupation_map.end(); ++it) | |
459 | { | |
460 | if (it->second.has_rounding_issues(it->first)) | |
461 | { | |
462 | if(distance == 0) | |
463 | { | |
464 | get_occupation(distance + 1); | |
465 | return; | |
466 | } | |
467 | } | |
468 | } | |
469 | } | |
470 | #endif | |
471 | ||
472 | // Get left turns from all clusters | |
473 | for (typename occupation_map_type::iterator it = occupation_map.begin(); | |
474 | it != occupation_map.end(); ++it) | |
475 | { | |
476 | it->second.get_left_turns(it->first, m_turns); | |
477 | } | |
478 | } | |
479 | ||
480 | inline void classify_turns(bool linear) | |
481 | { | |
482 | for (typename boost::range_iterator<turn_vector_type>::type it = | |
483 | boost::begin(m_turns); it != boost::end(m_turns); ++it) | |
484 | { | |
485 | if (it->count_within > 0) | |
486 | { | |
487 | it->location = inside_buffer; | |
488 | } | |
489 | if (it->count_on_original_boundary > 0 && ! linear) | |
490 | { | |
491 | it->location = inside_buffer; | |
492 | } | |
493 | #if ! defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION) | |
494 | if (it->count_within_near_offsetted > 0) | |
495 | { | |
496 | // Within can have in rare cases a rounding issue. We don't discard this | |
497 | // point, so it can be used to continue started rings in traversal. But | |
498 | // will never start a new ring from this type of points. | |
499 | it->operations[0].enriched.startable = false; | |
500 | it->operations[1].enriched.startable = false; | |
501 | } | |
502 | #endif | |
503 | } | |
504 | } | |
505 | ||
506 | template <typename DistanceStrategy> | |
507 | inline void check_remaining_points(DistanceStrategy const& distance_strategy) | |
508 | { | |
509 | // Check if a turn is inside any of the originals | |
510 | ||
511 | turn_in_original_visitor<turn_vector_type> visitor(m_turns); | |
512 | geometry::partition | |
513 | < | |
514 | robust_box_type, | |
515 | turn_get_box, turn_in_original_ovelaps_box, | |
516 | original_get_box, original_ovelaps_box, | |
517 | include_turn_policy, detail::partition::include_all_policy | |
518 | >::apply(m_turns, robust_originals, visitor); | |
519 | ||
520 | bool const deflate = distance_strategy.negative(); | |
521 | ||
522 | for (typename boost::range_iterator<turn_vector_type>::type it = | |
523 | boost::begin(m_turns); it != boost::end(m_turns); ++it) | |
524 | { | |
525 | buffer_turn_info_type& turn = *it; | |
526 | if (turn.location == location_ok) | |
527 | { | |
528 | if (deflate && turn.count_in_original <= 0) | |
529 | { | |
530 | // For deflate: it is not in original, discard | |
531 | turn.location = location_discard; | |
532 | } | |
533 | else if (! deflate && turn.count_in_original > 0) | |
534 | { | |
535 | // For inflate: it is in original, discard | |
536 | turn.location = location_discard; | |
537 | } | |
538 | } | |
539 | } | |
540 | } | |
541 | ||
542 | inline bool assert_indices_in_robust_rings() const | |
543 | { | |
544 | geometry::equal_to<robust_point_type> comparator; | |
545 | for (typename boost::range_iterator<turn_vector_type const>::type it = | |
546 | boost::begin(m_turns); it != boost::end(m_turns); ++it) | |
547 | { | |
548 | for (int i = 0; i < 2; i++) | |
549 | { | |
550 | robust_point_type const &p1 | |
551 | = m_pieces[it->operations[i].piece_index].robust_ring | |
552 | [it->operations[i].index_in_robust_ring]; | |
553 | robust_point_type const &p2 = it->robust_point; | |
554 | if (! comparator(p1, p2)) | |
555 | { | |
556 | return false; | |
557 | } | |
558 | } | |
559 | } | |
560 | return true; | |
561 | } | |
562 | ||
563 | inline void insert_rescaled_piece_turns() | |
564 | { | |
565 | // Add rescaled turn points to corresponding pieces | |
566 | // (after this, each turn occurs twice) | |
567 | std::size_t index = 0; | |
568 | for (typename boost::range_iterator<turn_vector_type>::type it = | |
569 | boost::begin(m_turns); it != boost::end(m_turns); ++it, ++index) | |
570 | { | |
571 | geometry::recalculate(it->robust_point, it->point, m_robust_policy); | |
572 | #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS) | |
573 | it->mapped_robust_point = it->robust_point; | |
574 | #endif | |
575 | ||
576 | robust_turn turn; | |
577 | it->turn_index = index; | |
578 | turn.turn_index = index; | |
579 | turn.point = it->robust_point; | |
580 | for (int i = 0; i < 2; i++) | |
581 | { | |
582 | turn.operation_index = i; | |
583 | turn.seg_id = it->operations[i].seg_id; | |
584 | turn.fraction = it->operations[i].fraction; | |
585 | ||
586 | piece& pc = m_pieces[it->operations[i].piece_index]; | |
587 | pc.robust_turns.push_back(turn); | |
588 | ||
589 | // Take into account for the box (intersection points should fall inside, | |
590 | // but in theory they can be one off because of rounding | |
591 | geometry::expand(pc.robust_envelope, it->robust_point); | |
592 | geometry::expand(pc.robust_offsetted_envelope, it->robust_point); | |
593 | } | |
594 | } | |
595 | ||
596 | #if ! defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION) | |
597 | // Insert all rescaled turn-points into these rings, to form a | |
598 | // reliable integer-based ring. All turns can be compared (inside) to this | |
599 | // rings to see if they are inside. | |
600 | ||
601 | for (typename boost::range_iterator<piece_vector_type>::type | |
602 | it = boost::begin(m_pieces); it != boost::end(m_pieces); ++it) | |
603 | { | |
604 | piece& pc = *it; | |
605 | signed_size_type piece_segment_index = pc.first_seg_id.segment_index; | |
606 | if (! pc.robust_turns.empty()) | |
607 | { | |
608 | if (pc.robust_turns.size() > 1u) | |
609 | { | |
610 | std::sort(pc.robust_turns.begin(), pc.robust_turns.end(), buffer_operation_less()); | |
611 | } | |
612 | // Walk through them, in reverse to insert at right index | |
613 | signed_size_type index_offset = static_cast<signed_size_type>(pc.robust_turns.size()) - 1; | |
614 | for (typename boost::range_reverse_iterator<const std::vector<robust_turn> >::type | |
615 | rit = boost::const_rbegin(pc.robust_turns); | |
616 | rit != boost::const_rend(pc.robust_turns); | |
617 | ++rit, --index_offset) | |
618 | { | |
619 | signed_size_type const index_in_vector = 1 + rit->seg_id.segment_index - piece_segment_index; | |
620 | BOOST_GEOMETRY_ASSERT | |
621 | ( | |
622 | index_in_vector > 0 | |
623 | && index_in_vector < pc.offsetted_count | |
624 | ); | |
625 | ||
626 | pc.robust_ring.insert(boost::begin(pc.robust_ring) + index_in_vector, rit->point); | |
627 | pc.offsetted_count++; | |
628 | ||
629 | m_turns[rit->turn_index].operations[rit->operation_index].index_in_robust_ring = index_in_vector + index_offset; | |
630 | } | |
631 | } | |
632 | } | |
633 | ||
634 | BOOST_GEOMETRY_ASSERT(assert_indices_in_robust_rings()); | |
635 | #endif | |
636 | } | |
637 | ||
638 | template <std::size_t Dimension> | |
639 | static inline void determine_monotonicity(piece& pc, | |
640 | robust_point_type const& current, | |
641 | robust_point_type const& next) | |
642 | { | |
643 | if (geometry::get<Dimension>(current) >= geometry::get<Dimension>(next)) | |
644 | { | |
645 | pc.is_monotonic_increasing[Dimension] = false; | |
646 | } | |
647 | if (geometry::get<Dimension>(current) <= geometry::get<Dimension>(next)) | |
648 | { | |
649 | pc.is_monotonic_decreasing[Dimension] = false; | |
650 | } | |
651 | } | |
652 | ||
653 | static inline void determine_properties(piece& pc) | |
654 | { | |
655 | pc.is_monotonic_increasing[0] = true; | |
656 | pc.is_monotonic_increasing[1] = true; | |
657 | pc.is_monotonic_decreasing[0] = true; | |
658 | pc.is_monotonic_decreasing[1] = true; | |
659 | ||
660 | pc.is_convex = geometry::is_convex(pc.robust_ring); | |
661 | ||
662 | if (pc.offsetted_count < 2) | |
663 | { | |
664 | return; | |
665 | } | |
666 | ||
667 | typename robust_ring_type::const_iterator current = pc.robust_ring.begin(); | |
668 | typename robust_ring_type::const_iterator next = current + 1; | |
669 | ||
670 | for (signed_size_type i = 1; i < pc.offsetted_count; i++) | |
671 | { | |
672 | determine_monotonicity<0>(pc, *current, *next); | |
673 | determine_monotonicity<1>(pc, *current, *next); | |
674 | current = next; | |
675 | ++next; | |
676 | } | |
677 | } | |
678 | ||
679 | void determine_properties() | |
680 | { | |
681 | for (typename piece_vector_type::iterator it = boost::begin(m_pieces); | |
682 | it != boost::end(m_pieces); | |
683 | ++it) | |
684 | { | |
685 | determine_properties(*it); | |
686 | } | |
687 | } | |
688 | ||
689 | inline void reverse_negative_robust_rings() | |
690 | { | |
691 | for (typename piece_vector_type::iterator it = boost::begin(m_pieces); | |
692 | it != boost::end(m_pieces); | |
693 | ++it) | |
694 | { | |
695 | piece& pc = *it; | |
696 | if (geometry::area(pc.robust_ring) < 0) | |
697 | { | |
698 | // Rings can be ccw: | |
699 | // - in a concave piece | |
700 | // - in a line-buffer with a negative buffer-distance | |
701 | std::reverse(pc.robust_ring.begin(), pc.robust_ring.end()); | |
702 | } | |
703 | } | |
704 | } | |
705 | ||
706 | inline void prepare_buffered_point_piece(piece& pc) | |
707 | { | |
708 | // create monotonic sections in y-dimension | |
709 | typedef boost::mpl::vector_c<std::size_t, 1> dimensions; | |
710 | geometry::sectionalize<false, dimensions>(pc.robust_ring, | |
711 | detail::no_rescale_policy(), pc.sections); | |
712 | ||
713 | // Determine min/max radius | |
714 | typedef geometry::model::referring_segment<robust_point_type const> | |
715 | robust_segment_type; | |
716 | ||
717 | typename robust_ring_type::const_iterator current = pc.robust_ring.begin(); | |
718 | typename robust_ring_type::const_iterator next = current + 1; | |
719 | ||
720 | for (signed_size_type i = 1; i < pc.offsetted_count; i++) | |
721 | { | |
722 | robust_segment_type s(*current, *next); | |
723 | robust_comparable_radius_type const d | |
724 | = geometry::comparable_distance(pc.robust_center, s); | |
725 | ||
726 | if (i == 1 || d < pc.robust_min_comparable_radius) | |
727 | { | |
728 | pc.robust_min_comparable_radius = d; | |
729 | } | |
730 | if (i == 1 || d > pc.robust_max_comparable_radius) | |
731 | { | |
732 | pc.robust_max_comparable_radius = d; | |
733 | } | |
734 | ||
735 | current = next; | |
736 | ++next; | |
737 | } | |
738 | } | |
739 | ||
740 | inline void prepare_buffered_point_pieces() | |
741 | { | |
742 | for (typename piece_vector_type::iterator it = boost::begin(m_pieces); | |
743 | it != boost::end(m_pieces); | |
744 | ++it) | |
745 | { | |
746 | if (it->type == geometry::strategy::buffer::buffered_point) | |
747 | { | |
748 | prepare_buffered_point_piece(*it); | |
749 | } | |
750 | } | |
751 | } | |
752 | ||
753 | inline void get_turns() | |
754 | { | |
755 | for(typename boost::range_iterator<sections_type>::type it | |
756 | = boost::begin(monotonic_sections); | |
757 | it != boost::end(monotonic_sections); | |
758 | ++it) | |
759 | { | |
760 | enlarge_box(it->bounding_box, 1); | |
761 | } | |
762 | ||
763 | { | |
764 | // Calculate the turns | |
765 | piece_turn_visitor | |
766 | < | |
767 | piece_vector_type, | |
768 | buffered_ring_collection<buffered_ring<Ring> >, | |
769 | turn_vector_type, | |
770 | RobustPolicy | |
771 | > visitor(m_pieces, offsetted_rings, m_turns, m_robust_policy); | |
772 | ||
773 | geometry::partition | |
774 | < | |
775 | robust_box_type, | |
776 | detail::section::get_section_box, | |
777 | detail::section::overlaps_section_box | |
778 | >::apply(monotonic_sections, visitor); | |
779 | } | |
780 | ||
781 | insert_rescaled_piece_turns(); | |
782 | ||
783 | reverse_negative_robust_rings(); | |
784 | ||
785 | determine_properties(); | |
786 | ||
787 | prepare_buffered_point_pieces(); | |
788 | ||
789 | { | |
790 | // Check if it is inside any of the pieces | |
791 | turn_in_piece_visitor | |
792 | < | |
793 | turn_vector_type, piece_vector_type | |
794 | > visitor(m_turns, m_pieces); | |
795 | ||
796 | geometry::partition | |
797 | < | |
798 | robust_box_type, | |
799 | turn_get_box, turn_ovelaps_box, | |
800 | piece_get_box, piece_ovelaps_box | |
801 | >::apply(m_turns, m_pieces, visitor); | |
802 | ||
803 | } | |
804 | } | |
805 | ||
806 | inline void start_new_ring() | |
807 | { | |
808 | signed_size_type const n = static_cast<signed_size_type>(offsetted_rings.size()); | |
809 | current_segment_id.source_index = 0; | |
810 | current_segment_id.multi_index = n; | |
811 | current_segment_id.ring_index = -1; | |
812 | current_segment_id.segment_index = 0; | |
813 | ||
814 | offsetted_rings.resize(n + 1); | |
815 | current_robust_ring.clear(); | |
816 | ||
817 | m_first_piece_index = static_cast<signed_size_type>(boost::size(m_pieces)); | |
818 | } | |
819 | ||
820 | inline void abort_ring() | |
821 | { | |
822 | // Remove all created pieces for this ring, sections, last offsetted | |
823 | while (! m_pieces.empty() | |
824 | && m_pieces.back().first_seg_id.multi_index | |
825 | == current_segment_id.multi_index) | |
826 | { | |
827 | m_pieces.erase(m_pieces.end() - 1); | |
828 | } | |
829 | ||
830 | while (! monotonic_sections.empty() | |
831 | && monotonic_sections.back().ring_id.multi_index | |
832 | == current_segment_id.multi_index) | |
833 | { | |
834 | monotonic_sections.erase(monotonic_sections.end() - 1); | |
835 | } | |
836 | ||
837 | offsetted_rings.erase(offsetted_rings.end() - 1); | |
838 | current_robust_ring.clear(); | |
839 | ||
840 | m_first_piece_index = -1; | |
841 | } | |
842 | ||
843 | inline void update_closing_point() | |
844 | { | |
845 | BOOST_GEOMETRY_ASSERT(! offsetted_rings.empty()); | |
846 | buffered_ring<Ring>& added = offsetted_rings.back(); | |
847 | if (! boost::empty(added)) | |
848 | { | |
849 | range::back(added) = range::front(added); | |
850 | } | |
851 | } | |
852 | ||
853 | inline void update_last_point(point_type const& p, | |
854 | buffered_ring<Ring>& ring) | |
855 | { | |
856 | // For the first point of a new piece, and there were already | |
857 | // points in the offsetted ring, for some piece types the first point | |
858 | // is a duplicate of the last point of the previous piece. | |
859 | ||
860 | // TODO: disable that, that point should not be added | |
861 | ||
862 | // For now, it is made equal because due to numerical instability, | |
863 | // it can be a tiny bit off, possibly causing a self-intersection | |
864 | ||
865 | BOOST_GEOMETRY_ASSERT(boost::size(m_pieces) > 0); | |
866 | if (! ring.empty() | |
867 | && current_segment_id.segment_index | |
868 | == m_pieces.back().first_seg_id.segment_index) | |
869 | { | |
870 | ring.back() = p; | |
871 | } | |
872 | } | |
873 | ||
874 | inline void set_piece_center(point_type const& center) | |
875 | { | |
876 | BOOST_GEOMETRY_ASSERT(! m_pieces.empty()); | |
877 | geometry::recalculate(m_pieces.back().robust_center, center, | |
878 | m_robust_policy); | |
879 | } | |
880 | ||
881 | inline void finish_ring(strategy::buffer::result_code code, | |
882 | bool is_interior = false, bool has_interiors = false) | |
883 | { | |
884 | if (code == strategy::buffer::result_error_numerical) | |
885 | { | |
886 | abort_ring(); | |
887 | return; | |
888 | } | |
889 | ||
890 | if (m_first_piece_index == -1) | |
891 | { | |
892 | return; | |
893 | } | |
894 | ||
895 | if (m_first_piece_index < static_cast<signed_size_type>(boost::size(m_pieces))) | |
896 | { | |
897 | // If piece was added | |
898 | // Reassign left-of-first and right-of-last | |
899 | geometry::range::at(m_pieces, m_first_piece_index).left_index | |
900 | = static_cast<signed_size_type>(boost::size(m_pieces)) - 1; | |
901 | geometry::range::back(m_pieces).right_index = m_first_piece_index; | |
902 | } | |
903 | m_first_piece_index = -1; | |
904 | ||
905 | update_closing_point(); | |
906 | ||
907 | if (! current_robust_ring.empty()) | |
908 | { | |
909 | BOOST_GEOMETRY_ASSERT | |
910 | ( | |
911 | geometry::equals(current_robust_ring.front(), | |
912 | current_robust_ring.back()) | |
913 | ); | |
914 | ||
915 | robust_originals.push_back( | |
916 | robust_original(current_robust_ring, | |
917 | is_interior, has_interiors)); | |
918 | } | |
919 | } | |
920 | ||
921 | inline void set_current_ring_concave() | |
922 | { | |
923 | BOOST_GEOMETRY_ASSERT(boost::size(offsetted_rings) > 0); | |
924 | offsetted_rings.back().has_concave = true; | |
925 | } | |
926 | ||
927 | inline signed_size_type add_point(point_type const& p) | |
928 | { | |
929 | BOOST_GEOMETRY_ASSERT(boost::size(offsetted_rings) > 0); | |
930 | ||
931 | buffered_ring<Ring>& current_ring = offsetted_rings.back(); | |
932 | update_last_point(p, current_ring); | |
933 | ||
934 | current_segment_id.segment_index++; | |
935 | current_ring.push_back(p); | |
936 | return static_cast<signed_size_type>(current_ring.size()); | |
937 | } | |
938 | ||
939 | //------------------------------------------------------------------------- | |
940 | ||
941 | inline piece& create_piece(strategy::buffer::piece_type type, | |
942 | bool decrease_segment_index_by_one) | |
943 | { | |
944 | if (type == strategy::buffer::buffered_concave) | |
945 | { | |
946 | offsetted_rings.back().has_concave = true; | |
947 | } | |
948 | ||
949 | piece pc; | |
950 | pc.type = type; | |
951 | pc.index = static_cast<signed_size_type>(boost::size(m_pieces)); | |
952 | ||
953 | current_segment_id.piece_index = pc.index; | |
954 | ||
955 | pc.first_seg_id = current_segment_id; | |
956 | ||
957 | ||
958 | // Assign left/right (for first/last piece per ring they will be re-assigned later) | |
959 | pc.left_index = pc.index - 1; | |
960 | pc.right_index = pc.index + 1; | |
961 | ||
962 | std::size_t const n = boost::size(offsetted_rings.back()); | |
963 | pc.first_seg_id.segment_index = decrease_segment_index_by_one ? n - 1 : n; | |
964 | pc.last_segment_index = pc.first_seg_id.segment_index; | |
965 | ||
966 | m_pieces.push_back(pc); | |
967 | return m_pieces.back(); | |
968 | } | |
969 | ||
970 | inline void init_rescale_piece(piece& pc, std::size_t helper_points_size) | |
971 | { | |
972 | if (pc.first_seg_id.segment_index < 0) | |
973 | { | |
974 | // This indicates an error situation: an earlier piece was empty | |
975 | // It currently does not happen | |
976 | // std::cout << "EMPTY " << pc.type << " " << pc.index << " " << pc.first_seg_id.multi_index << std::endl; | |
977 | pc.offsetted_count = 0; | |
978 | return; | |
979 | } | |
980 | ||
981 | BOOST_GEOMETRY_ASSERT(pc.first_seg_id.multi_index >= 0); | |
982 | BOOST_GEOMETRY_ASSERT(pc.last_segment_index >= 0); | |
983 | ||
984 | pc.offsetted_count = pc.last_segment_index - pc.first_seg_id.segment_index; | |
985 | BOOST_GEOMETRY_ASSERT(pc.offsetted_count >= 0); | |
986 | ||
987 | pc.robust_ring.reserve(pc.offsetted_count + helper_points_size); | |
988 | ||
989 | // Add rescaled offsetted segments | |
990 | { | |
991 | buffered_ring<Ring> const& ring = offsetted_rings[pc.first_seg_id.multi_index]; | |
992 | ||
993 | typedef typename boost::range_iterator<const buffered_ring<Ring> >::type it_type; | |
994 | for (it_type it = boost::begin(ring) + pc.first_seg_id.segment_index; | |
995 | it != boost::begin(ring) + pc.last_segment_index; | |
996 | ++it) | |
997 | { | |
998 | robust_point_type point; | |
999 | geometry::recalculate(point, *it, m_robust_policy); | |
1000 | pc.robust_ring.push_back(point); | |
1001 | } | |
1002 | } | |
1003 | } | |
1004 | ||
1005 | inline robust_point_type add_helper_point(piece& pc, const point_type& point) | |
1006 | { | |
1007 | #if defined(BOOST_GEOMETRY_BUFFER_USE_HELPER_POINTS) | |
1008 | pc.helper_points.push_back(point); | |
1009 | #endif | |
1010 | ||
1011 | robust_point_type rob_point; | |
1012 | geometry::recalculate(rob_point, point, m_robust_policy); | |
1013 | pc.robust_ring.push_back(rob_point); | |
1014 | return rob_point; | |
1015 | } | |
1016 | ||
1017 | // TODO: this is shared with sectionalize, move to somewhere else (assign?) | |
1018 | template <typename Box, typename Value> | |
1019 | inline void enlarge_box(Box& box, Value value) | |
1020 | { | |
1021 | geometry::set<0, 0>(box, geometry::get<0, 0>(box) - value); | |
1022 | geometry::set<0, 1>(box, geometry::get<0, 1>(box) - value); | |
1023 | geometry::set<1, 0>(box, geometry::get<1, 0>(box) + value); | |
1024 | geometry::set<1, 1>(box, geometry::get<1, 1>(box) + value); | |
1025 | } | |
1026 | ||
1027 | inline void calculate_robust_envelope(piece& pc) | |
1028 | { | |
1029 | if (pc.offsetted_count == 0) | |
1030 | { | |
1031 | return; | |
1032 | } | |
1033 | ||
1034 | geometry::envelope(pc.robust_ring, pc.robust_envelope); | |
1035 | ||
1036 | geometry::assign_inverse(pc.robust_offsetted_envelope); | |
1037 | for (signed_size_type i = 0; i < pc.offsetted_count; i++) | |
1038 | { | |
1039 | geometry::expand(pc.robust_offsetted_envelope, pc.robust_ring[i]); | |
1040 | } | |
1041 | ||
1042 | // Take roundings into account, enlarge boxes with 1 integer | |
1043 | enlarge_box(pc.robust_envelope, 1); | |
1044 | enlarge_box(pc.robust_offsetted_envelope, 1); | |
1045 | } | |
1046 | ||
1047 | inline void sectionalize(piece& pc) | |
1048 | { | |
1049 | ||
1050 | buffered_ring<Ring> const& ring = offsetted_rings.back(); | |
1051 | ||
1052 | typedef geometry::detail::sectionalize::sectionalize_part | |
1053 | < | |
1054 | point_type, | |
1055 | boost::mpl::vector_c<std::size_t, 0, 1> // x,y dimension | |
1056 | > sectionalizer; | |
1057 | ||
1058 | // Create a ring-identifier. The source-index is the piece index | |
1059 | // The multi_index is as in this collection (the ring), but not used here | |
1060 | // The ring_index is not used | |
1061 | ring_identifier ring_id(pc.index, pc.first_seg_id.multi_index, -1); | |
1062 | ||
1063 | sectionalizer::apply(monotonic_sections, | |
1064 | boost::begin(ring) + pc.first_seg_id.segment_index, | |
1065 | boost::begin(ring) + pc.last_segment_index, | |
1066 | m_robust_policy, | |
1067 | ring_id, 10); | |
1068 | } | |
1069 | ||
1070 | inline void finish_piece(piece& pc) | |
1071 | { | |
1072 | init_rescale_piece(pc, 0u); | |
1073 | calculate_robust_envelope(pc); | |
1074 | sectionalize(pc); | |
1075 | } | |
1076 | ||
1077 | inline void finish_piece(piece& pc, | |
1078 | const point_type& point1, | |
1079 | const point_type& point2, | |
1080 | const point_type& point3) | |
1081 | { | |
1082 | init_rescale_piece(pc, 3u); | |
1083 | if (pc.offsetted_count == 0) | |
1084 | { | |
1085 | return; | |
1086 | } | |
1087 | ||
1088 | add_helper_point(pc, point1); | |
1089 | robust_point_type mid_point = add_helper_point(pc, point2); | |
1090 | add_helper_point(pc, point3); | |
1091 | calculate_robust_envelope(pc); | |
1092 | sectionalize(pc); | |
1093 | ||
1094 | current_robust_ring.push_back(mid_point); | |
1095 | } | |
1096 | ||
1097 | inline void finish_piece(piece& pc, | |
1098 | const point_type& point1, | |
1099 | const point_type& point2, | |
1100 | const point_type& point3, | |
1101 | const point_type& point4) | |
1102 | { | |
1103 | init_rescale_piece(pc, 4u); | |
1104 | add_helper_point(pc, point1); | |
1105 | robust_point_type mid_point2 = add_helper_point(pc, point2); | |
1106 | robust_point_type mid_point1 = add_helper_point(pc, point3); | |
1107 | add_helper_point(pc, point4); | |
1108 | sectionalize(pc); | |
1109 | calculate_robust_envelope(pc); | |
1110 | ||
1111 | // Add mid-points in other order to current helper_ring | |
1112 | current_robust_ring.push_back(mid_point1); | |
1113 | current_robust_ring.push_back(mid_point2); | |
1114 | } | |
1115 | ||
1116 | inline void add_piece(strategy::buffer::piece_type type, point_type const& p, | |
1117 | point_type const& b1, point_type const& b2) | |
1118 | { | |
1119 | piece& pc = create_piece(type, false); | |
1120 | add_point(b1); | |
1121 | pc.last_segment_index = add_point(b2); | |
1122 | finish_piece(pc, b2, p, b1); | |
1123 | } | |
1124 | ||
1125 | template <typename Range> | |
1126 | inline void add_range_to_piece(piece& pc, Range const& range, bool add_front) | |
1127 | { | |
1128 | BOOST_GEOMETRY_ASSERT(boost::size(range) != 0u); | |
1129 | ||
1130 | typename Range::const_iterator it = boost::begin(range); | |
1131 | ||
1132 | // If it follows a non-join (so basically the same piece-type) point b1 should be added. | |
1133 | // There should be two intersections later and it should be discarded. | |
1134 | // But for now we need it to calculate intersections | |
1135 | if (add_front) | |
1136 | { | |
1137 | add_point(*it); | |
1138 | } | |
1139 | ||
1140 | for (++it; it != boost::end(range); ++it) | |
1141 | { | |
1142 | pc.last_segment_index = add_point(*it); | |
1143 | } | |
1144 | } | |
1145 | ||
1146 | ||
1147 | template <typename Range> | |
1148 | inline void add_piece(strategy::buffer::piece_type type, Range const& range, | |
1149 | bool decrease_segment_index_by_one) | |
1150 | { | |
1151 | piece& pc = create_piece(type, decrease_segment_index_by_one); | |
1152 | ||
1153 | if (boost::size(range) > 0u) | |
1154 | { | |
1155 | add_range_to_piece(pc, range, offsetted_rings.back().empty()); | |
1156 | } | |
1157 | finish_piece(pc); | |
1158 | } | |
1159 | ||
1160 | template <typename Range> | |
1161 | inline void add_side_piece(point_type const& p1, point_type const& p2, | |
1162 | Range const& range, bool first) | |
1163 | { | |
1164 | BOOST_GEOMETRY_ASSERT(boost::size(range) >= 2u); | |
1165 | ||
1166 | piece& pc = create_piece(strategy::buffer::buffered_segment, ! first); | |
1167 | add_range_to_piece(pc, range, first); | |
1168 | finish_piece(pc, range.back(), p2, p1, range.front()); | |
1169 | } | |
1170 | ||
1171 | template <typename Range> | |
1172 | inline void add_piece(strategy::buffer::piece_type type, | |
1173 | point_type const& p, Range const& range) | |
1174 | { | |
1175 | piece& pc = create_piece(type, true); | |
1176 | ||
1177 | if (boost::size(range) > 0u) | |
1178 | { | |
1179 | add_range_to_piece(pc, range, offsetted_rings.back().empty()); | |
1180 | finish_piece(pc, range.back(), p, range.front()); | |
1181 | } | |
1182 | else | |
1183 | { | |
1184 | finish_piece(pc); | |
1185 | } | |
1186 | } | |
1187 | ||
1188 | template <typename EndcapStrategy, typename Range> | |
1189 | inline void add_endcap(EndcapStrategy const& strategy, Range const& range, | |
1190 | point_type const& end_point) | |
1191 | { | |
1192 | boost::ignore_unused(strategy); | |
1193 | ||
1194 | if (range.empty()) | |
1195 | { | |
1196 | return; | |
1197 | } | |
1198 | strategy::buffer::piece_type pt = strategy.get_piece_type(); | |
1199 | if (pt == strategy::buffer::buffered_flat_end) | |
1200 | { | |
1201 | // It is flat, should just be added, without helper segments | |
1202 | add_piece(pt, range, true); | |
1203 | } | |
1204 | else | |
1205 | { | |
1206 | // Normal case, it has an "inside", helper segments should be added | |
1207 | add_piece(pt, end_point, range); | |
1208 | } | |
1209 | } | |
1210 | ||
1211 | //------------------------------------------------------------------------- | |
1212 | ||
1213 | inline void enrich() | |
1214 | { | |
1215 | typedef typename strategy::side::services::default_strategy | |
1216 | < | |
1217 | typename cs_tag<Ring>::type | |
1218 | >::type side_strategy_type; | |
1219 | ||
1220 | enrich_intersection_points<false, false, overlay_buffer>(m_turns, | |
1221 | m_clusters, offsetted_rings, offsetted_rings, | |
1222 | m_robust_policy, side_strategy_type()); | |
1223 | } | |
1224 | ||
1225 | // Discards all rings which do have not-OK intersection points only. | |
1226 | // Those can never be traversed and should not be part of the output. | |
1227 | inline void discard_rings() | |
1228 | { | |
1229 | for (typename boost::range_iterator<turn_vector_type const>::type it = | |
1230 | boost::begin(m_turns); it != boost::end(m_turns); ++it) | |
1231 | { | |
1232 | if (it->location != location_ok) | |
1233 | { | |
1234 | offsetted_rings[it->operations[0].seg_id.multi_index].has_discarded_intersections = true; | |
1235 | offsetted_rings[it->operations[1].seg_id.multi_index].has_discarded_intersections = true; | |
1236 | } | |
1237 | else | |
1238 | { | |
1239 | offsetted_rings[it->operations[0].seg_id.multi_index].has_accepted_intersections = true; | |
1240 | offsetted_rings[it->operations[1].seg_id.multi_index].has_accepted_intersections = true; | |
1241 | } | |
1242 | } | |
1243 | } | |
1244 | ||
1245 | inline bool point_coveredby_original(point_type const& point) | |
1246 | { | |
1247 | robust_point_type any_point; | |
1248 | geometry::recalculate(any_point, point, m_robust_policy); | |
1249 | ||
1250 | signed_size_type count_in_original = 0; | |
1251 | ||
1252 | // Check of the robust point of this outputted ring is in | |
1253 | // any of the robust original rings | |
1254 | // This can go quadratic if the input has many rings, and there | |
1255 | // are many untouched deflated rings around | |
1256 | for (typename std::vector<robust_original>::const_iterator it | |
1257 | = robust_originals.begin(); | |
1258 | it != robust_originals.end(); | |
1259 | ++it) | |
1260 | { | |
1261 | robust_original const& original = *it; | |
1262 | if (detail::disjoint::disjoint_point_box(any_point, | |
1263 | original.m_box)) | |
1264 | { | |
1265 | continue; | |
1266 | } | |
1267 | ||
1268 | int const geometry_code | |
1269 | = detail::within::point_in_geometry(any_point, | |
1270 | original.m_ring); | |
1271 | ||
1272 | if (geometry_code == -1) | |
1273 | { | |
1274 | // Outside, continue | |
1275 | continue; | |
1276 | } | |
1277 | ||
1278 | // Apply for possibly nested interior rings | |
1279 | if (original.m_is_interior) | |
1280 | { | |
1281 | count_in_original--; | |
1282 | } | |
1283 | else if (original.m_has_interiors) | |
1284 | { | |
1285 | count_in_original++; | |
1286 | } | |
1287 | else | |
1288 | { | |
1289 | // Exterior ring without interior rings | |
1290 | return true; | |
1291 | } | |
1292 | } | |
1293 | return count_in_original > 0; | |
1294 | } | |
1295 | ||
1296 | // For a deflate, all rings around inner rings which are untouched | |
1297 | // (no intersections/turns) and which are OUTSIDE the original should | |
1298 | // be discarded | |
1299 | inline void discard_nonintersecting_deflated_rings() | |
1300 | { | |
1301 | for(typename buffered_ring_collection<buffered_ring<Ring> >::iterator it | |
1302 | = boost::begin(offsetted_rings); | |
1303 | it != boost::end(offsetted_rings); | |
1304 | ++it) | |
1305 | { | |
1306 | buffered_ring<Ring>& ring = *it; | |
1307 | if (! ring.has_intersections() | |
1308 | && boost::size(ring) > 0u | |
1309 | && geometry::area(ring) < 0) | |
1310 | { | |
1311 | if (! point_coveredby_original(geometry::range::front(ring))) | |
1312 | { | |
1313 | ring.is_untouched_outside_original = true; | |
1314 | } | |
1315 | } | |
1316 | } | |
1317 | } | |
1318 | ||
1319 | inline void block_turns() | |
1320 | { | |
1321 | // To fix left-turn issues like #rt_u13 | |
1322 | // But currently it causes more other issues than it fixes | |
1323 | // m_turns.erase | |
1324 | // ( | |
1325 | // std::remove_if(boost::begin(m_turns), boost::end(m_turns), | |
1326 | // redundant_turn()), | |
1327 | // boost::end(m_turns) | |
1328 | // ); | |
1329 | ||
1330 | for (typename boost::range_iterator<turn_vector_type>::type it = | |
1331 | boost::begin(m_turns); it != boost::end(m_turns); ++it) | |
1332 | { | |
1333 | buffer_turn_info_type& turn = *it; | |
1334 | if (turn.location != location_ok) | |
1335 | { | |
1336 | // Discard this turn (don't set it to blocked to avoid colocated | |
1337 | // clusters being discarded afterwards | |
1338 | turn.discarded = true; | |
1339 | } | |
1340 | } | |
1341 | } | |
1342 | ||
1343 | inline void traverse() | |
1344 | { | |
1345 | typedef detail::overlay::traverse | |
1346 | < | |
1347 | false, false, | |
1348 | buffered_ring_collection<buffered_ring<Ring> >, | |
1349 | buffered_ring_collection<buffered_ring<Ring > >, | |
1350 | overlay_buffer, | |
1351 | backtrack_for_buffer | |
1352 | > traverser; | |
1353 | ||
1354 | traversed_rings.clear(); | |
1355 | buffer_overlay_visitor visitor; | |
1356 | traverser::apply(offsetted_rings, offsetted_rings, | |
1357 | m_robust_policy, m_turns, traversed_rings, | |
1358 | m_clusters, visitor); | |
1359 | } | |
1360 | ||
1361 | inline void reverse() | |
1362 | { | |
1363 | for(typename buffered_ring_collection<buffered_ring<Ring> >::iterator it = boost::begin(offsetted_rings); | |
1364 | it != boost::end(offsetted_rings); | |
1365 | ++it) | |
1366 | { | |
1367 | if (! it->has_intersections()) | |
1368 | { | |
1369 | std::reverse(it->begin(), it->end()); | |
1370 | } | |
1371 | } | |
1372 | for (typename boost::range_iterator<buffered_ring_collection<Ring> >::type | |
1373 | it = boost::begin(traversed_rings); | |
1374 | it != boost::end(traversed_rings); | |
1375 | ++it) | |
1376 | { | |
1377 | std::reverse(it->begin(), it->end()); | |
1378 | } | |
1379 | ||
1380 | } | |
1381 | ||
1382 | template <typename GeometryOutput, typename OutputIterator> | |
1383 | inline OutputIterator assign(OutputIterator out) const | |
1384 | { | |
1385 | typedef detail::overlay::ring_properties<point_type> properties; | |
1386 | ||
1387 | std::map<ring_identifier, properties> selected; | |
1388 | ||
1389 | // Select all rings which do not have any self-intersection | |
1390 | // Inner rings, for deflate, which do not have intersections, and | |
1391 | // which are outside originals, are skipped | |
1392 | // (other ones should be traversed) | |
1393 | signed_size_type index = 0; | |
1394 | for(typename buffered_ring_collection<buffered_ring<Ring> >::const_iterator it = boost::begin(offsetted_rings); | |
1395 | it != boost::end(offsetted_rings); | |
1396 | ++it, ++index) | |
1397 | { | |
1398 | if (! it->has_intersections() | |
1399 | && ! it->is_untouched_outside_original) | |
1400 | { | |
1401 | properties p = properties(*it); | |
1402 | if (p.valid) | |
1403 | { | |
1404 | ring_identifier id(0, index, -1); | |
1405 | selected[id] = p; | |
1406 | } | |
1407 | } | |
1408 | } | |
1409 | ||
1410 | // Select all created rings | |
1411 | index = 0; | |
1412 | for (typename boost::range_iterator<buffered_ring_collection<Ring> const>::type | |
1413 | it = boost::begin(traversed_rings); | |
1414 | it != boost::end(traversed_rings); | |
1415 | ++it, ++index) | |
1416 | { | |
1417 | properties p = properties(*it); | |
1418 | if (p.valid) | |
1419 | { | |
1420 | ring_identifier id(2, index, -1); | |
1421 | selected[id] = p; | |
1422 | } | |
1423 | } | |
1424 | ||
1425 | detail::overlay::assign_parents(offsetted_rings, traversed_rings, selected, true); | |
1426 | return detail::overlay::add_rings<GeometryOutput>(selected, offsetted_rings, traversed_rings, out); | |
1427 | } | |
1428 | ||
1429 | }; | |
1430 | ||
1431 | ||
1432 | }} // namespace detail::buffer | |
1433 | #endif // DOXYGEN_NO_DETAIL | |
1434 | ||
1435 | ||
1436 | }} // namespace boost::geometry | |
1437 | ||
1438 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP |