]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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/cluster_info.hpp> | |
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/ring_properties.hpp> | |
43 | #include <boost/geometry/algorithms/detail/overlay/select_rings.hpp> | |
44 | #include <boost/geometry/algorithms/detail/overlay/do_reverse.hpp> | |
45 | ||
46 | #include <boost/geometry/policies/robustness/segment_ratio_type.hpp> | |
47 | ||
48 | ||
49 | #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE | |
50 | # include <boost/geometry/io/dsv/write.hpp> | |
51 | #endif | |
52 | ||
53 | ||
54 | namespace boost { namespace geometry | |
55 | { | |
56 | ||
57 | ||
58 | #ifndef DOXYGEN_NO_DETAIL | |
59 | namespace detail { namespace overlay | |
60 | { | |
61 | ||
62 | ||
63 | //! Default visitor for overlay, doing nothing | |
64 | struct overlay_null_visitor | |
65 | { | |
66 | void print(char const* ) {} | |
67 | ||
68 | template <typename Turns> | |
69 | void print(char const* , Turns const& , int) {} | |
70 | ||
71 | template <typename Turns> | |
72 | void print(char const* , Turns const& , int , int ) {} | |
73 | ||
74 | template <typename Turns> | |
75 | void visit_turns(int , Turns const& ) {} | |
76 | ||
77 | template <typename Clusters, typename Turns> | |
78 | void visit_clusters(Clusters const& , Turns const& ) {} | |
79 | ||
80 | template <typename Turns, typename Turn, typename Operation> | |
81 | void visit_traverse(Turns const& , Turn const& , Operation const& , char const*) | |
82 | {} | |
83 | ||
84 | template <typename Turns, typename Turn, typename Operation> | |
85 | void visit_traverse_reject(Turns const& , Turn const& , Operation const& , traverse_error_type ) | |
86 | {} | |
87 | }; | |
88 | ||
89 | template <typename Turns, typename TurnInfoMap> | |
90 | inline void get_ring_turn_info(TurnInfoMap& turn_info_map, Turns const& turns) | |
91 | { | |
92 | typedef typename boost::range_value<Turns>::type turn_type; | |
93 | typedef typename turn_type::container_type container_type; | |
94 | ||
95 | for (typename boost::range_iterator<Turns const>::type | |
96 | it = boost::begin(turns); | |
97 | it != boost::end(turns); | |
98 | ++it) | |
99 | { | |
100 | typename boost::range_value<Turns>::type const& turn_info = *it; | |
101 | ||
102 | if (turn_info.discarded | |
103 | && ! turn_info.any_blocked() | |
104 | && ! turn_info.colocated) | |
105 | { | |
106 | continue; | |
107 | } | |
108 | ||
109 | for (typename boost::range_iterator<container_type const>::type | |
110 | op_it = boost::begin(turn_info.operations); | |
111 | op_it != boost::end(turn_info.operations); | |
112 | ++op_it) | |
113 | { | |
114 | ring_identifier const ring_id | |
115 | ( | |
116 | op_it->seg_id.source_index, | |
117 | op_it->seg_id.multi_index, | |
118 | op_it->seg_id.ring_index | |
119 | ); | |
120 | turn_info_map[ring_id].has_normal_turn = true; | |
121 | } | |
122 | } | |
123 | } | |
124 | ||
125 | ||
126 | template | |
127 | < | |
128 | typename GeometryOut, overlay_type OverlayType, bool ReverseOut, | |
129 | typename Geometry1, typename Geometry2, | |
130 | typename OutputIterator | |
131 | > | |
132 | inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1, | |
133 | Geometry2 const& geometry2, | |
134 | OutputIterator out) | |
135 | { | |
136 | typedef std::deque | |
137 | < | |
138 | typename geometry::ring_type<GeometryOut>::type | |
139 | > ring_container_type; | |
140 | ||
141 | typedef ring_properties<typename geometry::point_type<Geometry1>::type> properties; | |
142 | ||
143 | // Silence warning C4127: conditional expression is constant | |
144 | #if defined(_MSC_VER) | |
145 | #pragma warning(push) | |
146 | #pragma warning(disable : 4127) | |
147 | #endif | |
148 | ||
149 | // Union: return either of them | |
150 | // Intersection: return nothing | |
151 | // Difference: return first of them | |
152 | if (OverlayType == overlay_intersection | |
153 | || (OverlayType == overlay_difference && geometry::is_empty(geometry1))) | |
154 | { | |
155 | return out; | |
156 | } | |
157 | ||
158 | #if defined(_MSC_VER) | |
159 | #pragma warning(pop) | |
160 | #endif | |
161 | ||
162 | ||
163 | std::map<ring_identifier, ring_turn_info> empty; | |
164 | std::map<ring_identifier, properties> all_of_one_of_them; | |
165 | ||
166 | select_rings<OverlayType>(geometry1, geometry2, empty, all_of_one_of_them); | |
167 | ring_container_type rings; | |
168 | assign_parents(geometry1, geometry2, rings, all_of_one_of_them); | |
169 | return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out); | |
170 | } | |
171 | ||
172 | ||
173 | template | |
174 | < | |
175 | typename Geometry1, typename Geometry2, | |
176 | bool Reverse1, bool Reverse2, bool ReverseOut, | |
177 | typename GeometryOut, | |
178 | overlay_type OverlayType | |
179 | > | |
180 | struct overlay | |
181 | { | |
182 | template <typename RobustPolicy, typename OutputIterator, typename Strategy, typename Visitor> | |
183 | static inline OutputIterator apply( | |
184 | Geometry1 const& geometry1, Geometry2 const& geometry2, | |
185 | RobustPolicy const& robust_policy, | |
186 | OutputIterator out, | |
187 | Strategy const& , | |
188 | Visitor& visitor) | |
189 | { | |
190 | bool const is_empty1 = geometry::is_empty(geometry1); | |
191 | bool const is_empty2 = geometry::is_empty(geometry2); | |
192 | ||
193 | if (is_empty1 && is_empty2) | |
194 | { | |
195 | return out; | |
196 | } | |
197 | ||
198 | if (is_empty1 || is_empty2) | |
199 | { | |
200 | return return_if_one_input_is_empty | |
201 | < | |
202 | GeometryOut, OverlayType, ReverseOut | |
203 | >(geometry1, geometry2, out); | |
204 | } | |
205 | ||
206 | typedef typename geometry::point_type<GeometryOut>::type point_type; | |
207 | typedef detail::overlay::traversal_turn_info | |
208 | < | |
209 | point_type, | |
210 | typename geometry::segment_ratio_type<point_type, RobustPolicy>::type | |
211 | > turn_info; | |
212 | typedef std::deque<turn_info> turn_container_type; | |
213 | ||
214 | typedef std::deque | |
215 | < | |
216 | typename geometry::ring_type<GeometryOut>::type | |
217 | > ring_container_type; | |
218 | ||
219 | // Define the clusters, mapping cluster_id -> turns | |
220 | typedef std::map | |
221 | < | |
222 | signed_size_type, | |
223 | cluster_info | |
224 | > cluster_type; | |
225 | ||
226 | turn_container_type turns; | |
227 | ||
228 | #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE | |
229 | std::cout << "get turns" << std::endl; | |
230 | #endif | |
231 | detail::get_turns::no_interrupt_policy policy; | |
232 | geometry::get_turns | |
233 | < | |
234 | Reverse1, Reverse2, | |
235 | detail::overlay::assign_null_policy | |
236 | >(geometry1, geometry2, robust_policy, turns, policy); | |
237 | ||
238 | visitor.visit_turns(1, turns); | |
239 | ||
240 | #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE | |
241 | std::cout << "enrich" << std::endl; | |
242 | #endif | |
243 | typename Strategy::side_strategy_type side_strategy; | |
244 | cluster_type clusters; | |
245 | ||
246 | geometry::enrich_intersection_points<Reverse1, Reverse2, OverlayType>(turns, | |
247 | clusters, geometry1, geometry2, | |
248 | robust_policy, | |
249 | side_strategy); | |
250 | ||
251 | visitor.visit_turns(2, turns); | |
252 | ||
253 | visitor.visit_clusters(clusters, turns); | |
254 | ||
255 | #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE | |
256 | std::cout << "traverse" << std::endl; | |
257 | #endif | |
258 | // Traverse through intersection/turn points and create rings of them. | |
259 | // Note that these rings are always in clockwise order, even in CCW polygons, | |
260 | // and are marked as "to be reversed" below | |
261 | ring_container_type rings; | |
262 | traverse<Reverse1, Reverse2, Geometry1, Geometry2, OverlayType>::apply | |
263 | ( | |
264 | geometry1, geometry2, | |
265 | robust_policy, | |
266 | turns, rings, | |
267 | clusters, | |
268 | visitor | |
269 | ); | |
270 | ||
271 | std::map<ring_identifier, ring_turn_info> turn_info_per_ring; | |
272 | get_ring_turn_info(turn_info_per_ring, turns); | |
273 | ||
274 | typedef ring_properties | |
275 | < | |
276 | typename geometry::point_type<GeometryOut>::type | |
277 | > properties; | |
278 | ||
279 | // Select all rings which are NOT touched by any intersection point | |
280 | std::map<ring_identifier, properties> selected_ring_properties; | |
281 | select_rings<OverlayType>(geometry1, geometry2, turn_info_per_ring, | |
282 | selected_ring_properties); | |
283 | ||
284 | // Add rings created during traversal | |
285 | { | |
286 | ring_identifier id(2, 0, -1); | |
287 | for (typename boost::range_iterator<ring_container_type>::type | |
288 | it = boost::begin(rings); | |
289 | it != boost::end(rings); | |
290 | ++it) | |
291 | { | |
292 | selected_ring_properties[id] = properties(*it); | |
293 | selected_ring_properties[id].reversed = ReverseOut; | |
294 | id.multi_index++; | |
295 | } | |
296 | } | |
297 | ||
298 | assign_parents(geometry1, geometry2, rings, selected_ring_properties); | |
299 | ||
300 | return add_rings<GeometryOut>(selected_ring_properties, geometry1, geometry2, rings, out); | |
301 | } | |
302 | ||
303 | template <typename RobustPolicy, typename OutputIterator, typename Strategy> | |
304 | static inline OutputIterator apply( | |
305 | Geometry1 const& geometry1, Geometry2 const& geometry2, | |
306 | RobustPolicy const& robust_policy, | |
307 | OutputIterator out, | |
308 | Strategy const& strategy) | |
309 | { | |
310 | overlay_null_visitor visitor; | |
311 | return apply(geometry1, geometry2, robust_policy, out, strategy, visitor); | |
312 | } | |
313 | }; | |
314 | ||
315 | ||
316 | }} // namespace detail::overlay | |
317 | #endif // DOXYGEN_NO_DETAIL | |
318 | ||
319 | ||
320 | }} // namespace boost::geometry | |
321 | ||
322 | ||
323 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP |