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