1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2 
3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
4 
5 // This file was modified by Oracle on 2017.
6 // Modifications copyright (c) 2017 Oracle and/or its affiliates.
7 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
8 
9 // Use, modification and distribution is subject to the Boost Software License,
10 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
11 // http://www.boost.org/LICENSE_1_0.txt)
12 
13 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP
14 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP
15 
16 #include <boost/range.hpp>
17 
18 #include <boost/geometry/algorithms/area.hpp>
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 struct ring_info_helper_get_box
129 {
130     template <typename Box, typename InputItem>
applyboost::geometry::detail::overlay::ring_info_helper_get_box131     static inline void apply(Box& total, InputItem const& item)
132     {
133         geometry::expand(total, item.envelope);
134     }
135 };
136 
137 struct ring_info_helper_ovelaps_box
138 {
139     template <typename Box, typename InputItem>
applyboost::geometry::detail::overlay::ring_info_helper_ovelaps_box140     static inline bool apply(Box const& box, InputItem const& item)
141     {
142         return ! geometry::detail::disjoint::disjoint_box_box(box, item.envelope);
143     }
144 };
145 
146 template
147 <
148     typename Geometry1,
149     typename Geometry2,
150     typename Collection,
151     typename RingMap,
152     typename Strategy
153 >
154 struct assign_visitor
155 {
156     typedef typename RingMap::mapped_type ring_info_type;
157 
158     Geometry1 const& m_geometry1;
159     Geometry2 const& m_geometry2;
160     Collection const& m_collection;
161     RingMap& m_ring_map;
162     Strategy const& m_strategy;
163     bool m_check_for_orientation;
164 
assign_visitorboost::geometry::detail::overlay::assign_visitor165     inline assign_visitor(Geometry1 const& g1, Geometry2 const& g2, Collection const& c,
166                           RingMap& map, Strategy const& strategy, bool check)
167         : m_geometry1(g1)
168         , m_geometry2(g2)
169         , m_collection(c)
170         , m_ring_map(map)
171         , m_strategy(strategy)
172         , m_check_for_orientation(check)
173     {}
174 
175     template <typename Item>
applyboost::geometry::detail::overlay::assign_visitor176     inline bool apply(Item const& outer, Item const& inner, bool first = true)
177     {
178         if (first && outer.abs_area < inner.abs_area)
179         {
180             // Apply with reversed arguments
181             apply(inner, outer, false);
182             return true;
183         }
184 
185         if (m_check_for_orientation
186          || (math::larger(outer.real_area, 0)
187           && math::smaller(inner.real_area, 0)))
188         {
189             ring_info_type& inner_in_map = m_ring_map[inner.id];
190 
191             if (geometry::covered_by(inner_in_map.point, outer.envelope)
192                && within_selected_input(inner_in_map, inner.id, outer.id,
193                                         m_geometry1, m_geometry2, m_collection,
194                                         m_strategy)
195                )
196             {
197                 // Assign a parent if there was no earlier parent, or the newly
198                 // found parent is smaller than the previous one
199                 if (inner_in_map.parent.source_index == -1
200                     || outer.abs_area < inner_in_map.parent_area)
201                 {
202                     inner_in_map.parent = outer.id;
203                     inner_in_map.parent_area = outer.abs_area;
204                 }
205             }
206         }
207 
208         return true;
209     }
210 };
211 
212 
213 
214 
215 template
216 <
217     typename Geometry1, typename Geometry2,
218     typename RingCollection,
219     typename RingMap,
220     typename Strategy
221 >
assign_parents(Geometry1 const & geometry1,Geometry2 const & geometry2,RingCollection const & collection,RingMap & ring_map,Strategy const & strategy,bool check_for_orientation=false)222 inline void assign_parents(Geometry1 const& geometry1,
223             Geometry2 const& geometry2,
224             RingCollection const& collection,
225             RingMap& ring_map,
226             Strategy const& strategy,
227             bool check_for_orientation = false)
228 {
229     typedef typename geometry::tag<Geometry1>::type tag1;
230     typedef typename geometry::tag<Geometry2>::type tag2;
231 
232     typedef typename RingMap::mapped_type ring_info_type;
233     typedef typename ring_info_type::point_type point_type;
234     typedef model::box<point_type> box_type;
235     typedef typename Strategy::template area_strategy
236         <
237             point_type
238         >::type::return_type area_result_type;
239 
240     typedef typename RingMap::iterator map_iterator_type;
241 
242     {
243         typedef ring_info_helper<point_type, area_result_type> helper;
244         typedef std::vector<helper> vector_type;
245         typedef typename boost::range_iterator<vector_type const>::type vector_iterator_type;
246 
247         std::size_t count_total = ring_map.size();
248         std::size_t count_positive = 0;
249         std::size_t index_positive = 0; // only used if count_positive>0
250         std::size_t index = 0;
251 
252         // Copy to vector (with new approach this might be obsolete as well, using the map directly)
253         vector_type vector(count_total);
254 
255         for (map_iterator_type it = boost::begin(ring_map);
256             it != boost::end(ring_map); ++it, ++index)
257         {
258             vector[index] = helper(it->first, it->second.get_area());
259             helper& item = vector[index];
260             switch(it->first.source_index)
261             {
262                 case 0 :
263                     geometry::envelope(get_ring<tag1>::apply(it->first, geometry1),
264                                        item.envelope, strategy.get_envelope_strategy());
265                     break;
266                 case 1 :
267                     geometry::envelope(get_ring<tag2>::apply(it->first, geometry2),
268                                        item.envelope, strategy.get_envelope_strategy());
269                     break;
270                 case 2 :
271                     geometry::envelope(get_ring<void>::apply(it->first, collection),
272                                        item.envelope, strategy.get_envelope_strategy());
273                     break;
274             }
275 
276             // Expand envelope slightly
277             expand_by_epsilon(item.envelope);
278 
279             if (item.real_area > 0)
280             {
281                 count_positive++;
282                 index_positive = index;
283             }
284         }
285 
286         if (! check_for_orientation)
287         {
288             if (count_positive == count_total)
289             {
290                 // Optimization for only positive rings
291                 // -> no assignment of parents or reversal necessary, ready here.
292                 return;
293             }
294 
295             if (count_positive == 1)
296             {
297                 // Optimization for one outer ring
298                 // -> assign this as parent to all others (all interior rings)
299                 // In unions, this is probably the most occuring case and gives
300                 //    a dramatic improvement (factor 5 for star_comb testcase)
301                 ring_identifier id_of_positive = vector[index_positive].id;
302                 ring_info_type& outer = ring_map[id_of_positive];
303                 index = 0;
304                 for (vector_iterator_type it = boost::begin(vector);
305                     it != boost::end(vector); ++it, ++index)
306                 {
307                     if (index != index_positive)
308                     {
309                         ring_info_type& inner = ring_map[it->id];
310                         inner.parent = id_of_positive;
311                         outer.children.push_back(it->id);
312                     }
313                 }
314                 return;
315             }
316         }
317 
318         assign_visitor
319             <
320                 Geometry1, Geometry2,
321                 RingCollection, RingMap,
322                 Strategy
323             > visitor(geometry1, geometry2, collection, ring_map, strategy, check_for_orientation);
324 
325         geometry::partition
326             <
327                 box_type
328             >::apply(vector, visitor, ring_info_helper_get_box(),
329                      ring_info_helper_ovelaps_box());
330     }
331 
332     if (check_for_orientation)
333     {
334         for (map_iterator_type it = boost::begin(ring_map);
335             it != boost::end(ring_map); ++it)
336         {
337             if (geometry::math::equals(it->second.get_area(), 0))
338             {
339                 it->second.discarded = true;
340             }
341             else if (it->second.parent.source_index >= 0
342                     && math::larger(it->second.get_area(), 0))
343             {
344                 const ring_info_type& parent = ring_map[it->second.parent];
345 
346                 if (math::larger(parent.area, 0))
347                 {
348                     // Discard positive inner ring with positive parent
349                     it->second.discarded = true;
350                 }
351                 // Remove parent ID from any positive inner ring
352                 it->second.parent.source_index = -1;
353             }
354             else if (it->second.parent.source_index < 0
355                     && math::smaller(it->second.get_area(), 0))
356             {
357                 // Reverse negative ring without parent
358                 it->second.reversed = true;
359             }
360         }
361     }
362 
363     // Assign childlist
364     for (map_iterator_type it = boost::begin(ring_map);
365         it != boost::end(ring_map); ++it)
366     {
367         if (it->second.parent.source_index >= 0)
368         {
369             ring_map[it->second.parent].children.push_back(it->first);
370         }
371     }
372 }
373 
374 
375 // Version for one geometry (called by buffer)
376 template
377 <
378     typename Geometry,
379     typename RingCollection,
380     typename RingMap,
381     typename Strategy
382 >
assign_parents(Geometry const & geometry,RingCollection const & collection,RingMap & ring_map,Strategy const & strategy,bool check_for_orientation)383 inline void assign_parents(Geometry const& geometry,
384             RingCollection const& collection,
385             RingMap& ring_map,
386             Strategy const& strategy,
387             bool check_for_orientation)
388 {
389     // Call it with an empty geometry as second geometry (source_id == 1)
390     // (ring_map should be empty for source_id==1)
391 
392     Geometry empty;
393     assign_parents(geometry, empty, collection, ring_map, strategy, check_for_orientation);
394 }
395 
396 
397 }} // namespace detail::overlay
398 #endif // DOXYGEN_NO_DETAIL
399 
400 
401 }} // namespace geometry
402 
403 
404 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ASSIGN_PARENTS_HPP
405