]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. | |
11fdf7f2 | 4 | // Copyright (c) 2013-2017 Adam Wulkiewicz, Lodz, Poland |
7c673cae | 5 | |
20effc67 TL |
6 | // This file was modified by Oracle on 2015-2020. |
7 | // Modifications copyright (c) 2015-2020, Oracle and/or its affiliates. | |
7c673cae | 8 | // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle |
b32b8144 | 9 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle |
7c673cae FG |
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 | ||
20effc67 TL |
22 | #include <boost/range/begin.hpp> |
23 | #include <boost/range/end.hpp> | |
24 | #include <boost/range/value_type.hpp> | |
7c673cae FG |
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> | |
b32b8144 FG |
30 | #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp> |
31 | #include <boost/geometry/algorithms/detail/overlay/needs_self_turns.hpp> | |
7c673cae FG |
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> | |
b32b8144 | 35 | #include <boost/geometry/algorithms/detail/overlay/self_turn_points.hpp> |
7c673cae FG |
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 | ||
11fdf7f2 | 51 | #include <boost/geometry/util/condition.hpp> |
7c673cae FG |
52 | |
53 | #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE | |
54 | # include <boost/geometry/io/dsv/write.hpp> | |
55 | #endif | |
56 | ||
57 | ||
58 | namespace boost { namespace geometry | |
59 | { | |
60 | ||
61 | ||
62 | #ifndef DOXYGEN_NO_DETAIL | |
63 | namespace detail { namespace overlay | |
64 | { | |
65 | ||
66 | ||
67 | //! Default visitor for overlay, doing nothing | |
68 | struct overlay_null_visitor | |
69 | { | |
70 | void print(char const* ) {} | |
71 | ||
72 | template <typename Turns> | |
73 | void print(char const* , Turns const& , int) {} | |
74 | ||
75 | template <typename Turns> | |
76 | void print(char const* , Turns const& , int , int ) {} | |
77 | ||
78 | template <typename Turns> | |
79 | void visit_turns(int , Turns const& ) {} | |
80 | ||
81 | template <typename Clusters, typename Turns> | |
82 | void visit_clusters(Clusters const& , Turns const& ) {} | |
83 | ||
84 | template <typename Turns, typename Turn, typename Operation> | |
85 | void visit_traverse(Turns const& , Turn const& , Operation const& , char const*) | |
86 | {} | |
87 | ||
88 | template <typename Turns, typename Turn, typename Operation> | |
89 | void visit_traverse_reject(Turns const& , Turn const& , Operation const& , traverse_error_type ) | |
90 | {} | |
11fdf7f2 TL |
91 | |
92 | template <typename Rings> | |
93 | void visit_generated_rings(Rings const& ) | |
94 | {} | |
7c673cae FG |
95 | }; |
96 | ||
b32b8144 FG |
97 | template |
98 | < | |
99 | overlay_type OverlayType, | |
100 | typename TurnInfoMap, | |
101 | typename Turns, | |
102 | typename Clusters | |
103 | > | |
104 | inline void get_ring_turn_info(TurnInfoMap& turn_info_map, Turns const& turns, Clusters const& clusters) | |
7c673cae FG |
105 | { |
106 | typedef typename boost::range_value<Turns>::type turn_type; | |
b32b8144 | 107 | typedef typename turn_type::turn_operation_type turn_operation_type; |
7c673cae FG |
108 | typedef typename turn_type::container_type container_type; |
109 | ||
b32b8144 FG |
110 | static const operation_type target_operation |
111 | = operation_from_overlay<OverlayType>::value; | |
112 | static const operation_type opposite_operation | |
113 | = target_operation == operation_union | |
114 | ? operation_intersection | |
115 | : operation_union; | |
116 | ||
7c673cae FG |
117 | for (typename boost::range_iterator<Turns const>::type |
118 | it = boost::begin(turns); | |
119 | it != boost::end(turns); | |
120 | ++it) | |
121 | { | |
b32b8144 | 122 | turn_type const& turn = *it; |
7c673cae | 123 | |
b32b8144 FG |
124 | bool cluster_checked = false; |
125 | bool has_blocked = false; | |
7c673cae | 126 | |
92f5a8d4 TL |
127 | if (is_self_turn<OverlayType>(turn) && turn.discarded) |
128 | { | |
129 | // Discarded self-turns don't count as traversed | |
130 | continue; | |
131 | } | |
132 | ||
7c673cae | 133 | for (typename boost::range_iterator<container_type const>::type |
b32b8144 FG |
134 | op_it = boost::begin(turn.operations); |
135 | op_it != boost::end(turn.operations); | |
7c673cae FG |
136 | ++op_it) |
137 | { | |
b32b8144 | 138 | turn_operation_type const& op = *op_it; |
f67539c2 | 139 | ring_identifier const ring_id = ring_id_by_seg_id(op.seg_id); |
b32b8144 FG |
140 | |
141 | if (! is_self_turn<OverlayType>(turn) | |
142 | && ( | |
11fdf7f2 | 143 | (BOOST_GEOMETRY_CONDITION(target_operation == operation_union) |
b32b8144 | 144 | && op.enriched.count_left > 0) |
11fdf7f2 | 145 | || (BOOST_GEOMETRY_CONDITION(target_operation == operation_intersection) |
b32b8144 FG |
146 | && op.enriched.count_right <= 2))) |
147 | { | |
148 | // Avoid including untraversed rings which have polygons on | |
149 | // their left side (union) or not two on their right side (int) | |
150 | // This can only be done for non-self-turns because of count | |
151 | // information | |
152 | turn_info_map[ring_id].has_blocked_turn = true; | |
153 | continue; | |
154 | } | |
155 | ||
156 | if (turn.any_blocked()) | |
157 | { | |
158 | turn_info_map[ring_id].has_blocked_turn = true; | |
159 | } | |
160 | if (turn_info_map[ring_id].has_traversed_turn | |
161 | || turn_info_map[ring_id].has_blocked_turn) | |
162 | { | |
163 | continue; | |
164 | } | |
165 | ||
166 | // Check information in colocated turns | |
167 | if (! cluster_checked && turn.is_clustered()) | |
168 | { | |
169 | check_colocation(has_blocked, turn.cluster_id, turns, clusters); | |
170 | cluster_checked = true; | |
171 | } | |
172 | ||
173 | // Block rings where any other turn is blocked, | |
174 | // and (with exceptions): i for union and u for intersection | |
175 | // Exceptions: don't block self-uu for intersection | |
176 | // don't block self-ii for union | |
177 | // don't block (for union) i/u if there is an self-ii too | |
178 | if (has_blocked | |
179 | || (op.operation == opposite_operation | |
180 | && ! turn.has_colocated_both | |
181 | && ! (turn.both(opposite_operation) | |
182 | && is_self_turn<OverlayType>(turn)))) | |
183 | { | |
184 | turn_info_map[ring_id].has_blocked_turn = true; | |
185 | } | |
7c673cae FG |
186 | } |
187 | } | |
188 | } | |
189 | ||
7c673cae FG |
190 | template |
191 | < | |
192 | typename GeometryOut, overlay_type OverlayType, bool ReverseOut, | |
193 | typename Geometry1, typename Geometry2, | |
b32b8144 | 194 | typename OutputIterator, typename Strategy |
7c673cae FG |
195 | > |
196 | inline OutputIterator return_if_one_input_is_empty(Geometry1 const& geometry1, | |
197 | Geometry2 const& geometry2, | |
b32b8144 | 198 | OutputIterator out, Strategy const& strategy) |
7c673cae | 199 | { |
1e59de90 TL |
200 | typedef typename geometry::ring_type<GeometryOut>::type ring_type; |
201 | typedef std::deque<ring_type> ring_container_type; | |
b32b8144 FG |
202 | |
203 | typedef ring_properties | |
204 | < | |
1e59de90 TL |
205 | typename geometry::point_type<ring_type>::type, |
206 | typename geometry::area_result<ring_type, Strategy>::type | |
b32b8144 | 207 | > properties; |
7c673cae FG |
208 | |
209 | // Silence warning C4127: conditional expression is constant | |
210 | #if defined(_MSC_VER) | |
211 | #pragma warning(push) | |
212 | #pragma warning(disable : 4127) | |
213 | #endif | |
214 | ||
215 | // Union: return either of them | |
216 | // Intersection: return nothing | |
217 | // Difference: return first of them | |
218 | if (OverlayType == overlay_intersection | |
219 | || (OverlayType == overlay_difference && geometry::is_empty(geometry1))) | |
220 | { | |
221 | return out; | |
222 | } | |
223 | ||
224 | #if defined(_MSC_VER) | |
225 | #pragma warning(pop) | |
226 | #endif | |
227 | ||
228 | ||
229 | std::map<ring_identifier, ring_turn_info> empty; | |
230 | std::map<ring_identifier, properties> all_of_one_of_them; | |
231 | ||
b32b8144 | 232 | select_rings<OverlayType>(geometry1, geometry2, empty, all_of_one_of_them, strategy); |
7c673cae | 233 | ring_container_type rings; |
11fdf7f2 | 234 | assign_parents<OverlayType>(geometry1, geometry2, rings, all_of_one_of_them, strategy); |
1e59de90 | 235 | return add_rings<GeometryOut>(all_of_one_of_them, geometry1, geometry2, rings, out, strategy); |
7c673cae FG |
236 | } |
237 | ||
238 | ||
239 | template | |
240 | < | |
241 | typename Geometry1, typename Geometry2, | |
242 | bool Reverse1, bool Reverse2, bool ReverseOut, | |
243 | typename GeometryOut, | |
244 | overlay_type OverlayType | |
245 | > | |
246 | struct overlay | |
247 | { | |
248 | template <typename RobustPolicy, typename OutputIterator, typename Strategy, typename Visitor> | |
249 | static inline OutputIterator apply( | |
250 | Geometry1 const& geometry1, Geometry2 const& geometry2, | |
251 | RobustPolicy const& robust_policy, | |
252 | OutputIterator out, | |
b32b8144 | 253 | Strategy const& strategy, |
7c673cae FG |
254 | Visitor& visitor) |
255 | { | |
256 | bool const is_empty1 = geometry::is_empty(geometry1); | |
257 | bool const is_empty2 = geometry::is_empty(geometry2); | |
258 | ||
259 | if (is_empty1 && is_empty2) | |
260 | { | |
261 | return out; | |
262 | } | |
263 | ||
264 | if (is_empty1 || is_empty2) | |
265 | { | |
266 | return return_if_one_input_is_empty | |
267 | < | |
268 | GeometryOut, OverlayType, ReverseOut | |
b32b8144 | 269 | >(geometry1, geometry2, out, strategy); |
7c673cae FG |
270 | } |
271 | ||
272 | typedef typename geometry::point_type<GeometryOut>::type point_type; | |
273 | typedef detail::overlay::traversal_turn_info | |
274 | < | |
275 | point_type, | |
92f5a8d4 | 276 | typename segment_ratio_type<point_type, RobustPolicy>::type |
7c673cae FG |
277 | > turn_info; |
278 | typedef std::deque<turn_info> turn_container_type; | |
279 | ||
1e59de90 TL |
280 | typedef typename geometry::ring_type<GeometryOut>::type ring_type; |
281 | typedef std::deque<ring_type> ring_container_type; | |
7c673cae FG |
282 | |
283 | // Define the clusters, mapping cluster_id -> turns | |
284 | typedef std::map | |
285 | < | |
286 | signed_size_type, | |
287 | cluster_info | |
288 | > cluster_type; | |
289 | ||
290 | turn_container_type turns; | |
291 | ||
292 | #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE | |
293 | std::cout << "get turns" << std::endl; | |
294 | #endif | |
295 | detail::get_turns::no_interrupt_policy policy; | |
296 | geometry::get_turns | |
297 | < | |
298 | Reverse1, Reverse2, | |
20effc67 | 299 | assign_policy_only_start_turns |
b32b8144 | 300 | >(geometry1, geometry2, strategy, robust_policy, turns, policy); |
7c673cae FG |
301 | |
302 | visitor.visit_turns(1, turns); | |
303 | ||
11fdf7f2 | 304 | #if ! defined(BOOST_GEOMETRY_NO_SELF_TURNS) |
92f5a8d4 | 305 | if (! turns.empty() || OverlayType == overlay_dissolve) |
b32b8144 | 306 | { |
92f5a8d4 TL |
307 | // Calculate self turns if the output contains turns already, |
308 | // and if necessary (e.g.: multi-geometry, polygon with interior rings) | |
309 | if (needs_self_turns<Geometry1>::apply(geometry1)) | |
310 | { | |
20effc67 | 311 | self_get_turn_points::self_turns<Reverse1, assign_policy_only_start_turns>(geometry1, |
92f5a8d4 TL |
312 | strategy, robust_policy, turns, policy, 0); |
313 | } | |
314 | if (needs_self_turns<Geometry2>::apply(geometry2)) | |
315 | { | |
20effc67 | 316 | self_get_turn_points::self_turns<Reverse2, assign_policy_only_start_turns>(geometry2, |
92f5a8d4 TL |
317 | strategy, robust_policy, turns, policy, 1); |
318 | } | |
b32b8144 FG |
319 | } |
320 | #endif | |
321 | ||
322 | ||
7c673cae FG |
323 | #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE |
324 | std::cout << "enrich" << std::endl; | |
325 | #endif | |
92f5a8d4 | 326 | |
7c673cae | 327 | cluster_type clusters; |
b32b8144 | 328 | std::map<ring_identifier, ring_turn_info> turn_info_per_ring; |
7c673cae | 329 | |
92f5a8d4 TL |
330 | geometry::enrich_intersection_points<Reverse1, Reverse2, OverlayType>( |
331 | turns, clusters, geometry1, geometry2, robust_policy, strategy); | |
7c673cae FG |
332 | |
333 | visitor.visit_turns(2, turns); | |
334 | ||
335 | visitor.visit_clusters(clusters, turns); | |
336 | ||
337 | #ifdef BOOST_GEOMETRY_DEBUG_ASSEMBLE | |
338 | std::cout << "traverse" << std::endl; | |
339 | #endif | |
340 | // Traverse through intersection/turn points and create rings of them. | |
1e59de90 TL |
341 | // These rings are always in clockwise order. |
342 | // In CCW polygons they are marked as "to be reversed" below. | |
7c673cae FG |
343 | ring_container_type rings; |
344 | traverse<Reverse1, Reverse2, Geometry1, Geometry2, OverlayType>::apply | |
345 | ( | |
346 | geometry1, geometry2, | |
b32b8144 | 347 | strategy, |
7c673cae FG |
348 | robust_policy, |
349 | turns, rings, | |
b32b8144 | 350 | turn_info_per_ring, |
7c673cae FG |
351 | clusters, |
352 | visitor | |
353 | ); | |
b32b8144 | 354 | visitor.visit_turns(3, turns); |
7c673cae | 355 | |
b32b8144 FG |
356 | get_ring_turn_info<OverlayType>(turn_info_per_ring, turns, clusters); |
357 | ||
7c673cae | 358 | typedef ring_properties |
b32b8144 FG |
359 | < |
360 | point_type, | |
1e59de90 | 361 | typename geometry::area_result<ring_type, Strategy>::type |
b32b8144 | 362 | > properties; |
7c673cae FG |
363 | |
364 | // Select all rings which are NOT touched by any intersection point | |
365 | std::map<ring_identifier, properties> selected_ring_properties; | |
366 | select_rings<OverlayType>(geometry1, geometry2, turn_info_per_ring, | |
b32b8144 | 367 | selected_ring_properties, strategy); |
7c673cae FG |
368 | |
369 | // Add rings created during traversal | |
370 | { | |
371 | ring_identifier id(2, 0, -1); | |
1e59de90 | 372 | for (auto const& ring : rings) |
7c673cae | 373 | { |
1e59de90 | 374 | selected_ring_properties[id] = properties(ring, strategy); |
7c673cae FG |
375 | selected_ring_properties[id].reversed = ReverseOut; |
376 | id.multi_index++; | |
377 | } | |
378 | } | |
379 | ||
11fdf7f2 TL |
380 | assign_parents<OverlayType>(geometry1, geometry2, |
381 | rings, selected_ring_properties, strategy); | |
b32b8144 FG |
382 | |
383 | // NOTE: There is no need to check result area for union because | |
384 | // as long as the polygons in the input are valid the resulting | |
385 | // polygons should be valid as well. | |
386 | // By default the area is checked (this is old behavior) however this | |
387 | // can be changed with #define. This may be important in non-cartesian CSes. | |
388 | // The result may be too big, so the area is negative. In this case either | |
389 | // it can be returned or an exception can be thrown. | |
390 | return add_rings<GeometryOut>(selected_ring_properties, geometry1, geometry2, rings, out, | |
1e59de90 | 391 | strategy, |
b32b8144 FG |
392 | OverlayType == overlay_union ? |
393 | #if defined(BOOST_GEOMETRY_UNION_THROW_INVALID_OUTPUT_EXCEPTION) | |
394 | add_rings_throw_if_reversed | |
395 | #elif defined(BOOST_GEOMETRY_UNION_RETURN_INVALID) | |
396 | add_rings_add_unordered | |
397 | #else | |
398 | add_rings_ignore_unordered | |
399 | #endif | |
400 | : add_rings_ignore_unordered); | |
7c673cae FG |
401 | } |
402 | ||
403 | template <typename RobustPolicy, typename OutputIterator, typename Strategy> | |
404 | static inline OutputIterator apply( | |
405 | Geometry1 const& geometry1, Geometry2 const& geometry2, | |
406 | RobustPolicy const& robust_policy, | |
407 | OutputIterator out, | |
408 | Strategy const& strategy) | |
409 | { | |
410 | overlay_null_visitor visitor; | |
411 | return apply(geometry1, geometry2, robust_policy, out, strategy, visitor); | |
412 | } | |
413 | }; | |
414 | ||
415 | ||
416 | }} // namespace detail::overlay | |
417 | #endif // DOXYGEN_NO_DETAIL | |
418 | ||
419 | ||
420 | }} // namespace boost::geometry | |
421 | ||
422 | ||
423 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_OVERLAY_HPP |