]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
3 | // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands. | |
4 | ||
1e59de90 TL |
5 | // This file was modified by Oracle on 2014-2021. |
6 | // Modifications copyright (c) 2014-2021 Oracle and/or its affiliates. | |
7c673cae FG |
7 | // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle |
8 | // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle | |
9 | ||
10 | // Use, modification and distribution is subject to the Boost Software License, | |
11 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
12 | // http://www.boost.org/LICENSE_1_0.txt) | |
13 | ||
14 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENTS_HPP | |
15 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENTS_HPP | |
16 | ||
17 | ||
20effc67 | 18 | #include <type_traits> |
7c673cae FG |
19 | #include <vector> |
20 | ||
21 | #include <boost/array.hpp> | |
20effc67 TL |
22 | #include <boost/range/begin.hpp> |
23 | #include <boost/range/end.hpp> | |
24 | #include <boost/range/size.hpp> | |
7c673cae | 25 | |
92f5a8d4 TL |
26 | #include <boost/geometry/algorithms/detail/assign_box_corners.hpp> |
27 | #include <boost/geometry/algorithms/detail/signed_size_type.hpp> | |
28 | #include <boost/geometry/algorithms/detail/overlay/append_no_duplicates.hpp> | |
29 | #include <boost/geometry/algorithms/detail/overlay/append_no_dups_or_spikes.hpp> | |
30 | #include <boost/geometry/algorithms/not_implemented.hpp> | |
31 | ||
7c673cae FG |
32 | #include <boost/geometry/core/assert.hpp> |
33 | #include <boost/geometry/core/exterior_ring.hpp> | |
34 | #include <boost/geometry/core/interior_rings.hpp> | |
35 | #include <boost/geometry/core/ring_type.hpp> | |
36 | #include <boost/geometry/core/tags.hpp> | |
92f5a8d4 | 37 | |
7c673cae | 38 | #include <boost/geometry/geometries/concepts/check.hpp> |
7c673cae | 39 | |
92f5a8d4 | 40 | #include <boost/geometry/iterators/ever_circling_iterator.hpp> |
7c673cae FG |
41 | |
42 | #include <boost/geometry/util/range.hpp> | |
43 | ||
1e59de90 | 44 | #include <boost/geometry/views/detail/closed_clockwise_view.hpp> |
92f5a8d4 | 45 | |
7c673cae FG |
46 | |
47 | namespace boost { namespace geometry | |
48 | { | |
49 | ||
50 | ||
51 | #ifndef DOXYGEN_NO_DETAIL | |
52 | namespace detail { namespace copy_segments | |
53 | { | |
54 | ||
55 | ||
56 | template <bool Reverse> | |
57 | struct copy_segments_ring | |
58 | { | |
59 | template | |
60 | < | |
61 | typename Ring, | |
62 | typename SegmentIdentifier, | |
1e59de90 | 63 | typename Strategy, |
7c673cae FG |
64 | typename RobustPolicy, |
65 | typename RangeOut | |
66 | > | |
67 | static inline void apply(Ring const& ring, | |
68 | SegmentIdentifier const& seg_id, | |
69 | signed_size_type to_index, | |
1e59de90 | 70 | Strategy const& strategy, |
7c673cae FG |
71 | RobustPolicy const& robust_policy, |
72 | RangeOut& current_output) | |
73 | { | |
1e59de90 TL |
74 | using view_type = detail::closed_clockwise_view |
75 | < | |
76 | Ring const, | |
77 | closure<Ring>::value, | |
78 | Reverse ? counterclockwise : clockwise | |
79 | >; | |
7c673cae | 80 | |
1e59de90 TL |
81 | using iterator = typename boost::range_iterator<view_type const>::type; |
82 | using ec_iterator = geometry::ever_circling_iterator<iterator>; | |
7c673cae | 83 | |
1e59de90 | 84 | view_type view(ring); |
7c673cae FG |
85 | |
86 | // The problem: sometimes we want to from "3" to "2" | |
87 | // -> end = "3" -> end == begin | |
88 | // This is not convenient with iterators. | |
89 | ||
90 | // So we use the ever-circling iterator and determine when to step out | |
91 | ||
92 | signed_size_type const from_index = seg_id.segment_index + 1; | |
93 | ||
94 | // Sanity check | |
95 | BOOST_GEOMETRY_ASSERT(from_index < static_cast<signed_size_type>(boost::size(view))); | |
96 | ||
97 | ec_iterator it(boost::begin(view), boost::end(view), | |
98 | boost::begin(view) + from_index); | |
99 | ||
100 | // [2..4] -> 4 - 2 + 1 = 3 -> {2,3,4} -> OK | |
101 | // [4..2],size=6 -> 6 - 4 + 2 + 1 = 5 -> {4,5,0,1,2} -> OK | |
102 | // [1..1], travel the whole ring round | |
103 | signed_size_type const count = from_index <= to_index | |
104 | ? to_index - from_index + 1 | |
105 | : static_cast<signed_size_type>(boost::size(view)) | |
106 | - from_index + to_index + 1; | |
107 | ||
108 | for (signed_size_type i = 0; i < count; ++i, ++it) | |
109 | { | |
b32b8144 | 110 | detail::overlay::append_no_dups_or_spikes(current_output, *it, strategy, robust_policy); |
7c673cae FG |
111 | } |
112 | } | |
113 | }; | |
114 | ||
115 | template <bool Reverse, bool RemoveSpikes = true> | |
116 | class copy_segments_linestring | |
117 | { | |
118 | private: | |
119 | // remove spikes | |
1e59de90 | 120 | template <typename RangeOut, typename Point, typename Strategy, typename RobustPolicy> |
7c673cae FG |
121 | static inline void append_to_output(RangeOut& current_output, |
122 | Point const& point, | |
1e59de90 | 123 | Strategy const& strategy, |
7c673cae | 124 | RobustPolicy const& robust_policy, |
20effc67 | 125 | std::true_type const&) |
7c673cae FG |
126 | { |
127 | detail::overlay::append_no_dups_or_spikes(current_output, point, | |
b32b8144 | 128 | strategy, |
7c673cae FG |
129 | robust_policy); |
130 | } | |
131 | ||
132 | // keep spikes | |
1e59de90 | 133 | template <typename RangeOut, typename Point, typename Strategy, typename RobustPolicy> |
7c673cae FG |
134 | static inline void append_to_output(RangeOut& current_output, |
135 | Point const& point, | |
1e59de90 | 136 | Strategy const& strategy, |
7c673cae | 137 | RobustPolicy const&, |
20effc67 | 138 | std::false_type const&) |
7c673cae | 139 | { |
1e59de90 | 140 | detail::overlay::append_no_duplicates(current_output, point, strategy); |
7c673cae FG |
141 | } |
142 | ||
143 | public: | |
144 | template | |
145 | < | |
146 | typename LineString, | |
147 | typename SegmentIdentifier, | |
b32b8144 | 148 | typename SideStrategy, |
7c673cae FG |
149 | typename RobustPolicy, |
150 | typename RangeOut | |
151 | > | |
152 | static inline void apply(LineString const& ls, | |
153 | SegmentIdentifier const& seg_id, | |
154 | signed_size_type to_index, | |
b32b8144 | 155 | SideStrategy const& strategy, |
7c673cae FG |
156 | RobustPolicy const& robust_policy, |
157 | RangeOut& current_output) | |
158 | { | |
159 | signed_size_type const from_index = seg_id.segment_index + 1; | |
160 | ||
161 | // Sanity check | |
162 | if ( from_index > to_index | |
163 | || from_index < 0 | |
164 | || to_index >= static_cast<signed_size_type>(boost::size(ls)) ) | |
165 | { | |
166 | return; | |
167 | } | |
168 | ||
169 | signed_size_type const count = to_index - from_index + 1; | |
170 | ||
171 | typename boost::range_iterator<LineString const>::type | |
172 | it = boost::begin(ls) + from_index; | |
173 | ||
174 | for (signed_size_type i = 0; i < count; ++i, ++it) | |
175 | { | |
b32b8144 | 176 | append_to_output(current_output, *it, strategy, robust_policy, |
20effc67 | 177 | std::integral_constant<bool, RemoveSpikes>()); |
7c673cae FG |
178 | } |
179 | } | |
180 | }; | |
181 | ||
182 | template <bool Reverse> | |
183 | struct copy_segments_polygon | |
184 | { | |
185 | template | |
186 | < | |
187 | typename Polygon, | |
188 | typename SegmentIdentifier, | |
b32b8144 | 189 | typename SideStrategy, |
7c673cae FG |
190 | typename RobustPolicy, |
191 | typename RangeOut | |
192 | > | |
193 | static inline void apply(Polygon const& polygon, | |
194 | SegmentIdentifier const& seg_id, | |
195 | signed_size_type to_index, | |
b32b8144 | 196 | SideStrategy const& strategy, |
7c673cae FG |
197 | RobustPolicy const& robust_policy, |
198 | RangeOut& current_output) | |
199 | { | |
200 | // Call ring-version with the right ring | |
201 | copy_segments_ring<Reverse>::apply | |
202 | ( | |
203 | seg_id.ring_index < 0 | |
204 | ? geometry::exterior_ring(polygon) | |
205 | : range::at(geometry::interior_rings(polygon), seg_id.ring_index), | |
206 | seg_id, to_index, | |
b32b8144 | 207 | strategy, |
7c673cae FG |
208 | robust_policy, |
209 | current_output | |
210 | ); | |
211 | } | |
212 | }; | |
213 | ||
214 | ||
215 | template <bool Reverse> | |
216 | struct copy_segments_box | |
217 | { | |
218 | template | |
219 | < | |
220 | typename Box, | |
221 | typename SegmentIdentifier, | |
b32b8144 | 222 | typename SideStrategy, |
7c673cae FG |
223 | typename RobustPolicy, |
224 | typename RangeOut | |
225 | > | |
226 | static inline void apply(Box const& box, | |
227 | SegmentIdentifier const& seg_id, | |
228 | signed_size_type to_index, | |
b32b8144 | 229 | SideStrategy const& strategy, |
7c673cae FG |
230 | RobustPolicy const& robust_policy, |
231 | RangeOut& current_output) | |
232 | { | |
233 | signed_size_type index = seg_id.segment_index + 1; | |
234 | BOOST_GEOMETRY_ASSERT(index < 5); | |
235 | ||
236 | signed_size_type const count = index <= to_index | |
237 | ? to_index - index + 1 | |
238 | : 5 - index + to_index + 1; | |
239 | ||
240 | // Create array of points, the fifth one closes it | |
241 | boost::array<typename point_type<Box>::type, 5> bp; | |
242 | assign_box_corners_oriented<Reverse>(box, bp); | |
243 | bp[4] = bp[0]; | |
244 | ||
245 | // (possibly cyclic) copy to output | |
246 | // (see comments in ring-version) | |
247 | for (signed_size_type i = 0; i < count; i++, index++) | |
248 | { | |
249 | detail::overlay::append_no_dups_or_spikes(current_output, | |
b32b8144 | 250 | bp[index % 5], strategy, robust_policy); |
7c673cae FG |
251 | |
252 | } | |
253 | } | |
254 | }; | |
255 | ||
256 | ||
257 | template<typename Policy> | |
258 | struct copy_segments_multi | |
259 | { | |
260 | template | |
261 | < | |
262 | typename MultiGeometry, | |
263 | typename SegmentIdentifier, | |
b32b8144 | 264 | typename SideStrategy, |
7c673cae FG |
265 | typename RobustPolicy, |
266 | typename RangeOut | |
267 | > | |
268 | static inline void apply(MultiGeometry const& multi_geometry, | |
269 | SegmentIdentifier const& seg_id, | |
270 | signed_size_type to_index, | |
b32b8144 | 271 | SideStrategy const& strategy, |
7c673cae FG |
272 | RobustPolicy const& robust_policy, |
273 | RangeOut& current_output) | |
274 | { | |
275 | ||
276 | BOOST_GEOMETRY_ASSERT | |
277 | ( | |
278 | seg_id.multi_index >= 0 | |
279 | && static_cast<std::size_t>(seg_id.multi_index) < boost::size(multi_geometry) | |
280 | ); | |
281 | ||
282 | // Call the single-version | |
283 | Policy::apply(range::at(multi_geometry, seg_id.multi_index), | |
284 | seg_id, to_index, | |
b32b8144 | 285 | strategy, |
7c673cae FG |
286 | robust_policy, |
287 | current_output); | |
288 | } | |
289 | }; | |
290 | ||
291 | ||
292 | }} // namespace detail::copy_segments | |
293 | #endif // DOXYGEN_NO_DETAIL | |
294 | ||
295 | ||
296 | #ifndef DOXYGEN_NO_DISPATCH | |
297 | namespace dispatch | |
298 | { | |
299 | ||
300 | template | |
301 | < | |
302 | typename Tag, | |
303 | bool Reverse | |
304 | > | |
305 | struct copy_segments : not_implemented<Tag> | |
306 | {}; | |
307 | ||
308 | ||
309 | template <bool Reverse> | |
310 | struct copy_segments<ring_tag, Reverse> | |
311 | : detail::copy_segments::copy_segments_ring<Reverse> | |
312 | {}; | |
313 | ||
314 | ||
315 | template <bool Reverse> | |
316 | struct copy_segments<linestring_tag, Reverse> | |
317 | : detail::copy_segments::copy_segments_linestring<Reverse> | |
318 | {}; | |
319 | ||
320 | template <bool Reverse> | |
321 | struct copy_segments<polygon_tag, Reverse> | |
322 | : detail::copy_segments::copy_segments_polygon<Reverse> | |
323 | {}; | |
324 | ||
325 | ||
326 | template <bool Reverse> | |
327 | struct copy_segments<box_tag, Reverse> | |
328 | : detail::copy_segments::copy_segments_box<Reverse> | |
329 | {}; | |
330 | ||
331 | ||
332 | template<bool Reverse> | |
333 | struct copy_segments<multi_polygon_tag, Reverse> | |
334 | : detail::copy_segments::copy_segments_multi | |
335 | < | |
336 | detail::copy_segments::copy_segments_polygon<Reverse> | |
337 | > | |
338 | {}; | |
339 | ||
340 | ||
341 | } // namespace dispatch | |
342 | #endif // DOXYGEN_NO_DISPATCH | |
343 | ||
344 | ||
345 | /*! | |
346 | \brief Copy segments from a geometry, starting with the specified segment (seg_id) | |
347 | until the specified index (to_index) | |
348 | \ingroup overlay | |
349 | */ | |
350 | template | |
351 | < | |
352 | bool Reverse, | |
353 | typename Geometry, | |
354 | typename SegmentIdentifier, | |
b32b8144 | 355 | typename SideStrategy, |
7c673cae FG |
356 | typename RobustPolicy, |
357 | typename RangeOut | |
358 | > | |
359 | inline void copy_segments(Geometry const& geometry, | |
360 | SegmentIdentifier const& seg_id, | |
361 | signed_size_type to_index, | |
b32b8144 | 362 | SideStrategy const& strategy, |
7c673cae FG |
363 | RobustPolicy const& robust_policy, |
364 | RangeOut& range_out) | |
365 | { | |
366 | concepts::check<Geometry const>(); | |
367 | ||
368 | dispatch::copy_segments | |
369 | < | |
370 | typename tag<Geometry>::type, | |
371 | Reverse | |
b32b8144 | 372 | >::apply(geometry, seg_id, to_index, strategy, robust_policy, range_out); |
7c673cae FG |
373 | } |
374 | ||
375 | ||
376 | }} // namespace boost::geometry | |
377 | ||
378 | ||
379 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENTS_HPP |