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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2014 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
   5
   6 // This file was modified by Oracle on 2014, 2017, 2018, 2019, 2020.
   7 // Modifications copyright (c) 2014-2020 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
  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_FOLLOW_HPP
  16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_HPP
  17
  18 #include <cstddef>
  19
  20 #include <boost/range.hpp>
  21 #include <boost/mpl/assert.hpp>
  22
  23 #include <boost/geometry/algorithms/detail/point_on_border.hpp>
  24 #include <boost/geometry/algorithms/detail/overlay/append_no_duplicates.hpp>
  25 #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
  26 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
  27
  28 #include <boost/geometry/algorithms/covered_by.hpp>
  29 #include <boost/geometry/algorithms/clear.hpp>
  30 #include <boost/geometry/algorithms/detail/relate/turns.hpp>
  31 #include <boost/geometry/algorithms/detail/tupled_output.hpp>
  32
  33 namespace boost { namespace geometry
  34 {
  35
  36
  37 #ifndef DOXYGEN_NO_DETAIL
  38 namespace detail { namespace overlay
  39 {
  40
  41 namespace following
  42 {
  43
  44 template <typename Turn, typename Operation>
  45 inline bool is_entering(Turn const& /* TODO remove this parameter */, Operation const& op)
  46 {
  47     // (Blocked means: blocked for polygon/polygon intersection, because
  48     // they are reversed. But for polygon/line it is similar to continue)
  49     return op.operation == operation_intersection
  50         || op.operation == operation_continue
  51         || op.operation == operation_blocked
  52         ;
  53 }
  54
  55 template
  56 <
  57     typename Turn,
  58     typename Operation,
  59     typename LineString,
  60     typename Polygon,
  61     typename PtInPolyStrategy
  62 >
  63 inline bool last_covered_by(Turn const& /*turn*/, Operation const& op,
  64                 LineString const& linestring, Polygon const& polygon,
  65                 PtInPolyStrategy const& strategy)
  66 {
  67     return geometry::covered_by(range::at(linestring, op.seg_id.segment_index), polygon, strategy);
  68 }
  69
  70
  71 template
  72 <
  73     typename Turn,
  74     typename Operation,
  75     typename LineString,
  76     typename Polygon,
  77     typename PtInPolyStrategy
  78 >
  79 inline bool is_leaving(Turn const& turn, Operation const& op,
  80                 bool entered, bool first,
  81                 LineString const& linestring, Polygon const& polygon,
  82                 PtInPolyStrategy const& strategy)
  83 {
  84     if (op.operation == operation_union)
  85     {
  86         return entered
  87             || turn.method == method_crosses
  88             || (first
  89                 && op.position != position_front
  90                 && last_covered_by(turn, op, linestring, polygon, strategy))
  91             ;
  92     }
  93     return false;
  94 }
  95
  96
  97 template
  98 <
  99     typename Turn,
 100     typename Operation,
 101     typename LineString,
 102     typename Polygon,
 103     typename PtInPolyStrategy
 104 >
 105 inline bool is_staying_inside(Turn const& turn, Operation const& op,
 106                 bool entered, bool first,
 107                 LineString const& linestring, Polygon const& polygon,
 108                 PtInPolyStrategy const& strategy)
 109 {
 110     if (turn.method == method_crosses)
 111     {
 112         // The normal case, this is completely covered with entering/leaving
 113         // so stay out of this time consuming "covered_by"
 114         return false;
 115     }
 116
 117     if (is_entering(turn, op))
 118     {
 119         return entered || (first && last_covered_by(turn, op, linestring, polygon, strategy));
 120     }
 121
 122     return false;
 123 }
 124
 125 template
 126 <
 127     typename Turn,
 128     typename Operation,
 129     typename Linestring,
 130     typename Polygon,
 131     typename PtInPolyStrategy
 132 >
 133 inline bool was_entered(Turn const& turn, Operation const& op, bool first,
 134                 Linestring const& linestring, Polygon const& polygon,
 135                 PtInPolyStrategy const& strategy)
 136 {
 137     if (first && (turn.method == method_collinear || turn.method == method_equal))
 138     {
 139         return last_covered_by(turn, op, linestring, polygon, strategy);
 140     }
 141     return false;
 142 }
 143
 144 template
 145 <
 146     typename Turn,
 147     typename Operation
 148 >
 149 inline bool is_touching(Turn const& turn, Operation const& op,
 150                         bool entered)
 151 {
 152     return (op.operation == operation_union || op.operation == operation_blocked)
 153         && (turn.method == method_touch || turn.method == method_touch_interior)
 154         && !entered
 155         && !op.is_collinear;
 156 }
 157
 158
 159 template
 160 <
 161     typename GeometryOut,
 162     typename Tag = typename geometry::tag<GeometryOut>::type
 163 >
 164 struct add_isolated_point
 165 {};
 166
 167 template <typename LineStringOut>
 168 struct add_isolated_point<LineStringOut, linestring_tag>
 169 {
 170     template <typename Point, typename OutputIterator>
 171     static inline void apply(Point const& point, OutputIterator& out)
 172     {
 173         LineStringOut isolated_point_ls;
 174         geometry::append(isolated_point_ls, point);
 175
 176 #ifndef BOOST_GEOMETRY_ALLOW_ONE_POINT_LINESTRINGS
 177         geometry::append(isolated_point_ls, point);
 178 #endif // BOOST_GEOMETRY_ALLOW_ONE_POINT_LINESTRINGS
 179
 180         *out++ = isolated_point_ls;
 181     }
 182 };
 183
 184 template <typename PointOut>
 185 struct add_isolated_point<PointOut, point_tag>
 186 {
 187     template <typename Point, typename OutputIterator>
 188     static inline void apply(Point const& point, OutputIterator& out)
 189     {
 190         PointOut isolated_point;
 191
 192         geometry::detail::conversion::convert_point_to_point(point, isolated_point);
 193
 194         *out++ = isolated_point;
 195     }
 196 };
 197
 198
 199 // Template specialization structure to call the right actions for the right type
 200 template <overlay_type OverlayType, bool RemoveSpikes = true>
 201 struct action_selector
 202 {
 203     // If you get here the overlay type is not intersection or difference
 204     // BOOST_MPL_ASSERT(false);
 205 };
 206
 207 // Specialization for intersection, containing the implementation
 208 template <bool RemoveSpikes>
 209 struct action_selector<overlay_intersection, RemoveSpikes>
 210 {
 211     template
 212     <
 213         typename OutputIterator,
 214         typename LineStringOut,
 215         typename LineString,
 216         typename Point,
 217         typename Operation,
 218         typename Strategy,
 219         typename RobustPolicy
 220     >
 221     static inline void enter(LineStringOut& current_piece,
 222                 LineString const& ,
 223                 segment_identifier& segment_id,
 224                 signed_size_type , Point const& point,
 225                 Operation const& operation,
 226                 Strategy const& strategy,
 227                 RobustPolicy const& ,
 228                 OutputIterator& )
 229     {
 230         // On enter, append the intersection point and remember starting point
 231         // TODO: we don't check on spikes for linestrings (?). Consider this.
 232         detail::overlay::append_no_duplicates(current_piece, point, strategy.get_equals_point_point_strategy());
 233         segment_id = operation.seg_id;
 234     }
 235
 236     template
 237     <
 238         typename OutputIterator,
 239         typename LineStringOut,
 240         typename LineString,
 241         typename Point,
 242         typename Operation,
 243         typename Strategy,
 244         typename RobustPolicy
 245     >
 246     static inline void leave(LineStringOut& current_piece,
 247                 LineString const& linestring,
 248                 segment_identifier& segment_id,
 249                 signed_size_type index, Point const& point,
 250                 Operation const& ,
 251                 Strategy const& strategy,
 252                 RobustPolicy const& robust_policy,
 253                 OutputIterator& out)
 254     {
 255         // On leave, copy all segments from starting point, append the intersection point
 256         // and add the output piece
 257         detail::copy_segments::copy_segments_linestring
 258             <
 259                 false, RemoveSpikes
 260             >::apply(linestring, segment_id, index, strategy, robust_policy, current_piece);
 261         detail::overlay::append_no_duplicates(current_piece, point, strategy.get_equals_point_point_strategy());
 262         if (::boost::size(current_piece) > 1)
 263         {
 264             *out++ = current_piece;
 265         }
 266
 267         geometry::clear(current_piece);
 268     }
 269
 270     template
 271     <
 272         typename LineStringOrPointOut,
 273         typename Point,
 274         typename OutputIterator
 275     >
 276     static inline void isolated_point(Point const& point,
 277                                       OutputIterator& out)
 278     {
 279         add_isolated_point<LineStringOrPointOut>::apply(point, out);
 280     }
 281
 282     static inline bool is_entered(bool entered)
 283     {
 284         return entered;
 285     }
 286
 287     static inline bool included(int inside_value)
 288     {
 289         return inside_value >= 0; // covered_by
 290     }
 291
 292 };
 293
 294 // Specialization for difference, which reverses these actions
 295 template <bool RemoveSpikes>
 296 struct action_selector<overlay_difference, RemoveSpikes>
 297 {
 298     typedef action_selector<overlay_intersection, RemoveSpikes> normal_action;
 299
 300     template
 301     <
 302         typename OutputIterator,
 303         typename LineStringOut,
 304         typename LineString,
 305         typename Point,
 306         typename Operation,
 307         typename Strategy,
 308         typename RobustPolicy
 309     >
 310     static inline void enter(LineStringOut& current_piece,
 311                 LineString const& linestring,
 312                 segment_identifier& segment_id,
 313                 signed_size_type index, Point const& point,
 314                 Operation const& operation,
 315                 Strategy const& strategy,
 316                 RobustPolicy const& robust_policy,
 317                 OutputIterator& out)
 318     {
 319         normal_action::leave(current_piece, linestring, segment_id, index,
 320                     point, operation, strategy, robust_policy, out);
 321     }
 322
 323     template
 324     <
 325         typename OutputIterator,
 326         typename LineStringOut,
 327         typename LineString,
 328         typename Point,
 329         typename Operation,
 330         typename Strategy,
 331         typename RobustPolicy
 332     >
 333     static inline void leave(LineStringOut& current_piece,
 334                 LineString const& linestring,
 335                 segment_identifier& segment_id,
 336                 signed_size_type index, Point const& point,
 337                 Operation const& operation,
 338                 Strategy const& strategy,
 339                 RobustPolicy const& robust_policy,
 340                 OutputIterator& out)
 341     {
 342         normal_action::enter(current_piece, linestring, segment_id, index,
 343                     point, operation, strategy, robust_policy, out);
 344     }
 345
 346     template
 347     <
 348         typename LineStringOrPointOut,
 349         typename Point,
 350         typename OutputIterator
 351     >
 352     static inline void isolated_point(Point const&,
 353                                       OutputIterator const&)
 354     {
 355     }
 356
 357     static inline bool is_entered(bool entered)
 358     {
 359         return ! normal_action::is_entered(entered);
 360     }
 361
 362     static inline bool included(int inside_value)
 363     {
 364         return ! normal_action::included(inside_value);
 365     }
 366
 367 };
 368
 369 } // namespace following
 370
 371 /*!
 372 \brief Follows a linestring from intersection point to intersection point, outputting which
 373     is inside, or outside, a ring or polygon
 374 \ingroup overlay
 375  */
 376 template
 377 <
 378     typename GeometryOut,
 379     typename LineString,
 380     typename Polygon,
 381     overlay_type OverlayType,
 382     bool RemoveSpikes,
 383     bool FollowIsolatedPoints
 384 >
 385 class follow
 386 {
 387     typedef geometry::detail::output_geometry_access
 388         <
 389             GeometryOut, linestring_tag, linestring_tag
 390         > linear;
 391     typedef geometry::detail::output_geometry_access
 392         <
 393             GeometryOut, point_tag, linestring_tag
 394         > pointlike;
 395
 396 public :
 397
 398     static inline bool included(int inside_value)
 399     {
 400         return following::action_selector
 401             <
 402                 OverlayType, RemoveSpikes
 403             >::included(inside_value);
 404     }
 405
 406     template
 407     <
 408         typename Turns,
 409         typename OutputIterator,
 410         typename RobustPolicy,
 411         typename Strategy
 412     >
 413     static inline OutputIterator apply(LineString const& linestring, Polygon const& polygon,
 414                 detail::overlay::operation_type ,  // TODO: this parameter might be redundant
 415                 Turns& turns,
 416                 RobustPolicy const& robust_policy,
 417                 OutputIterator out,
 418                 Strategy const& strategy)
 419     {
 420         typedef typename boost::range_iterator<Turns>::type turn_iterator;
 421         typedef typename boost::range_value<Turns>::type turn_type;
 422         typedef typename boost::range_iterator
 423             <
 424                 typename turn_type::container_type
 425             >::type turn_operation_iterator_type;
 426
 427         typedef following::action_selector<OverlayType, RemoveSpikes> action;
 428
 429         typedef typename Strategy::cs_tag cs_tag;
 430
 431         typename Strategy::template point_in_geometry_strategy
 432             <
 433                 LineString, Polygon
 434             >::type const pt_in_poly_strategy
 435             = strategy.template get_point_in_geometry_strategy<LineString, Polygon>();
 436
 437         // Sort intersection points on segments-along-linestring, and distance
 438         // (like in enrich is done for poly/poly)
 439         // sort turns by Linear seg_id, then by fraction, then
 440         // for same ring id: x, u, i, c
 441         // for different ring id: c, i, u, x
 442         typedef relate::turns::less
 443             <
 444                 0, relate::turns::less_op_linear_areal_single<0>, cs_tag
 445             > turn_less;
 446         std::sort(boost::begin(turns), boost::end(turns), turn_less());
 447
 448         typename linear::type current_piece;
 449         geometry::segment_identifier current_segment_id(0, -1, -1, -1);
 450
 451         // Iterate through all intersection points (they are ordered along the line)
 452         bool entered = false;
 453         bool first = true;
 454         for (turn_iterator it = boost::begin(turns); it != boost::end(turns); ++it)
 455         {
 456             turn_operation_iterator_type iit = boost::begin(it->operations);
 457
 458             if (following::was_entered(*it, *iit, first, linestring, polygon, pt_in_poly_strategy))
 459             {
 460                 debug_traverse(*it, *iit, "-> Was entered");
 461                 entered = true;
 462             }
 463
 464             if (following::is_staying_inside(*it, *iit, entered, first, linestring, polygon, pt_in_poly_strategy))
 465             {
 466                 debug_traverse(*it, *iit, "-> Staying inside");
 467
 468                 entered = true;
 469             }
 470             else if (following::is_entering(*it, *iit))
 471             {
 472                 debug_traverse(*it, *iit, "-> Entering");
 473
 474                 entered = true;
 475                 action::enter(current_piece, linestring, current_segment_id,
 476                     iit->seg_id.segment_index, it->point, *iit,
 477                     strategy, robust_policy,
 478                     linear::get(out));
 479             }
 480             else if (following::is_leaving(*it, *iit, entered, first, linestring, polygon, pt_in_poly_strategy))
 481             {
 482                 debug_traverse(*it, *iit, "-> Leaving");
 483
 484                 entered = false;
 485                 action::leave(current_piece, linestring, current_segment_id,
 486                     iit->seg_id.segment_index, it->point, *iit,
 487                     strategy, robust_policy,
 488                     linear::get(out));
 489             }
 490             else if (FollowIsolatedPoints
 491                   && following::is_touching(*it, *iit, entered))
 492             {
 493                 debug_traverse(*it, *iit, "-> Isolated point");
 494
 495                 action::template isolated_point
 496                     <
 497                         typename pointlike::type
 498                     >(it->point, pointlike::get(out));
 499             }
 500
 501             first = false;
 502         }
 503
 504         if (action::is_entered(entered))
 505         {
 506             detail::copy_segments::copy_segments_linestring
 507                 <
 508                     false, RemoveSpikes
 509                 >::apply(linestring,
 510                          current_segment_id,
 511                          static_cast<signed_size_type>(boost::size(linestring) - 1),
 512                          strategy, robust_policy,
 513                          current_piece);
 514         }
 515
 516         // Output the last one, if applicable
 517         std::size_t current_piece_size = ::boost::size(current_piece);
 518         if (current_piece_size > 1)
 519         {
 520             *linear::get(out)++ = current_piece;
 521         }
 522         else if (FollowIsolatedPoints
 523               && current_piece_size == 1)
 524         {
 525             action::template isolated_point
 526                 <
 527                     typename pointlike::type
 528                 >(range::front(current_piece), pointlike::get(out));
 529         }
 530
 531         return out;
 532     }
 533
 534 };
 535
 536
 537 }} // namespace detail::overlay
 538 #endif // DOXYGEN_NO_DETAIL
 539
 540
 541 }} // namespace boost::geometry
 542
 543
 544 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_HPP