123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299 |
- // Boost.Geometry (aka GGL, Generic Geometry Library)
- // Copyright (c) 2017 Barend Gehrels, Amsterdam, the Netherlands.
- // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
- // This file was modified by Oracle on 2019.
- // Modifications copyright (c) 2019 Oracle and/or its affiliates.
- // 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_HANDLE_SELF_TURNS_HPP
- #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP
- #include <boost/range.hpp>
- #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
- #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
- #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
- #include <boost/geometry/algorithms/covered_by.hpp>
- #include <boost/geometry/algorithms/within.hpp>
- namespace boost { namespace geometry
- {
- #ifndef DOXYGEN_NO_DETAIL
- namespace detail { namespace overlay
- {
- template
- <
- typename Point, typename Geometry,
- typename Tag2 = typename geometry::tag<Geometry>::type
- >
- struct check_within_strategy
- {
- template <typename Strategy>
- static inline typename Strategy::template point_in_geometry_strategy<Point, Geometry>::type
- within(Strategy const& strategy)
- {
- return strategy.template get_point_in_geometry_strategy<Point, Geometry>();
- }
- template <typename Strategy>
- static inline typename Strategy::template point_in_geometry_strategy<Point, Geometry>::type
- covered_by(Strategy const& strategy)
- {
- return strategy.template get_point_in_geometry_strategy<Point, Geometry>();
- }
- };
- template <typename Point, typename Geometry>
- struct check_within_strategy<Point, Geometry, box_tag>
- {
- template <typename Strategy>
- static inline typename Strategy::within_point_box_strategy_type
- within(Strategy const& )
- {
- return typename Strategy::within_point_box_strategy_type();
- }
- template <typename Strategy>
- static inline typename Strategy::covered_by_point_box_strategy_type
- covered_by(Strategy const&)
- {
- return typename Strategy::covered_by_point_box_strategy_type();
- }
- };
- template <overlay_type OverlayType>
- struct check_within
- {
- template
- <
- typename Turn, typename Geometry0, typename Geometry1,
- typename UmbrellaStrategy
- >
- static inline
- bool apply(Turn const& turn, Geometry0 const& geometry0,
- Geometry1 const& geometry1, UmbrellaStrategy const& strategy)
- {
- typedef typename Turn::point_type point_type;
- // Operations 0 and 1 have the same source index in self-turns
- return turn.operations[0].seg_id.source_index == 0
- ? geometry::within(turn.point, geometry1,
- check_within_strategy<point_type, Geometry1>::within(strategy))
- : geometry::within(turn.point, geometry0,
- check_within_strategy<point_type, Geometry0>::within(strategy));
- }
- };
- template <>
- struct check_within<overlay_difference>
- {
- template
- <
- typename Turn, typename Geometry0, typename Geometry1,
- typename UmbrellaStrategy
- >
- static inline
- bool apply(Turn const& turn, Geometry0 const& geometry0,
- Geometry1 const& geometry1, UmbrellaStrategy const& strategy)
- {
- typedef typename Turn::point_type point_type;
- // difference = intersection(a, reverse(b))
- // therefore we should reverse the meaning of within for geometry1
- return turn.operations[0].seg_id.source_index == 0
- ? ! geometry::covered_by(turn.point, geometry1,
- check_within_strategy<point_type, Geometry1>::covered_by(strategy))
- : geometry::within(turn.point, geometry0,
- check_within_strategy<point_type, Geometry0>::within(strategy));
- }
- };
- struct discard_turns
- {
- template
- <
- typename Turns, typename Clusters,
- typename Geometry0, typename Geometry1,
- typename Strategy
- >
- static inline
- void apply(Turns& , Clusters const& ,
- Geometry0 const& , Geometry1 const& ,
- Strategy const& )
- {}
- };
- template <overlay_type OverlayType, operation_type OperationType>
- struct discard_closed_turns : discard_turns {};
- // It is only implemented for operation_union, not in buffer
- template <>
- struct discard_closed_turns<overlay_union, operation_union>
- {
- // Point in Geometry Strategy
- template
- <
- typename Turns, typename Clusters,
- typename Geometry0, typename Geometry1,
- typename Strategy
- >
- static inline
- void apply(Turns& turns, Clusters const& /*clusters*/,
- Geometry0 const& geometry0, Geometry1 const& geometry1,
- Strategy const& strategy)
- {
- typedef typename boost::range_value<Turns>::type turn_type;
- for (typename boost::range_iterator<Turns>::type
- it = boost::begin(turns);
- it != boost::end(turns);
- ++it)
- {
- turn_type& turn = *it;
- if (! turn.discarded
- && is_self_turn<overlay_union>(turn)
- && check_within<overlay_union>::apply(turn, geometry0,
- geometry1, strategy))
- {
- // Turn is in the interior of other geometry
- turn.discarded = true;
- }
- }
- }
- };
- template <overlay_type OverlayType>
- struct discard_self_intersection_turns
- {
- private :
- template <typename Turns, typename Clusters>
- static inline
- bool is_self_cluster(signed_size_type cluster_id,
- const Turns& turns, Clusters const& clusters)
- {
- typename Clusters::const_iterator cit = clusters.find(cluster_id);
- if (cit == clusters.end())
- {
- return false;
- }
- cluster_info const& cinfo = cit->second;
- for (std::set<signed_size_type>::const_iterator it
- = cinfo.turn_indices.begin();
- it != cinfo.turn_indices.end(); ++it)
- {
- if (! is_self_turn<OverlayType>(turns[*it]))
- {
- return false;
- }
- }
- return true;
- }
- template <typename Turns, typename Clusters,
- typename Geometry0, typename Geometry1, typename Strategy>
- static inline
- void discard_clusters(Turns& turns, Clusters const& clusters,
- Geometry0 const& geometry0, Geometry1 const& geometry1,
- Strategy const& strategy)
- {
- for (typename Clusters::const_iterator cit = clusters.begin();
- cit != clusters.end(); ++cit)
- {
- signed_size_type const cluster_id = cit->first;
- // If there are only self-turns in the cluster, the cluster should
- // be located within the other geometry, for intersection
- if (! cit->second.turn_indices.empty()
- && is_self_cluster(cluster_id, turns, clusters))
- {
- cluster_info const& cinfo = cit->second;
- signed_size_type const index = *cinfo.turn_indices.begin();
- if (! check_within<OverlayType>::apply(turns[index],
- geometry0, geometry1,
- strategy))
- {
- // Discard all turns in cluster
- for (std::set<signed_size_type>::const_iterator sit
- = cinfo.turn_indices.begin();
- sit != cinfo.turn_indices.end(); ++sit)
- {
- turns[*sit].discarded = true;
- }
- }
- }
- }
- }
- public :
- template <typename Turns, typename Clusters,
- typename Geometry0, typename Geometry1, typename Strategy>
- static inline
- void apply(Turns& turns, Clusters const& clusters,
- Geometry0 const& geometry0, Geometry1 const& geometry1,
- Strategy const& strategy)
- {
- discard_clusters(turns, clusters, geometry0, geometry1, strategy);
- typedef typename boost::range_value<Turns>::type turn_type;
- for (typename boost::range_iterator<Turns>::type
- it = boost::begin(turns);
- it != boost::end(turns);
- ++it)
- {
- turn_type& turn = *it;
- // It is a ii self-turn
- // Check if it is within the other geometry
- if (! turn.discarded
- && is_self_turn<overlay_intersection>(turn)
- && ! check_within<OverlayType>::apply(turn, geometry0,
- geometry1, strategy))
- {
- // It is not within another geometry, set it as non startable.
- // It still might be traveled (#case_recursive_boxes_70)
- turn.operations[0].enriched.startable = false;
- turn.operations[1].enriched.startable = false;
- }
- }
- }
- };
- template <overlay_type OverlayType, operation_type OperationType>
- struct discard_open_turns : discard_turns {};
- // Handler for intersection
- template <>
- struct discard_open_turns<overlay_intersection, operation_intersection>
- : discard_self_intersection_turns<overlay_intersection> {};
- // Handler for difference, with different meaning of 'within'
- template <>
- struct discard_open_turns<overlay_difference, operation_intersection>
- : discard_self_intersection_turns<overlay_difference> {};
- }} // namespace detail::overlay
- #endif //DOXYGEN_NO_DETAIL
- }} // namespace boost::geometry
- #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP
|