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