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, 2017.
7 // Modifications copyright (c) 2015-2017, Oracle and/or its affiliates.
8 
9 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
10 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
11 
12 // Use, modification and distribution is subject to the Boost Software License,
13 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
14 // http://www.boost.org/LICENSE_1_0.txt)
15 
16 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP
17 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP
18 
19 
20 #include <deque>
21 #include <map>
22 
23 #include <boost/range.hpp>
24 #include <boost/mpl/assert.hpp>
25 
26 
27 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
28 #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
29 #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
30 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
31 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
32 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
33 #include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
34 #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
35 #include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp>
36 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
37 
38 #include <boost/geometry/algorithms/detail/recalculate.hpp>
39 
40 #include <boost/geometry/algorithms/is_empty.hpp>
41 #include <boost/geometry/algorithms/reverse.hpp>
42 
43 #include <boost/geometry/algorithms/detail/overlay/add_rings.hpp>
44 #include <boost/geometry/algorithms/detail/overlay/assign_parents.hpp>
45 #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
46 #include <boost/geometry/algorithms/detail/overlay/select_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 //! Default visitor for overlay, doing nothing
67 struct overlay_null_visitor
68 {
printboost::geometry::detail::overlay::overlay_null_visitor69     void print(char const* ) {}
70 
71     template <typename Turns>
printboost::geometry::detail::overlay::overlay_null_visitor72     void print(char const* , Turns const& , int) {}
73 
74     template <typename Turns>
printboost::geometry::detail::overlay::overlay_null_visitor75     void print(char const* , Turns const& , int , int ) {}
76 
77     template <typename Turns>
visit_turnsboost::geometry::detail::overlay::overlay_null_visitor78     void visit_turns(int , Turns const& ) {}
79 
80     template <typename Clusters, typename Turns>
visit_clustersboost::geometry::detail::overlay::overlay_null_visitor81     void visit_clusters(Clusters const& , Turns const& ) {}
82 
83     template <typename Turns, typename Turn, typename Operation>
visit_traverseboost::geometry::detail::overlay::overlay_null_visitor84     void visit_traverse(Turns const& , Turn const& , Operation const& , char const*)
85     {}
86 
87     template <typename Turns, typename Turn, typename Operation>
visit_traverse_rejectboost::geometry::detail::overlay::overlay_null_visitor88     void visit_traverse_reject(Turns const& , Turn const& , Operation const& , traverse_error_type )
89     {}
90 };
91 
92 template
93 <
94     overlay_type OverlayType,
95     typename TurnInfoMap,
96     typename Turns,
97     typename Clusters
98 >
get_ring_turn_info(TurnInfoMap & turn_info_map,Turns const & turns,Clusters const & clusters)99 inline void get_ring_turn_info(TurnInfoMap& turn_info_map, Turns const& turns, Clusters const& clusters)
100 {
101     typedef typename boost::range_value<Turns>::type turn_type;
102     typedef typename turn_type::container_type container_type;
103 
104     static const operation_type target_operation
105             = operation_from_overlay<OverlayType>::value;
106     static const operation_type opposite_operation
107             = target_operation == operation_union ? operation_intersection : operation_union;
108 
109     signed_size_type turn_index = 0;
110     for (typename boost::range_iterator<Turns const>::type
111             it = boost::begin(turns);
112          it != boost::end(turns);
113          ++it, turn_index++)
114     {
115         typename boost::range_value<Turns>::type const& turn = *it;
116 
117         bool const colocated_target = target_operation == operation_union
118                 ? turn.colocated_uu : turn.colocated_ii;
119         bool const colocated_opp = target_operation == operation_union
120                 ? turn.colocated_ii : turn.colocated_uu;
121         bool const both_opposite = turn.both(opposite_operation);
122 
123         bool const traversed
124                 = turn.operations[0].visited.finalized()
125                 || turn.operations[0].visited.rejected()
126                 || turn.operations[1].visited.finalized()
127                 || turn.operations[1].visited.rejected()
128                 || turn.both(operation_blocked)
129                 || turn.combination(opposite_operation, operation_blocked);
130 
131         bool is_closed = false;
132         if (turn.cluster_id >= 0 && target_operation == operation_union)
133         {
134             typename Clusters::const_iterator mit = clusters.find(turn.cluster_id);
135             BOOST_ASSERT(mit != clusters.end());
136 
137             cluster_info const& cinfo = mit->second;
138             is_closed = cinfo.open_count == 0;
139         }
140 
141         for (typename boost::range_iterator<container_type const>::type
142                 op_it = boost::begin(turn.operations);
143             op_it != boost::end(turn.operations);
144             ++op_it)
145         {
146             ring_identifier const ring_id
147                 (
148                     op_it->seg_id.source_index,
149                     op_it->seg_id.multi_index,
150                     op_it->seg_id.ring_index
151                 );
152 
153             if (traversed || is_closed || ! op_it->enriched.startable)
154             {
155                 turn_info_map[ring_id].has_traversed_turn = true;
156             }
157             else if (both_opposite && colocated_target)
158             {
159                 // For union: ii, colocated with a uu
160                 // For example, two interior rings touch where two exterior rings also touch.
161                 // The interior rings are not yet traversed, and should be taken from the input
162 
163                 // For intersection: uu, colocated with an ii
164                 // unless it is two interior inner rings colocated with a uu
165 
166                 // So don't set has_traversed_turn here
167             }
168             else if (both_opposite && ! is_self_turn<OverlayType>(turn))
169             {
170                 // For union, mark any ring with a ii turn as traversed
171                 // For intersection, any uu - but not if it is a self-turn
172                 turn_info_map[ring_id].has_traversed_turn = true;
173             }
174             else if (colocated_opp && ! colocated_target)
175             {
176                 // For union, a turn colocated with ii and NOT with uu/ux
177                 // For intersection v.v.
178                 turn_info_map[ring_id].has_traversed_turn = true;
179             }
180         }
181     }
182 }
183 
184 
185 template
186 <
187     typename GeometryOut, overlay_type OverlayType, bool ReverseOut,
188     typename Geometry1, typename Geometry2,
189     typename OutputIterator, typename Strategy
190 >
return_if_one_input_is_empty(Geometry1 const & geometry1,Geometry2 const & geometry2,OutputIterator out,Strategy const & strategy)191 inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1,
192             Geometry2 const& geometry2,
193             OutputIterator out, Strategy const& strategy)
194 {
195     typedef std::deque
196         <
197             typename geometry::ring_type<GeometryOut>::type
198         > ring_container_type;
199 
200     typedef typename geometry::point_type<Geometry1>::type point_type1;
201 
202     typedef ring_properties
203         <
204             point_type1,
205             typename Strategy::template area_strategy
206                 <
207                     point_type1
208                 >::type::return_type
209         > properties;
210 
211 // Silence warning C4127: conditional expression is constant
212 #if defined(_MSC_VER)
213 #pragma warning(push)
214 #pragma warning(disable : 4127)
215 #endif
216 
217     // Union: return either of them
218     // Intersection: return nothing
219     // Difference: return first of them
220     if (OverlayType == overlay_intersection
221         || (OverlayType == overlay_difference && geometry::is_empty(geometry1)))
222     {
223         return out;
224     }
225 
226 #if defined(_MSC_VER)
227 #pragma warning(pop)
228 #endif
229 
230 
231     std::map<ring_identifier, ring_turn_info> empty;
232     std::map<ring_identifier, properties> all_of_one_of_them;
233 
234     select_rings<OverlayType>(geometry1, geometry2, empty, all_of_one_of_them, strategy);
235     ring_container_type rings;
236     assign_parents(geometry1, geometry2, rings, all_of_one_of_them, strategy);
237     return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out);
238 }
239 
240 
241 template
242 <
243     typename Geometry1, typename Geometry2,
244     bool Reverse1, bool Reverse2, bool ReverseOut,
245     typename GeometryOut,
246     overlay_type OverlayType
247 >
248 struct overlay
249 {
250     template <typename RobustPolicy, typename OutputIterator, typename Strategy, typename Visitor>
applyboost::geometry::detail::overlay::overlay251     static inline OutputIterator apply(
252                 Geometry1 const& geometry1, Geometry2 const& geometry2,
253                 RobustPolicy const& robust_policy,
254                 OutputIterator out,
255                 Strategy const& strategy,
256                 Visitor& visitor)
257     {
258         bool const is_empty1 = geometry::is_empty(geometry1);
259         bool const is_empty2 = geometry::is_empty(geometry2);
260 
261         if (is_empty1 && is_empty2)
262         {
263             return out;
264         }
265 
266         if (is_empty1 || is_empty2)
267         {
268             return return_if_one_input_is_empty
269                 <
270                     GeometryOut, OverlayType, ReverseOut
271                 >(geometry1, geometry2, out, strategy);
272         }
273 
274         typedef typename geometry::point_type<GeometryOut>::type point_type;
275         typedef detail::overlay::traversal_turn_info
276         <
277             point_type,
278             typename geometry::segment_ratio_type<point_type, RobustPolicy>::type
279         > turn_info;
280         typedef std::deque<turn_info> turn_container_type;
281 
282         typedef std::deque
283             <
284                 typename geometry::ring_type<GeometryOut>::type
285             > ring_container_type;
286 
287         // Define the clusters, mapping cluster_id -> turns
288         typedef std::map
289             <
290                 signed_size_type,
291                 cluster_info
292             > cluster_type;
293 
294         turn_container_type turns;
295 
296 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
297 std::cout << "get turns" << std::endl;
298 #endif
299         detail::get_turns::no_interrupt_policy policy;
300         geometry::get_turns
301             <
302                 Reverse1, Reverse2,
303                 detail::overlay::assign_null_policy
304             >(geometry1, geometry2, strategy, robust_policy, turns, policy);
305 
306         visitor.visit_turns(1, turns);
307 
308 #ifdef BOOST_GEOMETRY_INCLUDE_SELF_TURNS
309         {
310             self_get_turn_points::self_turns<Reverse1, assign_null_policy>(geometry1,
311                 strategy, robust_policy, turns, policy, 0);
312             self_get_turn_points::self_turns<Reverse2, assign_null_policy>(geometry2,
313                 strategy, robust_policy, turns, policy, 1);
314         }
315 #endif
316 
317 
318 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
319 std::cout << "enrich" << std::endl;
320 #endif
321         typename Strategy::side_strategy_type side_strategy = strategy.get_side_strategy();
322         cluster_type clusters;
323 
324         geometry::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(turns,
325                 clusters, geometry1, geometry2,
326                     robust_policy,
327                     side_strategy);
328 
329         visitor.visit_turns(2, turns);
330 
331         visitor.visit_clusters(clusters, turns);
332 
333 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
334 std::cout << "traverse" << std::endl;
335 #endif
336         // Traverse through intersection/turn points and create rings of them.
337         // Note that these rings are always in clockwise order, even in CCW polygons,
338         // and are marked as "to be reversed" below
339         ring_container_type rings;
340         traverse<Reverse1, Reverse2, Geometry1, Geometry2, OverlayType>::apply
341                 (
342                     geometry1, geometry2,
343                     strategy,
344                     robust_policy,
345                     turns, rings,
346                     clusters,
347                     visitor
348                 );
349 
350         std::map<ring_identifier, ring_turn_info> turn_info_per_ring;
351         get_ring_turn_info<OverlayType>(turn_info_per_ring, turns, clusters);
352 
353         typedef typename Strategy::template area_strategy<point_type>::type area_strategy_type;
354 
355         typedef ring_properties
356             <
357                 point_type,
358                 typename area_strategy_type::return_type
359             > properties;
360 
361         // Select all rings which are NOT touched by any intersection point
362         std::map<ring_identifier, properties> selected_ring_properties;
363         select_rings<OverlayType>(geometry1, geometry2, turn_info_per_ring,
364                 selected_ring_properties, strategy);
365 
366         // Add rings created during traversal
367         {
368             area_strategy_type const area_strategy = strategy.template get_area_strategy<point_type>();
369 
370             ring_identifier id(2, 0, -1);
371             for (typename boost::range_iterator<ring_container_type>::type
372                     it = boost::begin(rings);
373                  it != boost::end(rings);
374                  ++it)
375             {
376                 selected_ring_properties[id] = properties(*it, area_strategy);
377                 selected_ring_properties[id].reversed = ReverseOut;
378                 id.multi_index++;
379             }
380         }
381 
382         assign_parents(geometry1, geometry2, rings, selected_ring_properties, strategy);
383 
384         return add_rings<GeometryOut>(selected_ring_properties, geometry1, geometry2, rings, out);
385     }
386 
387     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
applyboost::geometry::detail::overlay::overlay388     static inline OutputIterator apply(
389                 Geometry1 const& geometry1, Geometry2 const& geometry2,
390                 RobustPolicy const& robust_policy,
391                 OutputIterator out,
392                 Strategy const& strategy)
393     {
394         overlay_null_visitor visitor;
395         return apply(geometry1, geometry2, robust_policy, out, strategy, visitor);
396     }
397 };
398 
399 
400 }} // namespace detail::overlay
401 #endif // DOXYGEN_NO_DETAIL
402 
403 
404 }} // namespace boost::geometry
405 
406 
407 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP
408