]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2012 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_ASSIGN_PARENTS_HPP | |
10 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP | |
11 | ||
12 | #include <boost/range.hpp> | |
13 | ||
14 | #include <boost/geometry/algorithms/area.hpp> | |
15 | #include <boost/geometry/algorithms/envelope.hpp> | |
16 | #include <boost/geometry/algorithms/expand.hpp> | |
17 | #include <boost/geometry/algorithms/detail/partition.hpp> | |
18 | #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp> | |
19 | #include <boost/geometry/algorithms/within.hpp> | |
20 | ||
21 | #include <boost/geometry/geometries/box.hpp> | |
22 | ||
23 | namespace boost { namespace geometry | |
24 | { | |
25 | ||
26 | ||
27 | #ifndef DOXYGEN_NO_DETAIL | |
28 | namespace detail { namespace overlay | |
29 | { | |
30 | ||
31 | ||
32 | ||
33 | template | |
34 | < | |
35 | typename Item, | |
36 | typename Geometry1, typename Geometry2, | |
37 | typename RingCollection | |
38 | > | |
39 | static inline bool within_selected_input(Item const& item2, ring_identifier const& ring_id, | |
40 | Geometry1 const& geometry1, Geometry2 const& geometry2, | |
41 | RingCollection const& collection) | |
42 | { | |
43 | typedef typename geometry::tag<Geometry1>::type tag1; | |
44 | typedef typename geometry::tag<Geometry2>::type tag2; | |
45 | ||
46 | switch (ring_id.source_index) | |
47 | { | |
48 | case 0 : | |
49 | return geometry::within(item2.point, | |
50 | get_ring<tag1>::apply(ring_id, geometry1)); | |
51 | break; | |
52 | case 1 : | |
53 | return geometry::within(item2.point, | |
54 | get_ring<tag2>::apply(ring_id, geometry2)); | |
55 | break; | |
56 | case 2 : | |
57 | return geometry::within(item2.point, | |
58 | get_ring<void>::apply(ring_id, collection)); | |
59 | break; | |
60 | } | |
61 | return false; | |
62 | } | |
63 | ||
64 | ||
65 | template <typename Point> | |
66 | struct ring_info_helper | |
67 | { | |
68 | typedef typename geometry::default_area_result<Point>::type area_type; | |
69 | ||
70 | ring_identifier id; | |
71 | area_type real_area; | |
72 | area_type abs_area; | |
73 | model::box<Point> envelope; | |
74 | ||
75 | inline ring_info_helper() | |
76 | : real_area(0), abs_area(0) | |
77 | {} | |
78 | ||
79 | inline ring_info_helper(ring_identifier i, area_type a) | |
80 | : id(i), real_area(a), abs_area(geometry::math::abs(a)) | |
81 | {} | |
82 | }; | |
83 | ||
84 | ||
85 | struct ring_info_helper_get_box | |
86 | { | |
87 | template <typename Box, typename InputItem> | |
88 | static inline void apply(Box& total, InputItem const& item) | |
89 | { | |
90 | geometry::expand(total, item.envelope); | |
91 | } | |
92 | }; | |
93 | ||
94 | struct ring_info_helper_ovelaps_box | |
95 | { | |
96 | template <typename Box, typename InputItem> | |
97 | static inline bool apply(Box const& box, InputItem const& item) | |
98 | { | |
99 | return ! geometry::detail::disjoint::disjoint_box_box(box, item.envelope); | |
100 | } | |
101 | }; | |
102 | ||
103 | template <typename Geometry1, typename Geometry2, typename Collection, typename RingMap> | |
104 | struct assign_visitor | |
105 | { | |
106 | typedef typename RingMap::mapped_type ring_info_type; | |
107 | ||
108 | Geometry1 const& m_geometry1; | |
109 | Geometry2 const& m_geometry2; | |
110 | Collection const& m_collection; | |
111 | RingMap& m_ring_map; | |
112 | bool m_check_for_orientation; | |
113 | ||
114 | ||
115 | inline assign_visitor(Geometry1 const& g1, Geometry2 const& g2, Collection const& c, | |
116 | RingMap& map, bool check) | |
117 | : m_geometry1(g1) | |
118 | , m_geometry2(g2) | |
119 | , m_collection(c) | |
120 | , m_ring_map(map) | |
121 | , m_check_for_orientation(check) | |
122 | {} | |
123 | ||
124 | template <typename Item> | |
125 | inline void apply(Item const& outer, Item const& inner, bool first = true) | |
126 | { | |
127 | if (first && outer.abs_area < inner.abs_area) | |
128 | { | |
129 | // Apply with reversed arguments | |
130 | apply(inner, outer, false); | |
131 | return; | |
132 | } | |
133 | ||
134 | if (m_check_for_orientation | |
135 | || (math::larger(outer.real_area, 0) | |
136 | && math::smaller(inner.real_area, 0))) | |
137 | { | |
138 | ring_info_type& inner_in_map = m_ring_map[inner.id]; | |
139 | ||
140 | if (geometry::within(inner_in_map.point, outer.envelope) | |
141 | && within_selected_input(inner_in_map, outer.id, m_geometry1, m_geometry2, m_collection) | |
142 | ) | |
143 | { | |
144 | // Assign a parent if there was no earlier parent, or the newly | |
145 | // found parent is smaller than the previous one | |
146 | if (inner_in_map.parent.source_index == -1 | |
147 | || outer.abs_area < inner_in_map.parent_area) | |
148 | { | |
149 | inner_in_map.parent = outer.id; | |
150 | inner_in_map.parent_area = outer.abs_area; | |
151 | } | |
152 | } | |
153 | } | |
154 | } | |
155 | }; | |
156 | ||
157 | ||
158 | ||
159 | ||
160 | template | |
161 | < | |
162 | typename Geometry1, typename Geometry2, | |
163 | typename RingCollection, | |
164 | typename RingMap | |
165 | > | |
166 | inline void assign_parents(Geometry1 const& geometry1, | |
167 | Geometry2 const& geometry2, | |
168 | RingCollection const& collection, | |
169 | RingMap& ring_map, | |
170 | bool check_for_orientation = false) | |
171 | { | |
172 | typedef typename geometry::tag<Geometry1>::type tag1; | |
173 | typedef typename geometry::tag<Geometry2>::type tag2; | |
174 | ||
175 | typedef typename RingMap::mapped_type ring_info_type; | |
176 | typedef typename ring_info_type::point_type point_type; | |
177 | typedef model::box<point_type> box_type; | |
178 | ||
179 | typedef typename RingMap::iterator map_iterator_type; | |
180 | ||
181 | { | |
182 | typedef ring_info_helper<point_type> helper; | |
183 | typedef std::vector<helper> vector_type; | |
184 | typedef typename boost::range_iterator<vector_type const>::type vector_iterator_type; | |
185 | ||
186 | std::size_t count_total = ring_map.size(); | |
187 | std::size_t count_positive = 0; | |
188 | std::size_t index_positive = 0; // only used if count_positive>0 | |
189 | std::size_t index = 0; | |
190 | ||
191 | // Copy to vector (with new approach this might be obsolete as well, using the map directly) | |
192 | vector_type vector(count_total); | |
193 | ||
194 | for (map_iterator_type it = boost::begin(ring_map); | |
195 | it != boost::end(ring_map); ++it, ++index) | |
196 | { | |
197 | vector[index] = helper(it->first, it->second.get_area()); | |
198 | helper& item = vector[index]; | |
199 | switch(it->first.source_index) | |
200 | { | |
201 | case 0 : | |
202 | geometry::envelope(get_ring<tag1>::apply(it->first, geometry1), | |
203 | item.envelope); | |
204 | break; | |
205 | case 1 : | |
206 | geometry::envelope(get_ring<tag2>::apply(it->first, geometry2), | |
207 | item.envelope); | |
208 | break; | |
209 | case 2 : | |
210 | geometry::envelope(get_ring<void>::apply(it->first, collection), | |
211 | item.envelope); | |
212 | break; | |
213 | } | |
214 | if (item.real_area > 0) | |
215 | { | |
216 | count_positive++; | |
217 | index_positive = index; | |
218 | } | |
219 | } | |
220 | ||
221 | if (! check_for_orientation) | |
222 | { | |
223 | if (count_positive == count_total) | |
224 | { | |
225 | // Optimization for only positive rings | |
226 | // -> no assignment of parents or reversal necessary, ready here. | |
227 | return; | |
228 | } | |
229 | ||
230 | if (count_positive == 1) | |
231 | { | |
232 | // Optimization for one outer ring | |
233 | // -> assign this as parent to all others (all interior rings) | |
234 | // In unions, this is probably the most occuring case and gives | |
235 | // a dramatic improvement (factor 5 for star_comb testcase) | |
236 | ring_identifier id_of_positive = vector[index_positive].id; | |
237 | ring_info_type& outer = ring_map[id_of_positive]; | |
238 | index = 0; | |
239 | for (vector_iterator_type it = boost::begin(vector); | |
240 | it != boost::end(vector); ++it, ++index) | |
241 | { | |
242 | if (index != index_positive) | |
243 | { | |
244 | ring_info_type& inner = ring_map[it->id]; | |
245 | inner.parent = id_of_positive; | |
246 | outer.children.push_back(it->id); | |
247 | } | |
248 | } | |
249 | return; | |
250 | } | |
251 | } | |
252 | ||
253 | assign_visitor | |
254 | < | |
255 | Geometry1, Geometry2, | |
256 | RingCollection, RingMap | |
257 | > visitor(geometry1, geometry2, collection, ring_map, check_for_orientation); | |
258 | ||
259 | geometry::partition | |
260 | < | |
261 | box_type, ring_info_helper_get_box, ring_info_helper_ovelaps_box | |
262 | >::apply(vector, visitor); | |
263 | } | |
264 | ||
265 | if (check_for_orientation) | |
266 | { | |
267 | for (map_iterator_type it = boost::begin(ring_map); | |
268 | it != boost::end(ring_map); ++it) | |
269 | { | |
270 | if (geometry::math::equals(it->second.get_area(), 0)) | |
271 | { | |
272 | it->second.discarded = true; | |
273 | } | |
274 | else if (it->second.parent.source_index >= 0 | |
275 | && math::larger(it->second.get_area(), 0)) | |
276 | { | |
277 | const ring_info_type& parent = ring_map[it->second.parent]; | |
278 | ||
279 | if (math::larger(parent.area, 0)) | |
280 | { | |
281 | // Discard positive inner ring with positive parent | |
282 | it->second.discarded = true; | |
283 | } | |
284 | // Remove parent ID from any positive inner ring | |
285 | it->second.parent.source_index = -1; | |
286 | } | |
287 | else if (it->second.parent.source_index < 0 | |
288 | && math::smaller(it->second.get_area(), 0)) | |
289 | { | |
290 | // Reverse negative ring without parent | |
291 | it->second.reversed = true; | |
292 | } | |
293 | } | |
294 | } | |
295 | ||
296 | // Assign childlist | |
297 | for (map_iterator_type it = boost::begin(ring_map); | |
298 | it != boost::end(ring_map); ++it) | |
299 | { | |
300 | if (it->second.parent.source_index >= 0) | |
301 | { | |
302 | ring_map[it->second.parent].children.push_back(it->first); | |
303 | } | |
304 | } | |
305 | } | |
306 | ||
307 | ||
308 | // Version for one geometry (called by buffer) | |
309 | template | |
310 | < | |
311 | typename Geometry, | |
312 | typename RingCollection, | |
313 | typename RingMap | |
314 | > | |
315 | inline void assign_parents(Geometry const& geometry, | |
316 | RingCollection const& collection, | |
317 | RingMap& ring_map, | |
318 | bool check_for_orientation) | |
319 | { | |
320 | // Call it with an empty geometry as second geometry (source_id == 1) | |
321 | // (ring_map should be empty for source_id==1) | |
322 | ||
323 | Geometry empty; | |
324 | assign_parents(geometry, empty, collection, ring_map, check_for_orientation); | |
325 | } | |
326 | ||
327 | ||
328 | }} // namespace detail::overlay | |
329 | #endif // DOXYGEN_NO_DETAIL | |
330 | ||
331 | ||
332 | }} // namespace geometry | |
333 | ||
334 | ||
335 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP |