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