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