1 // Boost.Geometry (aka GGL, Generic Geometry Library)
2
3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
4 // Copyright (c) 2013-2015 Adam Wulkiewicz, Lodz, Poland
5
6 // This file was modified by Oracle on 2015.
7 // Modifications Copyright (c) 2015, 2021, Oracle and/or its affiliates.
8
9 // Contributed and/or modified by Menelaos Karavelas, 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_OVERLAY_HPP
16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP
17
18
19 #include <deque>
20 #include <map>
21
22 #include <boost/range.hpp>
23 #include <boost/mpl/assert.hpp>
24
25 #include <boost/geometry/core/ring_type.hpp>
26
27 #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
28 #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
29 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
30 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
31 #include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
32 #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
33 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
34
35 #include <boost/geometry/algorithms/detail/recalculate.hpp>
36
37 #include <boost/geometry/algorithms/is_empty.hpp>
38 #include <boost/geometry/algorithms/reverse.hpp>
39
40 #include <boost/geometry/algorithms/detail/overlay/add_rings.hpp>
41 #include <boost/geometry/algorithms/detail/overlay/assign_parents.hpp>
42 #include <boost/geometry/algorithms/detail/overlay/insert_touch_interior_turns.hpp>
43 #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
44 #include <boost/geometry/algorithms/detail/overlay/select_rings.hpp>
45 #include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
46 #include <boost/geometry/algorithms/detail/overlay/split_rings.hpp>
47 #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
48
49 #include <boost/geometry/policies/robustness/segment_ratio_type.hpp>
50
51
52 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
53 # include <boost/geometry/io/dsv/write.hpp>
54 #endif
55
56
57 namespace boost { namespace geometry
58 {
59
60
61 #ifndef DOXYGEN_NO_DETAIL
62 namespace detail { namespace overlay
63 {
64
65
66 template <typename TurnPoints, typename TurnInfoMap>
get_ring_turn_info(TurnInfoMap & turn_info_map,TurnPoints const & turn_points)67 inline void get_ring_turn_info(TurnInfoMap& turn_info_map,
68 TurnPoints const& turn_points)
69 {
70 typedef typename boost::range_value<TurnPoints>::type turn_point_type;
71 typedef typename turn_point_type::container_type container_type;
72
73 for (typename boost::range_iterator<TurnPoints const>::type
74 it = boost::begin(turn_points);
75 it != boost::end(turn_points);
76 ++it)
77 {
78 typename boost::range_value<TurnPoints>::type const& turn_info = *it;
79 bool both_uu = turn_info.both(operation_union);
80 bool skip = (turn_info.discarded || both_uu)
81 && ! turn_info.any_blocked()
82 && ! turn_info.both(operation_intersection)
83 ;
84
85 if (! both_uu && turn_info.colocated)
86 {
87 skip = true;
88 }
89
90 for (typename boost::range_iterator<container_type const>::type
91 op_it = boost::begin(turn_info.operations);
92 op_it != boost::end(turn_info.operations);
93 ++op_it)
94 {
95 ring_identifier ring_id
96 (
97 op_it->seg_id.source_index,
98 op_it->seg_id.multi_index,
99 op_it->seg_id.ring_index
100 );
101
102 if (! skip)
103 {
104 turn_info_map[ring_id].has_normal_turn = true;
105 }
106 else if (both_uu)
107 {
108 turn_info_map[ring_id].has_uu_turn = true;
109 }
110 }
111 }
112 }
113
114
115 template
116 <
117 typename GeometryOut, overlay_type OverlayType, bool ReverseOut,
118 typename Geometry1, typename Geometry2,
119 typename OutputIterator
120 >
return_if_one_input_is_empty(Geometry1 const & geometry1,Geometry2 const & geometry2,OutputIterator out)121 inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1,
122 Geometry2 const& geometry2,
123 OutputIterator out)
124 {
125 typedef std::deque
126 <
127 typename geometry::ring_type<GeometryOut>::type
128 > ring_container_type;
129
130 typedef ring_properties<typename geometry::point_type<Geometry1>::type> properties;
131
132 // Silence warning C4127: conditional expression is constant
133 #if defined(_MSC_VER)
134 #pragma warning(push)
135 #pragma warning(disable : 4127)
136 #endif
137
138 // Union: return either of them
139 // Intersection: return nothing
140 // Difference: return first of them
141 if (OverlayType == overlay_intersection
142 || (OverlayType == overlay_difference && geometry::is_empty(geometry1)))
143 {
144 return out;
145 }
146
147 #if defined(_MSC_VER)
148 #pragma warning(pop)
149 #endif
150
151
152 std::map<ring_identifier, ring_turn_info> empty;
153 std::map<ring_identifier, properties> all_of_one_of_them;
154
155 select_rings<OverlayType>(geometry1, geometry2, empty, all_of_one_of_them);
156 ring_container_type rings;
157 assign_parents(geometry1, geometry2, rings, all_of_one_of_them);
158 return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out);
159 }
160
161
162 template
163 <
164 typename Geometry1, typename Geometry2,
165 bool Reverse1, bool Reverse2, bool ReverseOut,
166 typename GeometryOut,
167 overlay_type OverlayType
168 >
169 class overlay
170 {
171 private:
172 template <typename RobustPolicy, typename OutputIterator, typename Strategy>
do_overlay(Geometry1 const & geometry1,Geometry2 const & geometry2,RobustPolicy const & robust_policy,OutputIterator out,Strategy const &)173 static inline OutputIterator do_overlay(
174 Geometry1 const& geometry1, Geometry2 const& geometry2,
175 RobustPolicy const& robust_policy,
176 OutputIterator out,
177 Strategy const& )
178 {
179 bool const is_empty1 = geometry::is_empty(geometry1);
180 bool const is_empty2 = geometry::is_empty(geometry2);
181
182 if (is_empty1 && is_empty2)
183 {
184 return out;
185 }
186
187 if (is_empty1 || is_empty2)
188 {
189 return return_if_one_input_is_empty
190 <
191 GeometryOut, OverlayType, ReverseOut
192 >(geometry1, geometry2, out);
193 }
194
195 typedef typename geometry::point_type<GeometryOut>::type point_type;
196 typedef detail::overlay::traversal_turn_info
197 <
198 point_type,
199 typename geometry::segment_ratio_type<point_type, RobustPolicy>::type
200 > turn_info;
201 typedef std::deque<turn_info> container_type;
202
203 typedef std::deque
204 <
205 typename geometry::ring_type<GeometryOut>::type
206 > ring_container_type;
207
208 container_type turn_points;
209
210 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
211 std::cout << "get turns" << std::endl;
212 #endif
213 detail::get_turns::no_interrupt_policy policy;
214 geometry::get_turns
215 <
216 Reverse1, Reverse2,
217 detail::overlay::assign_null_policy
218 >(geometry1, geometry2, robust_policy, turn_points, policy);
219
220 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
221 std::cout << "enrich" << std::endl;
222 #endif
223 typename Strategy::side_strategy_type side_strategy;
224 geometry::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(turn_points,
225 OverlayType == overlay_union
226 ? geometry::detail::overlay::operation_union
227 : geometry::detail::overlay::operation_intersection,
228 geometry1, geometry2,
229 robust_policy,
230 side_strategy);
231
232 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
233 std::cout << "traverse" << std::endl;
234 #endif
235 // Traverse through intersection/turn points and create rings of them.
236 // Note that these rings are always in clockwise order, even in CCW polygons,
237 // and are marked as "to be reversed" below
238 ring_container_type rings;
239 traverse<Reverse1, Reverse2, Geometry1, Geometry2>::apply
240 (
241 geometry1, geometry2,
242 OverlayType == overlay_union
243 ? geometry::detail::overlay::operation_union
244 : geometry::detail::overlay::operation_intersection,
245 robust_policy,
246 turn_points, rings
247 );
248
249 std::map<ring_identifier, ring_turn_info> turn_info_per_ring;
250 get_ring_turn_info(turn_info_per_ring, turn_points);
251
252 typedef ring_properties
253 <
254 typename geometry::point_type<GeometryOut>::type
255 > properties;
256
257 // Select all rings which are NOT touched by any intersection point
258 std::map<ring_identifier, properties> selected_ring_properties;
259 select_rings<OverlayType>(geometry1, geometry2, turn_info_per_ring,
260 selected_ring_properties);
261
262 // split the rings into simple rings
263 split_rings<OverlayType>::apply(rings, robust_policy);
264
265 // Add rings created during traversal
266 {
267 ring_identifier id(2, 0, -1);
268 for (typename boost::range_iterator<ring_container_type>::type
269 it = boost::begin(rings);
270 it != boost::end(rings);
271 ++it)
272 {
273 selected_ring_properties[id] = properties(*it);
274 selected_ring_properties[id].reversed = ReverseOut;
275 id.multi_index++;
276 }
277 }
278
279 assign_parents(geometry1, geometry2, rings, selected_ring_properties);
280
281 return add_rings<GeometryOut>(selected_ring_properties, geometry1, geometry2, rings, out);
282 }
283
284 public:
285 template <typename RobustPolicy, typename OutputIterator, typename Strategy>
apply(Geometry1 const & geometry1,Geometry2 const & geometry2,RobustPolicy const & robust_policy,OutputIterator out,Strategy const & strategy)286 static inline OutputIterator apply(
287 Geometry1 const& geometry1, Geometry2 const& geometry2,
288 RobustPolicy const& robust_policy,
289 OutputIterator out,
290 Strategy const& strategy)
291 {
292 bool const is_empty1 = geometry::is_empty(geometry1);
293 bool const is_empty2 = geometry::is_empty(geometry2);
294
295 if (is_empty1 && is_empty2)
296 {
297 return out;
298 }
299
300 if (is_empty1 || is_empty2)
301 {
302 return return_if_one_input_is_empty
303 <
304 GeometryOut, OverlayType, ReverseOut
305 >(geometry1, geometry2, out);
306 }
307
308 Geometry1 modified_geometry1;
309 bool modified1 = insert_touch_interior_turns(geometry1,
310 modified_geometry1,
311 robust_policy);
312
313 Geometry2 modified_geometry2;
314 bool modified2 = insert_touch_interior_turns(geometry2,
315 modified_geometry2,
316 robust_policy);
317
318 if (modified1 && modified2)
319 {
320 return do_overlay(modified_geometry1, modified_geometry2,
321 robust_policy, out, strategy);
322 }
323 else if (! modified1 && modified2)
324 {
325 return do_overlay(geometry1, modified_geometry2,
326 robust_policy, out, strategy);
327 }
328 else if (modified1 && ! modified2)
329 {
330 return do_overlay(modified_geometry1, geometry2,
331 robust_policy, out, strategy);
332 }
333 else
334 {
335 return do_overlay(geometry1, geometry2,
336 robust_policy, out, strategy);
337 }
338 }
339 };
340
341
342 }} // namespace detail::overlay
343 #endif // DOXYGEN_NO_DETAIL
344
345
346 }} // namespace boost::geometry
347
348
349 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP
350