1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2007-2011 Barend Gehrels, Amsterdam, the Netherlands.
4
5 // Use, modification and distribution is subject to the Boost Software License,
6 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8
9 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
11
12
13 #include <cstddef>
14 #include <map>
15
16 #include <boost/array.hpp>
17 #include <boost/mpl/if.hpp>
18 #include <boost/range.hpp>
19 #include <boost/typeof/typeof.hpp>
20
21 #include <boost/tuple/tuple.hpp>
22
23 #include <boost/geometry/core/access.hpp>
24 #include <boost/geometry/core/coordinate_dimension.hpp>
25 #include <boost/geometry/core/reverse_dispatch.hpp>
26
27 #include <boost/geometry/core/exterior_ring.hpp>
28 #include <boost/geometry/core/interior_rings.hpp>
29 #include <boost/geometry/core/ring_type.hpp>
30
31 #include <boost/geometry/geometries/concepts/check.hpp>
32
33 #include <boost/geometry/util/math.hpp>
34 #include <boost/geometry/views/closeable_view.hpp>
35 #include <boost/geometry/views/reversible_view.hpp>
36 #include <boost/geometry/views/detail/range_type.hpp>
37
38 #include <boost/geometry/geometries/box.hpp>
39 #include <boost/geometry/geometries/segment.hpp>
40
41 #include <boost/geometry/iterators/ever_circling_iterator.hpp>
42
43 #include <boost/geometry/strategies/cartesian/cart_intersect.hpp>
44 #include <boost/geometry/strategies/intersection.hpp>
45 #include <boost/geometry/strategies/intersection_result.hpp>
46
47 #include <boost/geometry/algorithms/detail/disjoint.hpp>
48 #include <boost/geometry/algorithms/detail/partition.hpp>
49 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
50
51 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
52
53
54 #include <boost/geometry/algorithms/detail/sections/range_by_section.hpp>
55
56 #include <boost/geometry/algorithms/expand.hpp>
57 #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
58
59 #ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
60 # include <sstream>
61 # include <boost/geometry/util/write_dsv.hpp>
62 #endif
63
64
65 namespace boost { namespace geometry
66 {
67
68
69 #ifndef DOXYGEN_NO_DETAIL
70 namespace detail { namespace get_turns
71 {
72
73
74 struct no_interrupt_policy
75 {
76 static bool const enabled = false;
77
78 template <typename Range>
applyboost::geometry::detail::get_turns::no_interrupt_policy79 static inline bool apply(Range const&)
80 {
81 return false;
82 }
83 };
84
85
86 template
87 <
88 typename Geometry1, typename Geometry2,
89 bool Reverse1, bool Reverse2,
90 typename Section1, typename Section2,
91 typename Turns,
92 typename TurnPolicy,
93 typename InterruptPolicy
94 >
95 class get_turns_in_sections
96 {
97 typedef typename closeable_view
98 <
99 typename range_type<Geometry1>::type const,
100 closure<Geometry1>::value
101 >::type cview_type1;
102 typedef typename closeable_view
103 <
104 typename range_type<Geometry2>::type const,
105 closure<Geometry2>::value
106 >::type cview_type2;
107
108 typedef typename reversible_view
109 <
110 cview_type1 const,
111 Reverse1 ? iterate_reverse : iterate_forward
112 >::type view_type1;
113 typedef typename reversible_view
114 <
115 cview_type2 const,
116 Reverse2 ? iterate_reverse : iterate_forward
117 >::type view_type2;
118
119 typedef typename boost::range_iterator
120 <
121 view_type1 const
122 >::type range1_iterator;
123
124 typedef typename boost::range_iterator
125 <
126 view_type2 const
127 >::type range2_iterator;
128
129
130
131 public :
132 // Returns true if terminated, false if interrupted
apply(int source_id1,Geometry1 const & geometry1,Section1 const & sec1,int source_id2,Geometry2 const & geometry2,Section2 const & sec2,Turns & turns,InterruptPolicy & interrupt_policy)133 static inline bool apply(
134 int source_id1, Geometry1 const& geometry1, Section1 const& sec1,
135 int source_id2, Geometry2 const& geometry2, Section2 const& sec2,
136 Turns& turns,
137 InterruptPolicy& interrupt_policy)
138 {
139 cview_type1 cview1(range_by_section(geometry1, sec1));
140 cview_type2 cview2(range_by_section(geometry2, sec2));
141 view_type1 view1(cview1);
142 view_type2 view2(cview2);
143
144 range1_iterator begin_range_1 = boost::begin(view1);
145 range1_iterator end_range_1 = boost::end(view1);
146
147 range2_iterator begin_range_2 = boost::begin(view2);
148 range2_iterator end_range_2 = boost::end(view2);
149
150 int const dir1 = sec1.directions[0];
151 int const dir2 = sec2.directions[0];
152 int index1 = sec1.begin_index;
153 int ndi1 = sec1.non_duplicate_index;
154
155 bool const same_source =
156 source_id1 == source_id2
157 && sec1.ring_id.multi_index == sec2.ring_id.multi_index
158 && sec1.ring_id.ring_index == sec2.ring_id.ring_index;
159
160 range1_iterator prev1, it1, end1;
161
162 get_start_point_iterator(sec1, view1, prev1, it1, end1,
163 index1, ndi1, dir1, sec2.bounding_box);
164
165 // We need a circular iterator because it might run through the closing point.
166 // One circle is actually enough but this one is just convenient.
167 ever_circling_iterator<range1_iterator> next1(begin_range_1, end_range_1, it1, true);
168 next1++;
169
170 // Walk through section and stop if we exceed the other box
171 // section 2: [--------------]
172 // section 1: |----|---|---|---|---|
173 for (prev1 = it1++, next1++;
174 it1 != end1 && ! exceeding<0>(dir1, *prev1, sec2.bounding_box);
175 ++prev1, ++it1, ++index1, ++next1, ++ndi1)
176 {
177 ever_circling_iterator<range1_iterator> nd_next1(
178 begin_range_1, end_range_1, next1, true);
179 advance_to_non_duplicate_next(nd_next1, it1, sec1);
180
181 int index2 = sec2.begin_index;
182 int ndi2 = sec2.non_duplicate_index;
183
184 range2_iterator prev2, it2, end2;
185
186 get_start_point_iterator(sec2, view2, prev2, it2, end2,
187 index2, ndi2, dir2, sec1.bounding_box);
188 ever_circling_iterator<range2_iterator> next2(begin_range_2, end_range_2, it2, true);
189 next2++;
190
191 for (prev2 = it2++, next2++;
192 it2 != end2 && ! exceeding<0>(dir2, *prev2, sec1.bounding_box);
193 ++prev2, ++it2, ++index2, ++next2, ++ndi2)
194 {
195 bool skip = same_source;
196 if (skip)
197 {
198 // If sources are the same (possibly self-intersecting):
199 // skip if it is a neighbouring sement.
200 // (including first-last segment
201 // and two segments with one or more degenerate/duplicate
202 // (zero-length) segments in between)
203
204 // Also skip if index1 < index2 to avoid getting all
205 // intersections twice (only do this on same source!)
206
207 // About n-2:
208 // (square: range_count=5, indices 0,1,2,3
209 // -> 0-3 are adjacent)
210 skip = index2 >= index1
211 || ndi1 == ndi2 + 1
212 || (index2 == 0 && index1 >= int(sec1.range_count) - 2)
213 ;
214 }
215
216 if (! skip)
217 {
218 // Move to the "non duplicate next"
219 ever_circling_iterator<range2_iterator> nd_next2(
220 begin_range_2, end_range_2, next2, true);
221 advance_to_non_duplicate_next(nd_next2, it2, sec2);
222
223 typedef typename boost::range_value<Turns>::type turn_info;
224 typedef typename turn_info::point_type ip;
225
226 turn_info ti;
227 ti.operations[0].seg_id = segment_identifier(source_id1,
228 sec1.ring_id.multi_index, sec1.ring_id.ring_index, index1),
229 ti.operations[1].seg_id = segment_identifier(source_id2,
230 sec2.ring_id.multi_index, sec2.ring_id.ring_index, index2),
231
232 ti.operations[0].other_id = ti.operations[1].seg_id;
233 ti.operations[1].other_id = ti.operations[0].seg_id;
234
235 std::size_t const size_before = boost::size(turns);
236
237 TurnPolicy::apply(*prev1, *it1, *nd_next1, *prev2, *it2, *nd_next2,
238 ti, std::back_inserter(turns));
239
240 if (InterruptPolicy::enabled)
241 {
242 if (interrupt_policy.apply(
243 std::make_pair(boost::begin(turns) + size_before,
244 boost::end(turns))))
245 {
246 return false;
247 }
248 }
249 }
250 }
251 }
252 return true;
253 }
254
255
256 private :
257 typedef typename geometry::point_type<Geometry1>::type point1_type;
258 typedef typename geometry::point_type<Geometry2>::type point2_type;
259 typedef typename model::referring_segment<point1_type const> segment1_type;
260 typedef typename model::referring_segment<point2_type const> segment2_type;
261
262
263 template <size_t Dim, typename Point, typename Box>
preceding(int dir,Point const & point,Box const & box)264 static inline bool preceding(int dir, Point const& point, Box const& box)
265 {
266 return (dir == 1 && get<Dim>(point) < get<min_corner, Dim>(box))
267 || (dir == -1 && get<Dim>(point) > get<max_corner, Dim>(box));
268 }
269
270 template <size_t Dim, typename Point, typename Box>
exceeding(int dir,Point const & point,Box const & box)271 static inline bool exceeding(int dir, Point const& point, Box const& box)
272 {
273 return (dir == 1 && get<Dim>(point) > get<max_corner, Dim>(box))
274 || (dir == -1 && get<Dim>(point) < get<min_corner, Dim>(box));
275 }
276
277 template <typename Iterator, typename RangeIterator, typename Section>
advance_to_non_duplicate_next(Iterator & next,RangeIterator const & it,Section const & section)278 static inline void advance_to_non_duplicate_next(Iterator& next,
279 RangeIterator const& it, Section const& section)
280 {
281 // To see where the next segments bend to, in case of touch/intersections
282 // on end points, we need (in case of degenerate/duplicate points) an extra
283 // iterator which moves to the REAL next point, so non duplicate.
284 // This needs an extra comparison (disjoint).
285 // (Note that within sections, non duplicate points are already asserted,
286 // by the sectionalize process).
287
288 // So advance to the "non duplicate next"
289 // (the check is defensive, to avoid endless loops)
290 std::size_t check = 0;
291 while(! detail::disjoint::disjoint_point_point(*it, *next)
292 && check++ < section.range_count)
293 {
294 next++;
295 }
296 }
297
298 // It is NOT possible to have section-iterators here
299 // because of the logistics of "index" (the section-iterator automatically
300 // skips to the begin-point, we loose the index or have to recalculate it)
301 // So we mimic it here
302 template <typename Range, typename Section, typename Box>
get_start_point_iterator(Section & section,Range const & range,typename boost::range_iterator<Range const>::type & it,typename boost::range_iterator<Range const>::type & prev,typename boost::range_iterator<Range const>::type & end,int & index,int & ndi,int dir,Box const & other_bounding_box)303 static inline void get_start_point_iterator(Section & section,
304 Range const& range,
305 typename boost::range_iterator<Range const>::type& it,
306 typename boost::range_iterator<Range const>::type& prev,
307 typename boost::range_iterator<Range const>::type& end,
308 int& index, int& ndi,
309 int dir, Box const& other_bounding_box)
310 {
311 it = boost::begin(range) + section.begin_index;
312 end = boost::begin(range) + section.end_index + 1;
313
314 // Mimic section-iterator:
315 // Skip to point such that section interects other box
316 prev = it++;
317 for(; it != end && preceding<0>(dir, *it, other_bounding_box);
318 prev = it++, index++, ndi++)
319 {}
320 // Go back one step because we want to start completely preceding
321 it = prev;
322 }
323 };
324
325 struct get_section_box
326 {
327 template <typename Box, typename InputItem>
applyboost::geometry::detail::get_turns::get_section_box328 static inline void apply(Box& total, InputItem const& item)
329 {
330 geometry::expand(total, item.bounding_box);
331 }
332 };
333
334 struct ovelaps_section_box
335 {
336 template <typename Box, typename InputItem>
applyboost::geometry::detail::get_turns::ovelaps_section_box337 static inline bool apply(Box const& box, InputItem const& item)
338 {
339 return ! detail::disjoint::disjoint_box_box(box, item.bounding_box);
340 }
341 };
342
343 template
344 <
345 typename Geometry1, typename Geometry2,
346 bool Reverse1, bool Reverse2,
347 typename Turns,
348 typename TurnPolicy,
349 typename InterruptPolicy
350 >
351 struct section_visitor
352 {
353 int m_source_id1;
354 Geometry1 const& m_geometry1;
355 int m_source_id2;
356 Geometry2 const& m_geometry2;
357 Turns& m_turns;
358 InterruptPolicy& m_interrupt_policy;
359
section_visitorboost::geometry::detail::get_turns::section_visitor360 section_visitor(int id1, Geometry1 const& g1,
361 int id2, Geometry2 const& g2,
362 Turns& turns, InterruptPolicy& ip)
363 : m_source_id1(id1), m_geometry1(g1)
364 , m_source_id2(id2), m_geometry2(g2)
365 , m_turns(turns)
366 , m_interrupt_policy(ip)
367 {}
368
369 template <typename Section>
applyboost::geometry::detail::get_turns::section_visitor370 inline bool apply(Section const& sec1, Section const& sec2)
371 {
372 if (! detail::disjoint::disjoint_box_box(sec1.bounding_box, sec2.bounding_box))
373 {
374 return get_turns_in_sections
375 <
376 Geometry1,
377 Geometry2,
378 Reverse1, Reverse2,
379 Section, Section,
380 Turns,
381 TurnPolicy,
382 InterruptPolicy
383 >::apply(
384 m_source_id1, m_geometry1, sec1,
385 m_source_id2, m_geometry2, sec2,
386 m_turns, m_interrupt_policy);
387 }
388 return true;
389 }
390
391 };
392
393 template
394 <
395 typename Geometry1, typename Geometry2,
396 bool Reverse1, bool Reverse2,
397 typename Turns,
398 typename TurnPolicy,
399 typename InterruptPolicy
400 >
401 class get_turns_generic
402 {
403
404 public:
apply(int source_id1,Geometry1 const & geometry1,int source_id2,Geometry2 const & geometry2,Turns & turns,InterruptPolicy & interrupt_policy)405 static inline void apply(
406 int source_id1, Geometry1 const& geometry1,
407 int source_id2, Geometry2 const& geometry2,
408 Turns& turns, InterruptPolicy& interrupt_policy)
409 {
410 // First create monotonic sections...
411 typedef typename boost::range_value<Turns>::type ip_type;
412 typedef typename ip_type::point_type point_type;
413 typedef model::box<point_type> box_type;
414 typedef typename geometry::sections<box_type, 2> sections_type;
415
416 sections_type sec1, sec2;
417
418 geometry::sectionalize<Reverse1>(geometry1, sec1, 0);
419 geometry::sectionalize<Reverse2>(geometry2, sec2, 1);
420
421 // ... and then partition them, intersecting overlapping sections in visitor method
422 section_visitor
423 <
424 Geometry1, Geometry2,
425 Reverse1, Reverse2,
426 Turns, TurnPolicy, InterruptPolicy
427 > visitor(source_id1, geometry1, source_id2, geometry2, turns, interrupt_policy);
428
429 geometry::partition
430 <
431 box_type, get_section_box, ovelaps_section_box
432 >::apply(sec1, sec2, visitor);
433 }
434 };
435
436
437 // Get turns for a range with a box, following Cohen-Sutherland (cs) approach
438 template
439 <
440 typename Range, typename Box,
441 bool ReverseRange, bool ReverseBox,
442 typename Turns,
443 typename TurnPolicy,
444 typename InterruptPolicy
445 >
446 struct get_turns_cs
447 {
448 typedef typename boost::range_value<Turns>::type turn_info;
449 typedef typename geometry::point_type<Range>::type point_type;
450 typedef typename geometry::point_type<Box>::type box_point_type;
451
452 typedef typename closeable_view
453 <
454 Range const,
455 closure<Range>::value
456 >::type cview_type;
457
458 typedef typename reversible_view
459 <
460 cview_type const,
461 ReverseRange ? iterate_reverse : iterate_forward
462 >::type view_type;
463
464 typedef typename boost::range_iterator
465 <
466 view_type const
467 >::type iterator_type;
468
469
applyboost::geometry::detail::get_turns::get_turns_cs470 static inline void apply(
471 int source_id1, Range const& range,
472 int source_id2, Box const& box,
473 Turns& turns,
474 InterruptPolicy& ,
475 int multi_index = -1, int ring_index = -1)
476 {
477 if (boost::size(range) <= 1)
478 {
479 return;
480 }
481
482 boost::array<box_point_type,4> bp;
483 assign_box_corners_oriented<ReverseBox>(box, bp);
484
485 cview_type cview(range);
486 view_type view(cview);
487
488 iterator_type it = boost::begin(view);
489
490 ever_circling_iterator<iterator_type> next(
491 boost::begin(view), boost::end(view), it, true);
492 next++;
493 next++;
494
495 bool first = true;
496
497 char previous_side[2] = {0, 0};
498
499 int index = 0;
500
501 for (iterator_type prev = it++;
502 it != boost::end(view);
503 prev = it++, next++, index++)
504 {
505 segment_identifier seg_id(source_id1,
506 multi_index, ring_index, index);
507
508 if (first)
509 {
510 previous_side[0] = get_side<0>(box, *prev);
511 previous_side[1] = get_side<1>(box, *prev);
512 }
513
514 char current_side[2];
515 current_side[0] = get_side<0>(box, *it);
516 current_side[1] = get_side<1>(box, *it);
517
518 // There can NOT be intersections if
519 // 1) EITHER the two points are lying on one side of the box (! 0 && the same)
520 // 2) OR same in Y-direction
521 // 3) OR all points are inside the box (0)
522 /*if (! (
523 (current_side[0] != 0 && current_side[0] == previous_side[0])
524 || (current_side[1] != 0 && current_side[1] == previous_side[1])
525 || (current_side[0] == 0
526 && current_side[1] == 0
527 && previous_side[0] == 0
528 && previous_side[1] == 0)
529 )
530 )*/
531 if (true)
532 {
533 get_turns_with_box(seg_id, source_id2,
534 *prev, *it, *next,
535 bp[0], bp[1], bp[2], bp[3],
536 turns);
537 // Future performance enhancement:
538 // return if told by the interrupt policy
539 }
540 }
541 }
542
543 private:
544 template<std::size_t Index, typename Point>
get_sideboost::geometry::detail::get_turns::get_turns_cs545 static inline int get_side(Box const& box, Point const& point)
546 {
547 // Inside -> 0
548 // Outside -> -1 (left/below) or 1 (right/above)
549 // On border -> -2 (left/lower) or 2 (right/upper)
550 // The only purpose of the value is to not be the same,
551 // and to denote if it is inside (0)
552
553 typename coordinate_type<Point>::type const& c = get<Index>(point);
554 typename coordinate_type<Box>::type const& left = get<min_corner, Index>(box);
555 typename coordinate_type<Box>::type const& right = get<max_corner, Index>(box);
556
557 if (geometry::math::equals(c, left)) return -2;
558 else if (geometry::math::equals(c, right)) return 2;
559 else if (c < left) return -1;
560 else if (c > right) return 1;
561 else return 0;
562 }
563
get_turns_with_boxboost::geometry::detail::get_turns::get_turns_cs564 static inline void get_turns_with_box(segment_identifier const& seg_id, int source_id2,
565 // Points from a range:
566 point_type const& rp0,
567 point_type const& rp1,
568 point_type const& rp2,
569 // Points from the box
570 box_point_type const& bp0,
571 box_point_type const& bp1,
572 box_point_type const& bp2,
573 box_point_type const& bp3,
574 // Output
575 Turns& turns)
576 {
577 // Depending on code some relations can be left out
578
579 typedef typename boost::range_value<Turns>::type turn_info;
580
581 turn_info ti;
582 ti.operations[0].seg_id = seg_id;
583 ti.operations[0].other_id = ti.operations[1].seg_id;
584 ti.operations[1].other_id = seg_id;
585
586 ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 0);
587 TurnPolicy::apply(rp0, rp1, rp2, bp0, bp1, bp2,
588 ti, std::back_inserter(turns));
589
590 ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 1);
591 TurnPolicy::apply(rp0, rp1, rp2, bp1, bp2, bp3,
592 ti, std::back_inserter(turns));
593
594 ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 2);
595 TurnPolicy::apply(rp0, rp1, rp2, bp2, bp3, bp0,
596 ti, std::back_inserter(turns));
597
598 ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 3);
599 TurnPolicy::apply(rp0, rp1, rp2, bp3, bp0, bp1,
600 ti, std::back_inserter(turns));
601 }
602
603 };
604
605
606 template
607 <
608 typename Polygon, typename Box,
609 bool Reverse, bool ReverseBox,
610 typename Turns,
611 typename TurnPolicy,
612 typename InterruptPolicy
613 >
614 struct get_turns_polygon_cs
615 {
applyboost::geometry::detail::get_turns::get_turns_polygon_cs616 static inline void apply(
617 int source_id1, Polygon const& polygon,
618 int source_id2, Box const& box,
619 Turns& turns, InterruptPolicy& interrupt_policy,
620 int multi_index = -1)
621 {
622 typedef typename geometry::ring_type<Polygon>::type ring_type;
623
624 typedef detail::get_turns::get_turns_cs
625 <
626 ring_type, Box,
627 Reverse, ReverseBox,
628 Turns,
629 TurnPolicy,
630 InterruptPolicy
631 > intersector_type;
632
633 intersector_type::apply(
634 source_id1, geometry::exterior_ring(polygon),
635 source_id2, box, turns, interrupt_policy,
636 multi_index, -1);
637
638 int i = 0;
639
640 typename interior_return_type<Polygon const>::type rings
641 = interior_rings(polygon);
642 for (BOOST_AUTO_TPL(it, boost::begin(rings)); it != boost::end(rings);
643 ++it, ++i)
644 {
645 intersector_type::apply(
646 source_id1, *it,
647 source_id2, box, turns, interrupt_policy,
648 multi_index, i);
649 }
650
651 }
652 };
653
654 }} // namespace detail::get_turns
655 #endif // DOXYGEN_NO_DETAIL
656
657
658 #ifndef DOXYGEN_NO_DISPATCH
659 namespace dispatch
660 {
661
662 // Because this is "detail" method, and most implementations will use "generic",
663 // we take the freedom to derive it from "generic".
664 template
665 <
666 typename GeometryTag1, typename GeometryTag2,
667 typename Geometry1, typename Geometry2,
668 bool Reverse1, bool Reverse2,
669 typename Turns,
670 typename TurnPolicy,
671 typename InterruptPolicy
672 >
673 struct get_turns
674 : detail::get_turns::get_turns_generic
675 <
676 Geometry1, Geometry2,
677 Reverse1, Reverse2,
678 Turns,
679 TurnPolicy,
680 InterruptPolicy
681 >
682 {};
683
684
685 template
686 <
687 typename Polygon, typename Box,
688 bool ReversePolygon, bool ReverseBox,
689 typename Turns,
690 typename TurnPolicy,
691 typename InterruptPolicy
692 >
693 struct get_turns
694 <
695 polygon_tag, box_tag,
696 Polygon, Box,
697 ReversePolygon, ReverseBox,
698 Turns,
699 TurnPolicy,
700 InterruptPolicy
701 > : detail::get_turns::get_turns_polygon_cs
702 <
703 Polygon, Box,
704 ReversePolygon, ReverseBox,
705 Turns, TurnPolicy, InterruptPolicy
706 >
707 {};
708
709
710 template
711 <
712 typename Ring, typename Box,
713 bool ReverseRing, bool ReverseBox,
714 typename Turns,
715 typename TurnPolicy,
716 typename InterruptPolicy
717 >
718 struct get_turns
719 <
720 ring_tag, box_tag,
721 Ring, Box,
722 ReverseRing, ReverseBox,
723 Turns,
724 TurnPolicy,
725 InterruptPolicy
726 > : detail::get_turns::get_turns_cs
727 <
728 Ring, Box, ReverseRing, ReverseBox,
729 Turns, TurnPolicy, InterruptPolicy
730 >
731
732 {};
733
734
735 template
736 <
737 typename GeometryTag1, typename GeometryTag2,
738 typename Geometry1, typename Geometry2,
739 bool Reverse1, bool Reverse2,
740 typename Turns,
741 typename TurnPolicy,
742 typename InterruptPolicy
743 >
744 struct get_turns_reversed
745 {
applyboost::geometry::dispatch::get_turns_reversed746 static inline void apply(
747 int source_id1, Geometry1 const& g1,
748 int source_id2, Geometry2 const& g2,
749 Turns& turns, InterruptPolicy& interrupt_policy)
750 {
751 get_turns
752 <
753 GeometryTag2, GeometryTag1,
754 Geometry2, Geometry1,
755 Reverse2, Reverse1,
756 Turns, TurnPolicy,
757 InterruptPolicy
758 >::apply(source_id2, g2, source_id1, g1, turns, interrupt_policy);
759 }
760 };
761
762
763 } // namespace dispatch
764 #endif // DOXYGEN_NO_DISPATCH
765
766
767
768 /*!
769 \brief \brief_calc2{turn points}
770 \ingroup overlay
771 \tparam Geometry1 \tparam_geometry
772 \tparam Geometry2 \tparam_geometry
773 \tparam Turns type of turn-container (e.g. vector of "intersection/turn point"'s)
774 \param geometry1 \param_geometry
775 \param geometry2 \param_geometry
776 \param turns container which will contain turn points
777 \param interrupt_policy policy determining if process is stopped
778 when intersection is found
779 */
780 template
781 <
782 bool Reverse1, bool Reverse2,
783 typename AssignPolicy,
784 typename Geometry1,
785 typename Geometry2,
786 typename Turns,
787 typename InterruptPolicy
788 >
get_turns(Geometry1 const & geometry1,Geometry2 const & geometry2,Turns & turns,InterruptPolicy & interrupt_policy)789 inline void get_turns(Geometry1 const& geometry1,
790 Geometry2 const& geometry2,
791 Turns& turns,
792 InterruptPolicy& interrupt_policy)
793 {
794 concept::check_concepts_and_equal_dimensions<Geometry1 const, Geometry2 const>();
795
796 typedef typename strategy_intersection
797 <
798 typename cs_tag<Geometry1>::type,
799 Geometry1,
800 Geometry2,
801 typename boost::range_value<Turns>::type
802 >::segment_intersection_strategy_type segment_intersection_strategy_type;
803
804 typedef detail::overlay::get_turn_info
805 <
806 typename point_type<Geometry1>::type,
807 typename point_type<Geometry2>::type,
808 typename boost::range_value<Turns>::type,
809 AssignPolicy
810 > TurnPolicy;
811
812 boost::mpl::if_c
813 <
814 reverse_dispatch<Geometry1, Geometry2>::type::value,
815 dispatch::get_turns_reversed
816 <
817 typename tag<Geometry1>::type,
818 typename tag<Geometry2>::type,
819 Geometry1, Geometry2,
820 Reverse1, Reverse2,
821 Turns, TurnPolicy,
822 InterruptPolicy
823 >,
824 dispatch::get_turns
825 <
826 typename tag<Geometry1>::type,
827 typename tag<Geometry2>::type,
828 Geometry1, Geometry2,
829 Reverse1, Reverse2,
830 Turns, TurnPolicy,
831 InterruptPolicy
832 >
833 >::type::apply(
834 0, geometry1,
835 1, geometry2,
836 turns, interrupt_policy);
837 }
838
839
840 }} // namespace boost::geometry
841
842 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
843