ceph/src/boost/boost/geometry/algorithms/detail/overlay/copy_segments.hpp

   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     >
  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)
  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>
 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>
 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     >
 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     >
 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)
 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     >
 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)
 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     >
 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)
 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 >
 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