detail/overlay/copy_segments.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
0004 // Copyright (c) 2023 Adam Wulkiewicz, Lodz, Poland.
0005
0006 // This file was modified by Oracle on 2014-2021.
0007 // Modifications copyright (c) 2014-2021 Oracle and/or its affiliates.
0008 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
0009 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
0010
0011 // Use, modification and distribution is subject to the Boost Software License,
0012 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0013 // http://www.boost.org/LICENSE_1_0.txt)
0014
0015 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENTS_HPP
0016 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENTS_HPP
0017
0018
0019 #include <array>
0020 #include <type_traits>
0021 #include <vector>
0022
0023 #include <boost/range/begin.hpp>
0024 #include <boost/range/end.hpp>
0025 #include <boost/range/size.hpp>
0026
0027 #include <boost/geometry/algorithms/detail/assign_box_corners.hpp>
0028 #include <boost/geometry/algorithms/detail/signed_size_type.hpp>
0029 #include <boost/geometry/algorithms/detail/overlay/append_no_duplicates.hpp>
0030 #include <boost/geometry/algorithms/detail/overlay/append_no_dups_or_spikes.hpp>
0031 #include <boost/geometry/algorithms/not_implemented.hpp>
0032
0033 #include <boost/geometry/core/assert.hpp>
0034 #include <boost/geometry/core/exterior_ring.hpp>
0035 #include <boost/geometry/core/interior_rings.hpp>
0036 #include <boost/geometry/core/ring_type.hpp>
0037 #include <boost/geometry/core/tags.hpp>
0038
0039 #include <boost/geometry/geometries/concepts/check.hpp>
0040
0041 #include <boost/geometry/iterators/ever_circling_iterator.hpp>
0042
0043 #include <boost/geometry/util/range.hpp>
0044
0045 #include <boost/geometry/views/detail/closed_clockwise_view.hpp>
0046
0047
0048 namespace boost { namespace geometry
0049 {
0050
0051
0052 #ifndef DOXYGEN_NO_DETAIL
0053 namespace detail { namespace copy_segments
0054 {
0055
0056
0057 template <bool Reverse>
0058 struct copy_segments_ring
0059 {
0060     template
0061     <
0062         typename Ring,
0063         typename SegmentIdentifier,
0064         typename Strategy,
0065         typename RobustPolicy,
0066         typename RangeOut
0067     >
0068     static inline void apply(Ring const& ring,
0069             SegmentIdentifier const& seg_id,
0070             signed_size_type to_index,
0071             Strategy const& strategy,
0072             RobustPolicy const& robust_policy,
0073             RangeOut& current_output)
0074     {
0075         using view_type = detail::closed_clockwise_view
0076             <
0077                 Ring const,
0078                 closure<Ring>::value,
0079                 Reverse ? counterclockwise : clockwise
0080             >;
0081
0082         using iterator = typename boost::range_iterator<view_type const>::type;
0083         using ec_iterator = geometry::ever_circling_iterator<iterator>;
0084
0085         view_type view(ring);
0086
0087         // The problem: sometimes we want to from "3" to "2"
0088         // -> end = "3" -> end == begin
0089         // This is not convenient with iterators.
0090
0091         // So we use the ever-circling iterator and determine when to step out
0092
0093         signed_size_type const from_index = seg_id.segment_index + 1;
0094
0095         // Sanity check
0096         BOOST_GEOMETRY_ASSERT(from_index < static_cast<signed_size_type>(boost::size(view)));
0097
0098         ec_iterator it(boost::begin(view), boost::end(view),
0099                     boost::begin(view) + from_index);
0100
0101         // [2..4] -> 4 - 2 + 1 = 3 -> {2,3,4} -> OK
0102         // [4..2],size=6 -> 6 - 4 + 2 + 1 = 5 -> {4,5,0,1,2} -> OK
0103         // [1..1], travel the whole ring round
0104         signed_size_type const count = from_index <= to_index
0105             ? to_index - from_index + 1
0106             : static_cast<signed_size_type>(boost::size(view))
0107                 - from_index + to_index + 1;
0108
0109         for (signed_size_type i = 0; i < count; ++i, ++it)
0110         {
0111             detail::overlay::append_no_dups_or_spikes(current_output, *it, strategy, robust_policy);
0112         }
0113     }
0114 };
0115
0116 template <bool Reverse, bool RemoveSpikes = true>
0117 class copy_segments_linestring
0118 {
0119 private:
0120     // remove spikes
0121     template <typename RangeOut, typename Point, typename Strategy, typename RobustPolicy>
0122     static inline void append_to_output(RangeOut& current_output,
0123                                         Point const& point,
0124                                         Strategy const& strategy,
0125                                         RobustPolicy const& robust_policy,
0126                                         std::true_type const&)
0127     {
0128         detail::overlay::append_no_dups_or_spikes(current_output, point,
0129                                                   strategy,
0130                                                   robust_policy);
0131     }
0132
0133     // keep spikes
0134     template <typename RangeOut, typename Point, typename Strategy, typename RobustPolicy>
0135     static inline void append_to_output(RangeOut& current_output,
0136                                         Point const& point,
0137                                         Strategy const& strategy,
0138                                         RobustPolicy const&,
0139                                         std::false_type const&)
0140     {
0141         detail::overlay::append_no_duplicates(current_output, point, strategy);
0142     }
0143
0144 public:
0145     template
0146     <
0147         typename LineString,
0148         typename SegmentIdentifier,
0149         typename SideStrategy,
0150         typename RobustPolicy,
0151         typename RangeOut
0152     >
0153     static inline void apply(LineString const& ls,
0154             SegmentIdentifier const& seg_id,
0155             signed_size_type to_index,
0156             SideStrategy const& strategy,
0157             RobustPolicy const& robust_policy,
0158             RangeOut& current_output)
0159     {
0160         signed_size_type const from_index = seg_id.segment_index + 1;
0161
0162         // Sanity check
0163         if ( from_index > to_index
0164           || from_index < 0
0165           || to_index >= static_cast<signed_size_type>(boost::size(ls)) )
0166         {
0167             return;
0168         }
0169
0170         signed_size_type const count = to_index - from_index + 1;
0171         auto it = boost::begin(ls) + from_index;
0172         for (signed_size_type i = 0; i < count; ++i, ++it)
0173         {
0174             append_to_output(current_output, *it, strategy, robust_policy,
0175                              std::integral_constant<bool, RemoveSpikes>());
0176         }
0177     }
0178 };
0179
0180 template <bool Reverse>
0181 struct copy_segments_polygon
0182 {
0183     template
0184     <
0185         typename Polygon,
0186         typename SegmentIdentifier,
0187         typename SideStrategy,
0188         typename RobustPolicy,
0189         typename RangeOut
0190     >
0191     static inline void apply(Polygon const& polygon,
0192             SegmentIdentifier const& seg_id,
0193             signed_size_type to_index,
0194             SideStrategy const& strategy,
0195             RobustPolicy const& robust_policy,
0196             RangeOut& current_output)
0197     {
0198         // Call ring-version with the right ring
0199         copy_segments_ring<Reverse>::apply
0200             (
0201                 seg_id.ring_index < 0
0202                     ? geometry::exterior_ring(polygon)
0203                     : range::at(geometry::interior_rings(polygon), seg_id.ring_index),
0204                 seg_id, to_index,
0205                 strategy,
0206                 robust_policy,
0207                 current_output
0208             );
0209     }
0210 };
0211
0212
0213 template <bool Reverse>
0214 struct copy_segments_box
0215 {
0216     template
0217     <
0218         typename Box,
0219         typename SegmentIdentifier,
0220         typename SideStrategy,
0221         typename RobustPolicy,
0222         typename RangeOut
0223     >
0224     static inline void apply(Box const& box,
0225             SegmentIdentifier const& seg_id,
0226             signed_size_type to_index,
0227             SideStrategy const& strategy,
0228             RobustPolicy const& robust_policy,
0229             RangeOut& current_output)
0230     {
0231         signed_size_type index = seg_id.segment_index + 1;
0232         BOOST_GEOMETRY_ASSERT(index < 5);
0233
0234         signed_size_type const count = index <= to_index
0235             ? to_index - index + 1
0236             : 5 - index + to_index + 1;
0237
0238         // Create array of points, the fifth one closes it
0239         std::array<typename point_type<Box>::type, 5> bp;
0240         assign_box_corners_oriented<Reverse>(box, bp);
0241         bp[4] = bp[0];
0242
0243         // (possibly cyclic) copy to output
0244         //    (see comments in ring-version)
0245         for (signed_size_type i = 0; i < count; i++, index++)
0246         {
0247             detail::overlay::append_no_dups_or_spikes(current_output,
0248                 bp[index % 5], strategy, robust_policy);
0249
0250         }
0251     }
0252 };
0253
0254
0255 template<typename Policy>
0256 struct copy_segments_multi
0257 {
0258     template
0259     <
0260         typename MultiGeometry,
0261         typename SegmentIdentifier,
0262         typename SideStrategy,
0263         typename RobustPolicy,
0264         typename RangeOut
0265     >
0266     static inline void apply(MultiGeometry const& multi_geometry,
0267             SegmentIdentifier const& seg_id,
0268             signed_size_type to_index,
0269             SideStrategy const& strategy,
0270             RobustPolicy const& robust_policy,
0271             RangeOut& current_output)
0272     {
0273
0274         BOOST_GEOMETRY_ASSERT
0275             (
0276                 seg_id.multi_index >= 0
0277                 && static_cast<std::size_t>(seg_id.multi_index) < boost::size(multi_geometry)
0278             );
0279
0280         // Call the single-version
0281         Policy::apply(range::at(multi_geometry, seg_id.multi_index),
0282                       seg_id, to_index,
0283                       strategy,
0284                       robust_policy,
0285                       current_output);
0286     }
0287 };
0288
0289
0290 }} // namespace detail::copy_segments
0291 #endif // DOXYGEN_NO_DETAIL
0292
0293
0294 #ifndef DOXYGEN_NO_DISPATCH
0295 namespace dispatch
0296 {
0297
0298 template
0299 <
0300     typename Tag,
0301     bool Reverse
0302 >
0303 struct copy_segments : not_implemented<Tag>
0304 {};
0305
0306
0307 template <bool Reverse>
0308 struct copy_segments<ring_tag, Reverse>
0309     : detail::copy_segments::copy_segments_ring<Reverse>
0310 {};
0311
0312
0313 template <bool Reverse>
0314 struct copy_segments<linestring_tag, Reverse>
0315     : detail::copy_segments::copy_segments_linestring<Reverse>
0316 {};
0317
0318 template <bool Reverse>
0319 struct copy_segments<polygon_tag, Reverse>
0320     : detail::copy_segments::copy_segments_polygon<Reverse>
0321 {};
0322
0323
0324 template <bool Reverse>
0325 struct copy_segments<box_tag, Reverse>
0326     : detail::copy_segments::copy_segments_box<Reverse>
0327 {};
0328
0329
0330 template<bool Reverse>
0331 struct copy_segments<multi_polygon_tag, Reverse>
0332     : detail::copy_segments::copy_segments_multi
0333         <
0334             detail::copy_segments::copy_segments_polygon<Reverse>
0335         >
0336 {};
0337
0338
0339 } // namespace dispatch
0340 #endif // DOXYGEN_NO_DISPATCH
0341
0342
0343 /*!
0344     \brief Copy segments from a geometry, starting with the specified segment (seg_id)
0345         until the specified index (to_index)
0346     \ingroup overlay
0347  */
0348 template
0349 <
0350     bool Reverse,
0351     typename Geometry,
0352     typename SegmentIdentifier,
0353     typename SideStrategy,
0354     typename RobustPolicy,
0355     typename RangeOut
0356 >
0357 inline void copy_segments(Geometry const& geometry,
0358             SegmentIdentifier const& seg_id,
0359             signed_size_type to_index,
0360             SideStrategy const& strategy,
0361             RobustPolicy const& robust_policy,
0362             RangeOut& range_out)
0363 {
0364     concepts::check<Geometry const>();
0365
0366     dispatch::copy_segments
0367         <
0368             typename tag<Geometry>::type,
0369             Reverse
0370         >::apply(geometry, seg_id, to_index, strategy, robust_policy, range_out);
0371 }
0372
0373
0374 }} // namespace boost::geometry
0375
0376
0377 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_COPY_SEGMENTS_HPP