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