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