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