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