1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2014-2017 Adam Wulkiewicz, Lodz, Poland.
5
6 // This file was modified by Oracle on 2014-2021.
7 // Modifications copyright (c) 2014-2021 Oracle and/or its affiliates.
8
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
10
11 // Use, modification and distribution is subject to the Boost Software License,
12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
13 // http://www.boost.org/LICENSE_1_0.txt)
14
15 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
17
18
19 #include <cstddef>
20 #include <map>
21
22 #include <boost/array.hpp>
23 #include <boost/concept_check.hpp>
24 #include <boost/core/ignore_unused.hpp>
25 #include <boost/range/begin.hpp>
26 #include <boost/range/end.hpp>
27 #include <boost/range/size.hpp>
28 #include <boost/range/value_type.hpp>
29
30 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
31 #include <boost/geometry/algorithms/detail/disjoint/point_point.hpp>
32 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
33 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
34 #include <boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp>
35 #include <boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp>
36 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
37 #include <boost/geometry/algorithms/detail/partition.hpp>
38 #include <boost/geometry/algorithms/detail/recalculate.hpp>
39 #include <boost/geometry/algorithms/detail/sections/range_by_section.hpp>
40 #include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp>
41 #include <boost/geometry/algorithms/detail/sections/section_functions.hpp>
42 #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp>
43
44 #include <boost/geometry/core/access.hpp>
45 #include <boost/geometry/core/assert.hpp>
46 #include <boost/geometry/core/coordinate_dimension.hpp>
47 #include <boost/geometry/core/exterior_ring.hpp>
48 #include <boost/geometry/core/interior_rings.hpp>
49 #include <boost/geometry/core/reverse_dispatch.hpp>
50 #include <boost/geometry/core/ring_type.hpp>
51 #include <boost/geometry/core/tags.hpp>
52
53 #include <boost/geometry/geometries/box.hpp>
54 #include <boost/geometry/geometries/concepts/check.hpp>
55 #include <boost/geometry/geometries/segment.hpp>
56
57 #include <boost/geometry/iterators/ever_circling_iterator.hpp>
58
59 #include <boost/geometry/strategies/intersection_strategies.hpp>
60 #include <boost/geometry/strategies/intersection_result.hpp>
61
62 #include <boost/geometry/util/math.hpp>
63 #include <boost/geometry/util/type_traits.hpp>
64
65 #include <boost/geometry/views/detail/closed_clockwise_view.hpp>
66
67
68 #ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION
69 # include <sstream>
70 # include <boost/geometry/io/dsv/write.hpp>
71 #endif
72
73
74 namespace boost { namespace geometry
75 {
76
77 // Silence warning C4127: conditional expression is constant
78 #if defined(_MSC_VER)
79 #pragma warning(push)
80 #pragma warning(disable : 4127)
81 #endif
82
83
84 #ifndef DOXYGEN_NO_DETAIL
85 namespace detail { namespace get_turns
86 {
87
88
89 struct no_interrupt_policy
90 {
91 static bool const enabled = false;
92
93 // variable required by self_get_turn_points::get_turns
94 static bool const has_intersections = false;
95
96 template <typename Range>
applyboost::geometry::detail::get_turns::no_interrupt_policy97 static inline bool apply(Range const&)
98 {
99 return false;
100 }
101 };
102
103 template
104 <
105 bool IsAreal,
106 typename Section,
107 typename Point,
108 typename CircularIterator,
109 typename Strategy,
110 typename RobustPolicy
111 >
112 struct unique_sub_range_from_section
113 {
114 typedef Point point_type;
115
unique_sub_range_from_sectionboost::geometry::detail::get_turns::unique_sub_range_from_section116 unique_sub_range_from_section(Section const& section, signed_size_type index,
117 CircularIterator circular_iterator,
118 Point const& previous, Point const& current,
119 Strategy const& strategy,
120 RobustPolicy const& robust_policy)
121 : m_section(section)
122 , m_index(index)
123 , m_previous_point(previous)
124 , m_current_point(current)
125 , m_circular_iterator(circular_iterator)
126 , m_point_retrieved(false)
127 , m_strategy(strategy)
128 , m_robust_policy(robust_policy)
129 {}
130
is_first_segmentboost::geometry::detail::get_turns::unique_sub_range_from_section131 inline bool is_first_segment() const
132 {
133 return !IsAreal && m_section.is_non_duplicate_first && m_index == m_section.begin_index;
134 }
is_last_segmentboost::geometry::detail::get_turns::unique_sub_range_from_section135 inline bool is_last_segment() const
136 {
137 return size() == 2u;
138 }
139
sizeboost::geometry::detail::get_turns::unique_sub_range_from_section140 inline std::size_t size() const
141 {
142 return IsAreal ? 3
143 : m_section.is_non_duplicate_last && m_index + 1 >= m_section.end_index ? 2 : 3;
144 }
145
atboost::geometry::detail::get_turns::unique_sub_range_from_section146 inline Point const& at(std::size_t index) const
147 {
148 BOOST_GEOMETRY_ASSERT(index < size());
149 switch (index)
150 {
151 case 0 : return m_previous_point;
152 case 1 : return m_current_point;
153 case 2 : return get_next_point();
154 default : return m_previous_point;
155 }
156 }
157
158 private :
get_next_pointboost::geometry::detail::get_turns::unique_sub_range_from_section159 inline Point const& get_next_point() const
160 {
161 if (! m_point_retrieved)
162 {
163 advance_to_non_duplicate_next(m_current_point, m_circular_iterator);
164 m_point = *m_circular_iterator;
165 m_point_retrieved = true;
166 }
167 return m_point;
168 }
169
advance_to_non_duplicate_nextboost::geometry::detail::get_turns::unique_sub_range_from_section170 inline void advance_to_non_duplicate_next(Point const& current, CircularIterator& circular_iterator) const
171 {
172 typedef typename robust_point_type<Point, RobustPolicy>::type robust_point_type;
173 robust_point_type current_robust_point;
174 robust_point_type next_robust_point;
175 geometry::recalculate(current_robust_point, current, m_robust_policy);
176 geometry::recalculate(next_robust_point, *circular_iterator, m_robust_policy);
177
178 // To see where the next segments bend to, in case of touch/intersections
179 // on end points, we need (in case of degenerate/duplicate points) an extra
180 // iterator which moves to the REAL next point, so non duplicate.
181 // This needs an extra comparison (disjoint).
182 // (Note that within sections, non duplicate points are already asserted,
183 // by the sectionalize process).
184
185 // So advance to the "non duplicate next"
186 // (the check is defensive, to avoid endless loops)
187 std::size_t check = 0;
188 while (! detail::disjoint::disjoint_point_point(
189 current_robust_point, next_robust_point, m_strategy)
190 && check++ < m_section.range_count)
191 {
192 circular_iterator++;
193 geometry::recalculate(next_robust_point, *circular_iterator, m_robust_policy);
194 }
195 }
196
197 Section const& m_section;
198 signed_size_type m_index;
199 Point const& m_previous_point;
200 Point const& m_current_point;
201 mutable CircularIterator m_circular_iterator;
202 mutable Point m_point;
203 mutable bool m_point_retrieved;
204 Strategy m_strategy;
205 RobustPolicy m_robust_policy;
206 };
207
208 template
209 <
210 typename Geometry1, typename Geometry2,
211 bool Reverse1, bool Reverse2,
212 typename Section1, typename Section2,
213 typename TurnPolicy
214 >
215 class get_turns_in_sections
216 {
217 using range1_view = detail::closed_clockwise_view
218 <
219 typename ring_type<Geometry1>::type const,
220 geometry::closure<Geometry1>::value,
221 Reverse1 ? counterclockwise : clockwise
222 >;
223 using range2_view = detail::closed_clockwise_view
224 <
225 typename ring_type<Geometry2>::type const,
226 geometry::closure<Geometry2>::value,
227 Reverse2 ? counterclockwise : clockwise
228 >;
229
230 using range1_iterator = typename boost::range_iterator<range1_view const>::type;
231 using range2_iterator = typename boost::range_iterator<range2_view const>::type;
232
233 using circular1_iterator = ever_circling_iterator<range1_iterator>;
234 using circular2_iterator = ever_circling_iterator<range2_iterator>;
235
236 template <typename Geometry, typename Section>
adjacent(Section const & section,signed_size_type index1,signed_size_type index2)237 static inline bool adjacent(Section const& section,
238 signed_size_type index1, signed_size_type index2)
239 {
240 // About n-2:
241 // (square: range_count=5, indices 0,1,2,3
242 // -> 0-3 are adjacent, don't check on intersections)
243 // Also tested for open polygons, and/or duplicates
244 // About first condition: will be optimized by compiler (static)
245 // It checks if it is areal (box, ring, (multi)polygon)
246 signed_size_type const n = static_cast<signed_size_type>(section.range_count);
247
248 boost::ignore_unused(n, index1, index2);
249
250 return util::is_areal<Geometry>::value
251 && index1 == 0
252 && index2 >= n - 2
253 ;
254 }
255
256
257 public :
258 // Returns true if terminated, false if interrupted
259 template <typename Strategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
apply(int source_id1,Geometry1 const & geometry1,Section1 const & sec1,int source_id2,Geometry2 const & geometry2,Section2 const & sec2,bool skip_larger,bool skip_adjacent,Strategy const & strategy,RobustPolicy const & robust_policy,Turns & turns,InterruptPolicy & interrupt_policy)260 static inline bool apply(
261 int source_id1, Geometry1 const& geometry1, Section1 const& sec1,
262 int source_id2, Geometry2 const& geometry2, Section2 const& sec2,
263 bool skip_larger, bool skip_adjacent,
264 Strategy const& strategy,
265 RobustPolicy const& robust_policy,
266 Turns& turns,
267 InterruptPolicy& interrupt_policy)
268 {
269 boost::ignore_unused(interrupt_policy);
270
271 static bool const areal1 = util::is_areal<Geometry1>::value;
272 static bool const areal2 = util::is_areal<Geometry2>::value;
273
274 if ((sec1.duplicate && (sec1.count + 1) < sec1.range_count)
275 || (sec2.duplicate && (sec2.count + 1) < sec2.range_count))
276 {
277 // Skip sections containig only duplicates.
278 // They are still important (can indicate non-disjointness)
279 // but they will be found processing adjacent sections.
280 // Do NOT skip if they are the ONLY section
281 return true;
282 }
283
284 range1_view const view1(range_by_section(geometry1, sec1));
285 range2_view const view2(range_by_section(geometry2, sec2));
286
287 range1_iterator begin_range_1 = boost::begin(view1);
288 range1_iterator end_range_1 = boost::end(view1);
289
290 range2_iterator begin_range_2 = boost::begin(view2);
291 range2_iterator end_range_2 = boost::end(view2);
292
293 int const dir1 = sec1.directions[0];
294 int const dir2 = sec2.directions[0];
295 signed_size_type index1 = sec1.begin_index;
296 signed_size_type ndi1 = sec1.non_duplicate_index;
297
298 range1_iterator prev1, it1, end1;
299
300 get_start_point_iterator(sec1, view1, prev1, it1, end1,
301 index1, ndi1, dir1, sec2.bounding_box, robust_policy);
302
303 // We need a circular iterator because it might run through the closing point.
304 // One circle is actually enough but this one is just convenient.
305 circular1_iterator next1(begin_range_1, end_range_1, it1, true);
306 next1++;
307
308 // Walk through section and stop if we exceed the other box
309 // section 2: [--------------]
310 // section 1: |----|---|---|---|---|
311 for (prev1 = it1++, next1++;
312 it1 != end1 && ! detail::section::exceeding<0>(dir1, *prev1, sec1.bounding_box, sec2.bounding_box, robust_policy);
313 ++prev1, ++it1, ++index1, ++next1, ++ndi1)
314 {
315 unique_sub_range_from_section
316 <
317 areal1, Section1, point1_type, circular1_iterator,
318 Strategy, RobustPolicy
319 > unique_sub_range1(sec1, index1,
320 circular1_iterator(begin_range_1, end_range_1, next1, true),
321 *prev1, *it1,
322 strategy, robust_policy);
323
324 signed_size_type index2 = sec2.begin_index;
325 signed_size_type ndi2 = sec2.non_duplicate_index;
326
327 range2_iterator prev2, it2, end2;
328
329 get_start_point_iterator(sec2, view2, prev2, it2, end2,
330 index2, ndi2, dir2, sec1.bounding_box, robust_policy);
331 circular2_iterator next2(begin_range_2, end_range_2, it2, true);
332 next2++;
333
334 for (prev2 = it2++, next2++;
335 it2 != end2 && ! detail::section::exceeding<0>(dir2, *prev2, sec2.bounding_box, sec1.bounding_box, robust_policy);
336 ++prev2, ++it2, ++index2, ++next2, ++ndi2)
337 {
338 bool skip = false;
339
340 if (source_id1 == source_id2
341 && sec1.ring_id.multi_index == sec2.ring_id.multi_index
342 && sec1.ring_id.ring_index == sec2.ring_id.ring_index)
343 {
344 // Sources and rings are the same
345
346 if (skip_larger && index1 >= index2)
347 {
348 // Skip to avoid getting all intersections twice
349 skip = true;
350 }
351 else if (skip_adjacent)
352 {
353 // In some cases (dissolve, has_self_intersections)
354 // neighbouring segments should be checked
355 // (for example to detect spikes properly)
356
357 // skip if it is a neighbouring segment.
358 // (including, for areas, first-last segment
359 // and two segments with one or more degenerate/duplicate
360 // (zero-length) segments in between)
361 skip = ndi2 == ndi1 + 1
362 || adjacent<Geometry1>(sec1, index1, index2);
363 }
364 }
365
366 if (! skip)
367 {
368 unique_sub_range_from_section
369 <
370 areal2, Section2, point2_type, circular2_iterator,
371 Strategy, RobustPolicy
372 > unique_sub_range2(sec2, index2,
373 circular2_iterator(begin_range_2, end_range_2, next2),
374 *prev2, *it2,
375 strategy, robust_policy);
376
377 typedef typename boost::range_value<Turns>::type turn_info;
378
379 turn_info ti;
380 ti.operations[0].seg_id
381 = segment_identifier(source_id1, sec1.ring_id.multi_index,
382 sec1.ring_id.ring_index, index1);
383 ti.operations[1].seg_id
384 = segment_identifier(source_id2, sec2.ring_id.multi_index,
385 sec2.ring_id.ring_index, index2);
386
387 std::size_t const size_before = boost::size(turns);
388
389 TurnPolicy::apply(unique_sub_range1, unique_sub_range2,
390 ti, strategy, robust_policy,
391 std::back_inserter(turns));
392
393 if (InterruptPolicy::enabled)
394 {
395 if (interrupt_policy.apply(
396 std::make_pair(range::pos(turns, size_before),
397 boost::end(turns))))
398 {
399 return false;
400 }
401 }
402 }
403 }
404 }
405 return true;
406 }
407
408
409 private :
410 typedef typename geometry::point_type<Geometry1>::type point1_type;
411 typedef typename geometry::point_type<Geometry2>::type point2_type;
412
413 // It is NOT possible to have section-iterators here
414 // because of the logistics of "index" (the section-iterator automatically
415 // skips to the begin-point, we loose the index or have to recalculate it)
416 // So we mimic it here
417 template <typename Range, typename Section, typename Box, typename RobustPolicy>
get_start_point_iterator(Section const & 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,signed_size_type & index,signed_size_type & ndi,int dir,Box const & other_bounding_box,RobustPolicy const & robust_policy)418 static inline void get_start_point_iterator(Section const& section,
419 Range const& range,
420 typename boost::range_iterator<Range const>::type& it,
421 typename boost::range_iterator<Range const>::type& prev,
422 typename boost::range_iterator<Range const>::type& end,
423 signed_size_type& index, signed_size_type& ndi,
424 int dir, Box const& other_bounding_box, RobustPolicy const& robust_policy)
425 {
426 it = boost::begin(range) + section.begin_index;
427 end = boost::begin(range) + section.end_index + 1;
428
429 // Mimic section-iterator:
430 // Skip to point such that section interects other box
431 prev = it++;
432 for(; it != end && detail::section::preceding<0>(dir, *it, section.bounding_box, other_bounding_box, robust_policy);
433 prev = it++, index++, ndi++)
434 {}
435 // Go back one step because we want to start completely preceding
436 it = prev;
437 }
438 };
439
440 template
441 <
442 typename Geometry1, typename Geometry2,
443 bool Reverse1, bool Reverse2,
444 typename TurnPolicy,
445 typename Strategy,
446 typename RobustPolicy,
447 typename Turns,
448 typename InterruptPolicy
449 >
450 struct section_visitor
451 {
452 int m_source_id1;
453 Geometry1 const& m_geometry1;
454 int m_source_id2;
455 Geometry2 const& m_geometry2;
456 Strategy const& m_strategy;
457 RobustPolicy const& m_rescale_policy;
458 Turns& m_turns;
459 InterruptPolicy& m_interrupt_policy;
460
section_visitorboost::geometry::detail::get_turns::section_visitor461 section_visitor(int id1, Geometry1 const& g1,
462 int id2, Geometry2 const& g2,
463 Strategy const& strategy,
464 RobustPolicy const& robust_policy,
465 Turns& turns,
466 InterruptPolicy& ip)
467 : m_source_id1(id1), m_geometry1(g1)
468 , m_source_id2(id2), m_geometry2(g2)
469 , m_strategy(strategy)
470 , m_rescale_policy(robust_policy)
471 , m_turns(turns)
472 , m_interrupt_policy(ip)
473 {}
474
475 template <typename Section>
applyboost::geometry::detail::get_turns::section_visitor476 inline bool apply(Section const& sec1, Section const& sec2)
477 {
478 if (! detail::disjoint::disjoint_box_box(sec1.bounding_box,
479 sec2.bounding_box,
480 m_strategy) )
481 {
482 // false if interrupted
483 return get_turns_in_sections
484 <
485 Geometry1,
486 Geometry2,
487 Reverse1, Reverse2,
488 Section, Section,
489 TurnPolicy
490 >::apply(m_source_id1, m_geometry1, sec1,
491 m_source_id2, m_geometry2, sec2,
492 false, false,
493 m_strategy,
494 m_rescale_policy,
495 m_turns, m_interrupt_policy);
496 }
497 return true;
498 }
499
500 };
501
502 template
503 <
504 typename Geometry1, typename Geometry2,
505 bool Reverse1, bool Reverse2,
506 typename TurnPolicy
507 >
508 class get_turns_generic
509 {
510
511 public:
512 template <typename Strategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
apply(int source_id1,Geometry1 const & geometry1,int source_id2,Geometry2 const & geometry2,Strategy const & strategy,RobustPolicy const & robust_policy,Turns & turns,InterruptPolicy & interrupt_policy)513 static inline void apply(
514 int source_id1, Geometry1 const& geometry1,
515 int source_id2, Geometry2 const& geometry2,
516 Strategy const& strategy,
517 RobustPolicy const& robust_policy,
518 Turns& turns,
519 InterruptPolicy& interrupt_policy)
520 {
521 // First create monotonic sections...
522 typedef typename boost::range_value<Turns>::type ip_type;
523 typedef typename ip_type::point_type point_type;
524
525 typedef model::box
526 <
527 typename geometry::robust_point_type
528 <
529 point_type, RobustPolicy
530 >::type
531 > box_type;
532 typedef geometry::sections<box_type, 2> sections_type;
533
534 sections_type sec1, sec2;
535 typedef std::integer_sequence<std::size_t, 0, 1> dimensions;
536
537 geometry::sectionalize<Reverse1, dimensions>(geometry1, robust_policy,
538 sec1, strategy, 0);
539 geometry::sectionalize<Reverse2, dimensions>(geometry2, robust_policy,
540 sec2, strategy, 1);
541
542 // ... and then partition them, intersecting overlapping sections in visitor method
543 section_visitor
544 <
545 Geometry1, Geometry2,
546 Reverse1, Reverse2,
547 TurnPolicy,
548 Strategy, RobustPolicy,
549 Turns, InterruptPolicy
550 > visitor(source_id1, geometry1, source_id2, geometry2,
551 strategy, robust_policy, turns, interrupt_policy);
552
553 geometry::partition
554 <
555 box_type
556 >::apply(sec1, sec2, visitor,
557 detail::section::get_section_box<Strategy>(strategy),
558 detail::section::overlaps_section_box<Strategy>(strategy));
559 }
560 };
561
562
563 // Get turns for a range with a box, following Cohen-Sutherland (cs) approach
564 template
565 <
566 typename Range, typename Box,
567 bool ReverseRange, bool ReverseBox,
568 typename TurnPolicy
569 >
570 struct get_turns_cs
571 {
572 typedef typename geometry::point_type<Range>::type range_point_type;
573 typedef typename geometry::point_type<Box>::type box_point_type;
574 typedef boost::array<box_point_type, 4> box_array;
575
576 using view_type = detail::closed_clockwise_view
577 <
578 Range const,
579 geometry::closure<Range>::value,
580 ReverseRange ? counterclockwise : clockwise
581 >;
582
583 using iterator_type = typename boost::range_iterator<view_type const>::type;
584
585 struct unique_sub_range_from_box_policy
586 {
587 typedef box_point_type point_type;
588
unique_sub_range_from_box_policyboost::geometry::detail::get_turns::get_turns_cs::unique_sub_range_from_box_policy589 unique_sub_range_from_box_policy(box_array const& box)
590 : m_box(box)
591 , m_index(0)
592 {}
593
is_first_segmentboost::geometry::detail::get_turns::get_turns_cs::unique_sub_range_from_box_policy594 static inline bool is_first_segment() { return false; }
is_last_segmentboost::geometry::detail::get_turns::get_turns_cs::unique_sub_range_from_box_policy595 static inline bool is_last_segment() { return false; }
sizeboost::geometry::detail::get_turns::get_turns_cs::unique_sub_range_from_box_policy596 static inline std::size_t size() { return 4; }
597
atboost::geometry::detail::get_turns::get_turns_cs::unique_sub_range_from_box_policy598 inline box_point_type const& at(std::size_t index) const
599 {
600 BOOST_GEOMETRY_ASSERT(index < size());
601 return m_box[(m_index + index) % 4];
602 }
603
nextboost::geometry::detail::get_turns::get_turns_cs::unique_sub_range_from_box_policy604 inline void next()
605 {
606 m_index++;
607 }
608
609 private :
610 box_array const& m_box;
611 std::size_t m_index;
612 };
613
614 struct unique_sub_range_from_view_policy
615 {
616 typedef range_point_type point_type;
617
unique_sub_range_from_view_policyboost::geometry::detail::get_turns::get_turns_cs::unique_sub_range_from_view_policy618 unique_sub_range_from_view_policy(view_type const& view, point_type const& pi, point_type const& pj, iterator_type it)
619 : m_view(view)
620 , m_pi(pi)
621 , m_pj(pj)
622 , m_circular_iterator(boost::begin(view), boost::end(view), it, true)
623 {
624 ++m_circular_iterator;
625 }
626
is_first_segmentboost::geometry::detail::get_turns::get_turns_cs::unique_sub_range_from_view_policy627 static inline bool is_first_segment() { return false; }
is_last_segmentboost::geometry::detail::get_turns::get_turns_cs::unique_sub_range_from_view_policy628 static inline bool is_last_segment() { return false; }
sizeboost::geometry::detail::get_turns::get_turns_cs::unique_sub_range_from_view_policy629 static inline std::size_t size() { return 3; }
630
atboost::geometry::detail::get_turns::get_turns_cs::unique_sub_range_from_view_policy631 inline point_type const& at(std::size_t index) const
632 {
633 BOOST_GEOMETRY_ASSERT(index < size());
634 switch (index)
635 {
636 case 0 : return m_pi;
637 case 1 : return m_pj;
638 case 2 : return *m_circular_iterator;
639 default : return m_pi;
640 }
641 }
642
643 private :
644 view_type const& m_view;
645 point_type const& m_pi;
646 point_type const& m_pj;
647 ever_circling_iterator<iterator_type> m_circular_iterator;
648 };
649
650 template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
applyboost::geometry::detail::get_turns::get_turns_cs651 static inline void apply(
652 int source_id1, Range const& range,
653 int source_id2, Box const& box,
654 IntersectionStrategy const& intersection_strategy,
655 RobustPolicy const& robust_policy,
656 Turns& turns,
657 InterruptPolicy& interrupt_policy,
658 signed_size_type multi_index = -1,
659 signed_size_type ring_index = -1)
660 {
661 if ( boost::size(range) <= 1)
662 {
663 return;
664 }
665
666 box_array box_points;
667 assign_box_corners_oriented<ReverseBox>(box, box_points);
668
669 view_type const view(range);
670
671 // TODO: in this code, possible duplicate points are not yet taken
672 // into account (not in the iterator, nor in the retrieve policy)
673 iterator_type it = boost::begin(view);
674
675 //bool first = true;
676
677 //char previous_side[2] = {0, 0};
678
679 signed_size_type index = 0;
680
681 for (iterator_type prev = it++;
682 it != boost::end(view);
683 prev = it++, index++)
684 {
685 segment_identifier seg_id(source_id1,
686 multi_index, ring_index, index);
687
688 unique_sub_range_from_view_policy view_unique_sub_range(view, *prev, *it, it);
689
690 /*if (first)
691 {
692 previous_side[0] = get_side<0>(box, *prev);
693 previous_side[1] = get_side<1>(box, *prev);
694 }
695
696 char current_side[2];
697 current_side[0] = get_side<0>(box, *it);
698 current_side[1] = get_side<1>(box, *it);
699
700 // There can NOT be intersections if
701 // 1) EITHER the two points are lying on one side of the box (! 0 && the same)
702 // 2) OR same in Y-direction
703 // 3) OR all points are inside the box (0)
704 if (! (
705 (current_side[0] != 0 && current_side[0] == previous_side[0])
706 || (current_side[1] != 0 && current_side[1] == previous_side[1])
707 || (current_side[0] == 0
708 && current_side[1] == 0
709 && previous_side[0] == 0
710 && previous_side[1] == 0)
711 )
712 )*/
713 if (true)
714 {
715 get_turns_with_box(seg_id, source_id2,
716 view_unique_sub_range,
717 box_points,
718 intersection_strategy,
719 robust_policy,
720 turns,
721 interrupt_policy);
722 // Future performance enhancement:
723 // return if told by the interrupt policy
724 }
725 }
726 }
727
728 private:
729 template<std::size_t Index, typename Point>
get_sideboost::geometry::detail::get_turns::get_turns_cs730 static inline int get_side(Box const& box, Point const& point)
731 {
732 // Inside -> 0
733 // Outside -> -1 (left/below) or 1 (right/above)
734 // On border -> -2 (left/lower) or 2 (right/upper)
735 // The only purpose of the value is to not be the same,
736 // and to denote if it is inside (0)
737
738 typename coordinate_type<Point>::type const& c = get<Index>(point);
739 typename coordinate_type<Box>::type const& left = get<min_corner, Index>(box);
740 typename coordinate_type<Box>::type const& right = get<max_corner, Index>(box);
741
742 if (geometry::math::equals(c, left)) return -2;
743 else if (geometry::math::equals(c, right)) return 2;
744 else if (c < left) return -1;
745 else if (c > right) return 1;
746 else return 0;
747 }
748
749 template
750 <
751 typename IntersectionStrategy,
752 typename Turns,
753 typename InterruptPolicy,
754 typename RobustPolicy
755 >
get_turns_with_boxboost::geometry::detail::get_turns::get_turns_cs756 static inline void get_turns_with_box(segment_identifier const& seg_id, int source_id2,
757 unique_sub_range_from_view_policy const& range_unique_sub_range,
758 box_array const& box,
759 IntersectionStrategy const& intersection_strategy,
760 RobustPolicy const& robust_policy,
761 // Output
762 Turns& turns,
763 InterruptPolicy& interrupt_policy)
764 {
765 boost::ignore_unused(interrupt_policy);
766
767 // Depending on code some relations can be left out
768
769 typedef typename boost::range_value<Turns>::type turn_info;
770
771 turn_info ti;
772 ti.operations[0].seg_id = seg_id;
773
774 unique_sub_range_from_box_policy box_unique_sub_range(box);
775 ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 0);
776 TurnPolicy::apply(range_unique_sub_range, box_unique_sub_range,
777 ti, intersection_strategy, robust_policy,
778 std::back_inserter(turns));
779
780 ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 1);
781 box_unique_sub_range.next();
782 TurnPolicy::apply(range_unique_sub_range, box_unique_sub_range,
783 ti, intersection_strategy, robust_policy,
784 std::back_inserter(turns));
785
786 ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 2);
787 box_unique_sub_range.next();
788 TurnPolicy::apply(range_unique_sub_range, box_unique_sub_range,
789 ti, intersection_strategy, robust_policy,
790 std::back_inserter(turns));
791
792 ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 3);
793 box_unique_sub_range.next();
794 TurnPolicy::apply(range_unique_sub_range, box_unique_sub_range,
795 ti, intersection_strategy, robust_policy,
796 std::back_inserter(turns));
797
798 if (InterruptPolicy::enabled)
799 {
800 interrupt_policy.apply(turns);
801 }
802
803 }
804
805 };
806
807
808 template
809 <
810 typename Polygon, typename Box,
811 bool Reverse, bool ReverseBox,
812 typename TurnPolicy
813 >
814 struct get_turns_polygon_cs
815 {
816 template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
applyboost::geometry::detail::get_turns::get_turns_polygon_cs817 static inline void apply(
818 int source_id1, Polygon const& polygon,
819 int source_id2, Box const& box,
820 IntersectionStrategy const& intersection_strategy,
821 RobustPolicy const& robust_policy,
822 Turns& turns,
823 InterruptPolicy& interrupt_policy,
824 signed_size_type multi_index = -1)
825 {
826 typedef typename geometry::ring_type<Polygon>::type ring_type;
827
828 typedef detail::get_turns::get_turns_cs
829 <
830 ring_type, Box,
831 Reverse, ReverseBox,
832 TurnPolicy
833 > intersector_type;
834
835 intersector_type::apply(
836 source_id1, geometry::exterior_ring(polygon),
837 source_id2, box,
838 intersection_strategy,
839 robust_policy,
840 turns,
841 interrupt_policy,
842 multi_index, -1);
843
844 signed_size_type i = 0;
845
846 typename interior_return_type<Polygon const>::type
847 rings = interior_rings(polygon);
848 for (typename detail::interior_iterator<Polygon const>::type
849 it = boost::begin(rings); it != boost::end(rings); ++it, ++i)
850 {
851 intersector_type::apply(
852 source_id1, *it,
853 source_id2, box,
854 intersection_strategy,
855 robust_policy,
856 turns, interrupt_policy,
857 multi_index, i);
858 }
859
860 }
861 };
862
863
864 template
865 <
866 typename Multi, typename Box,
867 bool Reverse, bool ReverseBox,
868 typename TurnPolicy
869 >
870 struct get_turns_multi_polygon_cs
871 {
872 template <typename IntersectionStrategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
applyboost::geometry::detail::get_turns::get_turns_multi_polygon_cs873 static inline void apply(
874 int source_id1, Multi const& multi,
875 int source_id2, Box const& box,
876 IntersectionStrategy const& intersection_strategy,
877 RobustPolicy const& robust_policy,
878 Turns& turns,
879 InterruptPolicy& interrupt_policy)
880 {
881 typedef typename boost::range_iterator
882 <
883 Multi const
884 >::type iterator_type;
885
886 signed_size_type i = 0;
887 for (iterator_type it = boost::begin(multi);
888 it != boost::end(multi);
889 ++it, ++i)
890 {
891 // Call its single version
892 get_turns_polygon_cs
893 <
894 typename boost::range_value<Multi>::type, Box,
895 Reverse, ReverseBox,
896 TurnPolicy
897 >::apply(source_id1, *it, source_id2, box,
898 intersection_strategy, robust_policy,
899 turns, interrupt_policy, i);
900 }
901 }
902 };
903
904
905 // GET_TURN_INFO_TYPE
906
907 template <typename Geometry>
908 struct topological_tag_base
909 {
910 typedef typename tag_cast<typename tag<Geometry>::type, pointlike_tag, linear_tag, areal_tag>::type type;
911 };
912
913 template <typename Geometry1, typename Geometry2, typename AssignPolicy,
914 typename Tag1 = typename tag<Geometry1>::type, typename Tag2 = typename tag<Geometry2>::type,
915 typename TagBase1 = typename topological_tag_base<Geometry1>::type, typename TagBase2 = typename topological_tag_base<Geometry2>::type>
916 struct get_turn_info_type
917 : overlay::get_turn_info<AssignPolicy>
918 {};
919
920 template <typename Geometry1, typename Geometry2, typename AssignPolicy, typename Tag1, typename Tag2>
921 struct get_turn_info_type<Geometry1, Geometry2, AssignPolicy, Tag1, Tag2, linear_tag, linear_tag>
922 : overlay::get_turn_info_linear_linear<AssignPolicy>
923 {};
924
925 template <typename Geometry1, typename Geometry2, typename AssignPolicy, typename Tag1, typename Tag2>
926 struct get_turn_info_type<Geometry1, Geometry2, AssignPolicy, Tag1, Tag2, linear_tag, areal_tag>
927 : overlay::get_turn_info_linear_areal<AssignPolicy>
928 {};
929
930 template <typename Geometry1, typename Geometry2, typename SegmentRatio,
931 typename Tag1 = typename tag<Geometry1>::type, typename Tag2 = typename tag<Geometry2>::type,
932 typename TagBase1 = typename topological_tag_base<Geometry1>::type, typename TagBase2 = typename topological_tag_base<Geometry2>::type>
933 struct turn_operation_type
934 {
935 typedef overlay::turn_operation<typename point_type<Geometry1>::type, SegmentRatio> type;
936 };
937
938 template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename Tag1, typename Tag2>
939 struct turn_operation_type<Geometry1, Geometry2, SegmentRatio, Tag1, Tag2, linear_tag, linear_tag>
940 {
941 typedef overlay::turn_operation_linear<typename point_type<Geometry1>::type, SegmentRatio> type;
942 };
943
944 template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename Tag1, typename Tag2>
945 struct turn_operation_type<Geometry1, Geometry2, SegmentRatio, Tag1, Tag2, linear_tag, areal_tag>
946 {
947 typedef overlay::turn_operation_linear<typename point_type<Geometry1>::type, SegmentRatio> type;
948 };
949
950 }} // namespace detail::get_turns
951 #endif // DOXYGEN_NO_DETAIL
952
953
954 #ifndef DOXYGEN_NO_DISPATCH
955 namespace dispatch
956 {
957
958 // Because this is "detail" method, and most implementations will use "generic",
959 // we take the freedom to derive it from "generic".
960 template
961 <
962 typename GeometryTag1, typename GeometryTag2,
963 typename Geometry1, typename Geometry2,
964 bool Reverse1, bool Reverse2,
965 typename TurnPolicy
966 >
967 struct get_turns
968 : detail::get_turns::get_turns_generic
969 <
970 Geometry1, Geometry2,
971 Reverse1, Reverse2,
972 TurnPolicy
973 >
974 {};
975
976
977 template
978 <
979 typename Polygon, typename Box,
980 bool ReversePolygon, bool ReverseBox,
981 typename TurnPolicy
982 >
983 struct get_turns
984 <
985 polygon_tag, box_tag,
986 Polygon, Box,
987 ReversePolygon, ReverseBox,
988 TurnPolicy
989 > : detail::get_turns::get_turns_polygon_cs
990 <
991 Polygon, Box,
992 ReversePolygon, ReverseBox,
993 TurnPolicy
994 >
995 {};
996
997
998 template
999 <
1000 typename Ring, typename Box,
1001 bool ReverseRing, bool ReverseBox,
1002 typename TurnPolicy
1003 >
1004 struct get_turns
1005 <
1006 ring_tag, box_tag,
1007 Ring, Box,
1008 ReverseRing, ReverseBox,
1009 TurnPolicy
1010 > : detail::get_turns::get_turns_cs
1011 <
1012 Ring, Box, ReverseRing, ReverseBox,
1013 TurnPolicy
1014 >
1015
1016 {};
1017
1018
1019 template
1020 <
1021 typename MultiPolygon,
1022 typename Box,
1023 bool ReverseMultiPolygon, bool ReverseBox,
1024 typename TurnPolicy
1025 >
1026 struct get_turns
1027 <
1028 multi_polygon_tag, box_tag,
1029 MultiPolygon, Box,
1030 ReverseMultiPolygon, ReverseBox,
1031 TurnPolicy
1032 >
1033 : detail::get_turns::get_turns_multi_polygon_cs
1034 <
1035 MultiPolygon, Box,
1036 ReverseMultiPolygon, ReverseBox,
1037 TurnPolicy
1038 >
1039 {};
1040
1041
1042 template
1043 <
1044 typename GeometryTag1, typename GeometryTag2,
1045 typename Geometry1, typename Geometry2,
1046 bool Reverse1, bool Reverse2,
1047 typename TurnPolicy
1048 >
1049 struct get_turns_reversed
1050 {
1051 template <typename Strategy, typename RobustPolicy, typename Turns, typename InterruptPolicy>
applyboost::geometry::dispatch::get_turns_reversed1052 static inline void apply(int source_id1, Geometry1 const& g1,
1053 int source_id2, Geometry2 const& g2,
1054 Strategy const& strategy,
1055 RobustPolicy const& robust_policy,
1056 Turns& turns,
1057 InterruptPolicy& interrupt_policy)
1058 {
1059 get_turns
1060 <
1061 GeometryTag2, GeometryTag1,
1062 Geometry2, Geometry1,
1063 Reverse2, Reverse1,
1064 TurnPolicy
1065 >::apply(source_id2, g2, source_id1, g1,
1066 strategy, robust_policy,
1067 turns, interrupt_policy);
1068 }
1069 };
1070
1071
1072 } // namespace dispatch
1073 #endif // DOXYGEN_NO_DISPATCH
1074
1075
1076
1077 /*!
1078 \brief \brief_calc2{turn points}
1079 \ingroup overlay
1080 \tparam Geometry1 \tparam_geometry
1081 \tparam Geometry2 \tparam_geometry
1082 \tparam Turns type of turn-container (e.g. vector of "intersection/turn point"'s)
1083 \param geometry1 \param_geometry
1084 \param geometry2 \param_geometry
1085 \param intersection_strategy segments intersection strategy
1086 \param robust_policy policy to handle robustness issues
1087 \param turns container which will contain turn points
1088 \param interrupt_policy policy determining if process is stopped
1089 when intersection is found
1090 */
1091 template
1092 <
1093 bool Reverse1, bool Reverse2,
1094 typename AssignPolicy,
1095 typename Geometry1,
1096 typename Geometry2,
1097 typename Strategy,
1098 typename RobustPolicy,
1099 typename Turns,
1100 typename InterruptPolicy
1101 >
get_turns(Geometry1 const & geometry1,Geometry2 const & geometry2,Strategy const & strategy,RobustPolicy const & robust_policy,Turns & turns,InterruptPolicy & interrupt_policy)1102 inline void get_turns(Geometry1 const& geometry1,
1103 Geometry2 const& geometry2,
1104 Strategy const& strategy,
1105 RobustPolicy const& robust_policy,
1106 Turns& turns,
1107 InterruptPolicy& interrupt_policy)
1108 {
1109 concepts::check_concepts_and_equal_dimensions<Geometry1 const, Geometry2 const>();
1110
1111 typedef detail::overlay::get_turn_info<AssignPolicy> TurnPolicy;
1112 //typedef detail::get_turns::get_turn_info_type<Geometry1, Geometry2, AssignPolicy> TurnPolicy;
1113
1114 std::conditional_t
1115 <
1116 reverse_dispatch<Geometry1, Geometry2>::type::value,
1117 dispatch::get_turns_reversed
1118 <
1119 typename tag<Geometry1>::type,
1120 typename tag<Geometry2>::type,
1121 Geometry1, Geometry2,
1122 Reverse1, Reverse2,
1123 TurnPolicy
1124 >,
1125 dispatch::get_turns
1126 <
1127 typename tag<Geometry1>::type,
1128 typename tag<Geometry2>::type,
1129 Geometry1, Geometry2,
1130 Reverse1, Reverse2,
1131 TurnPolicy
1132 >
1133 >::apply(0, geometry1,
1134 1, geometry2,
1135 strategy,
1136 robust_policy,
1137 turns, interrupt_policy);
1138 }
1139
1140 #if defined(_MSC_VER)
1141 #pragma warning(pop)
1142 #endif
1143
1144 }} // namespace boost::geometry
1145
1146 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP
1147