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