1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
5
6 // This file was modified by Oracle on 2017, 2018, 2019.
7 // Modifications copyright (c) 2017-2019 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_ASSIGN_PARENTS_HPP
15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP
16
17 #include <boost/range.hpp>
18
19 #include <boost/geometry/algorithms/envelope.hpp>
20 #include <boost/geometry/algorithms/expand.hpp>
21 #include <boost/geometry/algorithms/detail/partition.hpp>
22 #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
23 #include <boost/geometry/algorithms/detail/overlay/range_in_geometry.hpp>
24 #include <boost/geometry/algorithms/covered_by.hpp>
25
26 #include <boost/geometry/geometries/box.hpp>
27
28 namespace boost { namespace geometry
29 {
30
31
32 #ifndef DOXYGEN_NO_DETAIL
33 namespace detail { namespace overlay
34 {
35
36
37
38 template
39 <
40 typename Item,
41 typename InnerGeometry,
42 typename Geometry1, typename Geometry2,
43 typename RingCollection,
44 typename Strategy
45 >
within_selected_input(Item const & item2,InnerGeometry const & inner_geometry,ring_identifier const & outer_id,Geometry1 const & geometry1,Geometry2 const & geometry2,RingCollection const & collection,Strategy const & strategy)46 static inline bool within_selected_input(Item const& item2,
47 InnerGeometry const& inner_geometry,
48 ring_identifier const& outer_id,
49 Geometry1 const& geometry1, Geometry2 const& geometry2,
50 RingCollection const& collection,
51 Strategy const& strategy)
52 {
53 typedef typename geometry::tag<Geometry1>::type tag1;
54 typedef typename geometry::tag<Geometry2>::type tag2;
55
56 // NOTE: range_in_geometry first checks the item2.point and then
57 // if this point is on boundary it checks points of inner_geometry
58 // ring until a point inside/outside other geometry ring is found
59 switch (outer_id.source_index)
60 {
61 // covered_by
62 case 0 :
63 return range_in_geometry(item2.point, inner_geometry,
64 get_ring<tag1>::apply(outer_id, geometry1), strategy) >= 0;
65 case 1 :
66 return range_in_geometry(item2.point, inner_geometry,
67 get_ring<tag2>::apply(outer_id, geometry2), strategy) >= 0;
68 case 2 :
69 return range_in_geometry(item2.point, inner_geometry,
70 get_ring<void>::apply(outer_id, collection), strategy) >= 0;
71 }
72 return false;
73 }
74
75 template
76 <
77 typename Item,
78 typename Geometry1, typename Geometry2,
79 typename RingCollection,
80 typename Strategy
81 >
within_selected_input(Item const & item2,ring_identifier const & inner_id,ring_identifier const & outer_id,Geometry1 const & geometry1,Geometry2 const & geometry2,RingCollection const & collection,Strategy const & strategy)82 static inline bool within_selected_input(Item const& item2,
83 ring_identifier const& inner_id, ring_identifier const& outer_id,
84 Geometry1 const& geometry1, Geometry2 const& geometry2,
85 RingCollection const& collection,
86 Strategy const& strategy)
87 {
88 typedef typename geometry::tag<Geometry1>::type tag1;
89 typedef typename geometry::tag<Geometry2>::type tag2;
90
91 switch (inner_id.source_index)
92 {
93 case 0 :
94 return within_selected_input(item2,
95 get_ring<tag1>::apply(inner_id, geometry1),
96 outer_id, geometry1, geometry2, collection, strategy);
97 case 1 :
98 return within_selected_input(item2,
99 get_ring<tag2>::apply(inner_id, geometry2),
100 outer_id, geometry1, geometry2, collection, strategy);
101 case 2 :
102 return within_selected_input(item2,
103 get_ring<void>::apply(inner_id, collection),
104 outer_id, geometry1, geometry2, collection, strategy);
105 }
106 return false;
107 }
108
109
110 template <typename Point, typename AreaType>
111 struct ring_info_helper
112 {
113 ring_identifier id;
114 AreaType real_area;
115 AreaType abs_area;
116 model::box<Point> envelope;
117
ring_info_helperboost::geometry::detail::overlay::ring_info_helper118 inline ring_info_helper()
119 : real_area(0), abs_area(0)
120 {}
121
ring_info_helperboost::geometry::detail::overlay::ring_info_helper122 inline ring_info_helper(ring_identifier i, AreaType const& a)
123 : id(i), real_area(a), abs_area(geometry::math::abs(a))
124 {}
125 };
126
127
128 template <typename BoxExpandStrategy>
129 struct ring_info_helper_get_box
130 {
131 template <typename Box, typename InputItem>
applyboost::geometry::detail::overlay::ring_info_helper_get_box132 static inline void apply(Box& total, InputItem const& item)
133 {
134 geometry::expand(total, item.envelope, BoxExpandStrategy());
135 }
136 };
137
138 template <typename DisjointBoxBoxStrategy>
139 struct ring_info_helper_ovelaps_box
140 {
141 template <typename Box, typename InputItem>
applyboost::geometry::detail::overlay::ring_info_helper_ovelaps_box142 static inline bool apply(Box const& box, InputItem const& item)
143 {
144 return ! geometry::detail::disjoint::disjoint_box_box(
145 box, item.envelope, DisjointBoxBoxStrategy());
146 }
147 };
148
149 // Segments intersection Strategy
150 template
151 <
152 typename Geometry1,
153 typename Geometry2,
154 typename Collection,
155 typename RingMap,
156 typename Strategy
157 >
158 struct assign_visitor
159 {
160 typedef typename RingMap::mapped_type ring_info_type;
161
162 Geometry1 const& m_geometry1;
163 Geometry2 const& m_geometry2;
164 Collection const& m_collection;
165 RingMap& m_ring_map;
166 Strategy const& m_strategy;
167 bool m_check_for_orientation;
168
assign_visitorboost::geometry::detail::overlay::assign_visitor169 inline assign_visitor(Geometry1 const& g1, Geometry2 const& g2, Collection const& c,
170 RingMap& map, Strategy const& strategy, bool check)
171 : m_geometry1(g1)
172 , m_geometry2(g2)
173 , m_collection(c)
174 , m_ring_map(map)
175 , m_strategy(strategy)
176 , m_check_for_orientation(check)
177 {}
178
179 template <typename Item>
applyboost::geometry::detail::overlay::assign_visitor180 inline bool apply(Item const& outer, Item const& inner, bool first = true)
181 {
182 if (first && outer.abs_area < inner.abs_area)
183 {
184 // Apply with reversed arguments
185 apply(inner, outer, false);
186 return true;
187 }
188
189 if (m_check_for_orientation
190 || (math::larger(outer.real_area, 0)
191 && math::smaller(inner.real_area, 0)))
192 {
193 ring_info_type& inner_in_map = m_ring_map[inner.id];
194
195 if (geometry::covered_by(inner_in_map.point, outer.envelope,
196 typename Strategy::disjoint_point_box_strategy_type())
197 && within_selected_input(inner_in_map, inner.id, outer.id,
198 m_geometry1, m_geometry2, m_collection,
199 m_strategy)
200 )
201 {
202 // Assign a parent if there was no earlier parent, or the newly
203 // found parent is smaller than the previous one
204 if (inner_in_map.parent.source_index == -1
205 || outer.abs_area < inner_in_map.parent_area)
206 {
207 inner_in_map.parent = outer.id;
208 inner_in_map.parent_area = outer.abs_area;
209 }
210 }
211 }
212
213 return true;
214 }
215 };
216
217
218 template
219 <
220 overlay_type OverlayType,
221 typename Geometry1, typename Geometry2,
222 typename RingCollection,
223 typename RingMap,
224 typename Strategy
225 >
assign_parents(Geometry1 const & geometry1,Geometry2 const & geometry2,RingCollection const & collection,RingMap & ring_map,Strategy const & strategy)226 inline void assign_parents(Geometry1 const& geometry1,
227 Geometry2 const& geometry2,
228 RingCollection const& collection,
229 RingMap& ring_map,
230 Strategy const& strategy)
231 {
232 static bool const is_difference = OverlayType == overlay_difference;
233 static bool const is_buffer = OverlayType == overlay_buffer;
234 static bool const is_dissolve = OverlayType == overlay_dissolve;
235 static bool const check_for_orientation = is_buffer || is_dissolve;
236
237 typedef typename geometry::tag<Geometry1>::type tag1;
238 typedef typename geometry::tag<Geometry2>::type tag2;
239
240 typedef typename RingMap::mapped_type ring_info_type;
241 typedef typename ring_info_type::point_type point_type;
242 typedef model::box<point_type> box_type;
243 typedef typename Strategy::template area_strategy
244 <
245 point_type
246 >::type::template result_type<point_type>::type area_result_type;
247
248 typedef typename RingMap::iterator map_iterator_type;
249
250 {
251 typedef ring_info_helper<point_type, area_result_type> helper;
252 typedef std::vector<helper> vector_type;
253 typedef typename boost::range_iterator<vector_type const>::type vector_iterator_type;
254
255 std::size_t count_total = ring_map.size();
256 std::size_t count_positive = 0;
257 std::size_t index_positive = 0; // only used if count_positive>0
258 std::size_t index = 0;
259
260 // Copy to vector (with new approach this might be obsolete as well, using the map directly)
261 vector_type vector(count_total);
262
263 for (map_iterator_type it = boost::begin(ring_map);
264 it != boost::end(ring_map); ++it, ++index)
265 {
266 vector[index] = helper(it->first, it->second.get_area());
267 helper& item = vector[index];
268 switch(it->first.source_index)
269 {
270 case 0 :
271 geometry::envelope(get_ring<tag1>::apply(it->first, geometry1),
272 item.envelope, strategy.get_envelope_strategy());
273 break;
274 case 1 :
275 geometry::envelope(get_ring<tag2>::apply(it->first, geometry2),
276 item.envelope, strategy.get_envelope_strategy());
277 break;
278 case 2 :
279 geometry::envelope(get_ring<void>::apply(it->first, collection),
280 item.envelope, strategy.get_envelope_strategy());
281 break;
282 }
283
284 // Expand envelope slightly
285 expand_by_epsilon(item.envelope);
286
287 if (item.real_area > 0)
288 {
289 count_positive++;
290 index_positive = index;
291 }
292 }
293
294 if (! check_for_orientation)
295 {
296 if (count_positive == count_total)
297 {
298 // Optimization for only positive rings
299 // -> no assignment of parents or reversal necessary, ready here.
300 return;
301 }
302
303 if (count_positive == 1 && ! is_difference && ! is_dissolve)
304 {
305 // Optimization for one outer ring
306 // -> assign this as parent to all others (all interior rings)
307 // In unions, this is probably the most occuring case and gives
308 // a dramatic improvement (factor 5 for star_comb testcase)
309 // In difference or other cases where interior rings might be
310 // located outside the outer ring, this cannot be done
311 ring_identifier id_of_positive = vector[index_positive].id;
312 ring_info_type& outer = ring_map[id_of_positive];
313 index = 0;
314 for (vector_iterator_type it = boost::begin(vector);
315 it != boost::end(vector); ++it, ++index)
316 {
317 if (index != index_positive)
318 {
319 ring_info_type& inner = ring_map[it->id];
320 inner.parent = id_of_positive;
321 outer.children.push_back(it->id);
322 }
323 }
324 return;
325 }
326 }
327
328 assign_visitor
329 <
330 Geometry1, Geometry2,
331 RingCollection, RingMap,
332 Strategy
333 > visitor(geometry1, geometry2, collection, ring_map, strategy, check_for_orientation);
334
335 typedef ring_info_helper_get_box
336 <
337 typename Strategy::expand_box_strategy_type
338 > expand_box_type;
339 typedef ring_info_helper_ovelaps_box
340 <
341 typename Strategy::disjoint_box_box_strategy_type
342 > overlaps_box_type;
343
344 geometry::partition
345 <
346 box_type
347 >::apply(vector, visitor, expand_box_type(), overlaps_box_type());
348 }
349
350 if (check_for_orientation)
351 {
352 for (map_iterator_type it = boost::begin(ring_map);
353 it != boost::end(ring_map); ++it)
354 {
355 ring_info_type& info = it->second;
356 if (geometry::math::equals(info.get_area(), 0))
357 {
358 info.discarded = true;
359 }
360 else if (info.parent.source_index >= 0)
361 {
362 const ring_info_type& parent = ring_map[info.parent];
363 bool const pos = math::larger(info.get_area(), 0);
364 bool const parent_pos = math::larger(parent.area, 0);
365
366 bool const double_neg = is_dissolve && ! pos && ! parent_pos;
367
368 if ((pos && parent_pos) || double_neg)
369 {
370 // Discard positive inner ring with positive parent
371 // Also, for some cases (dissolve), negative inner ring
372 // with negative parent should be discarded
373 info.discarded = true;
374 }
375
376 if (pos || info.discarded)
377 {
378 // Remove parent ID from any positive or discarded inner rings
379 info.parent.source_index = -1;
380 }
381 }
382 else if (info.parent.source_index < 0
383 && math::smaller(info.get_area(), 0))
384 {
385 // Reverse negative ring without parent
386 info.reversed = true;
387 }
388 }
389 }
390
391 // Assign childlist
392 for (map_iterator_type it = boost::begin(ring_map);
393 it != boost::end(ring_map); ++it)
394 {
395 if (it->second.parent.source_index >= 0)
396 {
397 ring_map[it->second.parent].children.push_back(it->first);
398 }
399 }
400 }
401
402
403 // Version for one geometry (called by buffer/dissolve)
404 template
405 <
406 overlay_type OverlayType,
407 typename Geometry,
408 typename RingCollection,
409 typename RingMap,
410 typename Strategy
411 >
assign_parents(Geometry const & geometry,RingCollection const & collection,RingMap & ring_map,Strategy const & strategy)412 inline void assign_parents(Geometry const& geometry,
413 RingCollection const& collection,
414 RingMap& ring_map,
415 Strategy const& strategy)
416 {
417 // Call it with an empty geometry as second geometry (source_id == 1)
418 // (ring_map should be empty for source_id==1)
419 Geometry empty;
420 assign_parents<OverlayType>(geometry, empty,
421 collection, ring_map, strategy);
422 }
423
424
425 }} // namespace detail::overlay
426 #endif // DOXYGEN_NO_DETAIL
427
428
429 }} // namespace geometry
430
431
432 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP
433