]>
Commit | Line | Data |
---|---|---|
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) | |
2 | ||
3 | // Copyright (c) 2017 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland. | |
5 | ||
6 | // This file was modified by Oracle on 2019-2020. | |
7 | // Modifications copyright (c) 2019-2020 Oracle and/or its affiliates. | |
8 | ||
9 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
10 | ||
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) | |
14 | ||
15 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP | |
16 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP | |
17 | ||
18 | #include <boost/range/begin.hpp> | |
19 | #include <boost/range/end.hpp> | |
20 | #include <boost/range/value_type.hpp> | |
21 | ||
22 | #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp> | |
23 | #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp> | |
24 | #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp> | |
25 | #include <boost/geometry/algorithms/covered_by.hpp> | |
26 | #include <boost/geometry/algorithms/within.hpp> | |
27 | ||
28 | namespace boost { namespace geometry | |
29 | { | |
30 | ||
31 | #ifndef DOXYGEN_NO_DETAIL | |
32 | namespace detail { namespace overlay | |
33 | { | |
34 | ||
35 | ||
36 | template | |
37 | < | |
38 | typename Point, typename Geometry, | |
39 | typename Tag2 = typename geometry::tag<Geometry>::type | |
40 | > | |
41 | struct check_within_strategy | |
42 | { | |
43 | template <typename Strategy> | |
44 | static inline typename Strategy::template point_in_geometry_strategy<Point, Geometry>::type | |
45 | within(Strategy const& strategy) | |
46 | { | |
47 | return strategy.template get_point_in_geometry_strategy<Point, Geometry>(); | |
48 | } | |
49 | ||
50 | template <typename Strategy> | |
51 | static inline typename Strategy::template point_in_geometry_strategy<Point, Geometry>::type | |
52 | covered_by(Strategy const& strategy) | |
53 | { | |
54 | return strategy.template get_point_in_geometry_strategy<Point, Geometry>(); | |
55 | } | |
56 | }; | |
57 | ||
58 | template <typename Point, typename Geometry> | |
59 | struct check_within_strategy<Point, Geometry, box_tag> | |
60 | { | |
61 | template <typename Strategy> | |
62 | static inline typename Strategy::within_point_box_strategy_type | |
63 | within(Strategy const& ) | |
64 | { | |
65 | return typename Strategy::within_point_box_strategy_type(); | |
66 | } | |
67 | ||
68 | template <typename Strategy> | |
69 | static inline typename Strategy::covered_by_point_box_strategy_type | |
70 | covered_by(Strategy const&) | |
71 | { | |
72 | return typename Strategy::covered_by_point_box_strategy_type(); | |
73 | } | |
74 | }; | |
75 | ||
76 | ||
77 | template <overlay_type OverlayType> | |
78 | struct check_within | |
79 | { | |
80 | template | |
81 | < | |
82 | typename Turn, typename Geometry0, typename Geometry1, | |
83 | typename UmbrellaStrategy | |
84 | > | |
85 | static inline | |
86 | bool apply(Turn const& turn, Geometry0 const& geometry0, | |
87 | Geometry1 const& geometry1, UmbrellaStrategy const& strategy) | |
88 | { | |
89 | typedef typename Turn::point_type point_type; | |
90 | ||
91 | // Operations 0 and 1 have the same source index in self-turns | |
92 | return turn.operations[0].seg_id.source_index == 0 | |
93 | ? geometry::within(turn.point, geometry1, | |
94 | check_within_strategy<point_type, Geometry1>::within(strategy)) | |
95 | : geometry::within(turn.point, geometry0, | |
96 | check_within_strategy<point_type, Geometry0>::within(strategy)); | |
97 | } | |
98 | ||
99 | }; | |
100 | ||
101 | template <> | |
102 | struct check_within<overlay_difference> | |
103 | { | |
104 | template | |
105 | < | |
106 | typename Turn, typename Geometry0, typename Geometry1, | |
107 | typename UmbrellaStrategy | |
108 | > | |
109 | static inline | |
110 | bool apply(Turn const& turn, Geometry0 const& geometry0, | |
111 | Geometry1 const& geometry1, UmbrellaStrategy const& strategy) | |
112 | { | |
113 | typedef typename Turn::point_type point_type; | |
114 | ||
115 | // difference = intersection(a, reverse(b)) | |
116 | // therefore we should reverse the meaning of within for geometry1 | |
117 | return turn.operations[0].seg_id.source_index == 0 | |
118 | ? ! geometry::covered_by(turn.point, geometry1, | |
119 | check_within_strategy<point_type, Geometry1>::covered_by(strategy)) | |
120 | : geometry::within(turn.point, geometry0, | |
121 | check_within_strategy<point_type, Geometry0>::within(strategy)); | |
122 | } | |
123 | }; | |
124 | ||
125 | struct discard_turns | |
126 | { | |
127 | template | |
128 | < | |
129 | typename Turns, typename Clusters, | |
130 | typename Geometry0, typename Geometry1, | |
131 | typename Strategy | |
132 | > | |
133 | static inline | |
134 | void apply(Turns& , Clusters const& , | |
135 | Geometry0 const& , Geometry1 const& , | |
136 | Strategy const& ) | |
137 | {} | |
138 | }; | |
139 | ||
140 | template <overlay_type OverlayType, operation_type OperationType> | |
141 | struct discard_closed_turns : discard_turns {}; | |
142 | ||
143 | // It is only implemented for operation_union, not in buffer | |
144 | template <> | |
145 | struct discard_closed_turns<overlay_union, operation_union> | |
146 | { | |
147 | // Point in Geometry Strategy | |
148 | template | |
149 | < | |
150 | typename Turns, typename Clusters, | |
151 | typename Geometry0, typename Geometry1, | |
152 | typename Strategy | |
153 | > | |
154 | static inline | |
155 | void apply(Turns& turns, Clusters const& /*clusters*/, | |
156 | Geometry0 const& geometry0, Geometry1 const& geometry1, | |
157 | Strategy const& strategy) | |
158 | { | |
159 | typedef typename boost::range_value<Turns>::type turn_type; | |
160 | ||
161 | for (typename boost::range_iterator<Turns>::type | |
162 | it = boost::begin(turns); | |
163 | it != boost::end(turns); | |
164 | ++it) | |
165 | { | |
166 | turn_type& turn = *it; | |
167 | ||
168 | if (! turn.discarded | |
169 | && is_self_turn<overlay_union>(turn) | |
170 | && check_within<overlay_union>::apply(turn, geometry0, | |
171 | geometry1, strategy)) | |
172 | { | |
173 | // Turn is in the interior of other geometry | |
174 | turn.discarded = true; | |
175 | } | |
176 | } | |
177 | } | |
178 | }; | |
179 | ||
180 | template <overlay_type OverlayType> | |
181 | struct discard_self_intersection_turns | |
182 | { | |
183 | private : | |
184 | ||
185 | template <typename Turns, typename Clusters> | |
186 | static inline | |
187 | bool is_self_cluster(signed_size_type cluster_id, | |
188 | const Turns& turns, Clusters const& clusters) | |
189 | { | |
190 | typename Clusters::const_iterator cit = clusters.find(cluster_id); | |
191 | if (cit == clusters.end()) | |
192 | { | |
193 | return false; | |
194 | } | |
195 | ||
196 | cluster_info const& cinfo = cit->second; | |
197 | for (std::set<signed_size_type>::const_iterator it | |
198 | = cinfo.turn_indices.begin(); | |
199 | it != cinfo.turn_indices.end(); ++it) | |
200 | { | |
201 | if (! is_self_turn<OverlayType>(turns[*it])) | |
202 | { | |
203 | return false; | |
204 | } | |
205 | } | |
206 | ||
207 | return true; | |
208 | } | |
209 | ||
210 | template <typename Turns, typename Clusters, | |
211 | typename Geometry0, typename Geometry1, typename Strategy> | |
212 | static inline | |
213 | void discard_clusters(Turns& turns, Clusters const& clusters, | |
214 | Geometry0 const& geometry0, Geometry1 const& geometry1, | |
215 | Strategy const& strategy) | |
216 | { | |
217 | for (typename Clusters::const_iterator cit = clusters.begin(); | |
218 | cit != clusters.end(); ++cit) | |
219 | { | |
220 | signed_size_type const cluster_id = cit->first; | |
221 | ||
222 | // If there are only self-turns in the cluster, the cluster should | |
223 | // be located within the other geometry, for intersection | |
224 | if (! cit->second.turn_indices.empty() | |
225 | && is_self_cluster(cluster_id, turns, clusters)) | |
226 | { | |
227 | cluster_info const& cinfo = cit->second; | |
228 | signed_size_type const index = *cinfo.turn_indices.begin(); | |
229 | if (! check_within<OverlayType>::apply(turns[index], | |
230 | geometry0, geometry1, | |
231 | strategy)) | |
232 | { | |
233 | // Discard all turns in cluster | |
234 | for (std::set<signed_size_type>::const_iterator sit | |
235 | = cinfo.turn_indices.begin(); | |
236 | sit != cinfo.turn_indices.end(); ++sit) | |
237 | { | |
238 | turns[*sit].discarded = true; | |
239 | } | |
240 | } | |
241 | } | |
242 | } | |
243 | } | |
244 | ||
245 | public : | |
246 | ||
247 | template <typename Turns, typename Clusters, | |
248 | typename Geometry0, typename Geometry1, typename Strategy> | |
249 | static inline | |
250 | void apply(Turns& turns, Clusters const& clusters, | |
251 | Geometry0 const& geometry0, Geometry1 const& geometry1, | |
252 | Strategy const& strategy) | |
253 | { | |
254 | discard_clusters(turns, clusters, geometry0, geometry1, strategy); | |
255 | ||
256 | typedef typename boost::range_value<Turns>::type turn_type; | |
257 | ||
258 | for (typename boost::range_iterator<Turns>::type | |
259 | it = boost::begin(turns); | |
260 | it != boost::end(turns); | |
261 | ++it) | |
262 | { | |
263 | turn_type& turn = *it; | |
264 | ||
265 | // It is a ii self-turn | |
266 | // Check if it is within the other geometry | |
267 | if (! turn.discarded | |
268 | && is_self_turn<overlay_intersection>(turn) | |
269 | && ! check_within<OverlayType>::apply(turn, geometry0, | |
270 | geometry1, strategy)) | |
271 | { | |
272 | // It is not within another geometry, set it as non startable. | |
273 | // It still might be traveled (#case_recursive_boxes_70) | |
274 | turn.operations[0].enriched.startable = false; | |
275 | turn.operations[1].enriched.startable = false; | |
276 | } | |
277 | } | |
278 | } | |
279 | }; | |
280 | ||
281 | ||
282 | template <overlay_type OverlayType, operation_type OperationType> | |
283 | struct discard_open_turns : discard_turns {}; | |
284 | ||
285 | // Handler for intersection | |
286 | template <> | |
287 | struct discard_open_turns<overlay_intersection, operation_intersection> | |
288 | : discard_self_intersection_turns<overlay_intersection> {}; | |
289 | ||
290 | // Handler for difference, with different meaning of 'within' | |
291 | template <> | |
292 | struct discard_open_turns<overlay_difference, operation_intersection> | |
293 | : discard_self_intersection_turns<overlay_difference> {}; | |
294 | ||
295 | }} // namespace detail::overlay | |
296 | #endif //DOXYGEN_NO_DETAIL | |
297 | ||
298 | ||
299 | }} // namespace boost::geometry | |
300 | ||
301 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_HANDLE_SELF_TURNS_HPP |