1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2017 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
6 // This file was modified by Oracle on 2019.
7 // Modifications copyright (c) 2019 Oracle and/or its affiliates.
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_HANDLE_SELF_TURNS_HPP
16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP
18 #include <boost/range.hpp>
20 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
21 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
22 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
23 #include <boost/geometry/algorithms/covered_by.hpp>
24 #include <boost/geometry/algorithms/within.hpp>
26 namespace boost { namespace geometry
29 #ifndef DOXYGEN_NO_DETAIL
30 namespace detail { namespace overlay
36 typename Point, typename Geometry,
37 typename Tag2 = typename geometry::tag<Geometry>::type
39 struct check_within_strategy
41 template <typename Strategy>
42 static inline typename Strategy::template point_in_geometry_strategy<Point, Geometry>::type
43 within(Strategy const& strategy)
45 return strategy.template get_point_in_geometry_strategy<Point, Geometry>();
48 template <typename Strategy>
49 static inline typename Strategy::template point_in_geometry_strategy<Point, Geometry>::type
50 covered_by(Strategy const& strategy)
52 return strategy.template get_point_in_geometry_strategy<Point, Geometry>();
56 template <typename Point, typename Geometry>
57 struct check_within_strategy<Point, Geometry, box_tag>
59 template <typename Strategy>
60 static inline typename Strategy::within_point_box_strategy_type
61 within(Strategy const& )
63 return typename Strategy::within_point_box_strategy_type();
66 template <typename Strategy>
67 static inline typename Strategy::covered_by_point_box_strategy_type
68 covered_by(Strategy const&)
70 return typename Strategy::covered_by_point_box_strategy_type();
75 template <overlay_type OverlayType>
80 typename Turn, typename Geometry0, typename Geometry1,
81 typename UmbrellaStrategy
84 bool apply(Turn const& turn, Geometry0 const& geometry0,
85 Geometry1 const& geometry1, UmbrellaStrategy const& strategy)
87 typedef typename Turn::point_type point_type;
89 // Operations 0 and 1 have the same source index in self-turns
90 return turn.operations[0].seg_id.source_index == 0
91 ? geometry::within(turn.point, geometry1,
92 check_within_strategy<point_type, Geometry1>::within(strategy))
93 : geometry::within(turn.point, geometry0,
94 check_within_strategy<point_type, Geometry0>::within(strategy));
100 struct check_within<overlay_difference>
104 typename Turn, typename Geometry0, typename Geometry1,
105 typename UmbrellaStrategy
108 bool apply(Turn const& turn, Geometry0 const& geometry0,
109 Geometry1 const& geometry1, UmbrellaStrategy const& strategy)
111 typedef typename Turn::point_type point_type;
113 // difference = intersection(a, reverse(b))
114 // therefore we should reverse the meaning of within for geometry1
115 return turn.operations[0].seg_id.source_index == 0
116 ? ! geometry::covered_by(turn.point, geometry1,
117 check_within_strategy<point_type, Geometry1>::covered_by(strategy))
118 : geometry::within(turn.point, geometry0,
119 check_within_strategy<point_type, Geometry0>::within(strategy));
127 typename Turns, typename Clusters,
128 typename Geometry0, typename Geometry1,
132 void apply(Turns& , Clusters const& ,
133 Geometry0 const& , Geometry1 const& ,
138 template <overlay_type OverlayType, operation_type OperationType>
139 struct discard_closed_turns : discard_turns {};
141 // It is only implemented for operation_union, not in buffer
143 struct discard_closed_turns<overlay_union, operation_union>
145 // Point in Geometry Strategy
148 typename Turns, typename Clusters,
149 typename Geometry0, typename Geometry1,
153 void apply(Turns& turns, Clusters const& /*clusters*/,
154 Geometry0 const& geometry0, Geometry1 const& geometry1,
155 Strategy const& strategy)
157 typedef typename boost::range_value<Turns>::type turn_type;
159 for (typename boost::range_iterator<Turns>::type
160 it = boost::begin(turns);
161 it != boost::end(turns);
164 turn_type& turn = *it;
167 && is_self_turn<overlay_union>(turn)
168 && check_within<overlay_union>::apply(turn, geometry0,
169 geometry1, strategy))
171 // Turn is in the interior of other geometry
172 turn.discarded = true;
178 template <overlay_type OverlayType>
179 struct discard_self_intersection_turns
183 template <typename Turns, typename Clusters>
185 bool is_self_cluster(signed_size_type cluster_id,
186 const Turns& turns, Clusters const& clusters)
188 typename Clusters::const_iterator cit = clusters.find(cluster_id);
189 if (cit == clusters.end())
194 cluster_info const& cinfo = cit->second;
195 for (std::set<signed_size_type>::const_iterator it
196 = cinfo.turn_indices.begin();
197 it != cinfo.turn_indices.end(); ++it)
199 if (! is_self_turn<OverlayType>(turns[*it]))
208 template <typename Turns, typename Clusters,
209 typename Geometry0, typename Geometry1, typename Strategy>
211 void discard_clusters(Turns& turns, Clusters const& clusters,
212 Geometry0 const& geometry0, Geometry1 const& geometry1,
213 Strategy const& strategy)
215 for (typename Clusters::const_iterator cit = clusters.begin();
216 cit != clusters.end(); ++cit)
218 signed_size_type const cluster_id = cit->first;
220 // If there are only self-turns in the cluster, the cluster should
221 // be located within the other geometry, for intersection
222 if (! cit->second.turn_indices.empty()
223 && is_self_cluster(cluster_id, turns, clusters))
225 cluster_info const& cinfo = cit->second;
226 signed_size_type const index = *cinfo.turn_indices.begin();
227 if (! check_within<OverlayType>::apply(turns[index],
228 geometry0, geometry1,
231 // Discard all turns in cluster
232 for (std::set<signed_size_type>::const_iterator sit
233 = cinfo.turn_indices.begin();
234 sit != cinfo.turn_indices.end(); ++sit)
236 turns[*sit].discarded = true;
245 template <typename Turns, typename Clusters,
246 typename Geometry0, typename Geometry1, typename Strategy>
248 void apply(Turns& turns, Clusters const& clusters,
249 Geometry0 const& geometry0, Geometry1 const& geometry1,
250 Strategy const& strategy)
252 discard_clusters(turns, clusters, geometry0, geometry1, strategy);
254 typedef typename boost::range_value<Turns>::type turn_type;
256 for (typename boost::range_iterator<Turns>::type
257 it = boost::begin(turns);
258 it != boost::end(turns);
261 turn_type& turn = *it;
263 // It is a ii self-turn
264 // Check if it is within the other geometry
266 && is_self_turn<overlay_intersection>(turn)
267 && ! check_within<OverlayType>::apply(turn, geometry0,
268 geometry1, strategy))
270 // It is not within another geometry, set it as non startable.
271 // It still might be traveled (#case_recursive_boxes_70)
272 turn.operations[0].enriched.startable = false;
273 turn.operations[1].enriched.startable = false;
280 template <overlay_type OverlayType, operation_type OperationType>
281 struct discard_open_turns : discard_turns {};
283 // Handler for intersection
285 struct discard_open_turns<overlay_intersection, operation_intersection>
286 : discard_self_intersection_turns<overlay_intersection> {};
288 // Handler for difference, with different meaning of 'within'
290 struct discard_open_turns<overlay_difference, operation_intersection>
291 : discard_self_intersection_turns<overlay_difference> {};
293 }} // namespace detail::overlay
294 #endif //DOXYGEN_NO_DETAIL
297 }} // namespace boost::geometry
299 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP