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