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, 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     >
  64     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>
 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>
 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     >
 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     >
 197     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     >
 230     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     >
 272     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 >
 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