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/area.hpp>
25 #include <boost/geometry/algorithms/covered_by.hpp>
26 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
27 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
28 #include <boost/geometry/algorithms/detail/overlay/range_in_geometry.hpp>
29 #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
30 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
31
32
33 namespace boost { namespace geometry
34 {
35
36
37 #ifndef DOXYGEN_NO_DETAIL
38 namespace detail { namespace overlay
39 {
40
41 struct ring_turn_info
42 {
43 bool has_traversed_turn;
44 bool within_other;
45
ring_turn_infoboost::geometry::detail::overlay::ring_turn_info46 ring_turn_info()
47 : has_traversed_turn(false)
48 , within_other(false)
49 {}
50 };
51
52 namespace dispatch
53 {
54
55 template <typename Tag, typename Geometry>
56 struct select_rings
57 {};
58
59 template <typename Box>
60 struct select_rings<box_tag, Box>
61 {
62 template <typename Geometry, typename RingPropertyMap, typename AreaStrategy>
applyboost::geometry::detail::overlay::dispatch::select_rings63 static inline void apply(Box const& box, Geometry const& ,
64 ring_identifier const& id, RingPropertyMap& ring_properties,
65 AreaStrategy const& strategy)
66 {
67 ring_properties[id] = typename RingPropertyMap::mapped_type(box, strategy);
68 }
69
70 template <typename RingPropertyMap, typename AreaStrategy>
applyboost::geometry::detail::overlay::dispatch::select_rings71 static inline void apply(Box const& box,
72 ring_identifier const& id, RingPropertyMap& ring_properties,
73 AreaStrategy const& strategy)
74 {
75 ring_properties[id] = typename RingPropertyMap::mapped_type(box, strategy);
76 }
77 };
78
79 template <typename Ring>
80 struct select_rings<ring_tag, Ring>
81 {
82 template <typename Geometry, typename RingPropertyMap, typename AreaStrategy>
applyboost::geometry::detail::overlay::dispatch::select_rings83 static inline void apply(Ring const& ring, Geometry const& ,
84 ring_identifier const& id, RingPropertyMap& ring_properties,
85 AreaStrategy const& strategy)
86 {
87 if (boost::size(ring) > 0)
88 {
89 ring_properties[id] = typename RingPropertyMap::mapped_type(ring, strategy);
90 }
91 }
92
93 template <typename RingPropertyMap, typename AreaStrategy>
applyboost::geometry::detail::overlay::dispatch::select_rings94 static inline void apply(Ring const& ring,
95 ring_identifier const& id, RingPropertyMap& ring_properties,
96 AreaStrategy const& strategy)
97 {
98 if (boost::size(ring) > 0)
99 {
100 ring_properties[id] = typename RingPropertyMap::mapped_type(ring, strategy);
101 }
102 }
103 };
104
105
106 template <typename Polygon>
107 struct select_rings<polygon_tag, Polygon>
108 {
109 template <typename Geometry, typename RingPropertyMap, typename AreaStrategy>
applyboost::geometry::detail::overlay::dispatch::select_rings110 static inline void apply(Polygon const& polygon, Geometry const& geometry,
111 ring_identifier id, RingPropertyMap& ring_properties,
112 AreaStrategy const& strategy)
113 {
114 typedef typename geometry::ring_type<Polygon>::type ring_type;
115 typedef select_rings<ring_tag, ring_type> per_ring;
116
117 per_ring::apply(exterior_ring(polygon), geometry, id, ring_properties, strategy);
118
119 typename interior_return_type<Polygon const>::type
120 rings = interior_rings(polygon);
121 for (typename detail::interior_iterator<Polygon const>::type
122 it = boost::begin(rings); it != boost::end(rings); ++it)
123 {
124 id.ring_index++;
125 per_ring::apply(*it, geometry, id, ring_properties, strategy);
126 }
127 }
128
129 template <typename RingPropertyMap, typename AreaStrategy>
applyboost::geometry::detail::overlay::dispatch::select_rings130 static inline void apply(Polygon const& polygon,
131 ring_identifier id, RingPropertyMap& ring_properties,
132 AreaStrategy const& strategy)
133 {
134 typedef typename geometry::ring_type<Polygon>::type ring_type;
135 typedef select_rings<ring_tag, ring_type> per_ring;
136
137 per_ring::apply(exterior_ring(polygon), id, ring_properties, strategy);
138
139 typename interior_return_type<Polygon const>::type
140 rings = interior_rings(polygon);
141 for (typename detail::interior_iterator<Polygon const>::type
142 it = boost::begin(rings); it != boost::end(rings); ++it)
143 {
144 id.ring_index++;
145 per_ring::apply(*it, id, ring_properties, strategy);
146 }
147 }
148 };
149
150 template <typename Multi>
151 struct select_rings<multi_polygon_tag, Multi>
152 {
153 template <typename Geometry, typename RingPropertyMap, typename AreaStrategy>
applyboost::geometry::detail::overlay::dispatch::select_rings154 static inline void apply(Multi const& multi, Geometry const& geometry,
155 ring_identifier id, RingPropertyMap& ring_properties,
156 AreaStrategy const& strategy)
157 {
158 typedef typename boost::range_iterator
159 <
160 Multi const
161 >::type iterator_type;
162
163 typedef select_rings<polygon_tag, typename boost::range_value<Multi>::type> per_polygon;
164
165 id.multi_index = 0;
166 for (iterator_type it = boost::begin(multi); it != boost::end(multi); ++it)
167 {
168 id.ring_index = -1;
169 per_polygon::apply(*it, geometry, id, ring_properties, strategy);
170 id.multi_index++;
171 }
172 }
173 };
174
175 } // namespace dispatch
176
177
178 template<overlay_type OverlayType>
179 struct decide
180 {
181 // Default implementation (union, inflate, deflate, dissolve)
includeboost::geometry::detail::overlay::decide182 static bool include(ring_identifier const& , ring_turn_info const& info)
183 {
184 return ! info.within_other;
185 }
186
reversedboost::geometry::detail::overlay::decide187 static bool reversed(ring_identifier const& , ring_turn_info const& )
188 {
189 return false;
190 }
191
192 };
193
194 template<>
195 struct decide<overlay_difference>
196 {
includeboost::geometry::detail::overlay::decide197 static bool include(ring_identifier const& id, ring_turn_info const& info)
198 {
199 // Difference: A - B
200
201 // If this is A (source_index=0), then the ring is inside B
202 // If this is B (source_index=1), then the ring is NOT inside A
203
204 // If this is A and the ring is within the other geometry,
205 // then we should NOT include it.
206 // If this is B then we SHOULD include it.
207
208 return id.source_index == 0
209 ? ! info.within_other
210 : info.within_other;
211 }
212
reversedboost::geometry::detail::overlay::decide213 static bool reversed(ring_identifier const& id, ring_turn_info const& info)
214 {
215 // Difference: A - B
216 // If this is B, and the ring is included, it should be reversed afterwards
217
218 return id.source_index == 1 && include(id, info);
219 }
220 };
221
222 template<>
223 struct decide<overlay_intersection>
224 {
includeboost::geometry::detail::overlay::decide225 static bool include(ring_identifier const& , ring_turn_info const& info)
226 {
227 return info.within_other;
228 }
229
reversedboost::geometry::detail::overlay::decide230 static bool reversed(ring_identifier const& , ring_turn_info const& )
231 {
232 return false;
233 }
234 };
235
236 template
237 <
238 overlay_type OverlayType,
239 typename Geometry1,
240 typename Geometry2,
241 typename TurnInfoMap,
242 typename RingPropertyMap,
243 typename Strategy
244 >
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)245 inline void update_ring_selection(Geometry1 const& geometry1,
246 Geometry2 const& geometry2,
247 TurnInfoMap const& turn_info_map,
248 RingPropertyMap const& all_ring_properties,
249 RingPropertyMap& selected_ring_properties,
250 Strategy const& strategy)
251 {
252 selected_ring_properties.clear();
253
254 for (typename RingPropertyMap::const_iterator it = boost::begin(all_ring_properties);
255 it != boost::end(all_ring_properties);
256 ++it)
257 {
258 ring_identifier const& id = it->first;
259
260 ring_turn_info info;
261
262 typename TurnInfoMap::const_iterator tcit = turn_info_map.find(id);
263 if (tcit != turn_info_map.end())
264 {
265 info = tcit->second; // Copy by value
266 }
267
268 if (info.has_traversed_turn)
269 {
270 // This turn is traversed (or blocked),
271 // don't include the original ring
272 continue;
273 }
274
275 // Check if the ring is within the other geometry, by taking
276 // a point lying on the ring
277 switch(id.source_index)
278 {
279 // within
280 case 0 :
281 info.within_other = range_in_geometry(it->second.point,
282 geometry1, geometry2,
283 strategy) > 0;
284 break;
285 case 1 :
286 info.within_other = range_in_geometry(it->second.point,
287 geometry2, geometry1,
288 strategy) > 0;
289 break;
290 }
291
292 if (decide<OverlayType>::include(id, info))
293 {
294 typename RingPropertyMap::mapped_type properties = it->second; // Copy by value
295 properties.reversed = decide<OverlayType>::reversed(id, info);
296 selected_ring_properties[id] = properties;
297 }
298 }
299 }
300
301
302 /*!
303 \brief The function select_rings select rings based on the overlay-type (union,intersection)
304 */
305 template
306 <
307 overlay_type OverlayType,
308 typename Geometry1,
309 typename Geometry2,
310 typename RingTurnInfoMap,
311 typename RingPropertyMap,
312 typename Strategy
313 >
select_rings(Geometry1 const & geometry1,Geometry2 const & geometry2,RingTurnInfoMap const & turn_info_per_ring,RingPropertyMap & selected_ring_properties,Strategy const & strategy)314 inline void select_rings(Geometry1 const& geometry1, Geometry2 const& geometry2,
315 RingTurnInfoMap const& turn_info_per_ring,
316 RingPropertyMap& selected_ring_properties,
317 Strategy const& strategy)
318 {
319 typedef typename geometry::tag<Geometry1>::type tag1;
320 typedef typename geometry::tag<Geometry2>::type tag2;
321 typedef typename geometry::point_type<Geometry1>::type point1_type;
322 typedef typename geometry::point_type<Geometry2>::type point2_type;
323
324 RingPropertyMap all_ring_properties;
325 dispatch::select_rings<tag1, Geometry1>::apply(geometry1, geometry2,
326 ring_identifier(0, -1, -1), all_ring_properties,
327 strategy.template get_area_strategy<point1_type>());
328 dispatch::select_rings<tag2, Geometry2>::apply(geometry2, geometry1,
329 ring_identifier(1, -1, -1), all_ring_properties,
330 strategy.template get_area_strategy<point2_type>());
331
332 update_ring_selection<OverlayType>(geometry1, geometry2, turn_info_per_ring,
333 all_ring_properties, selected_ring_properties,
334 strategy);
335 }
336
337 template
338 <
339 overlay_type OverlayType,
340 typename Geometry,
341 typename RingTurnInfoMap,
342 typename RingPropertyMap,
343 typename Strategy
344 >
select_rings(Geometry const & geometry,RingTurnInfoMap const & turn_info_per_ring,RingPropertyMap & selected_ring_properties,Strategy const & strategy)345 inline void select_rings(Geometry const& geometry,
346 RingTurnInfoMap const& turn_info_per_ring,
347 RingPropertyMap& selected_ring_properties,
348 Strategy const& strategy)
349 {
350 typedef typename geometry::tag<Geometry>::type tag;
351 typedef typename geometry::point_type<Geometry>::type point_type;
352
353 RingPropertyMap all_ring_properties;
354 dispatch::select_rings<tag, Geometry>::apply(geometry,
355 ring_identifier(0, -1, -1), all_ring_properties,
356 strategy.template get_area_strategy<point_type>());
357
358 update_ring_selection<OverlayType>(geometry, geometry, turn_info_per_ring,
359 all_ring_properties, selected_ring_properties,
360 strategy);
361 }
362
363
364 }} // namespace detail::overlay
365 #endif // DOXYGEN_NO_DETAIL
366
367
368 }} // namespace boost::geometry
369
370
371 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP
372