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 // Use, modification and distribution is subject to the Boost Software License,
7 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9
10 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP
11 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP
12
13
14 #include <map>
15
16 #include <boost/range.hpp>
17
18 #include <boost/geometry/core/tags.hpp>
19
20 #include <boost/geometry/algorithms/area.hpp>
21 #include <boost/geometry/algorithms/within.hpp>
22 #include <boost/geometry/algorithms/detail/interior_iterator.hpp>
23 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
24 #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
25 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
26
27
28 namespace boost { namespace geometry
29 {
30
31
32 #ifndef DOXYGEN_NO_DETAIL
33 namespace detail { namespace overlay
34 {
35
36 struct ring_turn_info
37 {
38 bool has_uu_turn;
39 bool has_normal_turn;
40 bool within_other;
41
ring_turn_infoboost::geometry::detail::overlay::ring_turn_info42 ring_turn_info()
43 : has_uu_turn(false)
44 , has_normal_turn(false)
45 , within_other(false)
46 {}
47 };
48
49 namespace dispatch
50 {
51
52 template <typename Tag, typename Geometry>
53 struct select_rings
54 {};
55
56 template <typename Box>
57 struct select_rings<box_tag, Box>
58 {
59 template <typename Geometry, typename RingPropertyMap>
applyboost::geometry::detail::overlay::dispatch::select_rings60 static inline void apply(Box const& box, Geometry const& ,
61 ring_identifier const& id, RingPropertyMap& ring_properties)
62 {
63 ring_properties[id] = typename RingPropertyMap::mapped_type(box);
64 }
65
66 template <typename RingPropertyMap>
applyboost::geometry::detail::overlay::dispatch::select_rings67 static inline void apply(Box const& box,
68 ring_identifier const& id, RingPropertyMap& ring_properties)
69 {
70 ring_properties[id] = typename RingPropertyMap::mapped_type(box);
71 }
72 };
73
74 template <typename Ring>
75 struct select_rings<ring_tag, Ring>
76 {
77 template <typename Geometry, typename RingPropertyMap>
applyboost::geometry::detail::overlay::dispatch::select_rings78 static inline void apply(Ring const& ring, Geometry const& ,
79 ring_identifier const& id, RingPropertyMap& ring_properties)
80 {
81 if (boost::size(ring) > 0)
82 {
83 ring_properties[id] = typename RingPropertyMap::mapped_type(ring);
84 }
85 }
86
87 template <typename RingPropertyMap>
applyboost::geometry::detail::overlay::dispatch::select_rings88 static inline void apply(Ring const& ring,
89 ring_identifier const& id, RingPropertyMap& ring_properties)
90 {
91 if (boost::size(ring) > 0)
92 {
93 ring_properties[id] = typename RingPropertyMap::mapped_type(ring);
94 }
95 }
96 };
97
98
99 template <typename Polygon>
100 struct select_rings<polygon_tag, Polygon>
101 {
102 template <typename Geometry, typename RingPropertyMap>
applyboost::geometry::detail::overlay::dispatch::select_rings103 static inline void apply(Polygon const& polygon, Geometry const& geometry,
104 ring_identifier id, RingPropertyMap& ring_properties)
105 {
106 typedef typename geometry::ring_type<Polygon>::type ring_type;
107 typedef select_rings<ring_tag, ring_type> per_ring;
108
109 per_ring::apply(exterior_ring(polygon), geometry, id, ring_properties);
110
111 typename interior_return_type<Polygon const>::type
112 rings = interior_rings(polygon);
113 for (typename detail::interior_iterator<Polygon const>::type
114 it = boost::begin(rings); it != boost::end(rings); ++it)
115 {
116 id.ring_index++;
117 per_ring::apply(*it, geometry, id, ring_properties);
118 }
119 }
120
121 template <typename RingPropertyMap>
applyboost::geometry::detail::overlay::dispatch::select_rings122 static inline void apply(Polygon const& polygon,
123 ring_identifier id, RingPropertyMap& ring_properties)
124 {
125 typedef typename geometry::ring_type<Polygon>::type ring_type;
126 typedef select_rings<ring_tag, ring_type> per_ring;
127
128 per_ring::apply(exterior_ring(polygon), id, ring_properties);
129
130 typename interior_return_type<Polygon const>::type
131 rings = interior_rings(polygon);
132 for (typename detail::interior_iterator<Polygon const>::type
133 it = boost::begin(rings); it != boost::end(rings); ++it)
134 {
135 id.ring_index++;
136 per_ring::apply(*it, id, ring_properties);
137 }
138 }
139 };
140
141 template <typename Multi>
142 struct select_rings<multi_polygon_tag, Multi>
143 {
144 template <typename Geometry, typename RingPropertyMap>
applyboost::geometry::detail::overlay::dispatch::select_rings145 static inline void apply(Multi const& multi, Geometry const& geometry,
146 ring_identifier id, RingPropertyMap& ring_properties)
147 {
148 typedef typename boost::range_iterator
149 <
150 Multi const
151 >::type iterator_type;
152
153 typedef select_rings<polygon_tag, typename boost::range_value<Multi>::type> per_polygon;
154
155 id.multi_index = 0;
156 for (iterator_type it = boost::begin(multi); it != boost::end(multi); ++it)
157 {
158 id.ring_index = -1;
159 per_polygon::apply(*it, geometry, id, ring_properties);
160 id.multi_index++;
161 }
162 }
163 };
164
165 } // namespace dispatch
166
167
168 template<overlay_type OverlayType>
169 struct decide
170 {};
171
172 template<>
173 struct decide<overlay_union>
174 {
includeboost::geometry::detail::overlay::decide175 static bool include(ring_identifier const& , ring_turn_info const& info)
176 {
177 return info.has_uu_turn || ! info.within_other;
178 }
179
reversedboost::geometry::detail::overlay::decide180 static bool reversed(ring_identifier const& , ring_turn_info const& )
181 {
182 return false;
183 }
184 };
185
186 template<>
187 struct decide<overlay_difference>
188 {
includeboost::geometry::detail::overlay::decide189 static bool include(ring_identifier const& id, ring_turn_info const& info)
190 {
191 // Difference: A - B
192
193 // If this is A (source_index=0) and there is only a u/u turn,
194 // then the ring is inside B
195 // If this is B (source_index=1) and there is only a u/u turn,
196 // then the ring is NOT inside A
197
198 // If this is A and the ring is within the other geometry,
199 // then we should NOT include it.
200 // If this is B then we SHOULD include it.
201
202 bool const is_first = id.source_index == 0;
203 bool const within_other = info.within_other
204 || (is_first && info.has_uu_turn);
205 return is_first ? ! within_other : within_other;
206 }
207
reversedboost::geometry::detail::overlay::decide208 static bool reversed(ring_identifier const& id, ring_turn_info const& info)
209 {
210 // Difference: A - B
211 // If this is B, and the ring is included, it should be reversed afterwards
212
213 return id.source_index == 1 && include(id, info);
214 }
215 };
216
217 template<>
218 struct decide<overlay_intersection>
219 {
includeboost::geometry::detail::overlay::decide220 static bool include(ring_identifier const& , ring_turn_info const& info)
221 {
222 return ! info.has_uu_turn && info.within_other;
223 }
224
reversedboost::geometry::detail::overlay::decide225 static bool reversed(ring_identifier const& , ring_turn_info const& )
226 {
227 return false;
228 }
229 };
230
231
232 template
233 <
234 overlay_type OverlayType,
235 typename Geometry1,
236 typename Geometry2,
237 typename TurnInfoMap,
238 typename RingPropertyMap
239 >
update_ring_selection(Geometry1 const & geometry1,Geometry2 const & geometry2,TurnInfoMap const & turn_info_map,RingPropertyMap const & all_ring_properties,RingPropertyMap & selected_ring_properties)240 inline void update_ring_selection(Geometry1 const& geometry1,
241 Geometry2 const& geometry2,
242 TurnInfoMap const& turn_info_map,
243 RingPropertyMap const& all_ring_properties,
244 RingPropertyMap& selected_ring_properties)
245 {
246 selected_ring_properties.clear();
247
248 for (typename RingPropertyMap::const_iterator it = boost::begin(all_ring_properties);
249 it != boost::end(all_ring_properties);
250 ++it)
251 {
252 ring_identifier const& id = it->first;
253
254 ring_turn_info info;
255
256 typename TurnInfoMap::const_iterator tcit = turn_info_map.find(id);
257 if (tcit != turn_info_map.end())
258 {
259 info = tcit->second; // Copy by value
260 }
261
262 if (info.has_normal_turn)
263 {
264 // There are normal turns on this ring. It should be traversed, we
265 // don't include the original ring
266 continue;
267 }
268
269 if (! info.has_uu_turn)
270 {
271 // Check if the ring is within the other geometry, by taking
272 // a point lying on the ring
273 switch(id.source_index)
274 {
275 case 0 :
276 info.within_other = geometry::within(it->second.point, geometry2);
277 break;
278 case 1 :
279 info.within_other = geometry::within(it->second.point, geometry1);
280 break;
281 }
282 }
283
284 if (decide<OverlayType>::include(id, info))
285 {
286 typename RingPropertyMap::mapped_type properties = it->second; // Copy by value
287 properties.reversed = decide<OverlayType>::reversed(id, info);
288 selected_ring_properties[id] = properties;
289 }
290 }
291 }
292
293
294 /*!
295 \brief The function select_rings select rings based on the overlay-type (union,intersection)
296 */
297 template
298 <
299 overlay_type OverlayType,
300 typename Geometry1,
301 typename Geometry2,
302 typename RingTurnInfoMap,
303 typename RingPropertyMap
304 >
select_rings(Geometry1 const & geometry1,Geometry2 const & geometry2,RingTurnInfoMap const & turn_info_per_ring,RingPropertyMap & selected_ring_properties)305 inline void select_rings(Geometry1 const& geometry1, Geometry2 const& geometry2,
306 RingTurnInfoMap const& turn_info_per_ring,
307 RingPropertyMap& selected_ring_properties)
308 {
309 typedef typename geometry::tag<Geometry1>::type tag1;
310 typedef typename geometry::tag<Geometry2>::type tag2;
311
312 RingPropertyMap all_ring_properties;
313 dispatch::select_rings<tag1, Geometry1>::apply(geometry1, geometry2,
314 ring_identifier(0, -1, -1), all_ring_properties);
315 dispatch::select_rings<tag2, Geometry2>::apply(geometry2, geometry1,
316 ring_identifier(1, -1, -1), all_ring_properties);
317
318 update_ring_selection<OverlayType>(geometry1, geometry2, turn_info_per_ring,
319 all_ring_properties, selected_ring_properties);
320 }
321
322 template
323 <
324 overlay_type OverlayType,
325 typename Geometry,
326 typename RingTurnInfoMap,
327 typename RingPropertyMap
328 >
select_rings(Geometry const & geometry,RingTurnInfoMap const & turn_info_per_ring,RingPropertyMap & selected_ring_properties)329 inline void select_rings(Geometry const& geometry,
330 RingTurnInfoMap const& turn_info_per_ring,
331 RingPropertyMap& selected_ring_properties)
332 {
333 typedef typename geometry::tag<Geometry>::type tag;
334
335 RingPropertyMap all_ring_properties;
336 dispatch::select_rings<tag, Geometry>::apply(geometry,
337 ring_identifier(0, -1, -1), all_ring_properties);
338
339 update_ring_selection<OverlayType>(geometry, geometry, turn_info_per_ring,
340 all_ring_properties, selected_ring_properties);
341 }
342
343
344 }} // namespace detail::overlay
345 #endif // DOXYGEN_NO_DETAIL
346
347
348 }} // namespace boost::geometry
349
350
351 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP
352