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 
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
10 
11 // Use, modification and distribution is subject to the Boost Software License,
12 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
13 // http://www.boost.org/LICENSE_1_0.txt)
14 
15 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ADD_RINGS_HPP
16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ADD_RINGS_HPP
17 
18 #include <boost/range/begin.hpp>
19 #include <boost/range/end.hpp>
20 #include <boost/range/value_type.hpp>
21 #include <boost/throw_exception.hpp>
22 
23 #include <boost/geometry/core/closure.hpp>
24 #include <boost/geometry/core/exception.hpp>
25 #include <boost/geometry/algorithms/area.hpp>
26 #include <boost/geometry/algorithms/detail/overlay/convert_ring.hpp>
27 #include <boost/geometry/algorithms/detail/overlay/get_ring.hpp>
28 
29 
30 namespace boost { namespace geometry
31 {
32 
33 
34 #ifndef DOXYGEN_NO_DETAIL
35 namespace detail { namespace overlay
36 {
37 
38 template
39 <
40     typename GeometryOut,
41     typename Geometry1,
42     typename Geometry2,
43     typename RingCollection
44 >
convert_and_add(GeometryOut & result,Geometry1 const & geometry1,Geometry2 const & geometry2,RingCollection const & collection,ring_identifier id,bool reversed,bool append)45 inline void convert_and_add(GeometryOut& result,
46             Geometry1 const& geometry1, Geometry2 const& geometry2,
47             RingCollection const& collection,
48             ring_identifier id,
49             bool reversed, bool append)
50 {
51     typedef typename geometry::tag<Geometry1>::type tag1;
52     typedef typename geometry::tag<Geometry2>::type tag2;
53     typedef typename geometry::tag<GeometryOut>::type tag_out;
54 
55     if (id.source_index == 0)
56     {
57         convert_ring<tag_out>::apply(result,
58                     get_ring<tag1>::apply(id, geometry1),
59                     append, reversed);
60     }
61     else if (id.source_index == 1)
62     {
63         convert_ring<tag_out>::apply(result,
64                     get_ring<tag2>::apply(id, geometry2),
65                     append, reversed);
66     }
67     else if (id.source_index == 2)
68     {
69         convert_ring<tag_out>::apply(result,
70                     get_ring<void>::apply(id, collection),
71                     append, reversed);
72     }
73 }
74 
75 enum add_rings_error_handling
76 {
77     add_rings_ignore_unordered,
78     add_rings_add_unordered,
79     add_rings_throw_if_reversed
80 };
81 
82 template
83 <
84     typename GeometryOut,
85     typename SelectionMap,
86     typename Geometry1,
87     typename Geometry2,
88     typename RingCollection,
89     typename OutputIterator,
90     typename Strategy
91 >
add_rings(SelectionMap const & map,Geometry1 const & geometry1,Geometry2 const & geometry2,RingCollection const & collection,OutputIterator out,Strategy const & strategy,add_rings_error_handling error_handling=add_rings_ignore_unordered)92 inline OutputIterator add_rings(SelectionMap const& map,
93             Geometry1 const& geometry1, Geometry2 const& geometry2,
94             RingCollection const& collection,
95             OutputIterator out,
96             Strategy const& strategy,
97             add_rings_error_handling error_handling = add_rings_ignore_unordered)
98 {
99     typedef typename SelectionMap::const_iterator iterator;
100 
101     std::size_t const min_num_points = core_detail::closure::minimum_ring_size
102         <
103             geometry::closure
104                 <
105                     typename boost::range_value
106                         <
107                             RingCollection const
108                         >::type
109                 >::value
110         >::value;
111 
112 
113     for (iterator it = boost::begin(map);
114         it != boost::end(map);
115         ++it)
116     {
117         if (! it->second.discarded
118             && it->second.parent.source_index == -1)
119         {
120             GeometryOut result;
121             convert_and_add(result, geometry1, geometry2, collection,
122                     it->first, it->second.reversed, false);
123 
124             // Add children
125             for (typename std::vector<ring_identifier>::const_iterator child_it
126                         = it->second.children.begin();
127                 child_it != it->second.children.end();
128                 ++child_it)
129             {
130                 iterator mit = map.find(*child_it);
131                 if (mit != map.end()
132                     && ! mit->second.discarded)
133                 {
134                     convert_and_add(result, geometry1, geometry2, collection,
135                             *child_it, mit->second.reversed, true);
136                 }
137             }
138 
139             // Only add rings if they satisfy minimal requirements.
140             // This cannot be done earlier (during traversal), not
141             // everything is figured out yet (sum of positive/negative rings)
142             if (geometry::num_points(result) >= min_num_points)
143             {
144                 typedef typename geometry::area_result<GeometryOut, Strategy>::type area_type;
145                 area_type const area = geometry::area(result, strategy);
146                 area_type const zero = 0;
147                 // Ignore if area is 0
148                 if (! math::equals(area, zero))
149                 {
150                     if (error_handling == add_rings_add_unordered
151                         || area > zero)
152                     {
153                         *out++ = result;
154                     }
155                     else if (error_handling == add_rings_throw_if_reversed)
156                     {
157                         BOOST_THROW_EXCEPTION(invalid_output_exception());
158                     }
159                 }
160             }
161         }
162     }
163     return out;
164 }
165 
166 
167 template
168 <
169     typename GeometryOut,
170     typename SelectionMap,
171     typename Geometry,
172     typename RingCollection,
173     typename OutputIterator,
174     typename Strategy
175 >
add_rings(SelectionMap const & map,Geometry const & geometry,RingCollection const & collection,OutputIterator out,Strategy const & strategy)176 inline OutputIterator add_rings(SelectionMap const& map,
177             Geometry const& geometry,
178             RingCollection const& collection,
179             OutputIterator out,
180             Strategy const& strategy)
181 {
182     Geometry empty;
183     return add_rings<GeometryOut>(map, geometry, empty, collection, out, strategy);
184 }
185 
186 
187 }} // namespace detail::overlay
188 #endif // DOXYGEN_NO_DETAIL
189 
190 
191 }} // namespace geometry
192 
193 
194 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ADD_RINGS_HPP
195