1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2014 Adam Wulkiewicz, Lodz, Poland.
5
6 // This file was modified by Oracle on 2017.
7 // Modifications copyright (c) 2017 Oracle and/or its affiliates.
8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
9
10 // Use, modification and distribution is subject to the Boost Software License,
11 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
12 // http://www.boost.org/LICENSE_1_0.txt)
13
14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP
15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP
16
17
18 #include <map>
19
20 #include <boost/range.hpp>
21
22 #include <boost/geometry/core/tags.hpp>
23
24 #include <boost/geometry/algorithms/covered_by.hpp>
25 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
26 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
27 #include <boost/geometry/algorithms/detail/overlay/range_in_geometry.hpp>
28 #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
29 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
30
31
32 namespace boost { namespace geometry
33 {
34
35
36 #ifndef DOXYGEN_NO_DETAIL
37 namespace detail { namespace overlay
38 {
39
40 struct ring_turn_info
41 {
42 bool has_traversed_turn;
43 bool has_blocked_turn;
44 bool within_other;
45
ring_turn_infoboost::geometry::detail::overlay::ring_turn_info46 ring_turn_info()
47 : has_traversed_turn(false)
48 , has_blocked_turn(false)
49 , within_other(false)
50 {}
51 };
52
53 namespace dispatch
54 {
55
56 template <typename Tag, typename Geometry>
57 struct select_rings
58 {};
59
60 template <typename Box>
61 struct select_rings<box_tag, Box>
62 {
63 template <typename Geometry, typename RingPropertyMap, typename AreaStrategy>
applyboost::geometry::detail::overlay::dispatch::select_rings64 static inline void apply(Box const& box, Geometry const& ,
65 ring_identifier const& id, RingPropertyMap& ring_properties,
66 AreaStrategy const& strategy)
67 {
68 ring_properties[id] = typename RingPropertyMap::mapped_type(box, strategy);
69 }
70
71 template <typename RingPropertyMap, typename AreaStrategy>
applyboost::geometry::detail::overlay::dispatch::select_rings72 static inline void apply(Box const& box,
73 ring_identifier const& id, RingPropertyMap& ring_properties,
74 AreaStrategy const& strategy)
75 {
76 ring_properties[id] = typename RingPropertyMap::mapped_type(box, strategy);
77 }
78 };
79
80 template <typename Ring>
81 struct select_rings<ring_tag, Ring>
82 {
83 template <typename Geometry, typename RingPropertyMap, typename AreaStrategy>
applyboost::geometry::detail::overlay::dispatch::select_rings84 static inline void apply(Ring const& ring, Geometry const& ,
85 ring_identifier const& id, RingPropertyMap& ring_properties,
86 AreaStrategy const& strategy)
87 {
88 if (boost::size(ring) > 0)
89 {
90 ring_properties[id] = typename RingPropertyMap::mapped_type(ring, strategy);
91 }
92 }
93
94 template <typename RingPropertyMap, typename AreaStrategy>
applyboost::geometry::detail::overlay::dispatch::select_rings95 static inline void apply(Ring const& ring,
96 ring_identifier const& id, RingPropertyMap& ring_properties,
97 AreaStrategy const& strategy)
98 {
99 if (boost::size(ring) > 0)
100 {
101 ring_properties[id] = typename RingPropertyMap::mapped_type(ring, strategy);
102 }
103 }
104 };
105
106
107 template <typename Polygon>
108 struct select_rings<polygon_tag, Polygon>
109 {
110 template <typename Geometry, typename RingPropertyMap, typename AreaStrategy>
applyboost::geometry::detail::overlay::dispatch::select_rings111 static inline void apply(Polygon const& polygon, Geometry const& geometry,
112 ring_identifier id, RingPropertyMap& ring_properties,
113 AreaStrategy const& strategy)
114 {
115 typedef typename geometry::ring_type<Polygon>::type ring_type;
116 typedef select_rings<ring_tag, ring_type> per_ring;
117
118 per_ring::apply(exterior_ring(polygon), geometry, id, ring_properties, strategy);
119
120 typename interior_return_type<Polygon const>::type
121 rings = interior_rings(polygon);
122 for (typename detail::interior_iterator<Polygon const>::type
123 it = boost::begin(rings); it != boost::end(rings); ++it)
124 {
125 id.ring_index++;
126 per_ring::apply(*it, geometry, id, ring_properties, strategy);
127 }
128 }
129
130 template <typename RingPropertyMap, typename AreaStrategy>
applyboost::geometry::detail::overlay::dispatch::select_rings131 static inline void apply(Polygon const& polygon,
132 ring_identifier id, RingPropertyMap& ring_properties,
133 AreaStrategy const& strategy)
134 {
135 typedef typename geometry::ring_type<Polygon>::type ring_type;
136 typedef select_rings<ring_tag, ring_type> per_ring;
137
138 per_ring::apply(exterior_ring(polygon), id, ring_properties, strategy);
139
140 typename interior_return_type<Polygon const>::type
141 rings = interior_rings(polygon);
142 for (typename detail::interior_iterator<Polygon const>::type
143 it = boost::begin(rings); it != boost::end(rings); ++it)
144 {
145 id.ring_index++;
146 per_ring::apply(*it, id, ring_properties, strategy);
147 }
148 }
149 };
150
151 template <typename Multi>
152 struct select_rings<multi_polygon_tag, Multi>
153 {
154 template <typename Geometry, typename RingPropertyMap, typename AreaStrategy>
applyboost::geometry::detail::overlay::dispatch::select_rings155 static inline void apply(Multi const& multi, Geometry const& geometry,
156 ring_identifier id, RingPropertyMap& ring_properties,
157 AreaStrategy const& strategy)
158 {
159 typedef typename boost::range_iterator
160 <
161 Multi const
162 >::type iterator_type;
163
164 typedef select_rings<polygon_tag, typename boost::range_value<Multi>::type> per_polygon;
165
166 id.multi_index = 0;
167 for (iterator_type it = boost::begin(multi); it != boost::end(multi); ++it)
168 {
169 id.ring_index = -1;
170 per_polygon::apply(*it, geometry, id, ring_properties, strategy);
171 id.multi_index++;
172 }
173 }
174 };
175
176 } // namespace dispatch
177
178
179 template<overlay_type OverlayType>
180 struct decide
181 {
182 // Default implementation (union, inflate, deflate, dissolve)
includeboost::geometry::detail::overlay::decide183 static bool include(ring_identifier const& , ring_turn_info const& info)
184 {
185 return ! info.within_other;
186 }
187
reversedboost::geometry::detail::overlay::decide188 static bool reversed(ring_identifier const& , ring_turn_info const& )
189 {
190 return false;
191 }
192
193 };
194
195 template<>
196 struct decide<overlay_difference>
197 {
includeboost::geometry::detail::overlay::decide198 static bool include(ring_identifier const& id, ring_turn_info const& info)
199 {
200 // Difference: A - B
201
202 // If this is A (source_index=0), then the ring is inside B
203 // If this is B (source_index=1), then the ring is NOT inside A
204
205 // If this is A and the ring is within the other geometry,
206 // then we should NOT include it.
207 // If this is B then we SHOULD include it.
208
209 return id.source_index == 0
210 ? ! info.within_other
211 : info.within_other;
212 }
213
reversedboost::geometry::detail::overlay::decide214 static bool reversed(ring_identifier const& id, ring_turn_info const& info)
215 {
216 // Difference: A - B
217 // If this is B, and the ring is included, it should be reversed afterwards
218
219 return id.source_index == 1 && include(id, info);
220 }
221 };
222
223 template<>
224 struct decide<overlay_intersection>
225 {
includeboost::geometry::detail::overlay::decide226 static bool include(ring_identifier const& , ring_turn_info const& info)
227 {
228 return info.within_other;
229 }
230
reversedboost::geometry::detail::overlay::decide231 static bool reversed(ring_identifier const& , ring_turn_info const& )
232 {
233 return false;
234 }
235 };
236
237 template
238 <
239 overlay_type OverlayType,
240 typename Geometry1,
241 typename Geometry2,
242 typename TurnInfoMap,
243 typename RingPropertyMap,
244 typename Strategy
245 >
update_ring_selection(Geometry1 const & geometry1,Geometry2 const & geometry2,TurnInfoMap const & turn_info_map,RingPropertyMap const & all_ring_properties,RingPropertyMap & selected_ring_properties,Strategy const & strategy)246 inline void update_ring_selection(Geometry1 const& geometry1,
247 Geometry2 const& geometry2,
248 TurnInfoMap const& turn_info_map,
249 RingPropertyMap const& all_ring_properties,
250 RingPropertyMap& selected_ring_properties,
251 Strategy const& strategy)
252 {
253 selected_ring_properties.clear();
254
255 for (typename RingPropertyMap::const_iterator it = boost::begin(all_ring_properties);
256 it != boost::end(all_ring_properties);
257 ++it)
258 {
259 ring_identifier const& id = it->first;
260
261 ring_turn_info info;
262
263 typename TurnInfoMap::const_iterator tcit = turn_info_map.find(id);
264 if (tcit != turn_info_map.end())
265 {
266 info = tcit->second; // Copy by value
267 }
268
269 if (info.has_traversed_turn || info.has_blocked_turn)
270 {
271 // This turn is traversed or blocked,
272 // don't include the original ring
273 continue;
274 }
275
276 // Check if the ring is within the other geometry, by taking
277 // a point lying on the ring
278 switch(id.source_index)
279 {
280 // within
281 case 0 :
282 info.within_other = range_in_geometry(it->second.point,
283 geometry1, geometry2,
284 strategy) > 0;
285 break;
286 case 1 :
287 info.within_other = range_in_geometry(it->second.point,
288 geometry2, geometry1,
289 strategy) > 0;
290 break;
291 }
292
293 if (decide<OverlayType>::include(id, info))
294 {
295 typename RingPropertyMap::mapped_type properties = it->second; // Copy by value
296 properties.reversed = decide<OverlayType>::reversed(id, info);
297 selected_ring_properties[id] = properties;
298 }
299 }
300 }
301
302
303 /*!
304 \brief The function select_rings select rings based on the overlay-type (union,intersection)
305 */
306 template
307 <
308 overlay_type OverlayType,
309 typename Geometry1,
310 typename Geometry2,
311 typename RingTurnInfoMap,
312 typename RingPropertyMap,
313 typename Strategy
314 >
select_rings(Geometry1 const & geometry1,Geometry2 const & geometry2,RingTurnInfoMap const & turn_info_per_ring,RingPropertyMap & selected_ring_properties,Strategy const & strategy)315 inline void select_rings(Geometry1 const& geometry1, Geometry2 const& geometry2,
316 RingTurnInfoMap const& turn_info_per_ring,
317 RingPropertyMap& selected_ring_properties,
318 Strategy const& strategy)
319 {
320 typedef typename geometry::tag<Geometry1>::type tag1;
321 typedef typename geometry::tag<Geometry2>::type tag2;
322 typedef typename geometry::point_type<Geometry1>::type point1_type;
323 typedef typename geometry::point_type<Geometry2>::type point2_type;
324
325 RingPropertyMap all_ring_properties;
326 dispatch::select_rings<tag1, Geometry1>::apply(geometry1, geometry2,
327 ring_identifier(0, -1, -1), all_ring_properties,
328 strategy.template get_area_strategy<point1_type>());
329 dispatch::select_rings<tag2, Geometry2>::apply(geometry2, geometry1,
330 ring_identifier(1, -1, -1), all_ring_properties,
331 strategy.template get_area_strategy<point2_type>());
332
333 update_ring_selection<OverlayType>(geometry1, geometry2, turn_info_per_ring,
334 all_ring_properties, selected_ring_properties,
335 strategy);
336 }
337
338 template
339 <
340 overlay_type OverlayType,
341 typename Geometry,
342 typename RingTurnInfoMap,
343 typename RingPropertyMap,
344 typename Strategy
345 >
select_rings(Geometry const & geometry,RingTurnInfoMap const & turn_info_per_ring,RingPropertyMap & selected_ring_properties,Strategy const & strategy)346 inline void select_rings(Geometry const& geometry,
347 RingTurnInfoMap const& turn_info_per_ring,
348 RingPropertyMap& selected_ring_properties,
349 Strategy const& strategy)
350 {
351 typedef typename geometry::tag<Geometry>::type tag;
352 typedef typename geometry::point_type<Geometry>::type point_type;
353
354 RingPropertyMap all_ring_properties;
355 dispatch::select_rings<tag, Geometry>::apply(geometry,
356 ring_identifier(0, -1, -1), all_ring_properties,
357 strategy.template get_area_strategy<point_type>());
358
359 update_ring_selection<OverlayType>(geometry, geometry, turn_info_per_ring,
360 all_ring_properties, selected_ring_properties,
361 strategy);
362 }
363
364
365 }} // namespace detail::overlay
366 #endif // DOXYGEN_NO_DETAIL
367
368
369 }} // namespace boost::geometry
370
371
372 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP
373