]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | // Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland. | |
5 | ||
6 | // This file was modified by Oracle on 2014, 2016. | |
7 | // Modifications copyright (c) 2014, 2016 Oracle and/or its affiliates. | |
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 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
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/mpl/if.hpp> | |
25 | #include <boost/mpl/vector_c.hpp> | |
26 | #include <boost/range.hpp> | |
27 | ||
28 | #include <boost/geometry/core/access.hpp> | |
29 | #include <boost/geometry/core/coordinate_dimension.hpp> | |
30 | #include <boost/geometry/core/exterior_ring.hpp> | |
31 | #include <boost/geometry/core/interior_rings.hpp> | |
32 | #include <boost/geometry/core/reverse_dispatch.hpp> | |
33 | #include <boost/geometry/core/ring_type.hpp> | |
34 | #include <boost/geometry/core/tags.hpp> | |
35 | ||
36 | #include <boost/geometry/geometries/concepts/check.hpp> | |
37 | ||
38 | #include <boost/geometry/util/math.hpp> | |
39 | #include <boost/geometry/views/closeable_view.hpp> | |
40 | #include <boost/geometry/views/reversible_view.hpp> | |
41 | #include <boost/geometry/views/detail/range_type.hpp> | |
42 | ||
43 | #include <boost/geometry/geometries/box.hpp> | |
44 | #include <boost/geometry/geometries/segment.hpp> | |
45 | ||
46 | #include <boost/geometry/iterators/ever_circling_iterator.hpp> | |
47 | ||
48 | #include <boost/geometry/strategies/cartesian/cart_intersect.hpp> | |
49 | #include <boost/geometry/strategies/intersection_strategies.hpp> | |
50 | #include <boost/geometry/strategies/intersection_result.hpp> | |
51 | ||
52 | #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp> | |
53 | #include <boost/geometry/algorithms/detail/disjoint/point_point.hpp> | |
54 | ||
55 | #include <boost/geometry/algorithms/detail/interior_iterator.hpp> | |
56 | #include <boost/geometry/algorithms/detail/partition.hpp> | |
57 | #include <boost/geometry/algorithms/detail/recalculate.hpp> | |
58 | #include <boost/geometry/algorithms/detail/sections/section_box_policies.hpp> | |
59 | ||
60 | #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp> | |
61 | #include <boost/geometry/algorithms/detail/overlay/get_turn_info_ll.hpp> | |
62 | #include <boost/geometry/algorithms/detail/overlay/get_turn_info_la.hpp> | |
63 | #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp> | |
64 | ||
65 | #include <boost/geometry/algorithms/detail/sections/range_by_section.hpp> | |
66 | #include <boost/geometry/algorithms/detail/sections/sectionalize.hpp> | |
67 | #include <boost/geometry/algorithms/detail/sections/section_functions.hpp> | |
68 | ||
69 | #ifdef BOOST_GEOMETRY_DEBUG_INTERSECTION | |
70 | # include <sstream> | |
71 | # include <boost/geometry/io/dsv/write.hpp> | |
72 | #endif | |
73 | ||
74 | ||
75 | namespace boost { namespace geometry | |
76 | { | |
77 | ||
78 | // Silence warning C4127: conditional expression is constant | |
79 | #if defined(_MSC_VER) | |
80 | #pragma warning(push) | |
81 | #pragma warning(disable : 4127) | |
82 | #endif | |
83 | ||
84 | ||
85 | #ifndef DOXYGEN_NO_DETAIL | |
86 | namespace detail { namespace get_turns | |
87 | { | |
88 | ||
89 | ||
90 | struct no_interrupt_policy | |
91 | { | |
92 | static bool const enabled = false; | |
93 | ||
94 | template <typename Range> | |
95 | static inline bool apply(Range const&) | |
96 | { | |
97 | return false; | |
98 | } | |
99 | }; | |
100 | ||
101 | ||
102 | template | |
103 | < | |
104 | typename Geometry1, typename Geometry2, | |
105 | bool Reverse1, bool Reverse2, | |
106 | typename Section1, typename Section2, | |
107 | typename TurnPolicy | |
108 | > | |
109 | class get_turns_in_sections | |
110 | { | |
111 | typedef typename closeable_view | |
112 | < | |
113 | typename range_type<Geometry1>::type const, | |
114 | closure<Geometry1>::value | |
115 | >::type cview_type1; | |
116 | typedef typename closeable_view | |
117 | < | |
118 | typename range_type<Geometry2>::type const, | |
119 | closure<Geometry2>::value | |
120 | >::type cview_type2; | |
121 | ||
122 | typedef typename reversible_view | |
123 | < | |
124 | cview_type1 const, | |
125 | Reverse1 ? iterate_reverse : iterate_forward | |
126 | >::type view_type1; | |
127 | typedef typename reversible_view | |
128 | < | |
129 | cview_type2 const, | |
130 | Reverse2 ? iterate_reverse : iterate_forward | |
131 | >::type view_type2; | |
132 | ||
133 | typedef typename boost::range_iterator | |
134 | < | |
135 | view_type1 const | |
136 | >::type range1_iterator; | |
137 | ||
138 | typedef typename boost::range_iterator | |
139 | < | |
140 | view_type2 const | |
141 | >::type range2_iterator; | |
142 | ||
143 | ||
144 | template <typename Geometry, typename Section> | |
145 | static inline bool neighbouring(Section const& section, | |
146 | signed_size_type index1, signed_size_type index2) | |
147 | { | |
148 | // About n-2: | |
149 | // (square: range_count=5, indices 0,1,2,3 | |
150 | // -> 0-3 are adjacent, don't check on intersections) | |
151 | // Also tested for open polygons, and/or duplicates | |
152 | // About first condition: will be optimized by compiler (static) | |
153 | // It checks if it is areal (box,ring,(multi)polygon | |
154 | signed_size_type const n = static_cast<signed_size_type>(section.range_count); | |
155 | ||
156 | boost::ignore_unused_variable_warning(n); | |
157 | boost::ignore_unused_variable_warning(index1); | |
158 | boost::ignore_unused_variable_warning(index2); | |
159 | ||
160 | return boost::is_same | |
161 | < | |
162 | typename tag_cast | |
163 | < | |
164 | typename geometry::tag<Geometry>::type, | |
165 | areal_tag | |
166 | >::type, | |
167 | areal_tag | |
168 | >::value | |
169 | && index1 == 0 | |
170 | && index2 >= n - 2 | |
171 | ; | |
172 | } | |
173 | ||
174 | ||
175 | public : | |
176 | // Returns true if terminated, false if interrupted | |
177 | template <typename Turns, typename RobustPolicy, typename InterruptPolicy> | |
178 | static inline bool apply( | |
179 | int source_id1, Geometry1 const& geometry1, Section1 const& sec1, | |
180 | int source_id2, Geometry2 const& geometry2, Section2 const& sec2, | |
181 | bool skip_larger, | |
182 | RobustPolicy const& robust_policy, | |
183 | Turns& turns, | |
184 | InterruptPolicy& interrupt_policy) | |
185 | { | |
186 | boost::ignore_unused_variable_warning(interrupt_policy); | |
187 | ||
188 | if ((sec1.duplicate && (sec1.count + 1) < sec1.range_count) | |
189 | || (sec2.duplicate && (sec2.count + 1) < sec2.range_count)) | |
190 | { | |
191 | // Skip sections containig only duplicates. | |
192 | // They are still important (can indicate non-disjointness) | |
193 | // but they will be found processing adjacent sections. | |
194 | // Do NOT skip if they are the ONLY section | |
195 | return true; | |
196 | } | |
197 | ||
198 | cview_type1 cview1(range_by_section(geometry1, sec1)); | |
199 | cview_type2 cview2(range_by_section(geometry2, sec2)); | |
200 | view_type1 view1(cview1); | |
201 | view_type2 view2(cview2); | |
202 | ||
203 | range1_iterator begin_range_1 = boost::begin(view1); | |
204 | range1_iterator end_range_1 = boost::end(view1); | |
205 | ||
206 | range2_iterator begin_range_2 = boost::begin(view2); | |
207 | range2_iterator end_range_2 = boost::end(view2); | |
208 | ||
209 | int const dir1 = sec1.directions[0]; | |
210 | int const dir2 = sec2.directions[0]; | |
211 | signed_size_type index1 = sec1.begin_index; | |
212 | signed_size_type ndi1 = sec1.non_duplicate_index; | |
213 | ||
214 | bool const same_source = | |
215 | source_id1 == source_id2 | |
216 | && sec1.ring_id.multi_index == sec2.ring_id.multi_index | |
217 | && sec1.ring_id.ring_index == sec2.ring_id.ring_index; | |
218 | ||
219 | range1_iterator prev1, it1, end1; | |
220 | ||
221 | get_start_point_iterator(sec1, view1, prev1, it1, end1, | |
222 | index1, ndi1, dir1, sec2.bounding_box, robust_policy); | |
223 | ||
224 | // We need a circular iterator because it might run through the closing point. | |
225 | // One circle is actually enough but this one is just convenient. | |
226 | ever_circling_iterator<range1_iterator> next1(begin_range_1, end_range_1, it1, true); | |
227 | next1++; | |
228 | ||
229 | // Walk through section and stop if we exceed the other box | |
230 | // section 2: [--------------] | |
231 | // section 1: |----|---|---|---|---| | |
232 | for (prev1 = it1++, next1++; | |
233 | it1 != end1 && ! detail::section::exceeding<0>(dir1, *prev1, sec2.bounding_box, robust_policy); | |
234 | ++prev1, ++it1, ++index1, ++next1, ++ndi1) | |
235 | { | |
236 | ever_circling_iterator<range1_iterator> nd_next1( | |
237 | begin_range_1, end_range_1, next1, true); | |
238 | advance_to_non_duplicate_next(nd_next1, it1, sec1, robust_policy); | |
239 | ||
240 | signed_size_type index2 = sec2.begin_index; | |
241 | signed_size_type ndi2 = sec2.non_duplicate_index; | |
242 | ||
243 | range2_iterator prev2, it2, end2; | |
244 | ||
245 | get_start_point_iterator(sec2, view2, prev2, it2, end2, | |
246 | index2, ndi2, dir2, sec1.bounding_box, robust_policy); | |
247 | ever_circling_iterator<range2_iterator> next2(begin_range_2, end_range_2, it2, true); | |
248 | next2++; | |
249 | ||
250 | for (prev2 = it2++, next2++; | |
251 | it2 != end2 && ! detail::section::exceeding<0>(dir2, *prev2, sec1.bounding_box, robust_policy); | |
252 | ++prev2, ++it2, ++index2, ++next2, ++ndi2) | |
253 | { | |
254 | bool skip = same_source; | |
255 | if (skip) | |
256 | { | |
257 | // If sources are the same (possibly self-intersecting): | |
258 | // skip if it is a neighbouring segment. | |
259 | // (including first-last segment | |
260 | // and two segments with one or more degenerate/duplicate | |
261 | // (zero-length) segments in between) | |
262 | ||
263 | // Also skip if index1 < index2 to avoid getting all | |
264 | // intersections twice (only do this on same source!) | |
265 | ||
266 | skip = (skip_larger && index1 >= index2) | |
267 | || ndi2 == ndi1 + 1 | |
268 | || neighbouring<Geometry1>(sec1, index1, index2) | |
269 | ; | |
270 | } | |
271 | ||
272 | if (! skip) | |
273 | { | |
274 | // Move to the "non duplicate next" | |
275 | ever_circling_iterator<range2_iterator> nd_next2( | |
276 | begin_range_2, end_range_2, next2, true); | |
277 | advance_to_non_duplicate_next(nd_next2, it2, sec2, robust_policy); | |
278 | ||
279 | typedef typename boost::range_value<Turns>::type turn_info; | |
280 | ||
281 | turn_info ti; | |
282 | ti.operations[0].seg_id | |
283 | = segment_identifier(source_id1, sec1.ring_id.multi_index, | |
284 | sec1.ring_id.ring_index, index1); | |
285 | ti.operations[1].seg_id | |
286 | = segment_identifier(source_id2, sec2.ring_id.multi_index, | |
287 | sec2.ring_id.ring_index, index2); | |
288 | ||
289 | std::size_t const size_before = boost::size(turns); | |
290 | ||
291 | bool const is_1_first = sec1.is_non_duplicate_first && index1 == sec1.begin_index; | |
292 | bool const is_1_last = sec1.is_non_duplicate_last && index1+1 >= sec1.end_index; | |
293 | bool const is_2_first = sec2.is_non_duplicate_first && index2 == sec2.begin_index; | |
294 | bool const is_2_last = sec2.is_non_duplicate_last && index2+1 >= sec2.end_index; | |
295 | ||
296 | TurnPolicy::apply(*prev1, *it1, *nd_next1, *prev2, *it2, *nd_next2, | |
297 | is_1_first, is_1_last, is_2_first, is_2_last, | |
298 | ti, robust_policy, std::back_inserter(turns)); | |
299 | ||
300 | if (InterruptPolicy::enabled) | |
301 | { | |
302 | if (interrupt_policy.apply( | |
303 | std::make_pair(range::pos(turns, size_before), | |
304 | boost::end(turns)))) | |
305 | { | |
306 | return false; | |
307 | } | |
308 | } | |
309 | } | |
310 | } | |
311 | } | |
312 | return true; | |
313 | } | |
314 | ||
315 | ||
316 | private : | |
317 | typedef typename geometry::point_type<Geometry1>::type point1_type; | |
318 | typedef typename geometry::point_type<Geometry2>::type point2_type; | |
319 | typedef typename model::referring_segment<point1_type const> segment1_type; | |
320 | typedef typename model::referring_segment<point2_type const> segment2_type; | |
321 | ||
322 | template <typename Iterator, typename RangeIterator, typename Section, typename RobustPolicy> | |
323 | static inline void advance_to_non_duplicate_next(Iterator& next, | |
324 | RangeIterator const& it, Section const& section, RobustPolicy const& robust_policy) | |
325 | { | |
326 | typedef typename robust_point_type<point1_type, RobustPolicy>::type robust_point_type; | |
327 | robust_point_type robust_point_from_it; | |
328 | robust_point_type robust_point_from_next; | |
329 | geometry::recalculate(robust_point_from_it, *it, robust_policy); | |
330 | geometry::recalculate(robust_point_from_next, *next, robust_policy); | |
331 | ||
332 | // To see where the next segments bend to, in case of touch/intersections | |
333 | // on end points, we need (in case of degenerate/duplicate points) an extra | |
334 | // iterator which moves to the REAL next point, so non duplicate. | |
335 | // This needs an extra comparison (disjoint). | |
336 | // (Note that within sections, non duplicate points are already asserted, | |
337 | // by the sectionalize process). | |
338 | ||
339 | // So advance to the "non duplicate next" | |
340 | // (the check is defensive, to avoid endless loops) | |
341 | std::size_t check = 0; | |
342 | while(! detail::disjoint::disjoint_point_point | |
343 | ( | |
344 | robust_point_from_it, robust_point_from_next | |
345 | ) | |
346 | && check++ < section.range_count) | |
347 | { | |
348 | next++; | |
349 | geometry::recalculate(robust_point_from_next, *next, robust_policy); | |
350 | } | |
351 | } | |
352 | ||
353 | // It is NOT possible to have section-iterators here | |
354 | // because of the logistics of "index" (the section-iterator automatically | |
355 | // skips to the begin-point, we loose the index or have to recalculate it) | |
356 | // So we mimic it here | |
357 | template <typename Range, typename Section, typename Box, typename RobustPolicy> | |
358 | static inline void get_start_point_iterator(Section & section, | |
359 | Range const& range, | |
360 | typename boost::range_iterator<Range const>::type& it, | |
361 | typename boost::range_iterator<Range const>::type& prev, | |
362 | typename boost::range_iterator<Range const>::type& end, | |
363 | signed_size_type& index, signed_size_type& ndi, | |
364 | int dir, Box const& other_bounding_box, RobustPolicy const& robust_policy) | |
365 | { | |
366 | it = boost::begin(range) + section.begin_index; | |
367 | end = boost::begin(range) + section.end_index + 1; | |
368 | ||
369 | // Mimic section-iterator: | |
370 | // Skip to point such that section interects other box | |
371 | prev = it++; | |
372 | for(; it != end && detail::section::preceding<0>(dir, *it, other_bounding_box, robust_policy); | |
373 | prev = it++, index++, ndi++) | |
374 | {} | |
375 | // Go back one step because we want to start completely preceding | |
376 | it = prev; | |
377 | } | |
378 | }; | |
379 | ||
380 | template | |
381 | < | |
382 | typename Geometry1, typename Geometry2, | |
383 | bool Reverse1, bool Reverse2, | |
384 | typename Turns, | |
385 | typename TurnPolicy, | |
386 | typename RobustPolicy, | |
387 | typename InterruptPolicy | |
388 | > | |
389 | struct section_visitor | |
390 | { | |
391 | int m_source_id1; | |
392 | Geometry1 const& m_geometry1; | |
393 | int m_source_id2; | |
394 | Geometry2 const& m_geometry2; | |
395 | RobustPolicy const& m_rescale_policy; | |
396 | Turns& m_turns; | |
397 | InterruptPolicy& m_interrupt_policy; | |
398 | ||
399 | section_visitor(int id1, Geometry1 const& g1, | |
400 | int id2, Geometry2 const& g2, | |
401 | RobustPolicy const& robust_policy, | |
402 | Turns& turns, InterruptPolicy& ip) | |
403 | : m_source_id1(id1), m_geometry1(g1) | |
404 | , m_source_id2(id2), m_geometry2(g2) | |
405 | , m_rescale_policy(robust_policy) | |
406 | , m_turns(turns) | |
407 | , m_interrupt_policy(ip) | |
408 | {} | |
409 | ||
410 | template <typename Section> | |
411 | inline bool apply(Section const& sec1, Section const& sec2) | |
412 | { | |
413 | if (! detail::disjoint::disjoint_box_box(sec1.bounding_box, sec2.bounding_box)) | |
414 | { | |
415 | return get_turns_in_sections | |
416 | < | |
417 | Geometry1, | |
418 | Geometry2, | |
419 | Reverse1, Reverse2, | |
420 | Section, Section, | |
421 | TurnPolicy | |
422 | >::apply( | |
423 | m_source_id1, m_geometry1, sec1, | |
424 | m_source_id2, m_geometry2, sec2, | |
425 | false, | |
426 | m_rescale_policy, | |
427 | m_turns, m_interrupt_policy); | |
428 | } | |
429 | return true; | |
430 | } | |
431 | ||
432 | }; | |
433 | ||
434 | template | |
435 | < | |
436 | typename Geometry1, typename Geometry2, | |
437 | bool Reverse1, bool Reverse2, | |
438 | typename TurnPolicy | |
439 | > | |
440 | class get_turns_generic | |
441 | { | |
442 | ||
443 | public: | |
444 | template <typename RobustPolicy, typename Turns, typename InterruptPolicy> | |
445 | static inline void apply( | |
446 | int source_id1, Geometry1 const& geometry1, | |
447 | int source_id2, Geometry2 const& geometry2, | |
448 | RobustPolicy const& robust_policy, | |
449 | Turns& turns, | |
450 | InterruptPolicy& interrupt_policy) | |
451 | { | |
452 | // First create monotonic sections... | |
453 | typedef typename boost::range_value<Turns>::type ip_type; | |
454 | typedef typename ip_type::point_type point_type; | |
455 | ||
456 | typedef model::box | |
457 | < | |
458 | typename geometry::robust_point_type | |
459 | < | |
460 | point_type, RobustPolicy | |
461 | >::type | |
462 | > box_type; | |
463 | typedef geometry::sections<box_type, 2> sections_type; | |
464 | ||
465 | sections_type sec1, sec2; | |
466 | typedef boost::mpl::vector_c<std::size_t, 0, 1> dimensions; | |
467 | ||
468 | geometry::sectionalize<Reverse1, dimensions>(geometry1, robust_policy, | |
469 | sec1, 0); | |
470 | geometry::sectionalize<Reverse2, dimensions>(geometry2, robust_policy, | |
471 | sec2, 1); | |
472 | ||
473 | // ... and then partition them, intersecting overlapping sections in visitor method | |
474 | section_visitor | |
475 | < | |
476 | Geometry1, Geometry2, | |
477 | Reverse1, Reverse2, | |
478 | Turns, TurnPolicy, RobustPolicy, InterruptPolicy | |
479 | > visitor(source_id1, geometry1, source_id2, geometry2, robust_policy, turns, interrupt_policy); | |
480 | ||
481 | geometry::partition | |
482 | < | |
483 | box_type, | |
484 | detail::section::get_section_box, | |
485 | detail::section::overlaps_section_box | |
486 | >::apply(sec1, sec2, visitor); | |
487 | } | |
488 | }; | |
489 | ||
490 | ||
491 | // Get turns for a range with a box, following Cohen-Sutherland (cs) approach | |
492 | template | |
493 | < | |
494 | typename Range, typename Box, | |
495 | bool ReverseRange, bool ReverseBox, | |
496 | typename TurnPolicy | |
497 | > | |
498 | struct get_turns_cs | |
499 | { | |
500 | typedef typename geometry::point_type<Range>::type point_type; | |
501 | typedef typename geometry::point_type<Box>::type box_point_type; | |
502 | ||
503 | typedef typename closeable_view | |
504 | < | |
505 | Range const, | |
506 | closure<Range>::value | |
507 | >::type cview_type; | |
508 | ||
509 | typedef typename reversible_view | |
510 | < | |
511 | cview_type const, | |
512 | ReverseRange ? iterate_reverse : iterate_forward | |
513 | >::type view_type; | |
514 | ||
515 | typedef typename boost::range_iterator | |
516 | < | |
517 | view_type const | |
518 | >::type iterator_type; | |
519 | ||
520 | ||
521 | template <typename RobustPolicy, typename Turns, typename InterruptPolicy> | |
522 | static inline void apply( | |
523 | int source_id1, Range const& range, | |
524 | int source_id2, Box const& box, | |
525 | RobustPolicy const& robust_policy, | |
526 | Turns& turns, | |
527 | InterruptPolicy& interrupt_policy, | |
528 | signed_size_type multi_index = -1, | |
529 | signed_size_type ring_index = -1) | |
530 | { | |
531 | if ( boost::size(range) <= 1) | |
532 | { | |
533 | return; | |
534 | } | |
535 | ||
536 | boost::array<box_point_type,4> bp; | |
537 | assign_box_corners_oriented<ReverseBox>(box, bp); | |
538 | ||
539 | cview_type cview(range); | |
540 | view_type view(cview); | |
541 | ||
542 | typedef typename boost::range_size<view_type>::type size_type; | |
543 | size_type segments_count1 = boost::size(view) - 1; | |
544 | ||
545 | iterator_type it = boost::begin(view); | |
546 | ||
547 | ever_circling_iterator<iterator_type> next( | |
548 | boost::begin(view), boost::end(view), it, true); | |
549 | next++; | |
550 | next++; | |
551 | ||
552 | //bool first = true; | |
553 | ||
554 | //char previous_side[2] = {0, 0}; | |
555 | ||
556 | signed_size_type index = 0; | |
557 | ||
558 | for (iterator_type prev = it++; | |
559 | it != boost::end(view); | |
560 | prev = it++, next++, index++) | |
561 | { | |
562 | segment_identifier seg_id(source_id1, | |
563 | multi_index, ring_index, index); | |
564 | ||
565 | /*if (first) | |
566 | { | |
567 | previous_side[0] = get_side<0>(box, *prev); | |
568 | previous_side[1] = get_side<1>(box, *prev); | |
569 | } | |
570 | ||
571 | char current_side[2]; | |
572 | current_side[0] = get_side<0>(box, *it); | |
573 | current_side[1] = get_side<1>(box, *it); | |
574 | ||
575 | // There can NOT be intersections if | |
576 | // 1) EITHER the two points are lying on one side of the box (! 0 && the same) | |
577 | // 2) OR same in Y-direction | |
578 | // 3) OR all points are inside the box (0) | |
579 | if (! ( | |
580 | (current_side[0] != 0 && current_side[0] == previous_side[0]) | |
581 | || (current_side[1] != 0 && current_side[1] == previous_side[1]) | |
582 | || (current_side[0] == 0 | |
583 | && current_side[1] == 0 | |
584 | && previous_side[0] == 0 | |
585 | && previous_side[1] == 0) | |
586 | ) | |
587 | )*/ | |
588 | if (true) | |
589 | { | |
590 | get_turns_with_box(seg_id, source_id2, | |
591 | *prev, *it, *next, | |
592 | bp[0], bp[1], bp[2], bp[3], | |
593 | // NOTE: some dummy values could be passed below since this would be called only for Polygons and Boxes | |
594 | index == 0, | |
595 | size_type(index) == segments_count1, | |
596 | robust_policy, | |
597 | turns, interrupt_policy); | |
598 | // Future performance enhancement: | |
599 | // return if told by the interrupt policy | |
600 | } | |
601 | } | |
602 | } | |
603 | ||
604 | private: | |
605 | template<std::size_t Index, typename Point> | |
606 | static inline int get_side(Box const& box, Point const& point) | |
607 | { | |
608 | // Inside -> 0 | |
609 | // Outside -> -1 (left/below) or 1 (right/above) | |
610 | // On border -> -2 (left/lower) or 2 (right/upper) | |
611 | // The only purpose of the value is to not be the same, | |
612 | // and to denote if it is inside (0) | |
613 | ||
614 | typename coordinate_type<Point>::type const& c = get<Index>(point); | |
615 | typename coordinate_type<Box>::type const& left = get<min_corner, Index>(box); | |
616 | typename coordinate_type<Box>::type const& right = get<max_corner, Index>(box); | |
617 | ||
618 | if (geometry::math::equals(c, left)) return -2; | |
619 | else if (geometry::math::equals(c, right)) return 2; | |
620 | else if (c < left) return -1; | |
621 | else if (c > right) return 1; | |
622 | else return 0; | |
623 | } | |
624 | ||
625 | template <typename RobustPolicy, typename Turns, typename InterruptPolicy> | |
626 | static inline void get_turns_with_box(segment_identifier const& seg_id, int source_id2, | |
627 | // Points from a range: | |
628 | point_type const& rp0, | |
629 | point_type const& rp1, | |
630 | point_type const& rp2, | |
631 | // Points from the box | |
632 | box_point_type const& bp0, | |
633 | box_point_type const& bp1, | |
634 | box_point_type const& bp2, | |
635 | box_point_type const& bp3, | |
636 | bool const is_range_first, | |
637 | bool const is_range_last, | |
638 | RobustPolicy const& robust_policy, | |
639 | // Output | |
640 | Turns& turns, | |
641 | InterruptPolicy& interrupt_policy) | |
642 | { | |
643 | boost::ignore_unused_variable_warning(interrupt_policy); | |
644 | ||
645 | // Depending on code some relations can be left out | |
646 | ||
647 | typedef typename boost::range_value<Turns>::type turn_info; | |
648 | ||
649 | turn_info ti; | |
650 | ti.operations[0].seg_id = seg_id; | |
651 | ||
652 | ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 0); | |
653 | TurnPolicy::apply(rp0, rp1, rp2, bp0, bp1, bp2, | |
654 | is_range_first, is_range_last, | |
655 | true, false, | |
656 | ti, robust_policy, std::back_inserter(turns)); | |
657 | ||
658 | ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 1); | |
659 | TurnPolicy::apply(rp0, rp1, rp2, bp1, bp2, bp3, | |
660 | is_range_first, is_range_last, | |
661 | false, false, | |
662 | ti, robust_policy, std::back_inserter(turns)); | |
663 | ||
664 | ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 2); | |
665 | TurnPolicy::apply(rp0, rp1, rp2, bp2, bp3, bp0, | |
666 | is_range_first, is_range_last, | |
667 | false, false, | |
668 | ti, robust_policy, std::back_inserter(turns)); | |
669 | ||
670 | ti.operations[1].seg_id = segment_identifier(source_id2, -1, -1, 3); | |
671 | TurnPolicy::apply(rp0, rp1, rp2, bp3, bp0, bp1, | |
672 | is_range_first, is_range_last, | |
673 | false, true, | |
674 | ti, robust_policy, std::back_inserter(turns)); | |
675 | ||
676 | if (InterruptPolicy::enabled) | |
677 | { | |
678 | interrupt_policy.apply(turns); | |
679 | } | |
680 | ||
681 | } | |
682 | ||
683 | }; | |
684 | ||
685 | ||
686 | template | |
687 | < | |
688 | typename Polygon, typename Box, | |
689 | bool Reverse, bool ReverseBox, | |
690 | typename TurnPolicy | |
691 | > | |
692 | struct get_turns_polygon_cs | |
693 | { | |
694 | template <typename RobustPolicy, typename Turns, typename InterruptPolicy> | |
695 | static inline void apply( | |
696 | int source_id1, Polygon const& polygon, | |
697 | int source_id2, Box const& box, | |
698 | RobustPolicy const& robust_policy, | |
699 | Turns& turns, InterruptPolicy& interrupt_policy, | |
700 | signed_size_type multi_index = -1) | |
701 | { | |
702 | typedef typename geometry::ring_type<Polygon>::type ring_type; | |
703 | ||
704 | typedef detail::get_turns::get_turns_cs | |
705 | < | |
706 | ring_type, Box, | |
707 | Reverse, ReverseBox, | |
708 | TurnPolicy | |
709 | > intersector_type; | |
710 | ||
711 | intersector_type::apply( | |
712 | source_id1, geometry::exterior_ring(polygon), | |
713 | source_id2, box, | |
714 | robust_policy, | |
715 | turns, interrupt_policy, | |
716 | multi_index, -1); | |
717 | ||
718 | signed_size_type i = 0; | |
719 | ||
720 | typename interior_return_type<Polygon const>::type | |
721 | rings = interior_rings(polygon); | |
722 | for (typename detail::interior_iterator<Polygon const>::type | |
723 | it = boost::begin(rings); it != boost::end(rings); ++it, ++i) | |
724 | { | |
725 | intersector_type::apply( | |
726 | source_id1, *it, | |
727 | source_id2, box, | |
728 | robust_policy, | |
729 | turns, interrupt_policy, | |
730 | multi_index, i); | |
731 | } | |
732 | ||
733 | } | |
734 | }; | |
735 | ||
736 | ||
737 | template | |
738 | < | |
739 | typename Multi, typename Box, | |
740 | bool Reverse, bool ReverseBox, | |
741 | typename TurnPolicy | |
742 | > | |
743 | struct get_turns_multi_polygon_cs | |
744 | { | |
745 | template <typename RobustPolicy, typename Turns, typename InterruptPolicy> | |
746 | static inline void apply( | |
747 | int source_id1, Multi const& multi, | |
748 | int source_id2, Box const& box, | |
749 | RobustPolicy const& robust_policy, | |
750 | Turns& turns, InterruptPolicy& interrupt_policy) | |
751 | { | |
752 | typedef typename boost::range_iterator | |
753 | < | |
754 | Multi const | |
755 | >::type iterator_type; | |
756 | ||
757 | signed_size_type i = 0; | |
758 | for (iterator_type it = boost::begin(multi); | |
759 | it != boost::end(multi); | |
760 | ++it, ++i) | |
761 | { | |
762 | // Call its single version | |
763 | get_turns_polygon_cs | |
764 | < | |
765 | typename boost::range_value<Multi>::type, Box, | |
766 | Reverse, ReverseBox, | |
767 | TurnPolicy | |
768 | >::apply(source_id1, *it, source_id2, box, | |
769 | robust_policy, turns, interrupt_policy, i); | |
770 | } | |
771 | } | |
772 | }; | |
773 | ||
774 | ||
775 | // GET_TURN_INFO_TYPE | |
776 | ||
777 | template <typename Geometry> | |
778 | struct topological_tag_base | |
779 | { | |
780 | typedef typename tag_cast<typename tag<Geometry>::type, pointlike_tag, linear_tag, areal_tag>::type type; | |
781 | }; | |
782 | ||
783 | template <typename Geometry1, typename Geometry2, typename AssignPolicy, | |
784 | typename Tag1 = typename tag<Geometry1>::type, typename Tag2 = typename tag<Geometry2>::type, | |
785 | typename TagBase1 = typename topological_tag_base<Geometry1>::type, typename TagBase2 = typename topological_tag_base<Geometry2>::type> | |
786 | struct get_turn_info_type | |
787 | : overlay::get_turn_info<AssignPolicy> | |
788 | {}; | |
789 | ||
790 | template <typename Geometry1, typename Geometry2, typename AssignPolicy, typename Tag1, typename Tag2> | |
791 | struct get_turn_info_type<Geometry1, Geometry2, AssignPolicy, Tag1, Tag2, linear_tag, linear_tag> | |
792 | : overlay::get_turn_info_linear_linear<AssignPolicy> | |
793 | {}; | |
794 | ||
795 | template <typename Geometry1, typename Geometry2, typename AssignPolicy, typename Tag1, typename Tag2> | |
796 | struct get_turn_info_type<Geometry1, Geometry2, AssignPolicy, Tag1, Tag2, linear_tag, areal_tag> | |
797 | : overlay::get_turn_info_linear_areal<AssignPolicy> | |
798 | {}; | |
799 | ||
800 | template <typename Geometry1, typename Geometry2, typename SegmentRatio, | |
801 | typename Tag1 = typename tag<Geometry1>::type, typename Tag2 = typename tag<Geometry2>::type, | |
802 | typename TagBase1 = typename topological_tag_base<Geometry1>::type, typename TagBase2 = typename topological_tag_base<Geometry2>::type> | |
803 | struct turn_operation_type | |
804 | { | |
805 | typedef overlay::turn_operation<typename point_type<Geometry1>::type, SegmentRatio> type; | |
806 | }; | |
807 | ||
808 | template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename Tag1, typename Tag2> | |
809 | struct turn_operation_type<Geometry1, Geometry2, SegmentRatio, Tag1, Tag2, linear_tag, linear_tag> | |
810 | { | |
811 | typedef overlay::turn_operation_linear<typename point_type<Geometry1>::type, SegmentRatio> type; | |
812 | }; | |
813 | ||
814 | template <typename Geometry1, typename Geometry2, typename SegmentRatio, typename Tag1, typename Tag2> | |
815 | struct turn_operation_type<Geometry1, Geometry2, SegmentRatio, Tag1, Tag2, linear_tag, areal_tag> | |
816 | { | |
817 | typedef overlay::turn_operation_linear<typename point_type<Geometry1>::type, SegmentRatio> type; | |
818 | }; | |
819 | ||
820 | }} // namespace detail::get_turns | |
821 | #endif // DOXYGEN_NO_DETAIL | |
822 | ||
823 | ||
824 | #ifndef DOXYGEN_NO_DISPATCH | |
825 | namespace dispatch | |
826 | { | |
827 | ||
828 | // Because this is "detail" method, and most implementations will use "generic", | |
829 | // we take the freedom to derive it from "generic". | |
830 | template | |
831 | < | |
832 | typename GeometryTag1, typename GeometryTag2, | |
833 | typename Geometry1, typename Geometry2, | |
834 | bool Reverse1, bool Reverse2, | |
835 | typename TurnPolicy | |
836 | > | |
837 | struct get_turns | |
838 | : detail::get_turns::get_turns_generic | |
839 | < | |
840 | Geometry1, Geometry2, | |
841 | Reverse1, Reverse2, | |
842 | TurnPolicy | |
843 | > | |
844 | {}; | |
845 | ||
846 | ||
847 | template | |
848 | < | |
849 | typename Polygon, typename Box, | |
850 | bool ReversePolygon, bool ReverseBox, | |
851 | typename TurnPolicy | |
852 | > | |
853 | struct get_turns | |
854 | < | |
855 | polygon_tag, box_tag, | |
856 | Polygon, Box, | |
857 | ReversePolygon, ReverseBox, | |
858 | TurnPolicy | |
859 | > : detail::get_turns::get_turns_polygon_cs | |
860 | < | |
861 | Polygon, Box, | |
862 | ReversePolygon, ReverseBox, | |
863 | TurnPolicy | |
864 | > | |
865 | {}; | |
866 | ||
867 | ||
868 | template | |
869 | < | |
870 | typename Ring, typename Box, | |
871 | bool ReverseRing, bool ReverseBox, | |
872 | typename TurnPolicy | |
873 | > | |
874 | struct get_turns | |
875 | < | |
876 | ring_tag, box_tag, | |
877 | Ring, Box, | |
878 | ReverseRing, ReverseBox, | |
879 | TurnPolicy | |
880 | > : detail::get_turns::get_turns_cs | |
881 | < | |
882 | Ring, Box, ReverseRing, ReverseBox, | |
883 | TurnPolicy | |
884 | > | |
885 | ||
886 | {}; | |
887 | ||
888 | ||
889 | template | |
890 | < | |
891 | typename MultiPolygon, | |
892 | typename Box, | |
893 | bool ReverseMultiPolygon, bool ReverseBox, | |
894 | typename TurnPolicy | |
895 | > | |
896 | struct get_turns | |
897 | < | |
898 | multi_polygon_tag, box_tag, | |
899 | MultiPolygon, Box, | |
900 | ReverseMultiPolygon, ReverseBox, | |
901 | TurnPolicy | |
902 | > | |
903 | : detail::get_turns::get_turns_multi_polygon_cs | |
904 | < | |
905 | MultiPolygon, Box, | |
906 | ReverseMultiPolygon, ReverseBox, | |
907 | TurnPolicy | |
908 | > | |
909 | {}; | |
910 | ||
911 | ||
912 | template | |
913 | < | |
914 | typename GeometryTag1, typename GeometryTag2, | |
915 | typename Geometry1, typename Geometry2, | |
916 | bool Reverse1, bool Reverse2, | |
917 | typename TurnPolicy | |
918 | > | |
919 | struct get_turns_reversed | |
920 | { | |
921 | template <typename RobustPolicy, typename Turns, typename InterruptPolicy> | |
922 | static inline void apply( | |
923 | int source_id1, Geometry1 const& g1, | |
924 | int source_id2, Geometry2 const& g2, | |
925 | RobustPolicy const& robust_policy, | |
926 | Turns& turns, | |
927 | InterruptPolicy& interrupt_policy) | |
928 | { | |
929 | get_turns | |
930 | < | |
931 | GeometryTag2, GeometryTag1, | |
932 | Geometry2, Geometry1, | |
933 | Reverse2, Reverse1, | |
934 | TurnPolicy | |
935 | >::apply(source_id2, g2, source_id1, g1, robust_policy, | |
936 | turns, interrupt_policy); | |
937 | } | |
938 | }; | |
939 | ||
940 | ||
941 | } // namespace dispatch | |
942 | #endif // DOXYGEN_NO_DISPATCH | |
943 | ||
944 | ||
945 | ||
946 | /*! | |
947 | \brief \brief_calc2{turn points} | |
948 | \ingroup overlay | |
949 | \tparam Geometry1 \tparam_geometry | |
950 | \tparam Geometry2 \tparam_geometry | |
951 | \tparam Turns type of turn-container (e.g. vector of "intersection/turn point"'s) | |
952 | \param geometry1 \param_geometry | |
953 | \param geometry2 \param_geometry | |
954 | \param robust_policy policy to handle robustness issues | |
955 | \param turns container which will contain turn points | |
956 | \param interrupt_policy policy determining if process is stopped | |
957 | when intersection is found | |
958 | */ | |
959 | template | |
960 | < | |
961 | bool Reverse1, bool Reverse2, | |
962 | typename AssignPolicy, | |
963 | typename Geometry1, | |
964 | typename Geometry2, | |
965 | typename RobustPolicy, | |
966 | typename Turns, | |
967 | typename InterruptPolicy | |
968 | > | |
969 | inline void get_turns(Geometry1 const& geometry1, | |
970 | Geometry2 const& geometry2, | |
971 | RobustPolicy const& robust_policy, | |
972 | Turns& turns, | |
973 | InterruptPolicy& interrupt_policy) | |
974 | { | |
975 | concepts::check_concepts_and_equal_dimensions<Geometry1 const, Geometry2 const>(); | |
976 | ||
977 | typedef detail::overlay::get_turn_info<AssignPolicy> TurnPolicy; | |
978 | //typedef detail::get_turns::get_turn_info_type<Geometry1, Geometry2, AssignPolicy> TurnPolicy; | |
979 | ||
980 | boost::mpl::if_c | |
981 | < | |
982 | reverse_dispatch<Geometry1, Geometry2>::type::value, | |
983 | dispatch::get_turns_reversed | |
984 | < | |
985 | typename tag<Geometry1>::type, | |
986 | typename tag<Geometry2>::type, | |
987 | Geometry1, Geometry2, | |
988 | Reverse1, Reverse2, | |
989 | TurnPolicy | |
990 | >, | |
991 | dispatch::get_turns | |
992 | < | |
993 | typename tag<Geometry1>::type, | |
994 | typename tag<Geometry2>::type, | |
995 | Geometry1, Geometry2, | |
996 | Reverse1, Reverse2, | |
997 | TurnPolicy | |
998 | > | |
999 | >::type::apply( | |
1000 | 0, geometry1, | |
1001 | 1, geometry2, | |
1002 | robust_policy, | |
1003 | turns, interrupt_policy); | |
1004 | } | |
1005 | ||
1006 | #if defined(_MSC_VER) | |
1007 | #pragma warning(pop) | |
1008 | #endif | |
1009 | ||
1010 | }} // namespace boost::geometry | |
1011 | ||
1012 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURNS_HPP |