1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2007-2011 Barend Gehrels, Amsterdam, the Netherlands.
4
5 // Use, modification and distribution is subject to the Boost Software License,
6 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8
9 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP
10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP
11
12 #include <map>
13
14
15 #include <boost/geometry/algorithms/area.hpp>
16 #include <boost/geometry/algorithms/within.hpp>
17 #include <boost/geometry/algorithms/detail/point_on_border.hpp>
18 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
19 #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
20 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
21
22
23 namespace boost { namespace geometry
24 {
25
26
27 #ifndef DOXYGEN_NO_DETAIL
28 namespace detail { namespace overlay
29 {
30
31
32 namespace dispatch
33 {
34
35 template <typename Tag, typename Geometry>
36 struct select_rings
37 {};
38
39 template <typename Box>
40 struct select_rings<box_tag, Box>
41 {
42 template <typename Geometry, typename Map>
applyboost::geometry::detail::overlay::dispatch::select_rings43 static inline void apply(Box const& box, Geometry const& geometry, ring_identifier const& id, Map& map)
44 {
45 map[id] = typename Map::mapped_type(box);
46 }
47
48 template <typename Map>
applyboost::geometry::detail::overlay::dispatch::select_rings49 static inline void apply(Box const& box, ring_identifier const& id, Map& map)
50 {
51 map[id] = typename Map::mapped_type(box);
52 }
53 };
54
55 template <typename Ring>
56 struct select_rings<ring_tag, Ring>
57 {
58 template <typename Geometry, typename Map>
applyboost::geometry::detail::overlay::dispatch::select_rings59 static inline void apply(Ring const& ring, Geometry const& geometry, ring_identifier const& id, Map& map)
60 {
61 if (boost::size(ring) > 0)
62 {
63 map[id] = typename Map::mapped_type(ring);
64 }
65 }
66
67 template <typename Map>
applyboost::geometry::detail::overlay::dispatch::select_rings68 static inline void apply(Ring const& ring, ring_identifier const& id, Map& map)
69 {
70 if (boost::size(ring) > 0)
71 {
72 map[id] = typename Map::mapped_type(ring);
73 }
74 }
75 };
76
77
78 template <typename Polygon>
79 struct select_rings<polygon_tag, Polygon>
80 {
81 template <typename Geometry, typename Map>
applyboost::geometry::detail::overlay::dispatch::select_rings82 static inline void apply(Polygon const& polygon, Geometry const& geometry, ring_identifier id, Map& map)
83 {
84 typedef typename geometry::ring_type<Polygon>::type ring_type;
85 typedef select_rings<ring_tag, ring_type> per_ring;
86
87 per_ring::apply(exterior_ring(polygon), geometry, id, map);
88
89 typename interior_return_type<Polygon const>::type rings
90 = interior_rings(polygon);
91 for (BOOST_AUTO_TPL(it, boost::begin(rings)); it != boost::end(rings); ++it)
92 {
93 id.ring_index++;
94 per_ring::apply(*it, geometry, id, map);
95 }
96 }
97
98 template <typename Map>
applyboost::geometry::detail::overlay::dispatch::select_rings99 static inline void apply(Polygon const& polygon, ring_identifier id, Map& map)
100 {
101 typedef typename geometry::ring_type<Polygon>::type ring_type;
102 typedef select_rings<ring_tag, ring_type> per_ring;
103
104 per_ring::apply(exterior_ring(polygon), id, map);
105
106 typename interior_return_type<Polygon const>::type rings
107 = interior_rings(polygon);
108 for (BOOST_AUTO_TPL(it, boost::begin(rings)); it != boost::end(rings); ++it)
109 {
110 id.ring_index++;
111 per_ring::apply(*it, id, map);
112 }
113 }
114 };
115 }
116
117
118 template<overlay_type OverlayType>
119 struct decide
120 {};
121
122 template<>
123 struct decide<overlay_union>
124 {
125 template <typename Code>
includeboost::geometry::detail::overlay::decide126 static bool include(ring_identifier const& id, Code const& code)
127 {
128 return code.within_code * -1 == 1;
129 }
130
131 template <typename Code>
reversedboost::geometry::detail::overlay::decide132 static bool reversed(ring_identifier const& , Code const& )
133 {
134 return false;
135 }
136 };
137
138 template<>
139 struct decide<overlay_difference>
140 {
141 template <typename Code>
includeboost::geometry::detail::overlay::decide142 static bool include(ring_identifier const& id, Code const& code)
143 {
144 bool is_first = id.source_index == 0;
145 return code.within_code * -1 * (is_first ? 1 : -1) == 1;
146 }
147
148 template <typename Code>
reversedboost::geometry::detail::overlay::decide149 static bool reversed(ring_identifier const& id, Code const& code)
150 {
151 return include(id, code) && id.source_index == 1;
152 }
153 };
154
155 template<>
156 struct decide<overlay_intersection>
157 {
158 template <typename Code>
includeboost::geometry::detail::overlay::decide159 static bool include(ring_identifier const& id, Code const& code)
160 {
161 return code.within_code * 1 == 1;
162 }
163
164 template <typename Code>
reversedboost::geometry::detail::overlay::decide165 static bool reversed(ring_identifier const& , Code const& )
166 {
167 return false;
168 }
169 };
170
171
172 template
173 <
174 overlay_type OverlayType,
175 typename Geometry1, typename Geometry2,
176 typename IntersectionMap, typename SelectionMap
177 >
update_selection_map(Geometry1 const & geometry1,Geometry2 const & geometry2,IntersectionMap const & intersection_map,SelectionMap const & map_with_all,SelectionMap & selection_map)178 inline void update_selection_map(Geometry1 const& geometry1,
179 Geometry2 const& geometry2,
180 IntersectionMap const& intersection_map,
181 SelectionMap const& map_with_all, SelectionMap& selection_map)
182 {
183 selection_map.clear();
184
185 for (typename SelectionMap::const_iterator it = boost::begin(map_with_all);
186 it != boost::end(map_with_all);
187 ++it)
188 {
189 /*
190 int union_code = it->second.within_code * -1;
191 bool is_first = it->first.source_index == 0;
192 std::cout << it->first << " " << it->second.area
193 << ": " << it->second.within_code
194 << " union: " << union_code
195 << " intersection: " << (it->second.within_code * 1)
196 << " G1-G2: " << (union_code * (is_first ? 1 : -1))
197 << " G2-G1: " << (union_code * (is_first ? -1 : 1))
198 << " -> " << (decide<OverlayType>::include(it->first, it->second) ? "INC" : "")
199 << decide<OverlayType>::reverse(it->first, it->second)
200 << std::endl;
201 */
202
203 bool found = intersection_map.find(it->first) != intersection_map.end();
204 if (! found)
205 {
206 ring_identifier id = it->first;
207 typename SelectionMap::mapped_type properties = it->second; // Copy by value
208
209 // Calculate the "within code" (previously this was done earlier but is
210 // must efficienter here - it can be even more efficient doing it all at once,
211 // using partition, TODO)
212 // So though this is less elegant than before, it avoids many unused point-in-poly calculations
213 switch(id.source_index)
214 {
215 case 0 :
216 properties.within_code
217 = geometry::within(properties.point, geometry2) ? 1 : -1;
218 break;
219 case 1 :
220 properties.within_code
221 = geometry::within(properties.point, geometry1) ? 1 : -1;
222 break;
223 }
224
225 if (decide<OverlayType>::include(id, properties))
226 {
227 properties.reversed = decide<OverlayType>::reversed(id, properties);
228 selection_map[id] = properties;
229 }
230 }
231 }
232 }
233
234
235 /*!
236 \brief The function select_rings select rings based on the overlay-type (union,intersection)
237 */
238 template
239 <
240 overlay_type OverlayType,
241 typename Geometry1, typename Geometry2,
242 typename IntersectionMap, typename SelectionMap
243 >
select_rings(Geometry1 const & geometry1,Geometry2 const & geometry2,IntersectionMap const & intersection_map,SelectionMap & selection_map)244 inline void select_rings(Geometry1 const& geometry1, Geometry2 const& geometry2,
245 IntersectionMap const& intersection_map, SelectionMap& selection_map)
246 {
247 typedef typename geometry::tag<Geometry1>::type tag1;
248 typedef typename geometry::tag<Geometry2>::type tag2;
249
250 SelectionMap map_with_all;
251 dispatch::select_rings<tag1, Geometry1>::apply(geometry1, geometry2, ring_identifier(0, -1, -1), map_with_all);
252 dispatch::select_rings<tag2, Geometry2>::apply(geometry2, geometry1, ring_identifier(1, -1, -1), map_with_all);
253
254 update_selection_map<OverlayType>(geometry1, geometry2, intersection_map, map_with_all, selection_map);
255 }
256
257 template
258 <
259 overlay_type OverlayType,
260 typename Geometry,
261 typename IntersectionMap, typename SelectionMap
262 >
select_rings(Geometry const & geometry,IntersectionMap const & intersection_map,SelectionMap & selection_map)263 inline void select_rings(Geometry const& geometry,
264 IntersectionMap const& intersection_map, SelectionMap& selection_map)
265 {
266 typedef typename geometry::tag<Geometry>::type tag;
267
268 SelectionMap map_with_all;
269 dispatch::select_rings<tag, Geometry>::apply(geometry, ring_identifier(0, -1, -1), map_with_all);
270
271 update_selection_map<OverlayType>(intersection_map, map_with_all, selection_map);
272 }
273
274
275 }} // namespace detail::overlay
276 #endif // DOXYGEN_NO_DETAIL
277
278
279 }} // namespace boost::geometry
280
281
282 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_SELECT_RINGS_HPP
283