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

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