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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
   4
   5 // Copyright (c) 2014-2017, Oracle and/or its affiliates.
   6
   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 // Licensed under the Boost Software License version 1.0.
  11 // http://www.boost.org/users/license.html
  12
  13
  14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_LINEAR_LINEAR_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_LINEAR_LINEAR_HPP
  16
  17 #include <cstddef>
  18 #include <algorithm>
  19 #include <iterator>
  20
  21 #include <boost/range.hpp>
  22 #include <boost/throw_exception.hpp>
  23
  24 #include <boost/geometry/core/assert.hpp>
  25 #include <boost/geometry/core/tag.hpp>
  26 #include <boost/geometry/core/tags.hpp>
  27
  28 #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
  29 #include <boost/geometry/algorithms/detail/overlay/follow.hpp>
  30 #include <boost/geometry/algorithms/detail/overlay/inconsistent_turns_exception.hpp>
  31 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
  32 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
  33 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
  34
  35 #include <boost/geometry/algorithms/detail/turns/debug_turn.hpp>
  36
  37 #include <boost/geometry/algorithms/convert.hpp>
  38 #include <boost/geometry/algorithms/not_implemented.hpp>
  39
  40
  41 namespace boost { namespace geometry
  42 {
  43
  44 #ifndef DOXYGEN_NO_DETAIL
  45 namespace detail { namespace overlay
  46 {
  47
  48 namespace following { namespace linear
  49 {
  50
  51
  52
  53
  54 // follower for linear/linear geometries set operations
  55
  56 template <typename Turn, typename Operation>
  57 static inline bool is_entering(Turn const& turn,
  58                                Operation const& operation)
  59 {
  60     if ( turn.method != method_touch && turn.method != method_touch_interior )
  61     {
  62         return false;
  63     }
  64     return operation.operation == operation_intersection;
  65 }
  66
  67
  68
  69 template <typename Turn, typename Operation>
  70 static inline bool is_staying_inside(Turn const& turn,
  71                                      Operation const& operation,
  72                                      bool entered)
  73 {
  74     if ( !entered )
  75     {
  76         return false;
  77     }
  78
  79     if ( turn.method != method_equal && turn.method != method_collinear )
  80     {
  81         return false;
  82     }
  83     return operation.operation == operation_continue;
  84 }
  85
  86
  87
  88 template <typename Turn, typename Operation>
  89 static inline bool is_leaving(Turn const& turn,
  90                               Operation const& operation,
  91                               bool entered)
  92 {
  93     if ( !entered )
  94     {
  95         return false;
  96     }
  97
  98     if ( turn.method != method_touch
  99          && turn.method != method_touch_interior
 100          && turn.method != method_equal
 101          && turn.method != method_collinear )
 102     {
 103         return false;
 104     }
 105
 106     if ( operation.operation == operation_blocked )
 107     {
 108         return true;
 109     }
 110
 111     if ( operation.operation != operation_union )
 112     {
 113         return false;
 114     }
 115
 116     return operation.is_collinear;
 117 }
 118
 119
 120
 121 template <typename Turn, typename Operation>
 122 static inline bool is_isolated_point(Turn const& turn,
 123                                      Operation const& operation,
 124                                      bool entered)
 125 {
 126     if ( entered )
 127     {
 128         return false;
 129     }
 130
 131     if ( turn.method == method_none )
 132     {
 133         BOOST_GEOMETRY_ASSERT( operation.operation == operation_continue );
 134         return true;
 135     }
 136
 137     if ( turn.method == method_crosses )
 138     {
 139         return true;
 140     }
 141
 142     if ( turn.method != method_touch && turn.method != method_touch_interior )
 143     {
 144         return false;
 145     }
 146
 147     if ( operation.operation == operation_blocked )
 148     {
 149         return true;
 150     }
 151
 152     if ( operation.operation != operation_union )
 153     {
 154         return false;
 155     }
 156
 157     return !operation.is_collinear;
 158 }
 159
 160
 161
 162
 163
 164
 165
 166
 167
 168 template
 169 <
 170     typename LinestringOut,
 171     typename Linestring,
 172     typename Linear,
 173     overlay_type OverlayType,
 174     bool FollowIsolatedPoints,
 175     bool FollowContinueTurns
 176 >
 177 class follow_linestring_linear_linestring
 178 {
 179 protected:
 180     // allow spikes (false indicates: do not remove spikes)
 181     typedef following::action_selector<OverlayType, false> action;
 182
 183     template
 184     <
 185         typename TurnIterator,
 186         typename TurnOperationIterator,
 187         typename SegmentIdentifier,
 188         typename OutputIterator,
 189         typename SideStrategy
 190     >
 191     static inline OutputIterator
 192     process_turn(TurnIterator it,
 193                  TurnOperationIterator op_it,
 194                  bool& entered,
 195                  std::size_t& enter_count,
 196                  Linestring const& linestring,
 197                  LinestringOut& current_piece,
 198                  SegmentIdentifier& current_segment_id,
 199                  OutputIterator oit,
 200                  SideStrategy const& strategy)
 201     {
 202         // We don't rescale linear/linear
 203         detail::no_rescale_policy robust_policy;
 204
 205         if ( is_entering(*it, *op_it) )
 206         {
 207             detail::turns::debug_turn(*it, *op_it, "-> Entering");
 208
 209             entered = true;
 210             if ( enter_count == 0 )
 211             {
 212                 action::enter(current_piece, linestring,
 213                               current_segment_id,
 214                               op_it->seg_id.segment_index,
 215                               it->point, *op_it, strategy, robust_policy, oit);
 216             }
 217             ++enter_count;
 218         }
 219         else if ( is_leaving(*it, *op_it, entered) )
 220         {
 221             detail::turns::debug_turn(*it, *op_it, "-> Leaving");
 222
 223             --enter_count;
 224             if ( enter_count == 0 )
 225             {
 226                 entered = false;
 227                 action::leave(current_piece, linestring,
 228                               current_segment_id,
 229                               op_it->seg_id.segment_index,
 230                               it->point, *op_it, strategy, robust_policy, oit);
 231             }
 232         }
 233         else if ( FollowIsolatedPoints
 234                   && is_isolated_point(*it, *op_it, entered) )
 235         {
 236             detail::turns::debug_turn(*it, *op_it, "-> Isolated point");
 237
 238             action::isolated_point(current_piece, linestring,
 239                                    current_segment_id,
 240                                    op_it->seg_id.segment_index,
 241                                    it->point, *op_it, oit);
 242         }
 243         else if ( FollowContinueTurns
 244                   && is_staying_inside(*it, *op_it, entered) )
 245         {
 246             detail::turns::debug_turn(*it, *op_it, "-> Staying inside");
 247
 248             entered = true;
 249         }
 250         return oit;
 251     }
 252
 253     template
 254     <
 255         typename SegmentIdentifier,
 256         typename OutputIterator,
 257         typename SideStrategy
 258     >
 259     static inline OutputIterator
 260     process_end(bool entered,
 261                 Linestring const& linestring,
 262                 SegmentIdentifier const& current_segment_id,
 263                 LinestringOut& current_piece,
 264                 OutputIterator oit,
 265                 SideStrategy const& strategy)
 266     {
 267         if ( action::is_entered(entered) )
 268         {
 269             // We don't rescale linear/linear
 270             detail::no_rescale_policy robust_policy;
 271
 272             detail::copy_segments::copy_segments_linestring
 273                 <
 274                     false, false // do not reverse; do not remove spikes
 275                 >::apply(linestring,
 276                          current_segment_id,
 277                          static_cast<signed_size_type>(boost::size(linestring) - 1),
 278                          strategy,
 279                          robust_policy,
 280                          current_piece);
 281         }
 282
 283         // Output the last one, if applicable
 284         if (::boost::size(current_piece) > 1)
 285         {
 286             *oit++ = current_piece;
 287         }
 288
 289         return oit;
 290     }
 291
 292 public:
 293     template <typename TurnIterator, typename OutputIterator, typename SideStrategy>
 294     static inline OutputIterator
 295     apply(Linestring const& linestring, Linear const&,
 296           TurnIterator first, TurnIterator beyond,
 297           OutputIterator oit,
 298           SideStrategy const& strategy)
 299     {
 300         // Iterate through all intersection points (they are
 301         // ordered along the each line)
 302
 303         LinestringOut current_piece;
 304         geometry::segment_identifier current_segment_id(0, -1, -1, -1);
 305
 306         bool entered = false;
 307         std::size_t enter_count = 0;
 308
 309         for (TurnIterator it = first; it != beyond; ++it)
 310         {
 311             oit = process_turn(it, boost::begin(it->operations),
 312                                entered, enter_count,
 313                                linestring,
 314                                current_piece, current_segment_id,
 315                                oit,
 316                                strategy);
 317         }
 318
 319 #if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
 320         if (enter_count != 0)
 321         {
 322             BOOST_THROW_EXCEPTION(inconsistent_turns_exception());
 323         }
 324 #else
 325         BOOST_GEOMETRY_ASSERT(enter_count == 0);
 326 #endif
 327
 328         return process_end(entered, linestring,
 329                            current_segment_id, current_piece,
 330                            oit,
 331                            strategy);
 332     }
 333 };
 334
 335
 336
 337
 338 template
 339 <
 340     typename LinestringOut,
 341     typename MultiLinestring,
 342     typename Linear,
 343     overlay_type OverlayType,
 344     bool FollowIsolatedPoints,
 345     bool FollowContinueTurns
 346 >
 347 class follow_multilinestring_linear_linestring
 348     : follow_linestring_linear_linestring
 349         <
 350             LinestringOut,
 351             typename boost::range_value<MultiLinestring>::type,
 352             Linear,
 353             OverlayType,
 354             FollowIsolatedPoints,
 355             FollowContinueTurns
 356         >
 357 {
 358 protected:
 359     typedef typename boost::range_value<MultiLinestring>::type Linestring;
 360
 361     typedef follow_linestring_linear_linestring
 362         <
 363             LinestringOut, Linestring, Linear,
 364             OverlayType, FollowIsolatedPoints, FollowContinueTurns
 365         > Base;
 366
 367     typedef following::action_selector<OverlayType> action;
 368
 369     typedef typename boost::range_iterator
 370         <
 371             MultiLinestring const
 372         >::type linestring_iterator;
 373
 374
 375     template <typename OutputIt, overlay_type OT>
 376     struct copy_linestrings_in_range
 377     {
 378         static inline OutputIt
 379         apply(linestring_iterator, linestring_iterator, OutputIt oit)
 380         {
 381             return oit;
 382         }
 383     };
 384
 385     template <typename OutputIt>
 386     struct copy_linestrings_in_range<OutputIt, overlay_difference>
 387     {
 388         static inline OutputIt
 389         apply(linestring_iterator first, linestring_iterator beyond,
 390               OutputIt oit)
 391         {
 392             for (linestring_iterator ls_it = first; ls_it != beyond; ++ls_it)
 393             {
 394                 LinestringOut line_out;
 395                 geometry::convert(*ls_it, line_out);
 396                 *oit++ = line_out;
 397             }
 398             return oit;
 399         }
 400     };
 401
 402     template <typename TurnIterator>
 403     static inline signed_size_type get_multi_index(TurnIterator it)
 404     {
 405         return boost::begin(it->operations)->seg_id.multi_index;
 406     }
 407
 408     class has_other_multi_id
 409     {
 410     private:
 411         signed_size_type m_multi_id;
 412
 413     public:
 414         has_other_multi_id(signed_size_type multi_id)
 415             : m_multi_id(multi_id) {}
 416
 417         template <typename Turn>
 418         bool operator()(Turn const& turn) const
 419         {
 420             return boost::begin(turn.operations)->seg_id.multi_index
 421                 != m_multi_id;
 422         }
 423     };
 424
 425 public:
 426     template <typename TurnIterator, typename OutputIterator, typename SideStrategy>
 427     static inline OutputIterator
 428     apply(MultiLinestring const& multilinestring, Linear const& linear,
 429           TurnIterator first, TurnIterator beyond,
 430           OutputIterator oit,
 431           SideStrategy const& strategy)
 432     {
 433         BOOST_GEOMETRY_ASSERT( first != beyond );
 434
 435         typedef copy_linestrings_in_range
 436             <
 437                 OutputIterator, OverlayType
 438             > copy_linestrings;
 439
 440         linestring_iterator ls_first = boost::begin(multilinestring);
 441         linestring_iterator ls_beyond = boost::end(multilinestring);
 442
 443         // Iterate through all intersection points (they are
 444         // ordered along the each linestring)
 445
 446         signed_size_type current_multi_id = get_multi_index(first);
 447
 448         oit = copy_linestrings::apply(ls_first,
 449                                       ls_first + current_multi_id,
 450                                       oit);
 451
 452         TurnIterator per_ls_next = first;
 453         do {
 454             TurnIterator per_ls_current = per_ls_next;
 455
 456             // find turn with different multi-index
 457             per_ls_next = std::find_if(per_ls_current, beyond,
 458                                        has_other_multi_id(current_multi_id));
 459
 460             oit = Base::apply(*(ls_first + current_multi_id),
 461                               linear, per_ls_current, per_ls_next, oit, strategy);
 462
 463             signed_size_type next_multi_id = -1;
 464             linestring_iterator ls_next = ls_beyond;
 465             if ( per_ls_next != beyond )
 466             {
 467                 next_multi_id = get_multi_index(per_ls_next);
 468                 ls_next = ls_first + next_multi_id;
 469             }
 470             oit = copy_linestrings::apply(ls_first + current_multi_id + 1,
 471                                           ls_next,
 472                                           oit);
 473
 474             current_multi_id = next_multi_id;
 475         }
 476         while ( per_ls_next != beyond );
 477
 478         return oit;
 479     }
 480 };
 481
 482
 483
 484
 485
 486
 487 template
 488 <
 489     typename LinestringOut,
 490     typename Geometry1,
 491     typename Geometry2,
 492     overlay_type OverlayType,
 493     bool FollowIsolatedPoints,
 494     bool FollowContinueTurns,
 495     typename TagOut = typename tag<LinestringOut>::type,
 496     typename TagIn1 = typename tag<Geometry1>::type
 497 >
 498 struct follow
 499     : not_implemented<LinestringOut, Geometry1>
 500 {};
 501
 502
 503
 504 template
 505 <
 506     typename LinestringOut,
 507     typename Linestring,
 508     typename Linear,
 509     overlay_type OverlayType,
 510     bool FollowIsolatedPoints,
 511     bool FollowContinueTurns
 512 >
 513 struct follow
 514     <
 515         LinestringOut, Linestring, Linear,
 516         OverlayType, FollowIsolatedPoints, FollowContinueTurns,
 517         linestring_tag, linestring_tag
 518     > : follow_linestring_linear_linestring
 519         <
 520             LinestringOut, Linestring, Linear,
 521             OverlayType, FollowIsolatedPoints, FollowContinueTurns
 522         >
 523 {};
 524
 525
 526 template
 527 <
 528     typename LinestringOut,
 529     typename MultiLinestring,
 530     typename Linear,
 531     overlay_type OverlayType,
 532     bool FollowIsolatedPoints,
 533     bool FollowContinueTurns
 534 >
 535 struct follow
 536     <
 537         LinestringOut, MultiLinestring, Linear,
 538         OverlayType, FollowIsolatedPoints, FollowContinueTurns,
 539         linestring_tag, multi_linestring_tag
 540     > : follow_multilinestring_linear_linestring
 541         <
 542             LinestringOut, MultiLinestring, Linear,
 543             OverlayType, FollowIsolatedPoints, FollowContinueTurns
 544         >
 545 {};
 546
 547
 548
 549 }} // namespace following::linear
 550
 551 }} // namespace detail::overlay
 552 #endif // DOXYGEN_NO_DETAIL
 553
 554 }} // namespace boost::geometry
 555
 556
 557 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_LINEAR_LINEAR_HPP