123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529 |
- // Boost.Geometry (aka GGL, Generic Geometry Library)
- // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
- // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
- // This file was modified by Oracle on 2014, 2017, 2018, 2019.
- // Modifications copyright (c) 2014-2019 Oracle and/or its affiliates.
- // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
- // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
- // Use, modification and distribution is subject to the Boost Software License,
- // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_HPP
- #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_HPP
- #include <cstddef>
- #include <boost/range.hpp>
- #include <boost/mpl/assert.hpp>
- #include <boost/geometry/algorithms/detail/point_on_border.hpp>
- #include <boost/geometry/algorithms/detail/overlay/append_no_duplicates.hpp>
- #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
- #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
- #include <boost/geometry/algorithms/covered_by.hpp>
- #include <boost/geometry/algorithms/clear.hpp>
- #include <boost/geometry/algorithms/detail/relate/turns.hpp>
- namespace boost { namespace geometry
- {
- #ifndef DOXYGEN_NO_DETAIL
- namespace detail { namespace overlay
- {
- namespace following
- {
- template <typename Turn, typename Operation>
- static inline bool is_entering(Turn const& /* TODO remove this parameter */, Operation const& op)
- {
- // (Blocked means: blocked for polygon/polygon intersection, because
- // they are reversed. But for polygon/line it is similar to continue)
- return op.operation == operation_intersection
- || op.operation == operation_continue
- || op.operation == operation_blocked
- ;
- }
- template
- <
- typename Turn,
- typename Operation,
- typename LineString,
- typename Polygon,
- typename PtInPolyStrategy
- >
- static inline bool last_covered_by(Turn const& /*turn*/, Operation const& op,
- LineString const& linestring, Polygon const& polygon,
- PtInPolyStrategy const& strategy)
- {
- return geometry::covered_by(range::at(linestring, op.seg_id.segment_index), polygon, strategy);
- }
- template
- <
- typename Turn,
- typename Operation,
- typename LineString,
- typename Polygon,
- typename PtInPolyStrategy
- >
- static inline bool is_leaving(Turn const& turn, Operation const& op,
- bool entered, bool first,
- LineString const& linestring, Polygon const& polygon,
- PtInPolyStrategy const& strategy)
- {
- if (op.operation == operation_union)
- {
- return entered
- || turn.method == method_crosses
- || (first && last_covered_by(turn, op, linestring, polygon, strategy))
- ;
- }
- return false;
- }
- template
- <
- typename Turn,
- typename Operation,
- typename LineString,
- typename Polygon,
- typename PtInPolyStrategy
- >
- static inline bool is_staying_inside(Turn const& turn, Operation const& op,
- bool entered, bool first,
- LineString const& linestring, Polygon const& polygon,
- PtInPolyStrategy const& strategy)
- {
- if (turn.method == method_crosses)
- {
- // The normal case, this is completely covered with entering/leaving
- // so stay out of this time consuming "covered_by"
- return false;
- }
- if (is_entering(turn, op))
- {
- return entered || (first && last_covered_by(turn, op, linestring, polygon, strategy));
- }
- return false;
- }
- template
- <
- typename Turn,
- typename Operation,
- typename Linestring,
- typename Polygon,
- typename PtInPolyStrategy
- >
- static inline bool was_entered(Turn const& turn, Operation const& op, bool first,
- Linestring const& linestring, Polygon const& polygon,
- PtInPolyStrategy const& strategy)
- {
- if (first && (turn.method == method_collinear || turn.method == method_equal))
- {
- return last_covered_by(turn, op, linestring, polygon, strategy);
- }
- return false;
- }
- // Template specialization structure to call the right actions for the right type
- template <overlay_type OverlayType, bool RemoveSpikes = true>
- struct action_selector
- {
- // If you get here the overlay type is not intersection or difference
- // BOOST_MPL_ASSERT(false);
- };
- // Specialization for intersection, containing the implementation
- template <bool RemoveSpikes>
- struct action_selector<overlay_intersection, RemoveSpikes>
- {
- template
- <
- typename OutputIterator,
- typename LineStringOut,
- typename LineString,
- typename Point,
- typename Operation,
- typename Strategy,
- typename RobustPolicy
- >
- static inline void enter(LineStringOut& current_piece,
- LineString const& ,
- segment_identifier& segment_id,
- signed_size_type , Point const& point,
- Operation const& operation,
- Strategy const& strategy,
- RobustPolicy const& ,
- OutputIterator& )
- {
- // On enter, append the intersection point and remember starting point
- // TODO: we don't check on spikes for linestrings (?). Consider this.
- detail::overlay::append_no_duplicates(current_piece, point, strategy.get_equals_point_point_strategy());
- segment_id = operation.seg_id;
- }
- template
- <
- typename OutputIterator,
- typename LineStringOut,
- typename LineString,
- typename Point,
- typename Operation,
- typename Strategy,
- typename RobustPolicy
- >
- static inline void leave(LineStringOut& current_piece,
- LineString const& linestring,
- segment_identifier& segment_id,
- signed_size_type index, Point const& point,
- Operation const& ,
- Strategy const& strategy,
- RobustPolicy const& robust_policy,
- OutputIterator& out)
- {
- // On leave, copy all segments from starting point, append the intersection point
- // and add the output piece
- detail::copy_segments::copy_segments_linestring
- <
- false, RemoveSpikes
- >::apply(linestring, segment_id, index, strategy, robust_policy, current_piece);
- detail::overlay::append_no_duplicates(current_piece, point, strategy.get_equals_point_point_strategy());
- if (::boost::size(current_piece) > 1)
- {
- *out++ = current_piece;
- }
- geometry::clear(current_piece);
- }
- template
- <
- typename OutputIterator,
- typename LineStringOut,
- typename LineString,
- typename Point,
- typename Operation
- >
- static inline void isolated_point(LineStringOut&,
- LineString const&,
- segment_identifier&,
- signed_size_type, Point const& point,
- Operation const& , OutputIterator& out)
- {
- LineStringOut isolated_point_ls;
- geometry::append(isolated_point_ls, point);
- #ifndef BOOST_GEOMETRY_ALLOW_ONE_POINT_LINESTRINGS
- geometry::append(isolated_point_ls, point);
- #endif // BOOST_GEOMETRY_ALLOW_ONE_POINT_LINESTRINGS
- *out++ = isolated_point_ls;
- }
- static inline bool is_entered(bool entered)
- {
- return entered;
- }
- static inline bool included(int inside_value)
- {
- return inside_value >= 0; // covered_by
- }
- };
- // Specialization for difference, which reverses these actions
- template <bool RemoveSpikes>
- struct action_selector<overlay_difference, RemoveSpikes>
- {
- typedef action_selector<overlay_intersection, RemoveSpikes> normal_action;
- template
- <
- typename OutputIterator,
- typename LineStringOut,
- typename LineString,
- typename Point,
- typename Operation,
- typename Strategy,
- typename RobustPolicy
- >
- static inline void enter(LineStringOut& current_piece,
- LineString const& linestring,
- segment_identifier& segment_id,
- signed_size_type index, Point const& point,
- Operation const& operation,
- Strategy const& strategy,
- RobustPolicy const& robust_policy,
- OutputIterator& out)
- {
- normal_action::leave(current_piece, linestring, segment_id, index,
- point, operation, strategy, robust_policy, out);
- }
- template
- <
- typename OutputIterator,
- typename LineStringOut,
- typename LineString,
- typename Point,
- typename Operation,
- typename Strategy,
- typename RobustPolicy
- >
- static inline void leave(LineStringOut& current_piece,
- LineString const& linestring,
- segment_identifier& segment_id,
- signed_size_type index, Point const& point,
- Operation const& operation,
- Strategy const& strategy,
- RobustPolicy const& robust_policy,
- OutputIterator& out)
- {
- normal_action::enter(current_piece, linestring, segment_id, index,
- point, operation, strategy, robust_policy, out);
- }
- template
- <
- typename OutputIterator,
- typename LineStringOut,
- typename LineString,
- typename Point,
- typename Operation
- >
- static inline void isolated_point(LineStringOut&,
- LineString const&,
- segment_identifier&,
- signed_size_type, Point const&,
- Operation const&, OutputIterator&)
- {
- }
- static inline bool is_entered(bool entered)
- {
- return ! normal_action::is_entered(entered);
- }
- static inline bool included(int inside_value)
- {
- return ! normal_action::included(inside_value);
- }
- };
- }
- /*!
- \brief Follows a linestring from intersection point to intersection point, outputting which
- is inside, or outside, a ring or polygon
- \ingroup overlay
- */
- template
- <
- typename LineStringOut,
- typename LineString,
- typename Polygon,
- overlay_type OverlayType,
- bool RemoveSpikes = true
- >
- class follow
- {
- #ifdef BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
- template <typename Turn>
- struct sort_on_segment
- {
- // In case of turn point at the same location, we want to have continue/blocked LAST
- // because that should be followed (intersection) or skipped (difference).
- inline int operation_order(Turn const& turn) const
- {
- operation_type const& operation = turn.operations[0].operation;
- switch(operation)
- {
- case operation_opposite : return 0;
- case operation_none : return 0;
- case operation_union : return 1;
- case operation_intersection : return 2;
- case operation_blocked : return 3;
- case operation_continue : return 4;
- }
- return -1;
- };
- inline bool use_operation(Turn const& left, Turn const& right) const
- {
- // If they are the same, OK.
- return operation_order(left) < operation_order(right);
- }
- inline bool use_distance(Turn const& left, Turn const& right) const
- {
- return left.operations[0].fraction == right.operations[0].fraction
- ? use_operation(left, right)
- : left.operations[0].fraction < right.operations[0].fraction
- ;
- }
- inline bool operator()(Turn const& left, Turn const& right) const
- {
- segment_identifier const& sl = left.operations[0].seg_id;
- segment_identifier const& sr = right.operations[0].seg_id;
- return sl == sr
- ? use_distance(left, right)
- : sl < sr
- ;
- }
- };
- #endif // BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
- public :
- static inline bool included(int inside_value)
- {
- return following::action_selector
- <
- OverlayType, RemoveSpikes
- >::included(inside_value);
- }
- template
- <
- typename Turns,
- typename OutputIterator,
- typename RobustPolicy,
- typename Strategy
- >
- static inline OutputIterator apply(LineString const& linestring, Polygon const& polygon,
- detail::overlay::operation_type , // TODO: this parameter might be redundant
- Turns& turns,
- RobustPolicy const& robust_policy,
- OutputIterator out,
- Strategy const& strategy)
- {
- typedef typename boost::range_iterator<Turns>::type turn_iterator;
- typedef typename boost::range_value<Turns>::type turn_type;
- typedef typename boost::range_iterator
- <
- typename turn_type::container_type
- >::type turn_operation_iterator_type;
- typedef following::action_selector<OverlayType, RemoveSpikes> action;
- typedef typename Strategy::cs_tag cs_tag;
- typename Strategy::template point_in_geometry_strategy
- <
- LineString, Polygon
- >::type const pt_in_poly_strategy
- = strategy.template get_point_in_geometry_strategy<LineString, Polygon>();
- // Sort intersection points on segments-along-linestring, and distance
- // (like in enrich is done for poly/poly)
- // sort turns by Linear seg_id, then by fraction, then
- // for same ring id: x, u, i, c
- // for different ring id: c, i, u, x
- #ifdef BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
- std::sort(boost::begin(turns), boost::end(turns), sort_on_segment<turn_type>());
- #else
- typedef relate::turns::less
- <
- 0, relate::turns::less_op_linear_areal_single<0>, cs_tag
- > turn_less;
- std::sort(boost::begin(turns), boost::end(turns), turn_less());
- #endif
- LineStringOut current_piece;
- geometry::segment_identifier current_segment_id(0, -1, -1, -1);
- // Iterate through all intersection points (they are ordered along the line)
- bool entered = false;
- bool first = true;
- for (turn_iterator it = boost::begin(turns); it != boost::end(turns); ++it)
- {
- turn_operation_iterator_type iit = boost::begin(it->operations);
- if (following::was_entered(*it, *iit, first, linestring, polygon, pt_in_poly_strategy))
- {
- debug_traverse(*it, *iit, "-> Was entered");
- entered = true;
- }
- if (following::is_staying_inside(*it, *iit, entered, first, linestring, polygon, pt_in_poly_strategy))
- {
- debug_traverse(*it, *iit, "-> Staying inside");
- entered = true;
- }
- else if (following::is_entering(*it, *iit))
- {
- debug_traverse(*it, *iit, "-> Entering");
- entered = true;
- action::enter(current_piece, linestring, current_segment_id,
- iit->seg_id.segment_index, it->point, *iit,
- strategy, robust_policy,
- out);
- }
- else if (following::is_leaving(*it, *iit, entered, first, linestring, polygon, pt_in_poly_strategy))
- {
- debug_traverse(*it, *iit, "-> Leaving");
- entered = false;
- action::leave(current_piece, linestring, current_segment_id,
- iit->seg_id.segment_index, it->point, *iit,
- strategy, robust_policy,
- out);
- }
- first = false;
- }
- if (action::is_entered(entered))
- {
- detail::copy_segments::copy_segments_linestring
- <
- false, RemoveSpikes
- >::apply(linestring,
- current_segment_id,
- static_cast<signed_size_type>(boost::size(linestring) - 1),
- strategy, robust_policy,
- current_piece);
- }
- // Output the last one, if applicable
- if (::boost::size(current_piece) > 1)
- {
- *out++ = current_piece;
- }
- return out;
- }
- };
- }} // namespace detail::overlay
- #endif // DOXYGEN_NO_DETAIL
- }} // namespace boost::geometry
- #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_HPP
|