1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
6 // This file was modified by Oracle on 2014, 2017, 2018, 2019.
7 // Modifications copyright (c) 2014-2019 Oracle and/or its affiliates.
8 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
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)
15 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_HPP
16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_HPP
20 #include <boost/range.hpp>
21 #include <boost/mpl/assert.hpp>
23 #include <boost/geometry/algorithms/detail/point_on_border.hpp>
24 #include <boost/geometry/algorithms/detail/overlay/append_no_duplicates.hpp>
25 #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
26 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
28 #include <boost/geometry/algorithms/covered_by.hpp>
29 #include <boost/geometry/algorithms/clear.hpp>
30 #include <boost/geometry/algorithms/detail/relate/turns.hpp>
33 namespace boost { namespace geometry
37 #ifndef DOXYGEN_NO_DETAIL
38 namespace detail { namespace overlay
44 template <typename Turn, typename Operation>
45 static inline bool is_entering(Turn const& /* TODO remove this parameter */, Operation const& op)
47 // (Blocked means: blocked for polygon/polygon intersection, because
48 // they are reversed. But for polygon/line it is similar to continue)
49 return op.operation == operation_intersection
50 || op.operation == operation_continue
51 || op.operation == operation_blocked
61 typename PtInPolyStrategy
63 static inline bool last_covered_by(Turn const& /*turn*/, Operation const& op,
64 LineString const& linestring, Polygon const& polygon,
65 PtInPolyStrategy const& strategy)
67 return geometry::covered_by(range::at(linestring, op.seg_id.segment_index), polygon, strategy);
77 typename PtInPolyStrategy
79 static inline bool is_leaving(Turn const& turn, Operation const& op,
80 bool entered, bool first,
81 LineString const& linestring, Polygon const& polygon,
82 PtInPolyStrategy const& strategy)
84 if (op.operation == operation_union)
87 || turn.method == method_crosses
88 || (first && last_covered_by(turn, op, linestring, polygon, strategy))
101 typename PtInPolyStrategy
103 static inline bool is_staying_inside(Turn const& turn, Operation const& op,
104 bool entered, bool first,
105 LineString const& linestring, Polygon const& polygon,
106 PtInPolyStrategy const& strategy)
108 if (turn.method == method_crosses)
110 // The normal case, this is completely covered with entering/leaving
111 // so stay out of this time consuming "covered_by"
115 if (is_entering(turn, op))
117 return entered || (first && last_covered_by(turn, op, linestring, polygon, strategy));
129 typename PtInPolyStrategy
131 static inline bool was_entered(Turn const& turn, Operation const& op, bool first,
132 Linestring const& linestring, Polygon const& polygon,
133 PtInPolyStrategy const& strategy)
135 if (first && (turn.method == method_collinear || turn.method == method_equal))
137 return last_covered_by(turn, op, linestring, polygon, strategy);
143 // Template specialization structure to call the right actions for the right type
144 template <overlay_type OverlayType, bool RemoveSpikes = true>
145 struct action_selector
147 // If you get here the overlay type is not intersection or difference
148 // BOOST_MPL_ASSERT(false);
151 // Specialization for intersection, containing the implementation
152 template <bool RemoveSpikes>
153 struct action_selector<overlay_intersection, RemoveSpikes>
157 typename OutputIterator,
158 typename LineStringOut,
163 typename RobustPolicy
165 static inline void enter(LineStringOut& current_piece,
167 segment_identifier& segment_id,
168 signed_size_type , Point const& point,
169 Operation const& operation,
170 Strategy const& strategy,
171 RobustPolicy const& ,
174 // On enter, append the intersection point and remember starting point
175 // TODO: we don't check on spikes for linestrings (?). Consider this.
176 detail::overlay::append_no_duplicates(current_piece, point, strategy.get_equals_point_point_strategy());
177 segment_id = operation.seg_id;
182 typename OutputIterator,
183 typename LineStringOut,
188 typename RobustPolicy
190 static inline void leave(LineStringOut& current_piece,
191 LineString const& linestring,
192 segment_identifier& segment_id,
193 signed_size_type index, Point const& point,
195 Strategy const& strategy,
196 RobustPolicy const& robust_policy,
199 // On leave, copy all segments from starting point, append the intersection point
200 // and add the output piece
201 detail::copy_segments::copy_segments_linestring
204 >::apply(linestring, segment_id, index, strategy, robust_policy, current_piece);
205 detail::overlay::append_no_duplicates(current_piece, point, strategy.get_equals_point_point_strategy());
206 if (::boost::size(current_piece) > 1)
208 *out++ = current_piece;
211 geometry::clear(current_piece);
216 typename OutputIterator,
217 typename LineStringOut,
222 static inline void isolated_point(LineStringOut&,
225 signed_size_type, Point const& point,
226 Operation const& , OutputIterator& out)
228 LineStringOut isolated_point_ls;
229 geometry::append(isolated_point_ls, point);
231 #ifndef BOOST_GEOMETRY_ALLOW_ONE_POINT_LINESTRINGS
232 geometry::append(isolated_point_ls, point);
233 #endif // BOOST_GEOMETRY_ALLOW_ONE_POINT_LINESTRINGS
235 *out++ = isolated_point_ls;
238 static inline bool is_entered(bool entered)
243 static inline bool included(int inside_value)
245 return inside_value >= 0; // covered_by
250 // Specialization for difference, which reverses these actions
251 template <bool RemoveSpikes>
252 struct action_selector<overlay_difference, RemoveSpikes>
254 typedef action_selector<overlay_intersection, RemoveSpikes> normal_action;
258 typename OutputIterator,
259 typename LineStringOut,
264 typename RobustPolicy
266 static inline void enter(LineStringOut& current_piece,
267 LineString const& linestring,
268 segment_identifier& segment_id,
269 signed_size_type index, Point const& point,
270 Operation const& operation,
271 Strategy const& strategy,
272 RobustPolicy const& robust_policy,
275 normal_action::leave(current_piece, linestring, segment_id, index,
276 point, operation, strategy, robust_policy, out);
281 typename OutputIterator,
282 typename LineStringOut,
287 typename RobustPolicy
289 static inline void leave(LineStringOut& current_piece,
290 LineString const& linestring,
291 segment_identifier& segment_id,
292 signed_size_type index, Point const& point,
293 Operation const& operation,
294 Strategy const& strategy,
295 RobustPolicy const& robust_policy,
298 normal_action::enter(current_piece, linestring, segment_id, index,
299 point, operation, strategy, robust_policy, out);
304 typename OutputIterator,
305 typename LineStringOut,
310 static inline void isolated_point(LineStringOut&,
313 signed_size_type, Point const&,
314 Operation const&, OutputIterator&)
318 static inline bool is_entered(bool entered)
320 return ! normal_action::is_entered(entered);
323 static inline bool included(int inside_value)
325 return ! normal_action::included(inside_value);
333 \brief Follows a linestring from intersection point to intersection point, outputting which
334 is inside, or outside, a ring or polygon
339 typename LineStringOut,
342 overlay_type OverlayType,
343 bool RemoveSpikes = true
348 #ifdef BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
349 template <typename Turn>
350 struct sort_on_segment
352 // In case of turn point at the same location, we want to have continue/blocked LAST
353 // because that should be followed (intersection) or skipped (difference).
354 inline int operation_order(Turn const& turn) const
356 operation_type const& operation = turn.operations[0].operation;
359 case operation_opposite : return 0;
360 case operation_none : return 0;
361 case operation_union : return 1;
362 case operation_intersection : return 2;
363 case operation_blocked : return 3;
364 case operation_continue : return 4;
369 inline bool use_operation(Turn const& left, Turn const& right) const
371 // If they are the same, OK.
372 return operation_order(left) < operation_order(right);
375 inline bool use_distance(Turn const& left, Turn const& right) const
377 return left.operations[0].fraction == right.operations[0].fraction
378 ? use_operation(left, right)
379 : left.operations[0].fraction < right.operations[0].fraction
383 inline bool operator()(Turn const& left, Turn const& right) const
385 segment_identifier const& sl = left.operations[0].seg_id;
386 segment_identifier const& sr = right.operations[0].seg_id;
389 ? use_distance(left, right)
395 #endif // BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
400 static inline bool included(int inside_value)
402 return following::action_selector
404 OverlayType, RemoveSpikes
405 >::included(inside_value);
411 typename OutputIterator,
412 typename RobustPolicy,
415 static inline OutputIterator apply(LineString const& linestring, Polygon const& polygon,
416 detail::overlay::operation_type , // TODO: this parameter might be redundant
418 RobustPolicy const& robust_policy,
420 Strategy const& strategy)
422 typedef typename boost::range_iterator<Turns>::type turn_iterator;
423 typedef typename boost::range_value<Turns>::type turn_type;
424 typedef typename boost::range_iterator
426 typename turn_type::container_type
427 >::type turn_operation_iterator_type;
429 typedef following::action_selector<OverlayType, RemoveSpikes> action;
431 typedef typename Strategy::cs_tag cs_tag;
433 typename Strategy::template point_in_geometry_strategy
436 >::type const pt_in_poly_strategy
437 = strategy.template get_point_in_geometry_strategy<LineString, Polygon>();
439 // Sort intersection points on segments-along-linestring, and distance
440 // (like in enrich is done for poly/poly)
441 // sort turns by Linear seg_id, then by fraction, then
442 // for same ring id: x, u, i, c
443 // for different ring id: c, i, u, x
444 #ifdef BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
445 std::sort(boost::begin(turns), boost::end(turns), sort_on_segment<turn_type>());
447 typedef relate::turns::less
449 0, relate::turns::less_op_linear_areal_single<0>, cs_tag
451 std::sort(boost::begin(turns), boost::end(turns), turn_less());
454 LineStringOut current_piece;
455 geometry::segment_identifier current_segment_id(0, -1, -1, -1);
457 // Iterate through all intersection points (they are ordered along the line)
458 bool entered = false;
460 for (turn_iterator it = boost::begin(turns); it != boost::end(turns); ++it)
462 turn_operation_iterator_type iit = boost::begin(it->operations);
464 if (following::was_entered(*it, *iit, first, linestring, polygon, pt_in_poly_strategy))
466 debug_traverse(*it, *iit, "-> Was entered");
470 if (following::is_staying_inside(*it, *iit, entered, first, linestring, polygon, pt_in_poly_strategy))
472 debug_traverse(*it, *iit, "-> Staying inside");
476 else if (following::is_entering(*it, *iit))
478 debug_traverse(*it, *iit, "-> Entering");
481 action::enter(current_piece, linestring, current_segment_id,
482 iit->seg_id.segment_index, it->point, *iit,
483 strategy, robust_policy,
486 else if (following::is_leaving(*it, *iit, entered, first, linestring, polygon, pt_in_poly_strategy))
488 debug_traverse(*it, *iit, "-> Leaving");
491 action::leave(current_piece, linestring, current_segment_id,
492 iit->seg_id.segment_index, it->point, *iit,
493 strategy, robust_policy,
499 if (action::is_entered(entered))
501 detail::copy_segments::copy_segments_linestring
506 static_cast<signed_size_type>(boost::size(linestring) - 1),
507 strategy, robust_policy,
511 // Output the last one, if applicable
512 if (::boost::size(current_piece) > 1)
514 *out++ = current_piece;
522 }} // namespace detail::overlay
523 #endif // DOXYGEN_NO_DETAIL
526 }} // namespace boost::geometry
529 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_HPP