]>
Commit | Line | Data |
---|---|---|
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) | |
2 | ||
3 | // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. | |
5 | ||
6 | // This file was modified by Oracle on 2016, 2018. | |
7 | // Modifications copyright (c) 2016-2018 Oracle and/or its affiliates. | |
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_TURN_IN_PIECE_VISITOR | |
15 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_PIECE_VISITOR | |
16 | ||
17 | ||
18 | #include <boost/core/ignore_unused.hpp> | |
19 | ||
20 | #include <boost/range.hpp> | |
21 | ||
22 | #include <boost/geometry/core/assert.hpp> | |
23 | #include <boost/geometry/core/config.hpp> | |
24 | ||
25 | #include <boost/geometry/arithmetic/dot_product.hpp> | |
26 | #include <boost/geometry/algorithms/assign.hpp> | |
27 | #include <boost/geometry/algorithms/comparable_distance.hpp> | |
28 | #include <boost/geometry/algorithms/equals.hpp> | |
29 | #include <boost/geometry/algorithms/expand.hpp> | |
30 | #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp> | |
31 | #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp> | |
32 | #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp> | |
33 | #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp> | |
34 | #include <boost/geometry/policies/compare.hpp> | |
35 | #include <boost/geometry/strategies/buffer.hpp> | |
36 | #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp> | |
37 | ||
38 | #include <boost/geometry/strategies/cartesian/side_of_intersection.hpp> | |
39 | ||
40 | ||
41 | namespace boost { namespace geometry | |
42 | { | |
43 | ||
44 | ||
45 | #ifndef DOXYGEN_NO_DETAIL | |
46 | namespace detail { namespace buffer | |
47 | { | |
48 | ||
49 | struct piece_get_box | |
50 | { | |
51 | template <typename Box, typename Piece> | |
52 | static inline void apply(Box& total, Piece const& piece) | |
53 | { | |
54 | geometry::expand(total, piece.robust_envelope); | |
55 | } | |
56 | }; | |
57 | ||
58 | template <typename DisjointBoxBoxStrategy> | |
59 | struct piece_ovelaps_box | |
60 | { | |
61 | template <typename Box, typename Piece> | |
62 | static inline bool apply(Box const& box, Piece const& piece) | |
63 | { | |
64 | if (piece.type == strategy::buffer::buffered_flat_end | |
65 | || piece.type == strategy::buffer::buffered_concave) | |
66 | { | |
67 | // Turns cannot be inside a flat end (though they can be on border) | |
68 | // Neither we need to check if they are inside concave helper pieces | |
69 | ||
70 | // Skip all pieces not used as soon as possible | |
71 | return false; | |
72 | } | |
73 | ||
74 | return ! geometry::detail::disjoint::disjoint_box_box(box, piece.robust_envelope, | |
75 | DisjointBoxBoxStrategy()); | |
76 | } | |
77 | }; | |
78 | ||
79 | struct turn_get_box | |
80 | { | |
81 | template <typename Box, typename Turn> | |
82 | static inline void apply(Box& total, Turn const& turn) | |
83 | { | |
84 | geometry::expand(total, turn.robust_point); | |
85 | } | |
86 | }; | |
87 | ||
88 | template <typename DisjointPointBoxStrategy> | |
89 | struct turn_ovelaps_box | |
90 | { | |
91 | template <typename Box, typename Turn> | |
92 | static inline bool apply(Box const& box, Turn const& turn) | |
93 | { | |
94 | return ! geometry::detail::disjoint::disjoint_point_box(turn.robust_point, box, | |
95 | DisjointPointBoxStrategy()); | |
96 | } | |
97 | }; | |
98 | ||
99 | ||
100 | enum analyse_result | |
101 | { | |
102 | analyse_unknown, | |
103 | analyse_continue, | |
104 | analyse_disjoint, | |
105 | analyse_within, | |
106 | analyse_on_original_boundary, | |
107 | analyse_on_offsetted, | |
108 | analyse_near_offsetted | |
109 | }; | |
110 | ||
111 | template <typename Point> | |
112 | inline bool in_box(Point const& previous, | |
113 | Point const& current, Point const& point) | |
114 | { | |
115 | // Get its box (TODO: this can be prepared-on-demand later) | |
116 | typedef geometry::model::box<Point> box_type; | |
117 | box_type box; | |
118 | geometry::assign_inverse(box); | |
119 | geometry::expand(box, previous); | |
120 | geometry::expand(box, current); | |
121 | ||
122 | return geometry::covered_by(point, box); | |
123 | } | |
124 | ||
125 | template <typename NumericType> | |
126 | inline bool is_one_sided(NumericType const& left, NumericType const& right) | |
127 | { | |
128 | static NumericType const zero = 0; | |
129 | return geometry::math::equals(left, zero) | |
130 | || geometry::math::equals(right, zero); | |
131 | } | |
132 | ||
133 | template <typename Point, typename DistanceStrategy> | |
134 | inline bool has_zero_distance_at(Point const& point, | |
135 | DistanceStrategy const& distance_strategy) | |
136 | { | |
137 | return is_one_sided(distance_strategy.apply(point, point, | |
138 | strategy::buffer::buffer_side_left), | |
139 | distance_strategy.apply(point, point, | |
140 | strategy::buffer::buffer_side_right)); | |
141 | } | |
142 | ||
143 | // meta-programming-structure defining if to use side-of-intersection | |
144 | // (only for cartesian / only necessary with rescaling) | |
145 | template <typename Tag> | |
146 | struct use_side_of_intersection {}; | |
147 | ||
148 | #if defined(BOOST_GEOMETRY_USE_RESCALING) | |
149 | // With rescaling, let Cartesian use side-of-intersection | |
150 | template <> | |
151 | struct use_side_of_intersection<cartesian_tag> { static bool const value = true; }; | |
152 | #else | |
153 | template <> | |
154 | struct use_side_of_intersection<cartesian_tag> { static bool const value = false; }; | |
155 | #endif | |
156 | ||
157 | template <> | |
158 | struct use_side_of_intersection<spherical_tag> { static bool const value = false; }; | |
159 | ||
160 | template <> | |
161 | struct use_side_of_intersection<geographic_tag> { static bool const value = false; }; | |
162 | ||
163 | ||
164 | template <bool UseSideOfIntersection> | |
165 | struct check_segment {}; | |
166 | ||
167 | // Implementation using side-of-intersection | |
168 | template <> | |
169 | struct check_segment<true> | |
170 | { | |
171 | template <typename Point, typename Turn, typename SideStrategy> | |
172 | static inline analyse_result apply(Point const& previous, | |
173 | Point const& current, Turn const& turn, | |
174 | bool from_monotonic, | |
175 | SideStrategy const& ) | |
176 | { | |
177 | typedef geometry::model::referring_segment<Point const> segment_type; | |
178 | segment_type const p(turn.rob_pi, turn.rob_pj); | |
179 | segment_type const q(turn.rob_qi, turn.rob_qj); | |
180 | segment_type const r(previous, current); | |
181 | int const side = strategy::side::side_of_intersection::apply(p, q, r, | |
182 | turn.robust_point); | |
183 | ||
184 | if (side == 0) | |
185 | { | |
186 | return analyse_on_offsetted; | |
187 | } | |
188 | if (side == -1 && from_monotonic) | |
189 | { | |
190 | return analyse_within; | |
191 | } | |
192 | if (side == 1 && from_monotonic) | |
193 | { | |
194 | return analyse_disjoint; | |
195 | } | |
196 | return analyse_continue; | |
197 | } | |
198 | }; | |
199 | ||
200 | template <> | |
201 | struct check_segment<false> | |
202 | { | |
203 | template <typename Point, typename Turn, typename SideStrategy> | |
204 | static inline analyse_result apply(Point const& previous, | |
205 | Point const& current, Turn const& turn, | |
206 | bool from_monotonic, | |
207 | SideStrategy const& side_strategy) | |
208 | { | |
209 | int const side = side_strategy.apply(previous, current, turn.robust_point); | |
210 | ||
211 | if (side == 0) | |
212 | { | |
213 | // Collinear, only on segment if it is covered by its bbox | |
214 | if (in_box(previous, current, turn.robust_point)) | |
215 | { | |
216 | return analyse_on_offsetted; | |
217 | } | |
218 | } | |
219 | else if (side == -1) | |
220 | { | |
221 | // It is in the triangle right-of the segment where the | |
222 | // segment is the hypothenusa. Check if it is close | |
223 | // (within rounding-area) | |
224 | if (in_box(previous, current, turn.robust_point)) | |
225 | { | |
226 | return analyse_near_offsetted; | |
227 | } | |
228 | else if (from_monotonic) | |
229 | { | |
230 | return analyse_within; | |
231 | } | |
232 | } | |
233 | else if (from_monotonic) | |
234 | { | |
235 | // Left of segment | |
236 | return analyse_disjoint; | |
237 | } | |
238 | ||
239 | // Not monotonic, on left or right side: continue analysing | |
240 | return analyse_continue; | |
241 | } | |
242 | }; | |
243 | ||
244 | template <bool UseSideOfIntersection> | |
245 | class analyse_turn_wrt_point_piece {}; | |
246 | ||
247 | template <> | |
248 | class analyse_turn_wrt_point_piece<true> | |
249 | { | |
250 | public : | |
251 | template <typename Turn, typename Piece, typename PointInGeometryStrategy, typename SideStrategy> | |
252 | static inline analyse_result apply(Turn const& turn, Piece const& piece, | |
253 | PointInGeometryStrategy const& , | |
254 | SideStrategy const& ) | |
255 | { | |
256 | typedef typename Piece::section_type section_type; | |
257 | typedef typename Turn::robust_point_type point_type; | |
258 | typedef typename geometry::coordinate_type<point_type>::type coordinate_type; | |
259 | ||
260 | typedef geometry::model::referring_segment<point_type const> segment_type; | |
261 | segment_type const p(turn.rob_pi, turn.rob_pj); | |
262 | segment_type const q(turn.rob_qi, turn.rob_qj); | |
263 | ||
264 | BOOST_GEOMETRY_ASSERT(! piece.sections.empty()); | |
265 | ||
266 | coordinate_type const point_x = geometry::get<0>(turn.robust_point); | |
267 | ||
268 | for (std::size_t s = 0; s < piece.sections.size(); s++) | |
269 | { | |
270 | section_type const& section = piece.sections[s]; | |
271 | // If point within horizontal range of monotonic section: | |
272 | if (! section.duplicate | |
273 | && section.begin_index < section.end_index | |
274 | && point_x >= geometry::get<min_corner, 0>(section.bounding_box) - 1 | |
275 | && point_x <= geometry::get<max_corner, 0>(section.bounding_box) + 1) | |
276 | { | |
277 | for (signed_size_type i = section.begin_index + 1; i <= section.end_index; i++) | |
278 | { | |
279 | point_type const& previous = piece.robust_ring[i - 1]; | |
280 | point_type const& current = piece.robust_ring[i]; | |
281 | ||
282 | ||
283 | // First check if it is in range - if it is not, the | |
284 | // expensive side_of_intersection does not need to be | |
285 | // applied | |
286 | coordinate_type x1 = geometry::get<0>(previous); | |
287 | coordinate_type x2 = geometry::get<0>(current); | |
288 | ||
289 | if (x1 > x2) | |
290 | { | |
291 | std::swap(x1, x2); | |
292 | } | |
293 | ||
294 | if (point_x >= x1 - 1 && point_x <= x2 + 1) | |
295 | { | |
296 | segment_type const r(previous, current); | |
297 | int const side = strategy::side::side_of_intersection::apply(p, q, r, | |
298 | turn.robust_point); | |
299 | ||
300 | // Sections are monotonic in x-dimension | |
301 | if (side == 1) | |
302 | { | |
303 | // Left on segment | |
304 | return analyse_disjoint; | |
305 | } | |
306 | else if (side == 0) | |
307 | { | |
308 | // Collinear - TODO: check if really on segment | |
309 | return analyse_on_offsetted; | |
310 | } | |
311 | } | |
312 | } | |
313 | } | |
314 | } | |
315 | ||
316 | // It is nowhere outside, and not on segment, so it is within | |
317 | return analyse_within; | |
318 | } | |
319 | ||
320 | }; | |
321 | ||
322 | template <> | |
323 | class analyse_turn_wrt_point_piece<false> | |
324 | { | |
325 | public : | |
326 | template <typename Turn, typename Piece, typename PointInGeometryStrategy, typename SideStrategy> | |
327 | static inline analyse_result apply(Turn const& turn, Piece const& piece, | |
328 | PointInGeometryStrategy const& point_in_geometry_strategy, | |
329 | SideStrategy const& side_strategy) | |
330 | { | |
331 | typedef typename Piece::section_type section_type; | |
332 | typedef typename Turn::robust_point_type point_type; | |
333 | typedef typename geometry::coordinate_type<point_type>::type coordinate_type; | |
334 | ||
335 | typename PointInGeometryStrategy::state_type state; | |
336 | ||
337 | BOOST_GEOMETRY_ASSERT(! piece.sections.empty()); | |
338 | ||
339 | coordinate_type const point_x = geometry::get<0>(turn.robust_point); | |
340 | ||
341 | for (std::size_t s = 0; s < piece.sections.size(); s++) | |
342 | { | |
343 | section_type const& section = piece.sections[s]; | |
344 | // If point within horizontal range of monotonic section: | |
345 | if (! section.duplicate | |
346 | && section.begin_index < section.end_index | |
347 | && point_x >= geometry::get<min_corner, 0>(section.bounding_box) - 1 | |
348 | && point_x <= geometry::get<max_corner, 0>(section.bounding_box) + 1) | |
349 | { | |
350 | for (signed_size_type i = section.begin_index + 1; i <= section.end_index; i++) | |
351 | { | |
352 | point_type const& previous = piece.robust_ring[i - 1]; | |
353 | point_type const& current = piece.robust_ring[i]; | |
354 | ||
355 | analyse_result code = check_segment<false>::apply(previous, current, turn, false, side_strategy); | |
356 | if (code != analyse_continue) | |
357 | { | |
358 | return code; | |
359 | } | |
360 | ||
361 | // Get the state (to determine it is within), we don't have | |
362 | // to cover the on-segment case (covered above) | |
363 | point_in_geometry_strategy.apply(turn.robust_point, previous, current, state); | |
364 | } | |
365 | } | |
366 | } | |
367 | ||
368 | int const code = point_in_geometry_strategy.result(state); | |
369 | if (code == 1) | |
370 | { | |
371 | return analyse_within; | |
372 | } | |
373 | else if (code == -1) | |
374 | { | |
375 | return analyse_disjoint; | |
376 | } | |
377 | ||
378 | // Should normally not occur - on-segment is covered | |
379 | return analyse_unknown; | |
380 | } | |
381 | ||
382 | }; | |
383 | ||
384 | template <bool UseSideOfIntersection> | |
385 | struct check_helper_segment {}; | |
386 | ||
387 | template <> | |
388 | struct check_helper_segment<true> | |
389 | { | |
390 | template <typename Point, typename Turn, typename SideStrategy> | |
391 | static inline analyse_result apply(Point const& s1, | |
392 | Point const& s2, Turn const& turn, | |
393 | bool is_original, | |
394 | analyse_result result_for_original, | |
395 | Point const& offsetted, | |
396 | SideStrategy const& ) | |
397 | { | |
398 | boost::ignore_unused(offsetted, is_original); | |
399 | ||
400 | typedef geometry::model::referring_segment<Point const> segment_type; | |
401 | segment_type const p(turn.rob_pi, turn.rob_pj); | |
402 | segment_type const q(turn.rob_qi, turn.rob_qj); | |
403 | segment_type const r(s1, s2); | |
404 | int const side = strategy::side::side_of_intersection::apply(p, q, r, | |
405 | turn.robust_point); | |
406 | ||
407 | if (side == 1) | |
408 | { | |
409 | // left of segment | |
410 | return analyse_disjoint; | |
411 | } | |
412 | else if (side == 0) | |
413 | { | |
414 | // If is collinear, either on segment or before/after | |
415 | typedef geometry::model::box<Point> box_type; | |
416 | ||
417 | box_type box; | |
418 | geometry::assign_inverse(box); | |
419 | geometry::expand(box, s1); | |
420 | geometry::expand(box, s2); | |
421 | ||
422 | if (geometry::covered_by(turn.robust_point, box)) | |
423 | { | |
424 | return result_for_original; | |
425 | } | |
426 | ||
427 | // It is collinear but not on the segment. Because these | |
428 | // segments are convex, it is outside | |
429 | // Unless the offsetted ring is collinear or concave w.r.t. | |
430 | // helper-segment but that scenario is not yet supported | |
431 | return analyse_disjoint; | |
432 | } | |
433 | ||
434 | // right of segment | |
435 | return analyse_continue; | |
436 | } | |
437 | ||
438 | }; | |
439 | ||
440 | template <> | |
441 | struct check_helper_segment<false> | |
442 | { | |
443 | template <typename Point, typename Turn, typename SideStrategy> | |
444 | static inline analyse_result apply(Point const& s1, | |
445 | Point const& s2, Turn const& turn, | |
446 | bool is_original, | |
447 | analyse_result result_for_original, | |
448 | Point const& offsetted, | |
449 | SideStrategy const& side_strategy) | |
450 | { | |
451 | switch(side_strategy.apply(s1, s2, turn.robust_point)) | |
452 | { | |
453 | case 1 : | |
454 | return analyse_disjoint; // left of segment | |
455 | case 0 : | |
456 | { | |
457 | // If is collinear, either on segment or before/after | |
458 | typedef geometry::model::box<Point> box_type; | |
459 | ||
460 | box_type box; | |
461 | geometry::assign_inverse(box); | |
462 | geometry::expand(box, s1); | |
463 | geometry::expand(box, s2); | |
464 | ||
465 | if (geometry::covered_by(turn.robust_point, box)) | |
466 | { | |
467 | // It is on the segment | |
468 | if (! is_original | |
469 | && geometry::comparable_distance(turn.robust_point, offsetted) <= 1) | |
470 | { | |
471 | // It is within, and close to the offsetted-boundary, | |
472 | // take any rounding-issues into account | |
473 | return analyse_near_offsetted; | |
474 | } | |
475 | ||
476 | // Points on helper-segments are considered as within | |
477 | // Points on original boundary are processed differently | |
478 | return result_for_original; | |
479 | } | |
480 | ||
481 | // It is collinear but not on the segment. Because these | |
482 | // segments are convex, it is outside | |
483 | // Unless the offsetted ring is collinear or concave w.r.t. | |
484 | // helper-segment but that scenario is not yet supported | |
485 | return analyse_disjoint; | |
486 | } | |
487 | break; | |
488 | } | |
489 | ||
490 | // right of segment | |
491 | return analyse_continue; | |
492 | } | |
493 | }; | |
494 | ||
495 | template <bool UseSideOfIntersection> | |
496 | class analyse_turn_wrt_piece | |
497 | { | |
498 | template | |
499 | < | |
500 | typename Turn, | |
501 | typename Piece, | |
502 | typename DistanceStrategy, | |
503 | typename SideStrategy | |
504 | > | |
505 | static inline analyse_result | |
506 | check_helper_segments(Turn const& turn, Piece const& piece, | |
507 | DistanceStrategy const& distance_strategy, | |
508 | SideStrategy const& side_strategy) | |
509 | { | |
510 | typedef typename Turn::robust_point_type point_type; | |
511 | geometry::equal_to<point_type> comparator; | |
512 | ||
513 | point_type points[4]; | |
514 | ||
515 | signed_size_type helper_count = static_cast<signed_size_type>(piece.robust_ring.size()) | |
516 | - piece.offsetted_count; | |
517 | if (helper_count == 4) | |
518 | { | |
519 | for (int i = 0; i < 4; i++) | |
520 | { | |
521 | points[i] = piece.robust_ring[piece.offsetted_count + i]; | |
522 | } | |
523 | ||
524 | // 3--offsetted outline--0 | |
525 | // | | | |
526 | // left | | right | |
527 | // | | | |
528 | // 2===>==original===>===1 | |
529 | ||
530 | } | |
531 | else if (helper_count == 3) | |
532 | { | |
533 | // Triangular piece, assign points but assign second twice | |
534 | for (int i = 0; i < 4; i++) | |
535 | { | |
536 | int index = i < 2 ? i : i - 1; | |
537 | points[i] = piece.robust_ring[piece.offsetted_count + index]; | |
538 | } | |
539 | } | |
540 | else | |
541 | { | |
542 | // Some pieces (e.g. around points) do not have helper segments. | |
543 | // Others should have 3 (join) or 4 (side) | |
544 | return analyse_continue; | |
545 | } | |
546 | ||
547 | // If a turn is located on the original, it is considered as within, | |
548 | // unless it is at a flat start or end, or the buffer (at that point) | |
549 | // is one-sided (zero-distance) | |
550 | bool const one_sided = has_zero_distance_at(turn.point, distance_strategy); | |
551 | ||
552 | analyse_result const result_for_original | |
553 | = one_sided || piece.is_flat_end || piece.is_flat_start | |
554 | ? analyse_on_original_boundary | |
555 | : analyse_within; | |
556 | ||
557 | // First check point-equality | |
558 | point_type const& point = turn.robust_point; | |
559 | if (comparator(point, points[0]) || comparator(point, points[3])) | |
560 | { | |
561 | return analyse_on_offsetted; | |
562 | } | |
563 | if (comparator(point, points[1])) | |
564 | { | |
565 | // On original, with right corner of piece | |
566 | return result_for_original; | |
567 | } | |
568 | if (comparator(point, points[2])) | |
569 | { | |
570 | // On original, with left corner of piece | |
571 | return result_for_original; | |
572 | } | |
573 | ||
574 | // Right side of the piece (never an original) | |
575 | analyse_result result | |
576 | = check_helper_segment<UseSideOfIntersection>::apply(points[0], points[1], turn, | |
577 | false, analyse_within, points[0], side_strategy); | |
578 | if (result != analyse_continue) | |
579 | { | |
580 | return result; | |
581 | } | |
582 | ||
583 | // Left side of the piece (never an original) | |
584 | result = check_helper_segment<UseSideOfIntersection>::apply(points[2], points[3], turn, | |
585 | false, analyse_within, points[3], side_strategy); | |
586 | if (result != analyse_continue) | |
587 | { | |
588 | return result; | |
589 | } | |
590 | ||
591 | // Side of the piece at side of original geometry | |
592 | // (here flat start/end will result in within) | |
593 | if (! comparator(points[1], points[2])) | |
594 | { | |
595 | result = check_helper_segment<UseSideOfIntersection>::apply(points[1], | |
596 | points[2], turn, true, | |
597 | one_sided ? analyse_on_original_boundary : analyse_within, | |
598 | point, side_strategy); | |
599 | if (result != analyse_continue) | |
600 | { | |
601 | return result; | |
602 | } | |
603 | } | |
604 | ||
605 | // We are within the \/ or |_| shaped piece, where the top is the | |
606 | // offsetted ring. | |
607 | if (! geometry::covered_by(point, piece.robust_offsetted_envelope)) | |
608 | { | |
609 | // Not in offsetted-area. This makes a cheap check possible | |
610 | switch(side_strategy.apply(points[3], points[0], point)) | |
611 | { | |
612 | case 1 : return analyse_disjoint; | |
613 | case -1 : return analyse_within; | |
614 | case 0 : return analyse_disjoint; | |
615 | } | |
616 | } | |
617 | ||
618 | return analyse_continue; | |
619 | } | |
620 | ||
621 | template <typename Turn, typename Piece, typename Compare, typename SideStrategy> | |
622 | static inline analyse_result check_monotonic(Turn const& turn, Piece const& piece, Compare const& compare, SideStrategy const& side_strategy) | |
623 | { | |
624 | typedef typename Piece::piece_robust_ring_type ring_type; | |
625 | typedef typename ring_type::const_iterator it_type; | |
626 | it_type end = piece.robust_ring.begin() + piece.offsetted_count; | |
627 | it_type it = std::lower_bound(piece.robust_ring.begin(), | |
628 | end, | |
629 | turn.robust_point, | |
630 | compare); | |
631 | ||
632 | if (it != end | |
633 | && it != piece.robust_ring.begin()) | |
634 | { | |
635 | // iterator points to point larger than point | |
636 | // w.r.t. specified direction, and prev points to a point smaller | |
637 | // We now know if it is inside/outside | |
638 | it_type prev = it - 1; | |
639 | return check_segment<UseSideOfIntersection>::apply(*prev, *it, turn, true, side_strategy); | |
640 | } | |
641 | return analyse_continue; | |
642 | } | |
643 | ||
644 | public : | |
645 | template | |
646 | < | |
647 | typename Turn, | |
648 | typename Piece, | |
649 | typename DistanceStrategy, | |
650 | typename SideStrategy | |
651 | > | |
652 | static inline analyse_result apply(Turn const& turn, Piece const& piece, | |
653 | DistanceStrategy const& distance_strategy, | |
654 | SideStrategy const& side_strategy) | |
655 | { | |
656 | typedef typename Turn::robust_point_type point_type; | |
657 | analyse_result code = check_helper_segments(turn, piece, distance_strategy, side_strategy); | |
658 | if (code != analyse_continue) | |
659 | { | |
660 | return code; | |
661 | } | |
662 | ||
663 | geometry::equal_to<point_type> comparator; | |
664 | ||
665 | if (piece.offsetted_count > 8) | |
666 | { | |
667 | // If the offset contains some points and is monotonic, we try | |
668 | // to avoid walking all points linearly. | |
669 | // We try it only once. | |
670 | if (piece.is_monotonic_increasing[0]) | |
671 | { | |
672 | code = check_monotonic(turn, piece, geometry::less<point_type, 0>(), side_strategy); | |
673 | if (code != analyse_continue) return code; | |
674 | } | |
675 | else if (piece.is_monotonic_increasing[1]) | |
676 | { | |
677 | code = check_monotonic(turn, piece, geometry::less<point_type, 1>(), side_strategy); | |
678 | if (code != analyse_continue) return code; | |
679 | } | |
680 | else if (piece.is_monotonic_decreasing[0]) | |
681 | { | |
682 | code = check_monotonic(turn, piece, geometry::greater<point_type, 0>(), side_strategy); | |
683 | if (code != analyse_continue) return code; | |
684 | } | |
685 | else if (piece.is_monotonic_decreasing[1]) | |
686 | { | |
687 | code = check_monotonic(turn, piece, geometry::greater<point_type, 1>(), side_strategy); | |
688 | if (code != analyse_continue) return code; | |
689 | } | |
690 | } | |
691 | ||
692 | // It is small or not monotonic, walk linearly through offset | |
693 | // TODO: this will be combined with winding strategy | |
694 | ||
695 | for (signed_size_type i = 1; i < piece.offsetted_count; i++) | |
696 | { | |
697 | point_type const& previous = piece.robust_ring[i - 1]; | |
698 | point_type const& current = piece.robust_ring[i]; | |
699 | ||
700 | // The robust ring can contain duplicates | |
701 | // (on which any side or side-value would return 0) | |
702 | if (! comparator(previous, current)) | |
703 | { | |
704 | code = check_segment<UseSideOfIntersection>::apply(previous, current, turn, false, side_strategy); | |
705 | if (code != analyse_continue) | |
706 | { | |
707 | return code; | |
708 | } | |
709 | } | |
710 | } | |
711 | ||
712 | return analyse_unknown; | |
713 | } | |
714 | ||
715 | }; | |
716 | ||
717 | // Helper Structure, of which the apply method returns a side value in {-1, 0, 1} | |
718 | template <bool UseSideOfIntersection> | |
719 | struct turn_in_piece {}; | |
720 | ||
721 | template <> | |
722 | struct turn_in_piece<true> | |
723 | { | |
724 | ||
725 | private : | |
726 | template <typename Turn, typename Piece> | |
727 | static inline int in_convex_piece(Turn const& turn, Piece const& piece) | |
728 | { | |
729 | typedef typename Turn::robust_point_type point_type; | |
730 | typedef typename Piece::piece_robust_ring_type ring_type; | |
731 | typedef geometry::model::referring_segment<point_type const> segment; | |
732 | ||
733 | segment const p(turn.rob_pi, turn.rob_pj); | |
734 | segment const q(turn.rob_qi, turn.rob_qj); | |
735 | ||
736 | typedef typename boost::range_iterator<ring_type const>::type iterator_type; | |
737 | iterator_type it = boost::begin(piece.robust_ring); | |
738 | iterator_type end = boost::end(piece.robust_ring); | |
739 | ||
740 | // A robust ring is always closed, and always clockwise | |
741 | for (iterator_type previous = it++; it != end; ++previous, ++it) | |
742 | { | |
743 | geometry::equal_to<point_type> comparator; | |
744 | if (comparator(*previous, *it)) | |
745 | { | |
746 | // Points are the same | |
747 | continue; | |
748 | } | |
749 | ||
750 | segment r(*previous, *it); | |
751 | ||
752 | int const side = strategy::side::side_of_intersection::apply(p, q, r, | |
753 | turn.robust_point); | |
754 | ||
755 | if (side == 1) | |
756 | { | |
757 | // IP is left of segment, so it is outside | |
758 | return -1; // outside | |
759 | } | |
760 | else if (side == 0) | |
761 | { | |
762 | // IP is collinear with segment. TODO: we should analyze this further | |
763 | // For now we use the fallback point | |
764 | if (in_box(*previous, *it, turn.robust_point)) | |
765 | { | |
766 | return 0; | |
767 | } | |
768 | else | |
769 | { | |
770 | return -1; // outside | |
771 | } | |
772 | } | |
773 | } | |
774 | return 1; // inside | |
775 | } | |
776 | ||
777 | public : | |
778 | ||
779 | template <typename Turn, typename Piece, typename Strategy> | |
780 | static inline int apply(Turn const& turn, Piece const& piece, | |
781 | Strategy const& strategy) | |
782 | { | |
783 | if (piece.is_convex) | |
784 | { | |
785 | return in_convex_piece(turn, piece); | |
786 | } | |
787 | else | |
788 | { | |
789 | // side-of-intersection only supported for convex pieces | |
790 | // Call point_in_geometry, a performance-bottleneck | |
791 | // TODO: might be replaced by extending analysing piece | |
792 | return detail::within::point_in_geometry(turn.robust_point, | |
793 | piece.robust_ring, strategy); | |
794 | } | |
795 | } | |
796 | }; | |
797 | ||
798 | template <> | |
799 | struct turn_in_piece<false> | |
800 | { | |
801 | public : | |
802 | ||
803 | template <typename Turn, typename Piece, typename Strategy> | |
804 | static inline int apply(Turn const& turn, Piece const& piece, | |
805 | Strategy const& strategy) | |
806 | { | |
807 | return detail::within::point_in_geometry(turn.robust_point, | |
808 | piece.robust_ring, strategy); | |
809 | } | |
810 | }; | |
811 | ||
812 | template | |
813 | < | |
814 | typename CsTag, | |
815 | typename Turns, | |
816 | typename Pieces, | |
817 | typename DistanceStrategy, | |
818 | typename PointInGeometryStrategy, | |
819 | typename SideStrategy | |
820 | ||
821 | > | |
822 | class turn_in_piece_visitor | |
823 | { | |
824 | Turns& m_turns; // because partition is currently operating on const input only | |
825 | Pieces const& m_pieces; // to check for piece-type | |
826 | DistanceStrategy const& m_distance_strategy; // to check if point is on original | |
827 | PointInGeometryStrategy const& m_point_in_geometry_strategy; | |
828 | SideStrategy const& m_side_strategy; | |
829 | ||
830 | template <typename Operation, typename Piece> | |
831 | inline bool skip(Operation const& op, Piece const& piece) const | |
832 | { | |
833 | if (op.piece_index == piece.index) | |
834 | { | |
835 | return true; | |
836 | } | |
837 | Piece const& pc = m_pieces[op.piece_index]; | |
838 | if (pc.left_index == piece.index || pc.right_index == piece.index) | |
839 | { | |
840 | if (pc.type == strategy::buffer::buffered_flat_end) | |
841 | { | |
842 | // If it is a flat end, don't compare against its neighbor: | |
843 | // it will always be located on one of the helper segments | |
844 | return true; | |
845 | } | |
846 | if (pc.type == strategy::buffer::buffered_concave) | |
847 | { | |
848 | // If it is concave, the same applies: the IP will be | |
849 | // located on one of the helper segments | |
850 | return true; | |
851 | } | |
852 | } | |
853 | ||
854 | return false; | |
855 | } | |
856 | ||
857 | ||
858 | public: | |
859 | ||
860 | inline turn_in_piece_visitor(Turns& turns, Pieces const& pieces, | |
861 | DistanceStrategy const& distance_strategy, | |
862 | PointInGeometryStrategy const& strategy, | |
863 | SideStrategy const& side_strategy) | |
864 | : m_turns(turns) | |
865 | , m_pieces(pieces) | |
866 | , m_distance_strategy(distance_strategy) | |
867 | , m_point_in_geometry_strategy(strategy) | |
868 | , m_side_strategy(side_strategy) | |
869 | {} | |
870 | ||
871 | template <typename Turn, typename Piece> | |
872 | inline bool apply(Turn const& turn, Piece const& piece, bool first = true) | |
873 | { | |
874 | boost::ignore_unused(first); | |
875 | ||
876 | if (turn.count_within > 0) | |
877 | { | |
878 | // Already inside - no need to check again | |
879 | return true; | |
880 | } | |
881 | ||
882 | if (piece.type == strategy::buffer::buffered_flat_end | |
883 | || piece.type == strategy::buffer::buffered_concave) | |
884 | { | |
885 | // Turns cannot be located within flat-end or concave pieces | |
886 | return true; | |
887 | } | |
888 | ||
889 | if (! geometry::covered_by(turn.robust_point, piece.robust_envelope)) | |
890 | { | |
891 | // Easy check: if the turn is not in the envelope, we can safely return | |
892 | return true; | |
893 | } | |
894 | ||
895 | if (skip(turn.operations[0], piece) || skip(turn.operations[1], piece)) | |
896 | { | |
897 | return true; | |
898 | } | |
899 | ||
900 | // TODO: mutable_piece to make some on-demand preparations in analyse | |
901 | Turn& mutable_turn = m_turns[turn.turn_index]; | |
902 | ||
903 | if (piece.type == geometry::strategy::buffer::buffered_point) | |
904 | { | |
905 | // Optimization for buffer around points: if distance from center | |
906 | // is not between min/max radius, the result is clear | |
907 | typedef typename default_comparable_distance_result | |
908 | < | |
909 | typename Turn::robust_point_type | |
910 | >::type distance_type; | |
911 | ||
912 | distance_type const cd | |
913 | = geometry::comparable_distance(piece.robust_center, | |
914 | turn.robust_point); | |
915 | ||
916 | if (cd < piece.robust_min_comparable_radius) | |
917 | { | |
918 | mutable_turn.count_within++; | |
919 | return true; | |
920 | } | |
921 | if (cd > piece.robust_max_comparable_radius) | |
922 | { | |
923 | return true; | |
924 | } | |
925 | } | |
926 | ||
927 | static const bool use_soi = use_side_of_intersection<CsTag>::value; | |
928 | boost::ignore_unused(use_soi); | |
929 | ||
930 | analyse_result const analyse_code = | |
931 | piece.type == geometry::strategy::buffer::buffered_point | |
932 | ? analyse_turn_wrt_point_piece<use_soi>::apply(turn, piece, m_point_in_geometry_strategy, m_side_strategy) | |
933 | : analyse_turn_wrt_piece<use_soi>::apply(turn, piece, m_distance_strategy, m_side_strategy); | |
934 | ||
935 | switch(analyse_code) | |
936 | { | |
937 | case analyse_disjoint : | |
938 | return true; | |
939 | case analyse_on_offsetted : | |
940 | mutable_turn.count_on_offsetted++; // value is not used anymore | |
941 | return true; | |
942 | case analyse_on_original_boundary : | |
943 | mutable_turn.count_on_original_boundary++; | |
944 | return true; | |
945 | case analyse_within : | |
946 | mutable_turn.count_within++; | |
947 | return true; | |
948 | case analyse_near_offsetted : | |
949 | mutable_turn.count_within_near_offsetted++; | |
950 | return true; | |
951 | default : | |
952 | break; | |
953 | } | |
954 | ||
955 | int const geometry_code = turn_in_piece<use_soi>::apply(turn, piece, | |
956 | m_point_in_geometry_strategy); | |
957 | ||
958 | if (geometry_code == 1) | |
959 | { | |
960 | mutable_turn.count_within++; | |
961 | } | |
962 | ||
963 | return true; | |
964 | } | |
965 | }; | |
966 | ||
967 | ||
968 | }} // namespace detail::buffer | |
969 | #endif // DOXYGEN_NO_DETAIL | |
970 | ||
971 | ||
972 | }} // namespace boost::geometry | |
973 | ||
974 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_PIECE_VISITOR |