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