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