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.
   7 // Modifications copyright (c) 2014-2019 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
  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 static 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 static 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 static 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 && last_covered_by(turn, op, linestring, polygon, strategy))
  89             ;
  90     }
  91     return false;
  92 }
  93
  94
  95 template
  96 <
  97     typename Turn,
  98     typename Operation,
  99     typename LineString,
 100     typename Polygon,
 101     typename PtInPolyStrategy
 102 >
 103 static inline bool is_staying_inside(Turn const& turn, Operation const& op,
 104                 bool entered, bool first,
 105                 LineString const& linestring, Polygon const& polygon,
 106                 PtInPolyStrategy const& strategy)
 107 {
 108     if (turn.method == method_crosses)
 109     {
 110         // The normal case, this is completely covered with entering/leaving
 111         // so stay out of this time consuming "covered_by"
 112         return false;
 113     }
 114
 115     if (is_entering(turn, op))
 116     {
 117         return entered || (first && last_covered_by(turn, op, linestring, polygon, strategy));
 118     }
 119
 120     return false;
 121 }
 122
 123 template
 124 <
 125     typename Turn,
 126     typename Operation,
 127     typename Linestring,
 128     typename Polygon,
 129     typename PtInPolyStrategy
 130 >
 131 static inline bool was_entered(Turn const& turn, Operation const& op, bool first,
 132                 Linestring const& linestring, Polygon const& polygon,
 133                 PtInPolyStrategy const& strategy)
 134 {
 135     if (first && (turn.method == method_collinear || turn.method == method_equal))
 136     {
 137         return last_covered_by(turn, op, linestring, polygon, strategy);
 138     }
 139     return false;
 140 }
 141
 142
 143 // Template specialization structure to call the right actions for the right type
 144 template <overlay_type OverlayType, bool RemoveSpikes = true>
 145 struct action_selector
 146 {
 147     // If you get here the overlay type is not intersection or difference
 148     // BOOST_MPL_ASSERT(false);
 149 };
 150
 151 // Specialization for intersection, containing the implementation
 152 template <bool RemoveSpikes>
 153 struct action_selector<overlay_intersection, RemoveSpikes>
 154 {
 155     template
 156     <
 157         typename OutputIterator,
 158         typename LineStringOut,
 159         typename LineString,
 160         typename Point,
 161         typename Operation,
 162         typename Strategy,
 163         typename RobustPolicy
 164     >
 165     static inline void enter(LineStringOut& current_piece,
 166                 LineString const& ,
 167                 segment_identifier& segment_id,
 168                 signed_size_type , Point const& point,
 169                 Operation const& operation,
 170                 Strategy const& strategy,
 171                 RobustPolicy const& ,
 172                 OutputIterator& )
 173     {
 174         // On enter, append the intersection point and remember starting point
 175         // TODO: we don't check on spikes for linestrings (?). Consider this.
 176         detail::overlay::append_no_duplicates(current_piece, point, strategy.get_equals_point_point_strategy());
 177         segment_id = operation.seg_id;
 178     }
 179
 180     template
 181     <
 182         typename OutputIterator,
 183         typename LineStringOut,
 184         typename LineString,
 185         typename Point,
 186         typename Operation,
 187         typename Strategy,
 188         typename RobustPolicy
 189     >
 190     static inline void leave(LineStringOut& current_piece,
 191                 LineString const& linestring,
 192                 segment_identifier& segment_id,
 193                 signed_size_type index, Point const& point,
 194                 Operation const& ,
 195                 Strategy const& strategy,
 196                 RobustPolicy const& robust_policy,
 197                 OutputIterator& out)
 198     {
 199         // On leave, copy all segments from starting point, append the intersection point
 200         // and add the output piece
 201         detail::copy_segments::copy_segments_linestring
 202             <
 203                 false, RemoveSpikes
 204             >::apply(linestring, segment_id, index, strategy, robust_policy, current_piece);
 205         detail::overlay::append_no_duplicates(current_piece, point, strategy.get_equals_point_point_strategy());
 206         if (::boost::size(current_piece) > 1)
 207         {
 208             *out++ = current_piece;
 209         }
 210
 211         geometry::clear(current_piece);
 212     }
 213
 214     template
 215     <
 216         typename OutputIterator,
 217         typename LineStringOut,
 218         typename LineString,
 219         typename Point,
 220         typename Operation
 221     >
 222     static inline void isolated_point(LineStringOut&,
 223                 LineString const&,
 224                 segment_identifier&,
 225                 signed_size_type, Point const& point,
 226                 Operation const& , OutputIterator& out)
 227     {
 228         LineStringOut isolated_point_ls;
 229         geometry::append(isolated_point_ls, point);
 230
 231 #ifndef BOOST_GEOMETRY_ALLOW_ONE_POINT_LINESTRINGS
 232         geometry::append(isolated_point_ls, point);
 233 #endif // BOOST_GEOMETRY_ALLOW_ONE_POINT_LINESTRINGS
 234
 235         *out++ = isolated_point_ls;
 236     }
 237
 238     static inline bool is_entered(bool entered)
 239     {
 240         return entered;
 241     }
 242
 243     static inline bool included(int inside_value)
 244     {
 245         return inside_value >= 0; // covered_by
 246     }
 247
 248 };
 249
 250 // Specialization for difference, which reverses these actions
 251 template <bool RemoveSpikes>
 252 struct action_selector<overlay_difference, RemoveSpikes>
 253 {
 254     typedef action_selector<overlay_intersection, RemoveSpikes> normal_action;
 255
 256     template
 257     <
 258         typename OutputIterator,
 259         typename LineStringOut,
 260         typename LineString,
 261         typename Point,
 262         typename Operation,
 263         typename Strategy,
 264         typename RobustPolicy
 265     >
 266     static inline void enter(LineStringOut& current_piece,
 267                 LineString const& linestring,
 268                 segment_identifier& segment_id,
 269                 signed_size_type index, Point const& point,
 270                 Operation const& operation,
 271                 Strategy const& strategy,
 272                 RobustPolicy const& robust_policy,
 273                 OutputIterator& out)
 274     {
 275         normal_action::leave(current_piece, linestring, segment_id, index,
 276                     point, operation, strategy, robust_policy, out);
 277     }
 278
 279     template
 280     <
 281         typename OutputIterator,
 282         typename LineStringOut,
 283         typename LineString,
 284         typename Point,
 285         typename Operation,
 286         typename Strategy,
 287         typename RobustPolicy
 288     >
 289     static inline void leave(LineStringOut& current_piece,
 290                 LineString const& linestring,
 291                 segment_identifier& segment_id,
 292                 signed_size_type index, Point const& point,
 293                 Operation const& operation,
 294                 Strategy const& strategy,
 295                 RobustPolicy const& robust_policy,
 296                 OutputIterator& out)
 297     {
 298         normal_action::enter(current_piece, linestring, segment_id, index,
 299                     point, operation, strategy, robust_policy, out);
 300     }
 301
 302     template
 303     <
 304         typename OutputIterator,
 305         typename LineStringOut,
 306         typename LineString,
 307         typename Point,
 308         typename Operation
 309     >
 310     static inline void isolated_point(LineStringOut&,
 311                 LineString const&,
 312                 segment_identifier&,
 313                 signed_size_type, Point const&,
 314                 Operation const&, OutputIterator&)
 315     {
 316     }
 317
 318     static inline bool is_entered(bool entered)
 319     {
 320         return ! normal_action::is_entered(entered);
 321     }
 322
 323     static inline bool included(int inside_value)
 324     {
 325         return ! normal_action::included(inside_value);
 326     }
 327
 328 };
 329
 330 }
 331
 332 /*!
 333 \brief Follows a linestring from intersection point to intersection point, outputting which
 334     is inside, or outside, a ring or polygon
 335 \ingroup overlay
 336  */
 337 template
 338 <
 339     typename LineStringOut,
 340     typename LineString,
 341     typename Polygon,
 342     overlay_type OverlayType,
 343     bool RemoveSpikes = true
 344 >
 345 class follow
 346 {
 347
 348 #ifdef BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
 349     template <typename Turn>
 350     struct sort_on_segment
 351     {
 352         // In case of turn point at the same location, we want to have continue/blocked LAST
 353         // because that should be followed (intersection) or skipped (difference).
 354         inline int operation_order(Turn const& turn) const
 355         {
 356             operation_type const& operation = turn.operations[0].operation;
 357             switch(operation)
 358             {
 359                 case operation_opposite : return 0;
 360                 case operation_none : return 0;
 361                 case operation_union : return 1;
 362                 case operation_intersection : return 2;
 363                 case operation_blocked : return 3;
 364                 case operation_continue : return 4;
 365             }
 366             return -1;
 367         };
 368
 369         inline bool use_operation(Turn const& left, Turn const& right) const
 370         {
 371             // If they are the same, OK.
 372             return operation_order(left) < operation_order(right);
 373         }
 374
 375         inline bool use_distance(Turn const& left, Turn const& right) const
 376         {
 377             return left.operations[0].fraction == right.operations[0].fraction
 378                 ? use_operation(left, right)
 379                 : left.operations[0].fraction < right.operations[0].fraction
 380                 ;
 381         }
 382
 383         inline bool operator()(Turn const& left, Turn const& right) const
 384         {
 385             segment_identifier const& sl = left.operations[0].seg_id;
 386             segment_identifier const& sr = right.operations[0].seg_id;
 387
 388             return sl == sr
 389                 ? use_distance(left, right)
 390                 : sl < sr
 391                 ;
 392
 393         }
 394     };
 395 #endif // BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
 396
 397
 398 public :
 399
 400     static inline bool included(int inside_value)
 401     {
 402         return following::action_selector
 403             <
 404                 OverlayType, RemoveSpikes
 405             >::included(inside_value);
 406     }
 407
 408     template
 409     <
 410         typename Turns,
 411         typename OutputIterator,
 412         typename RobustPolicy,
 413         typename Strategy
 414     >
 415     static inline OutputIterator apply(LineString const& linestring, Polygon const& polygon,
 416                 detail::overlay::operation_type ,  // TODO: this parameter might be redundant
 417                 Turns& turns,
 418                 RobustPolicy const& robust_policy,
 419                 OutputIterator out,
 420                 Strategy const& strategy)
 421     {
 422         typedef typename boost::range_iterator<Turns>::type turn_iterator;
 423         typedef typename boost::range_value<Turns>::type turn_type;
 424         typedef typename boost::range_iterator
 425             <
 426                 typename turn_type::container_type
 427             >::type turn_operation_iterator_type;
 428
 429         typedef following::action_selector<OverlayType, RemoveSpikes> action;
 430
 431         typedef typename Strategy::cs_tag cs_tag;
 432
 433         typename Strategy::template point_in_geometry_strategy
 434             <
 435                 LineString, Polygon
 436             >::type const pt_in_poly_strategy
 437             = strategy.template get_point_in_geometry_strategy<LineString, Polygon>();
 438
 439         // Sort intersection points on segments-along-linestring, and distance
 440         // (like in enrich is done for poly/poly)
 441         // sort turns by Linear seg_id, then by fraction, then
 442         // for same ring id: x, u, i, c
 443         // for different ring id: c, i, u, x
 444 #ifdef BOOST_GEOMETRY_SETOPS_LA_OLD_BEHAVIOR
 445         std::sort(boost::begin(turns), boost::end(turns), sort_on_segment<turn_type>());
 446 #else
 447         typedef relate::turns::less
 448             <
 449                 0, relate::turns::less_op_linear_areal_single<0>, cs_tag
 450             > turn_less;
 451         std::sort(boost::begin(turns), boost::end(turns), turn_less());
 452 #endif
 453
 454         LineStringOut current_piece;
 455         geometry::segment_identifier current_segment_id(0, -1, -1, -1);
 456
 457         // Iterate through all intersection points (they are ordered along the line)
 458         bool entered = false;
 459         bool first = true;
 460         for (turn_iterator it = boost::begin(turns); it != boost::end(turns); ++it)
 461         {
 462             turn_operation_iterator_type iit = boost::begin(it->operations);
 463
 464             if (following::was_entered(*it, *iit, first, linestring, polygon, pt_in_poly_strategy))
 465             {
 466                 debug_traverse(*it, *iit, "-> Was entered");
 467                 entered = true;
 468             }
 469
 470             if (following::is_staying_inside(*it, *iit, entered, first, linestring, polygon, pt_in_poly_strategy))
 471             {
 472                 debug_traverse(*it, *iit, "-> Staying inside");
 473
 474                 entered = true;
 475             }
 476             else if (following::is_entering(*it, *iit))
 477             {
 478                 debug_traverse(*it, *iit, "-> Entering");
 479
 480                 entered = true;
 481                 action::enter(current_piece, linestring, current_segment_id,
 482                     iit->seg_id.segment_index, it->point, *iit,
 483                     strategy, robust_policy,
 484                     out);
 485             }
 486             else if (following::is_leaving(*it, *iit, entered, first, linestring, polygon, pt_in_poly_strategy))
 487             {
 488                 debug_traverse(*it, *iit, "-> Leaving");
 489
 490                 entered = false;
 491                 action::leave(current_piece, linestring, current_segment_id,
 492                     iit->seg_id.segment_index, it->point, *iit,
 493                     strategy, robust_policy,
 494                     out);
 495             }
 496             first = false;
 497         }
 498
 499         if (action::is_entered(entered))
 500         {
 501             detail::copy_segments::copy_segments_linestring
 502                 <
 503                     false, RemoveSpikes
 504                 >::apply(linestring,
 505                          current_segment_id,
 506                          static_cast<signed_size_type>(boost::size(linestring) - 1),
 507                          strategy, robust_policy,
 508                          current_piece);
 509         }
 510
 511         // Output the last one, if applicable
 512         if (::boost::size(current_piece) > 1)
 513         {
 514             *out++ = current_piece;
 515         }
 516         return out;
 517     }
 518
 519 };
 520
 521
 522 }} // namespace detail::overlay
 523 #endif // DOXYGEN_NO_DETAIL
 524
 525
 526 }} // namespace boost::geometry
 527
 528
 529 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_HPP