1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
5 // Copyright (c) 2014-2020, Oracle and/or its affiliates.
7 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
10 // Licensed under the Boost Software License version 1.0.
11 // http://www.boost.org/users/license.html
14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_LINEAR_LINEAR_HPP
15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_LINEAR_LINEAR_HPP
21 #include <boost/range.hpp>
22 #include <boost/throw_exception.hpp>
24 #include <boost/geometry/core/assert.hpp>
25 #include <boost/geometry/core/tag.hpp>
26 #include <boost/geometry/core/tags.hpp>
28 #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
29 #include <boost/geometry/algorithms/detail/overlay/follow.hpp>
30 #include <boost/geometry/algorithms/detail/overlay/inconsistent_turns_exception.hpp>
31 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
32 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
33 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
35 #include <boost/geometry/algorithms/detail/turns/debug_turn.hpp>
37 #include <boost/geometry/algorithms/detail/tupled_output.hpp>
39 #include <boost/geometry/algorithms/convert.hpp>
40 #include <boost/geometry/algorithms/not_implemented.hpp>
43 namespace boost { namespace geometry
46 #ifndef DOXYGEN_NO_DETAIL
47 namespace detail { namespace overlay
50 namespace following { namespace linear
56 // follower for linear/linear geometries set operations
58 template <typename Turn, typename Operation>
59 static inline bool is_entering(Turn const& turn,
60 Operation const& operation)
62 if ( turn.method != method_touch && turn.method != method_touch_interior )
66 return operation.operation == operation_intersection;
71 template <typename Turn, typename Operation>
72 static inline bool is_staying_inside(Turn const& turn,
73 Operation const& operation,
81 if ( turn.method != method_equal && turn.method != method_collinear )
85 return operation.operation == operation_continue;
90 template <typename Turn, typename Operation>
91 static inline bool is_leaving(Turn const& turn,
92 Operation const& operation,
100 if ( turn.method != method_touch
101 && turn.method != method_touch_interior
102 && turn.method != method_equal
103 && turn.method != method_collinear )
108 if ( operation.operation == operation_blocked )
113 if ( operation.operation != operation_union )
118 return operation.is_collinear;
123 template <typename Turn, typename Operation>
124 static inline bool is_isolated_point(Turn const& turn,
125 Operation const& operation,
133 if ( turn.method == method_none )
135 BOOST_GEOMETRY_ASSERT( operation.operation == operation_continue );
139 if ( turn.method == method_crosses )
144 if ( turn.method != method_touch && turn.method != method_touch_interior )
149 if ( operation.operation == operation_blocked )
154 if ( operation.operation != operation_union )
159 return !operation.is_collinear;
166 // GeometryOut - linestring or tuple of at least point and linestring
169 typename GeometryOut,
172 overlay_type OverlayType,
173 bool FollowIsolatedPoints,
174 bool FollowContinueTurns
176 class follow_linestring_linear
179 // allow spikes (false indicates: do not remove spikes)
180 typedef following::action_selector<OverlayType, false> action;
182 typedef geometry::detail::output_geometry_access
184 GeometryOut, linestring_tag, linestring_tag
186 typedef geometry::detail::output_geometry_access
188 GeometryOut, point_tag, linestring_tag
193 typename TurnIterator,
194 typename TurnOperationIterator,
195 typename LinestringOut,
196 typename SegmentIdentifier,
197 typename OutputIterator,
198 typename SideStrategy
200 static inline OutputIterator
201 process_turn(TurnIterator it,
202 TurnOperationIterator op_it,
204 std::size_t& enter_count,
205 Linestring const& linestring,
206 LinestringOut& current_piece,
207 SegmentIdentifier& current_segment_id,
209 SideStrategy const& strategy)
211 // We don't rescale linear/linear
212 detail::no_rescale_policy robust_policy;
214 if ( is_entering(*it, *op_it) )
216 detail::turns::debug_turn(*it, *op_it, "-> Entering");
219 if ( enter_count == 0 )
221 action::enter(current_piece,
224 op_it->seg_id.segment_index,
225 it->point, *op_it, strategy, robust_policy,
230 else if ( is_leaving(*it, *op_it, entered) )
232 detail::turns::debug_turn(*it, *op_it, "-> Leaving");
235 if ( enter_count == 0 )
238 action::leave(current_piece,
241 op_it->seg_id.segment_index,
242 it->point, *op_it, strategy, robust_policy,
246 else if ( FollowIsolatedPoints
247 && is_isolated_point(*it, *op_it, entered) )
249 detail::turns::debug_turn(*it, *op_it, "-> Isolated point");
251 action::template isolated_point
253 typename pointlike::type
254 >(it->point, pointlike::get(oit));
256 else if ( FollowContinueTurns
257 && is_staying_inside(*it, *op_it, entered) )
259 detail::turns::debug_turn(*it, *op_it, "-> Staying inside");
268 typename SegmentIdentifier,
269 typename LinestringOut,
270 typename OutputIterator,
271 typename SideStrategy
273 static inline OutputIterator
274 process_end(bool entered,
275 Linestring const& linestring,
276 SegmentIdentifier const& current_segment_id,
277 LinestringOut& current_piece,
279 SideStrategy const& strategy)
281 if ( action::is_entered(entered) )
283 // We don't rescale linear/linear
284 detail::no_rescale_policy robust_policy;
286 detail::copy_segments::copy_segments_linestring
288 false, false // do not reverse; do not remove spikes
291 static_cast<signed_size_type>(boost::size(linestring) - 1),
297 // Output the last one, if applicable
298 if (::boost::size(current_piece) > 1)
300 *linear::get(oit)++ = current_piece;
307 template <typename TurnIterator, typename OutputIterator, typename SideStrategy>
308 static inline OutputIterator
309 apply(Linestring const& linestring, Linear const&,
310 TurnIterator first, TurnIterator beyond,
312 SideStrategy const& strategy)
314 // Iterate through all intersection points (they are
315 // ordered along the each line)
317 typename linear::type current_piece;
318 geometry::segment_identifier current_segment_id(0, -1, -1, -1);
320 bool entered = false;
321 std::size_t enter_count = 0;
323 for (TurnIterator it = first; it != beyond; ++it)
325 oit = process_turn(it, boost::begin(it->operations),
326 entered, enter_count,
328 current_piece, current_segment_id,
333 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
334 if (enter_count != 0)
336 BOOST_THROW_EXCEPTION(inconsistent_turns_exception());
339 BOOST_GEOMETRY_ASSERT(enter_count == 0);
342 return process_end(entered, linestring,
343 current_segment_id, current_piece,
354 typename LinestringOut,
355 typename MultiLinestring,
357 overlay_type OverlayType,
358 bool FollowIsolatedPoints,
359 bool FollowContinueTurns
361 class follow_multilinestring_linear
362 : follow_linestring_linear
365 typename boost::range_value<MultiLinestring>::type,
368 FollowIsolatedPoints,
373 typedef typename boost::range_value<MultiLinestring>::type Linestring;
375 typedef follow_linestring_linear
377 LinestringOut, Linestring, Linear,
378 OverlayType, FollowIsolatedPoints, FollowContinueTurns
381 typedef following::action_selector<OverlayType> action;
383 typedef typename boost::range_iterator
385 MultiLinestring const
386 >::type linestring_iterator;
389 template <typename OutputIt, overlay_type OT>
390 struct copy_linestrings_in_range
392 static inline OutputIt
393 apply(linestring_iterator, linestring_iterator, OutputIt oit)
399 template <typename OutputIt>
400 struct copy_linestrings_in_range<OutputIt, overlay_difference>
402 static inline OutputIt
403 apply(linestring_iterator first, linestring_iterator beyond,
406 for (linestring_iterator ls_it = first; ls_it != beyond; ++ls_it)
408 LinestringOut line_out;
409 geometry::convert(*ls_it, line_out);
416 template <typename TurnIterator>
417 static inline signed_size_type get_multi_index(TurnIterator it)
419 return boost::begin(it->operations)->seg_id.multi_index;
422 class has_other_multi_id
425 signed_size_type m_multi_id;
428 has_other_multi_id(signed_size_type multi_id)
429 : m_multi_id(multi_id) {}
431 template <typename Turn>
432 bool operator()(Turn const& turn) const
434 return boost::begin(turn.operations)->seg_id.multi_index
440 template <typename TurnIterator, typename OutputIterator, typename SideStrategy>
441 static inline OutputIterator
442 apply(MultiLinestring const& multilinestring, Linear const& linear,
443 TurnIterator first, TurnIterator beyond,
445 SideStrategy const& strategy)
447 BOOST_GEOMETRY_ASSERT( first != beyond );
449 typedef copy_linestrings_in_range
451 OutputIterator, OverlayType
454 linestring_iterator ls_first = boost::begin(multilinestring);
455 linestring_iterator ls_beyond = boost::end(multilinestring);
457 // Iterate through all intersection points (they are
458 // ordered along the each linestring)
460 signed_size_type current_multi_id = get_multi_index(first);
462 oit = copy_linestrings::apply(ls_first,
463 ls_first + current_multi_id,
466 TurnIterator per_ls_next = first;
468 TurnIterator per_ls_current = per_ls_next;
470 // find turn with different multi-index
471 per_ls_next = std::find_if(per_ls_current, beyond,
472 has_other_multi_id(current_multi_id));
474 oit = Base::apply(*(ls_first + current_multi_id),
475 linear, per_ls_current, per_ls_next, oit, strategy);
477 signed_size_type next_multi_id = -1;
478 linestring_iterator ls_next = ls_beyond;
479 if ( per_ls_next != beyond )
481 next_multi_id = get_multi_index(per_ls_next);
482 ls_next = ls_first + next_multi_id;
484 oit = copy_linestrings::apply(ls_first + current_multi_id + 1,
488 current_multi_id = next_multi_id;
490 while ( per_ls_next != beyond );
503 typename LinestringOut,
506 overlay_type OverlayType,
507 bool FollowIsolatedPoints,
508 bool FollowContinueTurns,
509 typename TagIn1 = typename tag<Geometry1>::type
512 : not_implemented<Geometry1>
519 typename LinestringOut,
522 overlay_type OverlayType,
523 bool FollowIsolatedPoints,
524 bool FollowContinueTurns
528 LinestringOut, Linestring, Linear,
529 OverlayType, FollowIsolatedPoints, FollowContinueTurns,
531 > : follow_linestring_linear
533 LinestringOut, Linestring, Linear,
534 OverlayType, FollowIsolatedPoints, FollowContinueTurns
541 typename LinestringOut,
542 typename MultiLinestring,
544 overlay_type OverlayType,
545 bool FollowIsolatedPoints,
546 bool FollowContinueTurns
550 LinestringOut, MultiLinestring, Linear,
551 OverlayType, FollowIsolatedPoints, FollowContinueTurns,
553 > : follow_multilinestring_linear
555 LinestringOut, MultiLinestring, Linear,
556 OverlayType, FollowIsolatedPoints, FollowContinueTurns
562 }} // namespace following::linear
564 }} // namespace detail::overlay
565 #endif // DOXYGEN_NO_DETAIL
567 }} // namespace boost::geometry
570 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_LINEAR_LINEAR_HPP