]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands. | |
11fdf7f2 | 4 | // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. |
7c673cae | 5 | |
1e59de90 TL |
6 | // This file was modified by Oracle on 2016-2022. |
7 | // Modifications copyright (c) 2016-2022 Oracle and/or its affiliates. | |
7c673cae FG |
8 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle |
9 | ||
10 | // Use, modification and distribution is subject to the Boost Software License, | |
11 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
12 | // http://www.boost.org/LICENSE_1_0.txt) | |
13 | ||
14 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP | |
15 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP | |
16 | ||
17 | #include <algorithm> | |
18 | #include <cstddef> | |
19 | #include <set> | |
20 | ||
21 | #include <boost/core/ignore_unused.hpp> | |
20effc67 TL |
22 | #include <boost/range/begin.hpp> |
23 | #include <boost/range/empty.hpp> | |
24 | #include <boost/range/end.hpp> | |
25 | #include <boost/range/size.hpp> | |
26 | #include <boost/range/value_type.hpp> | |
7c673cae FG |
27 | |
28 | #include <boost/geometry/core/assert.hpp> | |
29 | #include <boost/geometry/core/coordinate_type.hpp> | |
30 | #include <boost/geometry/core/point_type.hpp> | |
31 | ||
7c673cae FG |
32 | #include <boost/geometry/algorithms/covered_by.hpp> |
33 | #include <boost/geometry/algorithms/envelope.hpp> | |
7c673cae FG |
34 | |
35 | #include <boost/geometry/strategies/buffer.hpp> | |
36 | ||
37 | #include <boost/geometry/geometries/ring.hpp> | |
38 | ||
39 | #include <boost/geometry/algorithms/detail/buffer/buffered_ring.hpp> | |
40 | #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp> | |
41 | #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp> | |
42 | #include <boost/geometry/algorithms/detail/buffer/get_piece_turns.hpp> | |
20effc67 | 43 | #include <boost/geometry/algorithms/detail/buffer/piece_border.hpp> |
7c673cae FG |
44 | #include <boost/geometry/algorithms/detail/buffer/turn_in_piece_visitor.hpp> |
45 | #include <boost/geometry/algorithms/detail/buffer/turn_in_original_visitor.hpp> | |
46 | ||
47 | #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp> | |
48 | #include <boost/geometry/algorithms/detail/overlay/add_rings.hpp> | |
49 | #include <boost/geometry/algorithms/detail/overlay/assign_parents.hpp> | |
50 | #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp> | |
51 | #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp> | |
52 | #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp> | |
b32b8144 | 53 | #include <boost/geometry/algorithms/detail/overlay/select_rings.hpp> |
7c673cae FG |
54 | #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp> |
55 | #include <boost/geometry/algorithms/detail/overlay/traverse.hpp> | |
56 | #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> | |
7c673cae FG |
57 | #include <boost/geometry/algorithms/detail/partition.hpp> |
58 | #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp> | |
59 | #include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp> | |
60 | ||
1e59de90 | 61 | #include <boost/geometry/views/detail/closed_clockwise_view.hpp> |
7c673cae FG |
62 | #include <boost/geometry/util/range.hpp> |
63 | ||
20effc67 | 64 | |
7c673cae FG |
65 | namespace boost { namespace geometry |
66 | { | |
67 | ||
68 | ||
69 | #ifndef DOXYGEN_NO_DETAIL | |
70 | namespace detail { namespace buffer | |
71 | { | |
72 | ||
7c673cae FG |
73 | |
74 | /* | |
75 | * Terminology | |
76 | * | |
77 | * Suppose we make a buffer (using blocked corners) of this rectangle: | |
78 | * | |
79 | * +-------+ | |
80 | * | | | |
81 | * | rect | | |
82 | * | | | |
83 | * +-------+ | |
84 | * | |
85 | * For the sides we get these four buffered side-pieces (marked with s) | |
86 | * and four buffered corner pieces (marked with c) | |
87 | * | |
88 | * c---+---s---+---c | |
89 | * | | piece | | <- see below for details of the middle top-side-piece | |
90 | * +---+-------+---+ | |
91 | * | | | | | |
92 | * s | rect | s <- two side pieces left/right of rect | |
93 | * | | | | | |
94 | * +---+-------+---+ | |
95 | * | | piece | | <- one side-piece below, and two corner pieces | |
96 | * c---+---s---+---c | |
97 | * | |
98 | * The outer part of the picture above, using all pieces, | |
99 | * form together the offsetted ring (marked with o below) | |
100 | * The 8 pieces are part of the piece collection and use for inside-checks | |
101 | * The inner parts form (using 1 or 2 points per piece, often co-located) | |
102 | * form together the robust_polygons (marked with r below) | |
103 | * The remaining piece-segments are helper-segments (marked with h) | |
104 | * | |
105 | * ooooooooooooooooo | |
106 | * o h h o | |
107 | * ohhhrrrrrrrrrhhho | |
108 | * o r r o | |
109 | * o r r o | |
110 | * o r r o | |
111 | * ohhhrrrrrrrrrhhho | |
112 | * o h h o | |
113 | * ooooooooooooooooo | |
114 | * | |
115 | */ | |
116 | ||
f67539c2 TL |
117 | template |
118 | < | |
119 | typename Ring, | |
1e59de90 | 120 | typename Strategy, |
f67539c2 TL |
121 | typename DistanceStrategy, |
122 | typename RobustPolicy | |
123 | > | |
7c673cae FG |
124 | struct buffered_piece_collection |
125 | { | |
7c673cae FG |
126 | typedef typename geometry::point_type<Ring>::type point_type; |
127 | typedef typename geometry::coordinate_type<Ring>::type coordinate_type; | |
7c673cae | 128 | |
20effc67 TL |
129 | // Ring/polygon type, always clockwise |
130 | typedef geometry::model::ring<point_type> clockwise_ring_type; | |
7c673cae | 131 | |
20effc67 | 132 | typedef geometry::model::box<point_type> box_type; |
7c673cae | 133 | |
7c673cae FG |
134 | typedef buffer_turn_info |
135 | < | |
136 | point_type, | |
20effc67 | 137 | typename segment_ratio_type<point_type, RobustPolicy>::type |
7c673cae FG |
138 | > buffer_turn_info_type; |
139 | ||
140 | typedef buffer_turn_operation | |
141 | < | |
142 | point_type, | |
20effc67 | 143 | typename segment_ratio_type<point_type, RobustPolicy>::type |
7c673cae FG |
144 | > buffer_turn_operation_type; |
145 | ||
146 | typedef std::vector<buffer_turn_info_type> turn_vector_type; | |
147 | ||
20effc67 | 148 | typedef piece_border<Ring, point_type> piece_border_type; |
7c673cae FG |
149 | |
150 | struct piece | |
151 | { | |
7c673cae FG |
152 | strategy::buffer::piece_type type; |
153 | signed_size_type index; | |
154 | ||
155 | signed_size_type left_index; // points to previous piece of same ring | |
156 | signed_size_type right_index; // points to next piece of same ring | |
157 | ||
158 | // The next two members (1, 2) form together a complete clockwise ring | |
159 | // for each piece (with one dupped point) | |
160 | // The complete clockwise ring is also included as a robust ring (3) | |
161 | ||
162 | // 1: half, part of offsetted_rings | |
20effc67 TL |
163 | |
164 | // Segment identifier of this piece, including its start index | |
7c673cae | 165 | segment_identifier first_seg_id; |
7c673cae | 166 | |
20effc67 TL |
167 | // One-beyond index of this piece, to iterate over a ring |
168 | // from: ring.begin() + pc.first_seg_id.segment_index; | |
169 | // to (not including): ring.begin() + pc.beyond_last_segment_index; | |
170 | // Its ring_id etc are shared with first_seg_id | |
171 | signed_size_type beyond_last_segment_index; | |
172 | ||
173 | // part in offsetted ring which is part of offsetted ring | |
174 | signed_size_type offsetted_count; | |
175 | ||
b32b8144 FG |
176 | bool is_flat_start; |
177 | bool is_flat_end; | |
7c673cae | 178 | |
b32b8144 | 179 | bool is_deflated; |
7c673cae | 180 | |
20effc67 TL |
181 | // Ring (parts) of this piece, always clockwise |
182 | piece_border_type m_piece_border; | |
7c673cae | 183 | |
20effc67 | 184 | point_type m_label_point; |
7c673cae | 185 | |
20effc67 TL |
186 | // For a point buffer |
187 | point_type m_center; | |
7c673cae FG |
188 | |
189 | piece() | |
190 | : type(strategy::buffer::piece_type_unknown) | |
191 | , index(-1) | |
192 | , left_index(-1) | |
193 | , right_index(-1) | |
20effc67 | 194 | , beyond_last_segment_index(-1) |
7c673cae | 195 | , offsetted_count(-1) |
b32b8144 FG |
196 | , is_flat_start(false) |
197 | , is_flat_end(false) | |
198 | , is_deflated(false) | |
7c673cae | 199 | { |
7c673cae FG |
200 | } |
201 | }; | |
202 | ||
f67539c2 | 203 | struct original_ring |
7c673cae | 204 | { |
20effc67 | 205 | typedef geometry::sections<box_type, 1> sections_type; |
7c673cae | 206 | |
f67539c2 TL |
207 | // Creates an empty instance |
208 | inline original_ring() | |
7c673cae | 209 | : m_is_interior(false) |
f67539c2 | 210 | , m_has_interiors(false) |
7c673cae FG |
211 | {} |
212 | ||
20effc67 | 213 | inline original_ring(clockwise_ring_type const& ring, |
1e59de90 TL |
214 | bool is_interior, bool has_interiors, |
215 | Strategy const& strategy) | |
7c673cae FG |
216 | : m_ring(ring) |
217 | , m_is_interior(is_interior) | |
218 | , m_has_interiors(has_interiors) | |
219 | { | |
1e59de90 | 220 | geometry::envelope(m_ring, m_box, strategy); |
7c673cae FG |
221 | |
222 | // create monotonic sections in x-dimension | |
223 | // The dimension is critical because the direction is later used | |
224 | // in the optimization for within checks using winding strategy | |
225 | // and this strategy is scanning in x direction. | |
20effc67 | 226 | typedef std::integer_sequence<std::size_t, 0> dimensions; |
1e59de90 TL |
227 | geometry::sectionalize |
228 | < | |
229 | false, dimensions | |
230 | >(m_ring, detail::no_rescale_policy(), m_sections, strategy); | |
7c673cae FG |
231 | } |
232 | ||
20effc67 TL |
233 | clockwise_ring_type m_ring; |
234 | box_type m_box; | |
7c673cae FG |
235 | sections_type m_sections; |
236 | ||
237 | bool m_is_interior; | |
238 | bool m_has_interiors; | |
239 | }; | |
240 | ||
241 | typedef std::vector<piece> piece_vector_type; | |
242 | ||
243 | piece_vector_type m_pieces; | |
244 | turn_vector_type m_turns; | |
245 | signed_size_type m_first_piece_index; | |
b32b8144 FG |
246 | bool m_deflate; |
247 | bool m_has_deflated; | |
7c673cae | 248 | |
f67539c2 TL |
249 | // Offsetted rings, and representations of original ring(s) |
250 | // both indexed by multi_index | |
251 | buffered_ring_collection<buffered_ring<Ring> > offsetted_rings; | |
252 | std::vector<original_ring> original_rings; | |
20effc67 | 253 | std::vector<point_type> m_linear_end_points; |
f67539c2 | 254 | |
7c673cae FG |
255 | buffered_ring_collection<Ring> traversed_rings; |
256 | segment_identifier current_segment_id; | |
257 | ||
20effc67 TL |
258 | // Monotonic sections (used for offsetted rings around points) |
259 | // are still using a robust type, to be comparable with turn calculations, | |
260 | // which is using rescaling. | |
261 | typedef geometry::model::box | |
262 | < | |
263 | typename geometry::robust_point_type<point_type, RobustPolicy>::type | |
264 | > robust_box_type; | |
265 | typedef geometry::sections <robust_box_type, 2> robust_sections_type; | |
266 | robust_sections_type monotonic_sections; | |
7c673cae FG |
267 | |
268 | // Define the clusters, mapping cluster_id -> turns | |
269 | typedef std::map | |
270 | < | |
271 | signed_size_type, | |
272 | detail::overlay::cluster_info | |
273 | > cluster_type; | |
274 | ||
275 | cluster_type m_clusters; | |
276 | ||
1e59de90 | 277 | Strategy m_strategy; |
f67539c2 | 278 | DistanceStrategy m_distance_strategy; |
7c673cae FG |
279 | RobustPolicy const& m_robust_policy; |
280 | ||
1e59de90 | 281 | buffered_piece_collection(Strategy const& strategy, |
f67539c2 | 282 | DistanceStrategy const& distance_strategy, |
b32b8144 | 283 | RobustPolicy const& robust_policy) |
7c673cae | 284 | : m_first_piece_index(-1) |
b32b8144 FG |
285 | , m_deflate(false) |
286 | , m_has_deflated(false) | |
1e59de90 | 287 | , m_strategy(strategy) |
f67539c2 | 288 | , m_distance_strategy(distance_strategy) |
7c673cae FG |
289 | , m_robust_policy(robust_policy) |
290 | {} | |
291 | ||
20effc67 TL |
292 | inline bool is_following(buffer_turn_info_type const& turn, |
293 | buffer_turn_operation_type const& op) | |
294 | { | |
295 | return turn.operations[0].seg_id.segment_index == op.seg_id.segment_index | |
296 | || turn.operations[1].seg_id.segment_index == op.seg_id.segment_index; | |
297 | } | |
7c673cae | 298 | |
20effc67 TL |
299 | // Verify if turns which are classified as OK (outside or on border of |
300 | // offsetted ring) do not traverse through other turns which are classified | |
301 | // as WITHIN (inside a piece). This can happen if turns are nearly colocated | |
302 | // and due to floating point precision just classified as within, while | |
303 | // they should not be within. | |
304 | // In those cases the turns are fine to travel through (and should), | |
305 | // but they are not made startable. | |
306 | template <typename Vector> | |
307 | inline void pretraverse(Vector const& indexed_operations) | |
7c673cae | 308 | { |
20effc67 TL |
309 | // Verify if the turns which are OK don't skip segments |
310 | typedef typename boost::range_value<Vector>::type indexed_type; | |
311 | buffer_turn_operation_type last_traversable_operation; | |
312 | buffer_turn_info_type last_traversable_turn; | |
313 | bool first = true; | |
314 | for (std::size_t i = 0; i < indexed_operations.size(); i++) | |
7c673cae | 315 | { |
20effc67 TL |
316 | indexed_type const & itop = indexed_operations[i]; |
317 | buffer_turn_info_type const& turn = m_turns[itop.turn_index]; | |
318 | ||
319 | if (turn.is_turn_traversable && ! first) | |
7c673cae | 320 | { |
20effc67 TL |
321 | // Check previous and next turns. The first is handled |
322 | BOOST_GEOMETRY_ASSERT(i > 0); | |
323 | indexed_type const& previous_itop = indexed_operations[i - 1]; | |
324 | std::size_t const next_index = i + 1 < indexed_operations.size() ? i + 1 : 0; | |
325 | indexed_type const& next_itop = indexed_operations[next_index]; | |
326 | ||
327 | buffer_turn_info_type& previous_turn = m_turns[previous_itop.turn_index]; | |
328 | buffer_turn_info_type& next_turn = m_turns[next_itop.turn_index]; | |
329 | ||
330 | if (previous_turn.close_to_offset | |
331 | && is_following(previous_turn, last_traversable_operation)) | |
332 | { | |
333 | previous_turn.is_turn_traversable = true; | |
334 | } | |
335 | else if (next_turn.close_to_offset | |
336 | && is_following(next_turn, last_traversable_operation)) | |
337 | { | |
338 | next_turn.is_turn_traversable = true; | |
339 | } | |
7c673cae | 340 | } |
20effc67 TL |
341 | |
342 | if (turn.is_turn_traversable) | |
7c673cae | 343 | { |
20effc67 TL |
344 | first = false; |
345 | last_traversable_operation = *itop.subject; | |
346 | last_traversable_turn = turn; | |
7c673cae | 347 | } |
7c673cae FG |
348 | } |
349 | } | |
350 | ||
20effc67 | 351 | inline void check_linear_endpoints(buffer_turn_info_type& turn) const |
b32b8144 | 352 | { |
20effc67 TL |
353 | // TODO this is quadratic. But the #endpoints, expected, is low, |
354 | // and only applicable for linear features | |
355 | // (in a multi linestring with many short lines, the #endpoints can be | |
356 | // much higher) | |
357 | for (typename boost::range_iterator<std::vector<point_type> const>::type it | |
358 | = boost::begin(m_linear_end_points); | |
359 | it != boost::end(m_linear_end_points); | |
360 | ++it) | |
361 | { | |
1e59de90 | 362 | if (detail::equals::equals_point_point(turn.point, *it, m_strategy)) |
20effc67 TL |
363 | { |
364 | turn.is_linear_end_point = true; | |
365 | } | |
366 | } | |
367 | } | |
b32b8144 | 368 | |
20effc67 | 369 | inline void verify_turns() |
b32b8144 | 370 | { |
20effc67 TL |
371 | typedef detail::overlay::indexed_turn_operation |
372 | < | |
373 | buffer_turn_operation_type | |
374 | > indexed_turn_operation; | |
375 | typedef std::map | |
376 | < | |
377 | ring_identifier, | |
378 | std::vector<indexed_turn_operation> | |
379 | > mapped_vector_type; | |
380 | mapped_vector_type mapped_vector; | |
381 | ||
382 | detail::overlay::create_map(m_turns, mapped_vector, | |
383 | enriched_map_buffer_include_policy()); | |
384 | ||
385 | // Sort turns over offsetted ring(s) | |
386 | for (typename mapped_vector_type::iterator mit | |
387 | = mapped_vector.begin(); | |
388 | mit != mapped_vector.end(); | |
389 | ++mit) | |
b32b8144 | 390 | { |
20effc67 TL |
391 | std::sort(mit->second.begin(), mit->second.end(), buffer_less()); |
392 | } | |
b32b8144 | 393 | |
20effc67 TL |
394 | for (typename mapped_vector_type::iterator mit |
395 | = mapped_vector.begin(); | |
396 | mit != mapped_vector.end(); | |
397 | ++mit) | |
398 | { | |
399 | pretraverse(mit->second); | |
400 | } | |
401 | } | |
b32b8144 | 402 | |
20effc67 TL |
403 | inline void deflate_check_turns() |
404 | { | |
405 | if (! m_has_deflated) | |
406 | { | |
407 | return; | |
b32b8144 FG |
408 | } |
409 | ||
20effc67 TL |
410 | // Deflated rings may not travel to themselves, there should at least |
411 | // be three turns (which cannot be checked here - TODO: add to traverse) | |
b32b8144 FG |
412 | for (typename boost::range_iterator<turn_vector_type>::type it = |
413 | boost::begin(m_turns); it != boost::end(m_turns); ++it) | |
414 | { | |
415 | buffer_turn_info_type& turn = *it; | |
20effc67 | 416 | if (! turn.is_turn_traversable) |
b32b8144 | 417 | { |
20effc67 TL |
418 | continue; |
419 | } | |
420 | for (int i = 0; i < 2; i++) | |
421 | { | |
422 | buffer_turn_operation_type& op = turn.operations[i]; | |
423 | if (op.enriched.get_next_turn_index() == static_cast<signed_size_type>(turn.turn_index) | |
424 | && m_pieces[op.seg_id.piece_index].is_deflated) | |
b32b8144 | 425 | { |
20effc67 TL |
426 | // Keep traversable, but don't start here |
427 | op.enriched.startable = false; | |
b32b8144 FG |
428 | } |
429 | } | |
430 | } | |
431 | } | |
432 | ||
20effc67 TL |
433 | // Check if a turn is inside any of the originals |
434 | inline void check_turn_in_original() | |
7c673cae | 435 | { |
92f5a8d4 TL |
436 | turn_in_original_visitor |
437 | < | |
438 | turn_vector_type, | |
1e59de90 TL |
439 | Strategy |
440 | > visitor(m_turns, m_strategy); | |
92f5a8d4 | 441 | |
7c673cae FG |
442 | geometry::partition |
443 | < | |
20effc67 | 444 | box_type, |
b32b8144 FG |
445 | include_turn_policy, |
446 | detail::partition::include_all_policy | |
f67539c2 | 447 | >::apply(m_turns, original_rings, visitor, |
1e59de90 TL |
448 | turn_get_box<Strategy>(m_strategy), |
449 | turn_in_original_overlaps_box<Strategy>(m_strategy), | |
450 | original_get_box<Strategy>(m_strategy), | |
451 | original_overlaps_box<Strategy>(m_strategy)); | |
7c673cae | 452 | |
f67539c2 | 453 | bool const deflate = m_distance_strategy.negative(); |
7c673cae FG |
454 | |
455 | for (typename boost::range_iterator<turn_vector_type>::type it = | |
456 | boost::begin(m_turns); it != boost::end(m_turns); ++it) | |
457 | { | |
458 | buffer_turn_info_type& turn = *it; | |
20effc67 | 459 | if (turn.is_turn_traversable) |
7c673cae FG |
460 | { |
461 | if (deflate && turn.count_in_original <= 0) | |
462 | { | |
20effc67 TL |
463 | // For deflate/negative buffers: |
464 | // it is not in the original, so don't use it | |
465 | turn.is_turn_traversable = false; | |
7c673cae FG |
466 | } |
467 | else if (! deflate && turn.count_in_original > 0) | |
468 | { | |
20effc67 TL |
469 | // For inflate: it is in original, so don't use it |
470 | turn.is_turn_traversable = false; | |
7c673cae FG |
471 | } |
472 | } | |
473 | } | |
474 | } | |
475 | ||
f67539c2 | 476 | inline void update_turn_administration() |
7c673cae | 477 | { |
7c673cae FG |
478 | std::size_t index = 0; |
479 | for (typename boost::range_iterator<turn_vector_type>::type it = | |
480 | boost::begin(m_turns); it != boost::end(m_turns); ++it, ++index) | |
481 | { | |
20effc67 | 482 | buffer_turn_info_type& turn = *it; |
7c673cae | 483 | |
20effc67 TL |
484 | // Update member used |
485 | turn.turn_index = index; | |
7c673cae | 486 | |
20effc67 TL |
487 | // Verify if a turn is a linear endpoint |
488 | if (! turn.is_linear_end_point) | |
489 | { | |
490 | check_linear_endpoints(turn); | |
491 | } | |
7c673cae FG |
492 | } |
493 | } | |
494 | ||
20effc67 TL |
495 | // Calculate properties of piece borders which are not influenced |
496 | // by turns themselves: | |
497 | // - envelopes (essential for partitioning during calc turns) | |
498 | // - convexity | |
499 | // - monotonicity | |
500 | // - min/max radius of point buffers | |
501 | // - (if pieces are reversed) | |
502 | inline void update_piece_administration() | |
7c673cae FG |
503 | { |
504 | for (typename piece_vector_type::iterator it = boost::begin(m_pieces); | |
505 | it != boost::end(m_pieces); | |
506 | ++it) | |
507 | { | |
508 | piece& pc = *it; | |
20effc67 TL |
509 | piece_border_type& border = pc.m_piece_border; |
510 | buffered_ring<Ring> const& ring = offsetted_rings[pc.first_seg_id.multi_index]; | |
7c673cae | 511 | |
20effc67 | 512 | if (pc.offsetted_count > 0) |
7c673cae | 513 | { |
20effc67 TL |
514 | if (pc.type != strategy::buffer::buffered_concave) |
515 | { | |
516 | border.set_offsetted(ring, pc.first_seg_id.segment_index, | |
517 | pc.beyond_last_segment_index); | |
518 | } | |
7c673cae | 519 | |
20effc67 | 520 | // Calculate envelopes for piece borders |
1e59de90 TL |
521 | border.get_properties_of_border(pc.type == geometry::strategy::buffer::buffered_point, |
522 | pc.m_center, m_strategy); | |
20effc67 TL |
523 | if (! pc.is_flat_end && ! pc.is_flat_start) |
524 | { | |
1e59de90 | 525 | border.get_properties_of_offsetted_ring_part(m_strategy); |
20effc67 | 526 | } |
7c673cae FG |
527 | } |
528 | } | |
529 | } | |
530 | ||
f67539c2 | 531 | inline void get_turns() |
7c673cae | 532 | { |
20effc67 TL |
533 | update_piece_administration(); |
534 | ||
7c673cae FG |
535 | { |
536 | // Calculate the turns | |
537 | piece_turn_visitor | |
538 | < | |
539 | piece_vector_type, | |
540 | buffered_ring_collection<buffered_ring<Ring> >, | |
541 | turn_vector_type, | |
1e59de90 | 542 | Strategy, |
7c673cae | 543 | RobustPolicy |
b32b8144 | 544 | > visitor(m_pieces, offsetted_rings, m_turns, |
1e59de90 | 545 | m_strategy, m_robust_policy); |
7c673cae | 546 | |
1e59de90 | 547 | detail::sectionalize::enlarge_sections(monotonic_sections, m_strategy); |
92f5a8d4 | 548 | |
7c673cae FG |
549 | geometry::partition |
550 | < | |
b32b8144 FG |
551 | robust_box_type |
552 | >::apply(monotonic_sections, visitor, | |
1e59de90 TL |
553 | detail::section::get_section_box<Strategy>(m_strategy), |
554 | detail::section::overlaps_section_box<Strategy>(m_strategy)); | |
7c673cae FG |
555 | } |
556 | ||
f67539c2 | 557 | update_turn_administration(); |
7c673cae | 558 | |
7c673cae | 559 | { |
20effc67 | 560 | // Check if turns are inside pieces |
7c673cae FG |
561 | turn_in_piece_visitor |
562 | < | |
92f5a8d4 | 563 | typename geometry::cs_tag<point_type>::type, |
1e59de90 TL |
564 | turn_vector_type, piece_vector_type, DistanceStrategy, Strategy |
565 | > visitor(m_turns, m_pieces, m_distance_strategy, m_strategy); | |
7c673cae FG |
566 | |
567 | geometry::partition | |
568 | < | |
20effc67 | 569 | box_type |
b32b8144 | 570 | >::apply(m_turns, m_pieces, visitor, |
1e59de90 TL |
571 | turn_get_box<Strategy>(m_strategy), |
572 | turn_overlaps_box<Strategy>(m_strategy), | |
573 | piece_get_box<Strategy>(m_strategy), | |
574 | piece_overlaps_box<Strategy>(m_strategy)); | |
7c673cae FG |
575 | } |
576 | } | |
577 | ||
b32b8144 | 578 | inline void start_new_ring(bool deflate) |
7c673cae | 579 | { |
f67539c2 | 580 | std::size_t const n = offsetted_rings.size(); |
7c673cae | 581 | current_segment_id.source_index = 0; |
f67539c2 | 582 | current_segment_id.multi_index = static_cast<signed_size_type>(n); |
7c673cae FG |
583 | current_segment_id.ring_index = -1; |
584 | current_segment_id.segment_index = 0; | |
585 | ||
586 | offsetted_rings.resize(n + 1); | |
f67539c2 | 587 | original_rings.resize(n + 1); |
7c673cae FG |
588 | |
589 | m_first_piece_index = static_cast<signed_size_type>(boost::size(m_pieces)); | |
b32b8144 FG |
590 | m_deflate = deflate; |
591 | if (deflate) | |
592 | { | |
593 | // Pieces contain either deflated exterior rings, or inflated | |
594 | // interior rings which are effectively deflated too | |
595 | m_has_deflated = true; | |
596 | } | |
7c673cae FG |
597 | } |
598 | ||
599 | inline void abort_ring() | |
600 | { | |
601 | // Remove all created pieces for this ring, sections, last offsetted | |
602 | while (! m_pieces.empty() | |
603 | && m_pieces.back().first_seg_id.multi_index | |
604 | == current_segment_id.multi_index) | |
605 | { | |
f67539c2 | 606 | m_pieces.pop_back(); |
7c673cae FG |
607 | } |
608 | ||
f67539c2 TL |
609 | offsetted_rings.pop_back(); |
610 | original_rings.pop_back(); | |
7c673cae FG |
611 | |
612 | m_first_piece_index = -1; | |
613 | } | |
614 | ||
7c673cae FG |
615 | inline void update_last_point(point_type const& p, |
616 | buffered_ring<Ring>& ring) | |
617 | { | |
618 | // For the first point of a new piece, and there were already | |
619 | // points in the offsetted ring, for some piece types the first point | |
620 | // is a duplicate of the last point of the previous piece. | |
621 | ||
622 | // TODO: disable that, that point should not be added | |
623 | ||
624 | // For now, it is made equal because due to numerical instability, | |
625 | // it can be a tiny bit off, possibly causing a self-intersection | |
626 | ||
627 | BOOST_GEOMETRY_ASSERT(boost::size(m_pieces) > 0); | |
628 | if (! ring.empty() | |
629 | && current_segment_id.segment_index | |
630 | == m_pieces.back().first_seg_id.segment_index) | |
631 | { | |
632 | ring.back() = p; | |
633 | } | |
634 | } | |
635 | ||
636 | inline void set_piece_center(point_type const& center) | |
637 | { | |
638 | BOOST_GEOMETRY_ASSERT(! m_pieces.empty()); | |
20effc67 | 639 | m_pieces.back().m_center = center; |
7c673cae FG |
640 | } |
641 | ||
f67539c2 | 642 | inline bool finish_ring(strategy::buffer::result_code code) |
7c673cae FG |
643 | { |
644 | if (code == strategy::buffer::result_error_numerical) | |
645 | { | |
646 | abort_ring(); | |
f67539c2 | 647 | return false; |
7c673cae FG |
648 | } |
649 | ||
650 | if (m_first_piece_index == -1) | |
651 | { | |
f67539c2 | 652 | return false; |
7c673cae FG |
653 | } |
654 | ||
f67539c2 TL |
655 | // Casted version |
656 | std::size_t const first_piece_index | |
657 | = static_cast<std::size_t>(m_first_piece_index); | |
658 | signed_size_type const last_piece_index | |
659 | = static_cast<signed_size_type>(boost::size(m_pieces)) - 1; | |
660 | ||
661 | if (first_piece_index < boost::size(m_pieces)) | |
7c673cae | 662 | { |
f67539c2 TL |
663 | // If pieces were added, |
664 | // reassign left-of-first and right-of-last | |
665 | geometry::range::at(m_pieces, first_piece_index).left_index | |
666 | = last_piece_index; | |
7c673cae FG |
667 | geometry::range::back(m_pieces).right_index = m_first_piece_index; |
668 | } | |
f67539c2 TL |
669 | |
670 | buffered_ring<Ring>& added = offsetted_rings.back(); | |
671 | if (! boost::empty(added)) | |
672 | { | |
673 | // Make sure the closing point is identical (they are calculated | |
674 | // separately by different pieces) | |
675 | range::back(added) = range::front(added); | |
676 | } | |
677 | ||
678 | for (std::size_t i = first_piece_index; i < boost::size(m_pieces); i++) | |
679 | { | |
680 | sectionalize(m_pieces[i], added); | |
681 | } | |
682 | ||
7c673cae | 683 | m_first_piece_index = -1; |
f67539c2 TL |
684 | return true; |
685 | } | |
7c673cae | 686 | |
f67539c2 TL |
687 | template <typename InputRing> |
688 | inline void finish_ring(strategy::buffer::result_code code, | |
689 | InputRing const& input_ring, | |
690 | bool is_interior, bool has_interiors) | |
691 | { | |
692 | if (! finish_ring(code)) | |
693 | { | |
694 | return; | |
695 | } | |
7c673cae | 696 | |
f67539c2 | 697 | if (! input_ring.empty()) |
7c673cae | 698 | { |
f67539c2 TL |
699 | // Assign the ring to the original_ring collection |
700 | // For rescaling, it is recalculated. Without rescaling, it | |
701 | // is just assigning (note that this Ring type is the | |
702 | // GeometryOut type, which might differ from the input ring type) | |
20effc67 | 703 | clockwise_ring_type clockwise_ring; |
f67539c2 | 704 | |
1e59de90 | 705 | using view_type = detail::closed_clockwise_view<InputRing const>; |
f67539c2 TL |
706 | view_type const view(input_ring); |
707 | ||
708 | for (typename boost::range_iterator<view_type const>::type it = | |
709 | boost::begin(view); it != boost::end(view); ++it) | |
710 | { | |
20effc67 | 711 | clockwise_ring.push_back(*it); |
f67539c2 TL |
712 | } |
713 | ||
714 | original_rings.back() | |
20effc67 | 715 | = original_ring(clockwise_ring, |
f67539c2 | 716 | is_interior, has_interiors, |
1e59de90 | 717 | m_strategy); |
7c673cae FG |
718 | } |
719 | } | |
720 | ||
721 | inline void set_current_ring_concave() | |
722 | { | |
723 | BOOST_GEOMETRY_ASSERT(boost::size(offsetted_rings) > 0); | |
724 | offsetted_rings.back().has_concave = true; | |
725 | } | |
726 | ||
727 | inline signed_size_type add_point(point_type const& p) | |
728 | { | |
729 | BOOST_GEOMETRY_ASSERT(boost::size(offsetted_rings) > 0); | |
730 | ||
731 | buffered_ring<Ring>& current_ring = offsetted_rings.back(); | |
732 | update_last_point(p, current_ring); | |
733 | ||
734 | current_segment_id.segment_index++; | |
735 | current_ring.push_back(p); | |
736 | return static_cast<signed_size_type>(current_ring.size()); | |
737 | } | |
738 | ||
739 | //------------------------------------------------------------------------- | |
740 | ||
741 | inline piece& create_piece(strategy::buffer::piece_type type, | |
742 | bool decrease_segment_index_by_one) | |
743 | { | |
744 | if (type == strategy::buffer::buffered_concave) | |
745 | { | |
746 | offsetted_rings.back().has_concave = true; | |
747 | } | |
748 | ||
749 | piece pc; | |
750 | pc.type = type; | |
751 | pc.index = static_cast<signed_size_type>(boost::size(m_pieces)); | |
b32b8144 | 752 | pc.is_deflated = m_deflate; |
7c673cae FG |
753 | |
754 | current_segment_id.piece_index = pc.index; | |
755 | ||
756 | pc.first_seg_id = current_segment_id; | |
757 | ||
7c673cae FG |
758 | // Assign left/right (for first/last piece per ring they will be re-assigned later) |
759 | pc.left_index = pc.index - 1; | |
760 | pc.right_index = pc.index + 1; | |
761 | ||
762 | std::size_t const n = boost::size(offsetted_rings.back()); | |
763 | pc.first_seg_id.segment_index = decrease_segment_index_by_one ? n - 1 : n; | |
20effc67 | 764 | pc.beyond_last_segment_index = pc.first_seg_id.segment_index; |
7c673cae FG |
765 | |
766 | m_pieces.push_back(pc); | |
767 | return m_pieces.back(); | |
768 | } | |
769 | ||
20effc67 | 770 | inline void init_rescale_piece(piece& pc) |
7c673cae FG |
771 | { |
772 | if (pc.first_seg_id.segment_index < 0) | |
773 | { | |
774 | // This indicates an error situation: an earlier piece was empty | |
775 | // It currently does not happen | |
7c673cae FG |
776 | pc.offsetted_count = 0; |
777 | return; | |
778 | } | |
779 | ||
780 | BOOST_GEOMETRY_ASSERT(pc.first_seg_id.multi_index >= 0); | |
20effc67 | 781 | BOOST_GEOMETRY_ASSERT(pc.beyond_last_segment_index >= 0); |
7c673cae | 782 | |
20effc67 | 783 | pc.offsetted_count = pc.beyond_last_segment_index - pc.first_seg_id.segment_index; |
7c673cae | 784 | BOOST_GEOMETRY_ASSERT(pc.offsetted_count >= 0); |
7c673cae FG |
785 | } |
786 | ||
20effc67 | 787 | inline void add_piece_point(piece& pc, const point_type& point, bool add_to_original) |
7c673cae | 788 | { |
20effc67 | 789 | if (add_to_original && pc.type != strategy::buffer::buffered_concave) |
7c673cae | 790 | { |
20effc67 | 791 | pc.m_piece_border.add_original_point(point); |
7c673cae | 792 | } |
20effc67 | 793 | else |
7c673cae | 794 | { |
20effc67 | 795 | pc.m_label_point = point; |
7c673cae | 796 | } |
7c673cae FG |
797 | } |
798 | ||
f67539c2 | 799 | inline void sectionalize(piece const& pc, buffered_ring<Ring> const& ring) |
7c673cae | 800 | { |
1e59de90 | 801 | using sectionalizer = geometry::detail::sectionalize::sectionalize_part |
7c673cae | 802 | < |
20effc67 | 803 | std::integer_sequence<std::size_t, 0, 1> // x,y dimension |
1e59de90 | 804 | >; |
7c673cae FG |
805 | |
806 | // Create a ring-identifier. The source-index is the piece index | |
807 | // The multi_index is as in this collection (the ring), but not used here | |
808 | // The ring_index is not used | |
f67539c2 | 809 | ring_identifier const ring_id(pc.index, pc.first_seg_id.multi_index, -1); |
7c673cae FG |
810 | |
811 | sectionalizer::apply(monotonic_sections, | |
812 | boost::begin(ring) + pc.first_seg_id.segment_index, | |
20effc67 | 813 | boost::begin(ring) + pc.beyond_last_segment_index, |
7c673cae | 814 | m_robust_policy, |
1e59de90 | 815 | m_strategy, |
7c673cae FG |
816 | ring_id, 10); |
817 | } | |
818 | ||
819 | inline void finish_piece(piece& pc) | |
820 | { | |
20effc67 | 821 | init_rescale_piece(pc); |
7c673cae FG |
822 | } |
823 | ||
824 | inline void finish_piece(piece& pc, | |
20effc67 TL |
825 | point_type const& point1, |
826 | point_type const& point2, | |
827 | point_type const& point3) | |
7c673cae | 828 | { |
20effc67 | 829 | init_rescale_piece(pc); |
7c673cae FG |
830 | if (pc.offsetted_count == 0) |
831 | { | |
832 | return; | |
833 | } | |
834 | ||
20effc67 TL |
835 | add_piece_point(pc, point1, false); |
836 | add_piece_point(pc, point2, true); | |
837 | add_piece_point(pc, point3, false); | |
7c673cae FG |
838 | } |
839 | ||
840 | inline void finish_piece(piece& pc, | |
20effc67 TL |
841 | point_type const& point1, |
842 | point_type const& point2, | |
843 | point_type const& point3, | |
844 | point_type const& point4) | |
7c673cae | 845 | { |
20effc67 TL |
846 | init_rescale_piece(pc); |
847 | ||
848 | // Add the four points. Note that points 2 and 3 are the originals, | |
849 | // and that they are already passed in reverse order | |
850 | // (because the offsetted ring is in clockwise order) | |
851 | add_piece_point(pc, point1, false); | |
852 | add_piece_point(pc, point2, true); | |
853 | add_piece_point(pc, point3, true); | |
854 | add_piece_point(pc, point4, false); | |
7c673cae FG |
855 | } |
856 | ||
857 | template <typename Range> | |
858 | inline void add_range_to_piece(piece& pc, Range const& range, bool add_front) | |
859 | { | |
860 | BOOST_GEOMETRY_ASSERT(boost::size(range) != 0u); | |
861 | ||
862 | typename Range::const_iterator it = boost::begin(range); | |
863 | ||
864 | // If it follows a non-join (so basically the same piece-type) point b1 should be added. | |
865 | // There should be two intersections later and it should be discarded. | |
866 | // But for now we need it to calculate intersections | |
867 | if (add_front) | |
868 | { | |
869 | add_point(*it); | |
870 | } | |
871 | ||
872 | for (++it; it != boost::end(range); ++it) | |
873 | { | |
20effc67 | 874 | pc.beyond_last_segment_index = add_point(*it); |
7c673cae FG |
875 | } |
876 | } | |
877 | ||
f67539c2 TL |
878 | inline void add_piece(strategy::buffer::piece_type type, point_type const& p, |
879 | point_type const& b1, point_type const& b2) | |
880 | { | |
881 | piece& pc = create_piece(type, false); | |
882 | add_point(b1); | |
20effc67 | 883 | pc.beyond_last_segment_index = add_point(b2); |
f67539c2 TL |
884 | finish_piece(pc, b2, p, b1); |
885 | } | |
7c673cae FG |
886 | |
887 | template <typename Range> | |
888 | inline void add_piece(strategy::buffer::piece_type type, Range const& range, | |
889 | bool decrease_segment_index_by_one) | |
890 | { | |
891 | piece& pc = create_piece(type, decrease_segment_index_by_one); | |
892 | ||
893 | if (boost::size(range) > 0u) | |
894 | { | |
895 | add_range_to_piece(pc, range, offsetted_rings.back().empty()); | |
896 | } | |
897 | finish_piece(pc); | |
898 | } | |
899 | ||
7c673cae FG |
900 | template <typename Range> |
901 | inline void add_piece(strategy::buffer::piece_type type, | |
902 | point_type const& p, Range const& range) | |
903 | { | |
904 | piece& pc = create_piece(type, true); | |
905 | ||
906 | if (boost::size(range) > 0u) | |
907 | { | |
908 | add_range_to_piece(pc, range, offsetted_rings.back().empty()); | |
909 | finish_piece(pc, range.back(), p, range.front()); | |
910 | } | |
911 | else | |
912 | { | |
913 | finish_piece(pc); | |
914 | } | |
915 | } | |
916 | ||
f67539c2 | 917 | template <typename Range> |
20effc67 TL |
918 | inline void add_side_piece(point_type const& original_point1, |
919 | point_type const& original_point2, | |
f67539c2 TL |
920 | Range const& range, bool first) |
921 | { | |
922 | BOOST_GEOMETRY_ASSERT(boost::size(range) >= 2u); | |
923 | ||
924 | piece& pc = create_piece(strategy::buffer::buffered_segment, ! first); | |
925 | add_range_to_piece(pc, range, first); | |
20effc67 TL |
926 | |
927 | // Add the four points of the side, starting with the last point of the | |
928 | // range, and reversing the order of the originals to keep it clockwise | |
929 | finish_piece(pc, range.back(), original_point2, original_point1, range.front()); | |
f67539c2 TL |
930 | } |
931 | ||
7c673cae FG |
932 | template <typename EndcapStrategy, typename Range> |
933 | inline void add_endcap(EndcapStrategy const& strategy, Range const& range, | |
934 | point_type const& end_point) | |
935 | { | |
936 | boost::ignore_unused(strategy); | |
937 | ||
938 | if (range.empty()) | |
939 | { | |
940 | return; | |
941 | } | |
942 | strategy::buffer::piece_type pt = strategy.get_piece_type(); | |
943 | if (pt == strategy::buffer::buffered_flat_end) | |
944 | { | |
945 | // It is flat, should just be added, without helper segments | |
946 | add_piece(pt, range, true); | |
947 | } | |
948 | else | |
949 | { | |
950 | // Normal case, it has an "inside", helper segments should be added | |
951 | add_piece(pt, end_point, range); | |
952 | } | |
953 | } | |
954 | ||
20effc67 | 955 | inline void mark_flat_start(point_type const& point) |
b32b8144 FG |
956 | { |
957 | if (! m_pieces.empty()) | |
958 | { | |
959 | piece& back = m_pieces.back(); | |
960 | back.is_flat_start = true; | |
20effc67 TL |
961 | |
962 | // This happens to linear buffers, and it will be the very | |
963 | // first or last point. If that coincides with a turn, | |
964 | // and the turn was marked as ON_BORDER | |
965 | // the turn should NOT be within (even though it can be marked | |
966 | // as such) | |
967 | m_linear_end_points.push_back(point); | |
b32b8144 FG |
968 | } |
969 | } | |
970 | ||
20effc67 | 971 | inline void mark_flat_end(point_type const& point) |
b32b8144 FG |
972 | { |
973 | if (! m_pieces.empty()) | |
974 | { | |
975 | piece& back = m_pieces.back(); | |
976 | back.is_flat_end = true; | |
20effc67 | 977 | m_linear_end_points.push_back(point); |
b32b8144 FG |
978 | } |
979 | } | |
980 | ||
7c673cae FG |
981 | //------------------------------------------------------------------------- |
982 | ||
983 | inline void enrich() | |
984 | { | |
7c673cae | 985 | enrich_intersection_points<false, false, overlay_buffer>(m_turns, |
92f5a8d4 TL |
986 | m_clusters, offsetted_rings, offsetted_rings, |
987 | m_robust_policy, | |
1e59de90 | 988 | m_strategy); |
7c673cae FG |
989 | } |
990 | ||
991 | // Discards all rings which do have not-OK intersection points only. | |
992 | // Those can never be traversed and should not be part of the output. | |
993 | inline void discard_rings() | |
994 | { | |
995 | for (typename boost::range_iterator<turn_vector_type const>::type it = | |
996 | boost::begin(m_turns); it != boost::end(m_turns); ++it) | |
997 | { | |
20effc67 | 998 | if (it->is_turn_traversable) |
7c673cae | 999 | { |
20effc67 TL |
1000 | offsetted_rings[it->operations[0].seg_id.multi_index].has_accepted_intersections = true; |
1001 | offsetted_rings[it->operations[1].seg_id.multi_index].has_accepted_intersections = true; | |
7c673cae FG |
1002 | } |
1003 | else | |
1004 | { | |
20effc67 TL |
1005 | offsetted_rings[it->operations[0].seg_id.multi_index].has_discarded_intersections = true; |
1006 | offsetted_rings[it->operations[1].seg_id.multi_index].has_discarded_intersections = true; | |
7c673cae FG |
1007 | } |
1008 | } | |
1009 | } | |
1010 | ||
1011 | inline bool point_coveredby_original(point_type const& point) | |
1012 | { | |
7c673cae FG |
1013 | signed_size_type count_in_original = 0; |
1014 | ||
1015 | // Check of the robust point of this outputted ring is in | |
1016 | // any of the robust original rings | |
1017 | // This can go quadratic if the input has many rings, and there | |
1018 | // are many untouched deflated rings around | |
f67539c2 TL |
1019 | for (typename std::vector<original_ring>::const_iterator it |
1020 | = original_rings.begin(); | |
1021 | it != original_rings.end(); | |
7c673cae FG |
1022 | ++it) |
1023 | { | |
f67539c2 TL |
1024 | original_ring const& original = *it; |
1025 | if (original.m_ring.empty()) | |
1026 | { | |
1027 | continue; | |
1028 | } | |
1e59de90 | 1029 | if (detail::disjoint::disjoint_point_box(point, original.m_box,m_strategy)) |
7c673cae FG |
1030 | { |
1031 | continue; | |
1032 | } | |
1033 | ||
1034 | int const geometry_code | |
1e59de90 | 1035 | = detail::within::point_in_geometry(point, original.m_ring, m_strategy); |
7c673cae FG |
1036 | |
1037 | if (geometry_code == -1) | |
1038 | { | |
1039 | // Outside, continue | |
1040 | continue; | |
1041 | } | |
1042 | ||
1043 | // Apply for possibly nested interior rings | |
1044 | if (original.m_is_interior) | |
1045 | { | |
1046 | count_in_original--; | |
1047 | } | |
1048 | else if (original.m_has_interiors) | |
1049 | { | |
1050 | count_in_original++; | |
1051 | } | |
1052 | else | |
1053 | { | |
1054 | // Exterior ring without interior rings | |
1055 | return true; | |
1056 | } | |
1057 | } | |
1058 | return count_in_original > 0; | |
1059 | } | |
1060 | ||
1061 | // For a deflate, all rings around inner rings which are untouched | |
1062 | // (no intersections/turns) and which are OUTSIDE the original should | |
1063 | // be discarded | |
1064 | inline void discard_nonintersecting_deflated_rings() | |
1065 | { | |
1066 | for(typename buffered_ring_collection<buffered_ring<Ring> >::iterator it | |
1067 | = boost::begin(offsetted_rings); | |
1068 | it != boost::end(offsetted_rings); | |
1069 | ++it) | |
1070 | { | |
1071 | buffered_ring<Ring>& ring = *it; | |
1072 | if (! ring.has_intersections() | |
1073 | && boost::size(ring) > 0u | |
1e59de90 | 1074 | && geometry::area(ring, m_strategy) < 0) |
7c673cae FG |
1075 | { |
1076 | if (! point_coveredby_original(geometry::range::front(ring))) | |
1077 | { | |
1078 | ring.is_untouched_outside_original = true; | |
1079 | } | |
1080 | } | |
1081 | } | |
1082 | } | |
1083 | ||
1084 | inline void block_turns() | |
1085 | { | |
7c673cae FG |
1086 | for (typename boost::range_iterator<turn_vector_type>::type it = |
1087 | boost::begin(m_turns); it != boost::end(m_turns); ++it) | |
1088 | { | |
1089 | buffer_turn_info_type& turn = *it; | |
20effc67 | 1090 | if (! turn.is_turn_traversable) |
7c673cae FG |
1091 | { |
1092 | // Discard this turn (don't set it to blocked to avoid colocated | |
1093 | // clusters being discarded afterwards | |
1094 | turn.discarded = true; | |
1095 | } | |
1096 | } | |
1097 | } | |
1098 | ||
1099 | inline void traverse() | |
1100 | { | |
1101 | typedef detail::overlay::traverse | |
1102 | < | |
1103 | false, false, | |
1104 | buffered_ring_collection<buffered_ring<Ring> >, | |
1105 | buffered_ring_collection<buffered_ring<Ring > >, | |
1106 | overlay_buffer, | |
1107 | backtrack_for_buffer | |
1108 | > traverser; | |
b32b8144 | 1109 | std::map<ring_identifier, overlay::ring_turn_info> turn_info_per_ring; |
7c673cae FG |
1110 | |
1111 | traversed_rings.clear(); | |
1112 | buffer_overlay_visitor visitor; | |
1113 | traverser::apply(offsetted_rings, offsetted_rings, | |
1e59de90 | 1114 | m_strategy, m_robust_policy, |
b32b8144 FG |
1115 | m_turns, traversed_rings, |
1116 | turn_info_per_ring, | |
7c673cae FG |
1117 | m_clusters, visitor); |
1118 | } | |
1119 | ||
1120 | inline void reverse() | |
1121 | { | |
1122 | for(typename buffered_ring_collection<buffered_ring<Ring> >::iterator it = boost::begin(offsetted_rings); | |
1123 | it != boost::end(offsetted_rings); | |
1124 | ++it) | |
1125 | { | |
1126 | if (! it->has_intersections()) | |
1127 | { | |
1128 | std::reverse(it->begin(), it->end()); | |
1129 | } | |
1130 | } | |
1131 | for (typename boost::range_iterator<buffered_ring_collection<Ring> >::type | |
1132 | it = boost::begin(traversed_rings); | |
1133 | it != boost::end(traversed_rings); | |
1134 | ++it) | |
1135 | { | |
1136 | std::reverse(it->begin(), it->end()); | |
1137 | } | |
7c673cae FG |
1138 | } |
1139 | ||
1140 | template <typename GeometryOutput, typename OutputIterator> | |
1141 | inline OutputIterator assign(OutputIterator out) const | |
1142 | { | |
1e59de90 TL |
1143 | typedef typename geometry::area_result |
1144 | < | |
1145 | buffered_ring<Ring>, Strategy | |
1146 | >::type area_result_type; | |
1147 | typedef detail::overlay::ring_properties | |
1148 | < | |
1149 | point_type, area_result_type | |
1150 | > properties; | |
7c673cae FG |
1151 | |
1152 | std::map<ring_identifier, properties> selected; | |
1153 | ||
1154 | // Select all rings which do not have any self-intersection | |
1155 | // Inner rings, for deflate, which do not have intersections, and | |
1156 | // which are outside originals, are skipped | |
1157 | // (other ones should be traversed) | |
1158 | signed_size_type index = 0; | |
1159 | for(typename buffered_ring_collection<buffered_ring<Ring> >::const_iterator it = boost::begin(offsetted_rings); | |
1160 | it != boost::end(offsetted_rings); | |
1161 | ++it, ++index) | |
1162 | { | |
1163 | if (! it->has_intersections() | |
1164 | && ! it->is_untouched_outside_original) | |
1165 | { | |
1e59de90 | 1166 | properties p = properties(*it, m_strategy); |
7c673cae FG |
1167 | if (p.valid) |
1168 | { | |
1169 | ring_identifier id(0, index, -1); | |
1170 | selected[id] = p; | |
1171 | } | |
1172 | } | |
1173 | } | |
1174 | ||
1175 | // Select all created rings | |
1176 | index = 0; | |
1177 | for (typename boost::range_iterator<buffered_ring_collection<Ring> const>::type | |
1178 | it = boost::begin(traversed_rings); | |
1179 | it != boost::end(traversed_rings); | |
1180 | ++it, ++index) | |
1181 | { | |
1e59de90 | 1182 | properties p = properties(*it, m_strategy); |
7c673cae FG |
1183 | if (p.valid) |
1184 | { | |
1185 | ring_identifier id(2, index, -1); | |
1186 | selected[id] = p; | |
1187 | } | |
1188 | } | |
1189 | ||
11fdf7f2 | 1190 | detail::overlay::assign_parents<overlay_buffer>(offsetted_rings, traversed_rings, |
1e59de90 | 1191 | selected, m_strategy); |
b32b8144 | 1192 | return detail::overlay::add_rings<GeometryOutput>(selected, offsetted_rings, traversed_rings, out, |
1e59de90 | 1193 | m_strategy); |
7c673cae FG |
1194 | } |
1195 | ||
1196 | }; | |
1197 | ||
1198 | ||
1199 | }} // namespace detail::buffer | |
1200 | #endif // DOXYGEN_NO_DETAIL | |
1201 | ||
1202 | ||
1203 | }} // namespace boost::geometry | |
1204 | ||
1205 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFERED_PIECE_COLLECTION_HPP |