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