ceph/src/boost/libs/geometry/include/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.
   6 // Modifications copyright (c) 2014 Oracle and/or its affiliates.
   7
   8 // Contributed and/or modified by Menelaos Karavelas, 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
  30
  31 namespace boost { namespace geometry
  32 {
  33
  34
  35 #ifndef DOXYGEN_NO_DETAIL
  36 namespace detail { namespace overlay
  37 {
  38
  39 namespace following
  40 {
  41
  42 template <typename Turn, typename Operation>
  43 static inline bool is_entering(Turn const& /* TODO remove this parameter */, Operation const& op)
  44 {
  45     // (Blocked means: blocked for polygon/polygon intersection, because
  46     // they are reversed. But for polygon/line it is similar to continue)
  47     return op.operation == operation_intersection
  48         || op.operation == operation_continue
  49         || op.operation == operation_blocked
  50         ;
  51 }
  52
  53 template
  54 <
  55     typename Turn,
  56     typename Operation,
  57     typename LineString,
  58     typename Polygon
  59 >
  60 static inline bool last_covered_by(Turn const& turn, Operation const& op,
  61                 LineString const& linestring, Polygon const& polygon)
  62 {
  63     // Check any point between the this one and the first IP
  64     typedef typename geometry::point_type<LineString>::type point_type;
  65     point_type point_in_between;
  66     detail::point_on_border::midpoint_helper
  67         <
  68             point_type,
  69             0, dimension<point_type>::value
  70         >::apply(point_in_between, *(::boost::begin(linestring) + op.seg_id.segment_index), turn.point);
  71
  72     return geometry::covered_by(point_in_between, polygon);
  73 }
  74
  75
  76 template
  77 <
  78     typename Turn,
  79     typename Operation,
  80     typename LineString,
  81     typename Polygon
  82 >
  83 static inline bool is_leaving(Turn const& turn, Operation const& op,
  84                 bool entered, bool first,
  85                 LineString const& linestring, Polygon const& polygon)
  86 {
  87     if (op.operation == operation_union)
  88     {
  89         return entered
  90             || turn.method == method_crosses
  91             || (first && last_covered_by(turn, op, linestring, polygon))
  92             ;
  93     }
  94     return false;
  95 }
  96
  97
  98 template
  99 <
 100     typename Turn,
 101     typename Operation,
 102     typename LineString,
 103     typename Polygon
 104 >
 105 static inline bool is_staying_inside(Turn const& turn, Operation const& op,
 106                 bool entered, bool first,
 107                 LineString const& linestring, Polygon const& polygon)
 108 {
 109     if (turn.method == method_crosses)
 110     {
 111         // The normal case, this is completely covered with entering/leaving
 112         // so stay out of this time consuming "covered_by"
 113         return false;
 114     }
 115
 116     if (is_entering(turn, op))
 117     {
 118         return entered || (first && last_covered_by(turn, op, linestring, polygon));
 119     }
 120
 121     return false;
 122 }
 123
 124 template
 125 <
 126     typename Turn,
 127     typename Operation,
 128     typename Linestring,
 129     typename Polygon
 130 >
 131 static inline bool was_entered(Turn const& turn, Operation const& op, bool first,
 132                 Linestring const& linestring, Polygon const& polygon)
 133 {
 134     if (first && (turn.method == method_collinear || turn.method == method_equal))
 135     {
 136         return last_covered_by(turn, op, linestring, polygon);
 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 RobustPolicy
 162     >
 163     static inline void enter(LineStringOut& current_piece,
 164                 LineString const& ,
 165                 segment_identifier& segment_id,
 166                 signed_size_type , Point const& point,
 167                 Operation const& operation,
 168                 RobustPolicy const& ,
 169                 OutputIterator& )
 170     {
 171         // On enter, append the intersection point and remember starting point
 172         // TODO: we don't check on spikes for linestrings (?). Consider this.
 173         detail::overlay::append_no_duplicates(current_piece, point);
 174         segment_id = operation.seg_id;
 175     }
 176
 177     template
 178     <
 179         typename OutputIterator,
 180         typename LineStringOut,
 181         typename LineString,
 182         typename Point,
 183         typename Operation,
 184         typename RobustPolicy
 185     >
 186     static inline void leave(LineStringOut& current_piece,
 187                 LineString const& linestring,
 188                 segment_identifier& segment_id,
 189                 signed_size_type index, Point const& point,
 190                 Operation const& ,
 191                 RobustPolicy const& robust_policy,
 192                 OutputIterator& out)
 193     {
 194         // On leave, copy all segments from starting point, append the intersection point
 195         // and add the output piece
 196         detail::copy_segments::copy_segments_linestring
 197             <
 198                 false, RemoveSpikes
 199             >::apply(linestring, segment_id, index, robust_policy, current_piece);
 200         detail::overlay::append_no_duplicates(current_piece, point);
 201         if (::boost::size(current_piece) > 1)
 202         {
 203             *out++ = current_piece;
 204         }
 205
 206         geometry::clear(current_piece);
 207     }
 208
 209     template
 210     <
 211         typename OutputIterator,
 212         typename LineStringOut,
 213         typename LineString,
 214         typename Point,
 215         typename Operation
 216     >
 217     static inline void isolated_point(LineStringOut&,
 218                 LineString const&,
 219                 segment_identifier&,
 220                 signed_size_type, Point const& point,
 221                 Operation const& , OutputIterator& out)
 222     {
 223         LineStringOut isolated_point_ls;
 224         geometry::append(isolated_point_ls, point);
 225
 226 #ifndef BOOST_GEOMETRY_ALLOW_ONE_POINT_LINESTRINGS
 227         geometry::append(isolated_point_ls, point);
 228 #endif // BOOST_GEOMETRY_ALLOW_ONE_POINT_LINESTRINGS
 229
 230         *out++ = isolated_point_ls;
 231     }
 232
 233     static inline bool is_entered(bool entered)
 234     {
 235         return entered;
 236     }
 237
 238     template
 239     <
 240         typename Point,
 241         typename Geometry,
 242         typename RobustPolicy
 243     >
 244     static inline bool included(Point const& point,
 245             Geometry const& geometry,
 246             RobustPolicy const& )
 247     {
 248         return geometry::covered_by(point, geometry);
 249     }
 250
 251 };
 252
 253 // Specialization for difference, which reverses these actions
 254 template <bool RemoveSpikes>
 255 struct action_selector<overlay_difference, RemoveSpikes>
 256 {
 257     typedef action_selector<overlay_intersection, RemoveSpikes> normal_action;
 258
 259     template
 260     <
 261         typename OutputIterator,
 262         typename LineStringOut,
 263         typename LineString,
 264         typename Point,
 265         typename Operation,
 266         typename RobustPolicy
 267     >
 268     static inline void enter(LineStringOut& current_piece,
 269                 LineString const& linestring,
 270                 segment_identifier& segment_id,
 271                 signed_size_type index, Point const& point,
 272                 Operation const& operation,
 273                 RobustPolicy const& robust_policy,
 274                 OutputIterator& out)
 275     {
 276         normal_action::leave(current_piece, linestring, segment_id, index,
 277                     point, operation, robust_policy, out);
 278     }
 279
 280     template
 281     <
 282         typename OutputIterator,
 283         typename LineStringOut,
 284         typename LineString,
 285         typename Point,
 286         typename Operation,
 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                 RobustPolicy const& robust_policy,
 295                 OutputIterator& out)
 296     {
 297         normal_action::enter(current_piece, linestring, segment_id, index,
 298                     point, operation, 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     template
 323     <
 324         typename Point,
 325         typename Geometry,
 326         typename RobustPolicy
 327     >
 328     static inline bool included(Point const& point,
 329         Geometry const& geometry,
 330         RobustPolicy const& robust_policy)
 331     {
 332         return ! normal_action::included(point, geometry, robust_policy);
 333     }
 334
 335 };
 336
 337 }
 338
 339 /*!
 340 \brief Follows a linestring from intersection point to intersection point, outputting which
 341     is inside, or outside, a ring or polygon
 342 \ingroup overlay
 343  */
 344 template
 345 <
 346     typename LineStringOut,
 347     typename LineString,
 348     typename Polygon,
 349     overlay_type OverlayType,
 350     bool RemoveSpikes = true
 351 >
 352 class follow
 353 {
 354
 355     template <typename Turn>
 356     struct sort_on_segment
 357     {
 358         // In case of turn point at the same location, we want to have continue/blocked LAST
 359         // because that should be followed (intersection) or skipped (difference).
 360         inline int operation_order(Turn const& turn) const
 361         {
 362             operation_type const& operation = turn.operations[0].operation;
 363             switch(operation)
 364             {
 365                 case operation_opposite : return 0;
 366                 case operation_none : return 0;
 367                 case operation_union : return 1;
 368                 case operation_intersection : return 2;
 369                 case operation_blocked : return 3;
 370                 case operation_continue : return 4;
 371             }
 372             return -1;
 373         };
 374
 375         inline bool use_operation(Turn const& left, Turn const& right) const
 376         {
 377             // If they are the same, OK.
 378             return operation_order(left) < operation_order(right);
 379         }
 380
 381         inline bool use_distance(Turn const& left, Turn const& right) const
 382         {
 383             return left.operations[0].fraction == right.operations[0].fraction
 384                 ? use_operation(left, right)
 385                 : left.operations[0].fraction < right.operations[0].fraction
 386                 ;
 387         }
 388
 389         inline bool operator()(Turn const& left, Turn const& right) const
 390         {
 391             segment_identifier const& sl = left.operations[0].seg_id;
 392             segment_identifier const& sr = right.operations[0].seg_id;
 393
 394             return sl == sr
 395                 ? use_distance(left, right)
 396                 : sl < sr
 397                 ;
 398
 399         }
 400     };
 401
 402
 403
 404 public :
 405
 406     template
 407     <
 408         typename Point,
 409         typename Geometry,
 410         typename RobustPolicy
 411     >
 412     static inline bool included(Point const& point,
 413             Geometry const& geometry,
 414             RobustPolicy const& robust_policy)
 415     {
 416         return following::action_selector
 417             <
 418                 OverlayType, RemoveSpikes
 419             >::included(point, geometry, robust_policy);
 420     }
 421
 422     template
 423     <
 424         typename Turns,
 425         typename OutputIterator,
 426         typename RobustPolicy
 427     >
 428     static inline OutputIterator apply(LineString const& linestring, Polygon const& polygon,
 429                 detail::overlay::operation_type ,  // TODO: this parameter might be redundant
 430                 Turns& turns,
 431                 RobustPolicy const& robust_policy,
 432                 OutputIterator out)
 433     {
 434         typedef typename boost::range_iterator<Turns>::type turn_iterator;
 435         typedef typename boost::range_value<Turns>::type turn_type;
 436         typedef typename boost::range_iterator
 437             <
 438                 typename turn_type::container_type
 439             >::type turn_operation_iterator_type;
 440
 441         typedef following::action_selector<OverlayType, RemoveSpikes> action;
 442
 443         // Sort intersection points on segments-along-linestring, and distance
 444         // (like in enrich is done for poly/poly)
 445         std::sort(boost::begin(turns), boost::end(turns), sort_on_segment<turn_type>());
 446
 447         LineStringOut current_piece;
 448         geometry::segment_identifier current_segment_id(0, -1, -1, -1);
 449
 450         // Iterate through all intersection points (they are ordered along the line)
 451         bool entered = false;
 452         bool first = true;
 453         for (turn_iterator it = boost::begin(turns); it != boost::end(turns); ++it)
 454         {
 455             turn_operation_iterator_type iit = boost::begin(it->operations);
 456
 457             if (following::was_entered(*it, *iit, first, linestring, polygon))
 458             {
 459                 debug_traverse(*it, *iit, "-> Was entered");
 460                 entered = true;
 461             }
 462
 463             if (following::is_staying_inside(*it, *iit, entered, first, linestring, polygon))
 464             {
 465                 debug_traverse(*it, *iit, "-> Staying inside");
 466
 467                 entered = true;
 468             }
 469             else if (following::is_entering(*it, *iit))
 470             {
 471                 debug_traverse(*it, *iit, "-> Entering");
 472
 473                 entered = true;
 474                 action::enter(current_piece, linestring, current_segment_id,
 475                     iit->seg_id.segment_index, it->point, *iit,
 476                     robust_policy,
 477                     out);
 478             }
 479             else if (following::is_leaving(*it, *iit, entered, first, linestring, polygon))
 480             {
 481                 debug_traverse(*it, *iit, "-> Leaving");
 482
 483                 entered = false;
 484                 action::leave(current_piece, linestring, current_segment_id,
 485                     iit->seg_id.segment_index, it->point, *iit,
 486                     robust_policy,
 487                     out);
 488             }
 489             first = false;
 490         }
 491
 492         if (action::is_entered(entered))
 493         {
 494             detail::copy_segments::copy_segments_linestring
 495                 <
 496                     false, RemoveSpikes
 497                 >::apply(linestring,
 498                          current_segment_id,
 499                          static_cast<signed_size_type>(boost::size(linestring) - 1),
 500                          robust_policy,
 501                          current_piece);
 502         }
 503
 504         // Output the last one, if applicable
 505         if (::boost::size(current_piece) > 1)
 506         {
 507             *out++ = current_piece;
 508         }
 509         return out;
 510     }
 511
 512 };
 513
 514
 515 }} // namespace detail::overlay
 516 #endif // DOXYGEN_NO_DETAIL
 517
 518
 519 }} // namespace boost::geometry
 520
 521
 522 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_FOLLOW_HPP