1 // Boost.Geometry (aka GGL, Generic Geometry Library)
3 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
5 // This file was modified by Oracle on 2014, 2017, 2018.
6 // Modifications copyright (c) 2014-2018 Oracle and/or its affiliates.
8 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
9 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
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)
15 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENTS_HPP
16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENTS_HPP
21 #include <boost/array.hpp>
22 #include <boost/mpl/assert.hpp>
23 #include <boost/range.hpp>
24 #include <boost/type_traits/integral_constant.hpp>
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>
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>
38 #include <boost/geometry/geometries/concepts/check.hpp>
40 #include <boost/geometry/iterators/ever_circling_iterator.hpp>
42 #include <boost/geometry/util/range.hpp>
44 #include <boost/geometry/views/closeable_view.hpp>
45 #include <boost/geometry/views/reversible_view.hpp>
48 namespace boost { namespace geometry
52 #ifndef DOXYGEN_NO_DETAIL
53 namespace detail { namespace copy_segments
57 template <bool Reverse>
58 struct copy_segments_ring
63 typename SegmentIdentifier,
64 typename SideStrategy,
65 typename RobustPolicy,
68 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)
75 typedef typename closeable_view
81 typedef typename reversible_view
84 Reverse ? iterate_reverse : iterate_forward
87 typedef typename boost::range_iterator<rview_type const>::type iterator;
88 typedef geometry::ever_circling_iterator<iterator> ec_iterator;
91 cview_type cview(ring);
92 rview_type view(cview);
94 // The problem: sometimes we want to from "3" to "2"
95 // -> end = "3" -> end == begin
96 // This is not convenient with iterators.
98 // So we use the ever-circling iterator and determine when to step out
100 signed_size_type const from_index = seg_id.segment_index + 1;
103 BOOST_GEOMETRY_ASSERT(from_index < static_cast<signed_size_type>(boost::size(view)));
105 ec_iterator it(boost::begin(view), boost::end(view),
106 boost::begin(view) + from_index);
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;
116 for (signed_size_type i = 0; i < count; ++i, ++it)
118 detail::overlay::append_no_dups_or_spikes(current_output, *it, strategy, robust_policy);
123 template <bool Reverse, bool RemoveSpikes = true>
124 class copy_segments_linestring
128 template <typename RangeOut, typename Point, typename SideStrategy, typename RobustPolicy>
129 static inline void append_to_output(RangeOut& current_output,
131 SideStrategy const& strategy,
132 RobustPolicy const& robust_policy,
133 boost::true_type const&)
135 detail::overlay::append_no_dups_or_spikes(current_output, point,
141 template <typename RangeOut, typename Point, typename SideStrategy, typename RobustPolicy>
142 static inline void append_to_output(RangeOut& current_output,
144 SideStrategy const& strategy,
146 boost::false_type const&)
148 detail::overlay::append_no_duplicates(current_output, point, strategy.get_equals_point_point_strategy());
155 typename SegmentIdentifier,
156 typename SideStrategy,
157 typename RobustPolicy,
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)
167 signed_size_type const from_index = seg_id.segment_index + 1;
170 if ( from_index > to_index
172 || to_index >= static_cast<signed_size_type>(boost::size(ls)) )
177 signed_size_type const count = to_index - from_index + 1;
179 typename boost::range_iterator<LineString const>::type
180 it = boost::begin(ls) + from_index;
182 for (signed_size_type i = 0; i < count; ++i, ++it)
184 append_to_output(current_output, *it, strategy, robust_policy,
185 boost::integral_constant<bool, RemoveSpikes>());
190 template <bool Reverse>
191 struct copy_segments_polygon
196 typename SegmentIdentifier,
197 typename SideStrategy,
198 typename RobustPolicy,
201 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)
208 // Call ring-version with the right ring
209 copy_segments_ring<Reverse>::apply
211 seg_id.ring_index < 0
212 ? geometry::exterior_ring(polygon)
213 : range::at(geometry::interior_rings(polygon), seg_id.ring_index),
223 template <bool Reverse>
224 struct copy_segments_box
229 typename SegmentIdentifier,
230 typename SideStrategy,
231 typename RobustPolicy,
234 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)
241 signed_size_type index = seg_id.segment_index + 1;
242 BOOST_GEOMETRY_ASSERT(index < 5);
244 signed_size_type const count = index <= to_index
245 ? to_index - index + 1
246 : 5 - index + to_index + 1;
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);
253 // (possibly cyclic) copy to output
254 // (see comments in ring-version)
255 for (signed_size_type i = 0; i < count; i++, index++)
257 detail::overlay::append_no_dups_or_spikes(current_output,
258 bp[index % 5], strategy, robust_policy);
265 template<typename Policy>
266 struct copy_segments_multi
270 typename MultiGeometry,
271 typename SegmentIdentifier,
272 typename SideStrategy,
273 typename RobustPolicy,
276 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)
284 BOOST_GEOMETRY_ASSERT
286 seg_id.multi_index >= 0
287 && static_cast<std::size_t>(seg_id.multi_index) < boost::size(multi_geometry)
290 // Call the single-version
291 Policy::apply(range::at(multi_geometry, seg_id.multi_index),
300 }} // namespace detail::copy_segments
301 #endif // DOXYGEN_NO_DETAIL
304 #ifndef DOXYGEN_NO_DISPATCH
313 struct copy_segments : not_implemented<Tag>
317 template <bool Reverse>
318 struct copy_segments<ring_tag, Reverse>
319 : detail::copy_segments::copy_segments_ring<Reverse>
323 template <bool Reverse>
324 struct copy_segments<linestring_tag, Reverse>
325 : detail::copy_segments::copy_segments_linestring<Reverse>
328 template <bool Reverse>
329 struct copy_segments<polygon_tag, Reverse>
330 : detail::copy_segments::copy_segments_polygon<Reverse>
334 template <bool Reverse>
335 struct copy_segments<box_tag, Reverse>
336 : detail::copy_segments::copy_segments_box<Reverse>
340 template<bool Reverse>
341 struct copy_segments<multi_polygon_tag, Reverse>
342 : detail::copy_segments::copy_segments_multi
344 detail::copy_segments::copy_segments_polygon<Reverse>
349 } // namespace dispatch
350 #endif // DOXYGEN_NO_DISPATCH
354 \brief Copy segments from a geometry, starting with the specified segment (seg_id)
355 until the specified index (to_index)
362 typename SegmentIdentifier,
363 typename SideStrategy,
364 typename RobustPolicy,
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,
374 concepts::check<Geometry const>();
376 dispatch::copy_segments
378 typename tag<Geometry>::type,
380 >::apply(geometry, seg_id, to_index, strategy, robust_policy, range_out);
384 }} // namespace boost::geometry
387 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENTS_HPP