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, 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 
26 #include <boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp>
27 #include <boost/geometry/algorithms/detail/overlay/enrichment_info.hpp>
28 #include <boost/geometry/algorithms/detail/overlay/get_turns.hpp>
29 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
30 #include <boost/geometry/algorithms/detail/overlay/traverse.hpp>
31 #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
32 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
33 
34 #include <boost/geometry/algorithms/detail/recalculate.hpp>
35 
36 #include <boost/geometry/algorithms/is_empty.hpp>
37 #include <boost/geometry/algorithms/reverse.hpp>
38 
39 #include <boost/geometry/algorithms/detail/overlay/add_rings.hpp>
40 #include <boost/geometry/algorithms/detail/overlay/assign_parents.hpp>
41 #include <boost/geometry/algorithms/detail/overlay/ring_properties.hpp>
42 #include <boost/geometry/algorithms/detail/overlay/select_rings.hpp>
43 #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp>
44 
45 #include <boost/geometry/policies/robustness/segment_ratio_type.hpp>
46 
47 
48 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
49 #  include <boost/geometry/io/dsv/write.hpp>
50 #endif
51 
52 
53 namespace boost { namespace geometry
54 {
55 
56 
57 #ifndef DOXYGEN_NO_DETAIL
58 namespace detail { namespace overlay
59 {
60 
61 
62 template <typename TurnPoints, typename TurnInfoMap>
get_ring_turn_info(TurnInfoMap & turn_info_map,TurnPoints const & turn_points)63 inline void get_ring_turn_info(TurnInfoMap& turn_info_map,
64         TurnPoints const& turn_points)
65 {
66     typedef typename boost::range_value<TurnPoints>::type turn_point_type;
67     typedef typename turn_point_type::container_type container_type;
68 
69     for (typename boost::range_iterator<TurnPoints const>::type
70             it = boost::begin(turn_points);
71          it != boost::end(turn_points);
72          ++it)
73     {
74         typename boost::range_value<TurnPoints>::type const& turn_info = *it;
75         bool both_uu = turn_info.both(operation_union);
76         bool skip = (turn_info.discarded || both_uu)
77             && ! turn_info.any_blocked()
78             && ! turn_info.both(operation_intersection)
79             ;
80 
81         for (typename boost::range_iterator<container_type const>::type
82                 op_it = boost::begin(turn_info.operations);
83             op_it != boost::end(turn_info.operations);
84             ++op_it)
85         {
86             ring_identifier ring_id
87                 (
88                     op_it->seg_id.source_index,
89                     op_it->seg_id.multi_index,
90                     op_it->seg_id.ring_index
91                 );
92 
93             if (! skip)
94             {
95                 turn_info_map[ring_id].has_normal_turn = true;
96             }
97             else if (both_uu)
98             {
99                 turn_info_map[ring_id].has_uu_turn = true;
100             }
101         }
102     }
103 }
104 
105 
106 template
107 <
108     typename GeometryOut, overlay_type Direction, bool ReverseOut,
109     typename Geometry1, typename Geometry2,
110     typename OutputIterator
111 >
return_if_one_input_is_empty(Geometry1 const & geometry1,Geometry2 const & geometry2,OutputIterator out)112 inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1,
113             Geometry2 const& geometry2,
114             OutputIterator out)
115 {
116     typedef std::deque
117         <
118             typename geometry::ring_type<GeometryOut>::type
119         > ring_container_type;
120 
121     typedef ring_properties<typename geometry::point_type<Geometry1>::type> properties;
122 
123 // Silence warning C4127: conditional expression is constant
124 #if defined(_MSC_VER)
125 #pragma warning(push)
126 #pragma warning(disable : 4127)
127 #endif
128 
129     // Union: return either of them
130     // Intersection: return nothing
131     // Difference: return first of them
132     if (Direction == overlay_intersection
133         || (Direction == overlay_difference && geometry::is_empty(geometry1)))
134     {
135         return out;
136     }
137 
138 #if defined(_MSC_VER)
139 #pragma warning(pop)
140 #endif
141 
142 
143     std::map<ring_identifier, ring_turn_info> empty;
144     std::map<ring_identifier, properties> all_of_one_of_them;
145 
146     select_rings<Direction>(geometry1, geometry2, empty, all_of_one_of_them);
147     ring_container_type rings;
148     assign_parents(geometry1, geometry2, rings, all_of_one_of_them);
149     return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out);
150 }
151 
152 
153 template
154 <
155     typename Geometry1, typename Geometry2,
156     bool Reverse1, bool Reverse2, bool ReverseOut,
157     typename GeometryOut,
158     overlay_type Direction
159 >
160 struct overlay
161 {
162     template <typename RobustPolicy, typename OutputIterator, typename Strategy>
applyboost::geometry::detail::overlay::overlay163     static inline OutputIterator apply(
164                 Geometry1 const& geometry1, Geometry2 const& geometry2,
165                 RobustPolicy const& robust_policy,
166                 OutputIterator out,
167                 Strategy const& )
168     {
169         bool const is_empty1 = geometry::is_empty(geometry1);
170         bool const is_empty2 = geometry::is_empty(geometry2);
171 
172         if (is_empty1 && is_empty2)
173         {
174             return out;
175         }
176 
177         if (is_empty1 || is_empty2)
178         {
179             return return_if_one_input_is_empty
180                 <
181                     GeometryOut, Direction, ReverseOut
182                 >(geometry1, geometry2, out);
183         }
184 
185         typedef typename geometry::point_type<GeometryOut>::type point_type;
186         typedef detail::overlay::traversal_turn_info
187         <
188             point_type,
189             typename geometry::segment_ratio_type<point_type, RobustPolicy>::type
190         > turn_info;
191         typedef std::deque<turn_info> container_type;
192 
193         typedef std::deque
194             <
195                 typename geometry::ring_type<GeometryOut>::type
196             > ring_container_type;
197 
198         container_type turn_points;
199 
200 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
201 std::cout << "get turns" << std::endl;
202 #endif
203         detail::get_turns::no_interrupt_policy policy;
204         geometry::get_turns
205             <
206                 Reverse1, Reverse2,
207                 detail::overlay::assign_null_policy
208             >(geometry1, geometry2, robust_policy, turn_points, policy);
209 
210 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
211 std::cout << "enrich" << std::endl;
212 #endif
213         typename Strategy::side_strategy_type side_strategy;
214         geometry::enrich_intersection_points<Reverse1, Reverse2>(turn_points,
215                 Direction == overlay_union
216                     ? geometry::detail::overlay::operation_union
217                     : geometry::detail::overlay::operation_intersection,
218                     geometry1, geometry2,
219                     robust_policy,
220                     side_strategy);
221 
222 #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE
223 std::cout << "traverse" << std::endl;
224 #endif
225         // Traverse through intersection/turn points and create rings of them.
226         // Note that these rings are always in clockwise order, even in CCW polygons,
227         // and are marked as "to be reversed" below
228         ring_container_type rings;
229         traverse<Reverse1, Reverse2, Geometry1, Geometry2>::apply
230                 (
231                     geometry1, geometry2,
232                     Direction == overlay_union
233                         ? geometry::detail::overlay::operation_union
234                         : geometry::detail::overlay::operation_intersection,
235                     robust_policy,
236                     turn_points, rings
237                 );
238 
239         std::map<ring_identifier, ring_turn_info> turn_info_per_ring;
240         get_ring_turn_info(turn_info_per_ring, turn_points);
241 
242         typedef ring_properties
243         <
244             typename geometry::point_type<GeometryOut>::type
245         > properties;
246 
247         // Select all rings which are NOT touched by any intersection point
248         std::map<ring_identifier, properties> selected_ring_properties;
249         select_rings<Direction>(geometry1, geometry2, turn_info_per_ring,
250                 selected_ring_properties);
251 
252         // Add rings created during traversal
253         {
254             ring_identifier id(2, 0, -1);
255             for (typename boost::range_iterator<ring_container_type>::type
256                     it = boost::begin(rings);
257                  it != boost::end(rings);
258                  ++it)
259             {
260                 selected_ring_properties[id] = properties(*it);
261                 selected_ring_properties[id].reversed = ReverseOut;
262                 id.multi_index++;
263             }
264         }
265 
266         assign_parents(geometry1, geometry2, rings, selected_ring_properties);
267 
268         return add_rings<GeometryOut>(selected_ring_properties, geometry1, geometry2, rings, out);
269     }
270 };
271 
272 
273 }} // namespace detail::overlay
274 #endif // DOXYGEN_NO_DETAIL
275 
276 
277 }} // namespace boost::geometry
278 
279 
280 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP
281