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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   4
   5 // Use, modification and distribution is subject to the Boost Software License,
   6 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8
   9 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_HPP
  10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_HPP
  11
  12 #include <cstddef>
  13
  14 #include <boost/range.hpp>
  15
  16 #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
  17 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
  18 #include <boost/geometry/core/access.hpp>
  19 #include <boost/geometry/core/assert.hpp>
  20
  21 #if defined(BOOST_GEOMETRY_DEBUG_INTERSECTION) \
  22     || defined(BOOST_GEOMETRY_OVERLAY_REPORT_WKT) \
  23     || defined(BOOST_GEOMETRY_DEBUG_TRAVERSE)
  24 #  include <string>
  25 #  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
  26 #  include <boost/geometry/io/wkt/wkt.hpp>
  27 #endif
  28
  29 namespace boost { namespace geometry
  30 {
  31
  32 #ifndef DOXYGEN_NO_DETAIL
  33 namespace detail { namespace overlay
  34 {
  35
  36 template <typename Turn, typename Operation>
  37 #ifdef BOOST_GEOMETRY_DEBUG_TRAVERSE
  38 inline void debug_traverse(Turn const& turn, Operation op,
  39                 std::string const& header)
  40 {
  41     std::cout << header
  42         << " at " << op.seg_id
  43         << " meth: " << method_char(turn.method)
  44         << " op: " << operation_char(op.operation)
  45         << " vis: " << visited_char(op.visited)
  46         << " of:  " << operation_char(turn.operations[0].operation)
  47         << operation_char(turn.operations[1].operation)
  48         << " " << geometry::wkt(turn.point)
  49         << std::endl;
  50
  51     if (boost::contains(header, "Finished"))
  52     {
  53         std::cout << std::endl;
  54     }
  55 }
  56 #else
  57 inline void debug_traverse(Turn const& , Operation, const char*)
  58 {
  59 }
  60 #endif
  61
  62
  63 //! Metafunction to define side_order (clockwise, ccw) by operation_type
  64 template <operation_type OpType>
  65 struct side_compare {};
  66
  67 template <>
  68 struct side_compare<operation_union>
  69 {
  70     typedef std::greater<int> type;
  71 };
  72
  73 template <>
  74 struct side_compare<operation_intersection>
  75 {
  76     typedef std::less<int> type;
  77 };
  78
  79
  80 template
  81 <
  82     bool Reverse1,
  83     bool Reverse2,
  84     overlay_type OverlayType,
  85     typename Geometry1,
  86     typename Geometry2,
  87     typename Turns,
  88     typename Clusters,
  89     typename RobustPolicy,
  90     typename Visitor
  91 >
  92 struct traversal
  93 {
  94     static const operation_type target_operation = operation_from_overlay<OverlayType>::value;
  95
  96     typedef typename side_compare<target_operation>::type side_compare_type;
  97     typedef typename boost::range_value<Turns>::type turn_type;
  98     typedef typename turn_type::turn_operation_type turn_operation_type;
  99
 100     typedef typename geometry::point_type<Geometry1>::type point_type;
 101     typedef sort_by_side::side_sorter
 102         <
 103             Reverse1, Reverse2,
 104             point_type, side_compare_type
 105         > sbs_type;
 106
 107     inline traversal(Geometry1 const& geometry1, Geometry2 const& geometry2,
 108             Turns& turns, Clusters const& clusters,
 109             RobustPolicy const& robust_policy, Visitor& visitor)
 110         : m_geometry1(geometry1)
 111         , m_geometry2(geometry2)
 112         , m_turns(turns)
 113         , m_clusters(clusters)
 114         , m_robust_policy(robust_policy)
 115         , m_visitor(visitor)
 116     {
 117     }
 118
 119     inline void finalize_visit_info()
 120     {
 121         for (typename boost::range_iterator<Turns>::type
 122             it = boost::begin(m_turns);
 123             it != boost::end(m_turns);
 124             ++it)
 125         {
 126             turn_type& turn = *it;
 127             for (int i = 0; i < 2; i++)
 128             {
 129                 turn_operation_type& op = turn.operations[i];
 130                 op.visited.finalize();
 131             }
 132         }
 133     }
 134
 135     inline void set_visited(turn_type& turn, turn_operation_type& op)
 136     {
 137         // On "continue", set "visited" for ALL directions in this turn
 138         if (op.operation == detail::overlay::operation_continue)
 139         {
 140             for (int i = 0; i < 2; i++)
 141             {
 142                 turn_operation_type& op = turn.operations[i];
 143                 if (op.visited.none())
 144                 {
 145                     op.visited.set_visited();
 146                 }
 147             }
 148         }
 149         else
 150         {
 151             op.visited.set_visited();
 152         }
 153     }
 154
 155     inline bool is_visited(turn_type const& turn, turn_operation_type const& op,
 156                            signed_size_type turn_index, int op_index) const
 157     {
 158         return op.visited.visited();
 159     }
 160
 161     inline bool select_source(signed_size_type turn_index,
 162                               segment_identifier const& seg_id1,
 163                               segment_identifier const& seg_id2) const
 164     {
 165         if (target_operation == operation_intersection)
 166         {
 167             // For intersections always switch sources
 168             return seg_id1.source_index != seg_id2.source_index;
 169         }
 170         else if (target_operation == operation_union)
 171         {
 172             // For uu, only switch sources if indicated
 173             turn_type const& turn = m_turns[turn_index];
 174
 175             if (OverlayType == overlay_buffer)
 176             {
 177                 // Buffer does not use source_index (always 0)
 178                 return turn.switch_source
 179                         ? seg_id1.multi_index != seg_id2.multi_index
 180                         : seg_id1.multi_index == seg_id2.multi_index;
 181             }
 182
 183 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
 184             if (turn.switch_source == 1)
 185             {
 186                 std::cout << "Switch source at " << turn_index << std::endl;
 187             }
 188             else
 189             {
 190                 std::cout << "DON'T SWITCH SOURCES at " << turn_index << std::endl;
 191             }
 192 #endif
 193             return turn.switch_source
 194                     ? seg_id1.source_index != seg_id2.source_index
 195                     : seg_id1.source_index == seg_id2.source_index;
 196         }
 197         return false;
 198     }
 199
 200     inline
 201     signed_size_type get_next_turn_index(turn_operation_type const& op) const
 202     {
 203         return op.enriched.next_ip_index == -1
 204                 ? op.enriched.travels_to_ip_index
 205                 : op.enriched.next_ip_index;
 206     }
 207
 208     inline bool traverse_possible(signed_size_type turn_index) const
 209     {
 210         if (turn_index == -1)
 211         {
 212             return false;
 213         }
 214
 215         turn_type const& turn = m_turns[turn_index];
 216
 217         // It is not a dead end if there is an operation to continue, or of
 218         // there is a cluster (assuming for now we can get out of the cluster)
 219         return turn.cluster_id >= 0
 220             || turn.has(target_operation)
 221             || turn.has(operation_continue);
 222     }
 223
 224     inline
 225     bool select_cc_operation(turn_type const& turn,
 226                 signed_size_type start_turn_index,
 227                 int& selected_op_index) const
 228     {
 229         // For "cc", take either one, but if there is a starting one,
 230         //           take that one. If next is dead end, skip that one.
 231
 232         bool result = false;
 233
 234         typename turn_operation_type::comparable_distance_type
 235                 max_remaining_distance = 0;
 236
 237         for (int i = 0; i < 2; i++)
 238         {
 239             turn_operation_type const& op = turn.operations[i];
 240
 241             signed_size_type const next_turn_index = get_next_turn_index(op);
 242
 243             if (! result && traverse_possible(next_turn_index))
 244             {
 245                 max_remaining_distance = op.remaining_distance;
 246                 selected_op_index = i;
 247                 debug_traverse(turn, op, " Candidate");
 248                 result = true;
 249             }
 250
 251             if (result)
 252             {
 253                 if (next_turn_index == start_turn_index)
 254                 {
 255                     selected_op_index = i;
 256                     debug_traverse(turn, op, " Candidate cc override (start)");
 257                 }
 258                 else if (op.remaining_distance > max_remaining_distance)
 259                 {
 260                     max_remaining_distance = op.remaining_distance;
 261                     selected_op_index = i;
 262                     debug_traverse(turn, op, " Candidate cc override (remaining)");
 263                 }
 264             }
 265         }
 266
 267         return result;
 268     }
 269
 270     inline
 271     bool select_noncc_operation(turn_type const& turn,
 272                 signed_size_type turn_index,
 273                 segment_identifier const& seg_id,
 274                 int& selected_op_index) const
 275     {
 276         // For "ii", take the other one (alternate)
 277         //           UNLESS the other one is already visited
 278         // For "uu", take the same one (see above);
 279
 280         bool result = false;
 281
 282         for (int i = 0; i < 2; i++)
 283         {
 284             turn_operation_type const& op = turn.operations[i];
 285
 286             if (op.operation == target_operation
 287                 && ! op.visited.finished()
 288                 && (! result || select_source(turn_index, op.seg_id, seg_id)))
 289             {
 290                 selected_op_index = i;
 291                 debug_traverse(turn, op, " Candidate");
 292                 result = true;
 293             }
 294         }
 295
 296         return result;
 297     }
 298
 299     inline
 300     bool select_operation(const turn_type& turn,
 301                 signed_size_type turn_index,
 302                 signed_size_type start_turn_index,
 303                 segment_identifier const& previous_seg_id,
 304                 int& selected_op_index) const
 305     {
 306         bool result = false;
 307         selected_op_index = -1;
 308         if (turn.both(operation_continue))
 309         {
 310             result = select_cc_operation(turn, start_turn_index,
 311                                          selected_op_index);
 312         }
 313         else
 314         {
 315             result = select_noncc_operation(turn, turn_index,
 316                                             previous_seg_id, selected_op_index);
 317         }
 318         if (result)
 319         {
 320            debug_traverse(turn, turn.operations[selected_op_index], " Accepted");
 321         }
 322
 323         return result;
 324     }
 325
 326     inline int starting_operation_index(const turn_type& turn) const
 327     {
 328         for (int i = 0; i < 2; i++)
 329         {
 330             if (turn.operations[i].visited.started())
 331             {
 332                 return i;
 333             }
 334         }
 335         return -1;
 336     }
 337
 338     inline bool both_finished(const turn_type& turn) const
 339     {
 340         for (int i = 0; i < 2; i++)
 341         {
 342             if (! turn.operations[i].visited.finished())
 343             {
 344                 return false;
 345             }
 346         }
 347         return true;
 348     }
 349
 350     inline bool select_from_cluster(signed_size_type& turn_index,
 351         int& op_index, signed_size_type start_turn_index,
 352         sbs_type const& sbs, bool is_touching) const
 353     {
 354         bool const is_union = target_operation == operation_union;
 355         bool const is_intersection = target_operation == operation_intersection;
 356
 357         std::size_t selected_rank = 0;
 358         std::size_t min_rank = 0;
 359         bool result = false;
 360         for (std::size_t i = 0; i < sbs.m_ranked_points.size(); i++)
 361         {
 362             typename sbs_type::rp const& ranked_point = sbs.m_ranked_points[i];
 363             if (result && ranked_point.rank > selected_rank)
 364             {
 365                 return result;
 366             }
 367
 368             turn_type const& ranked_turn = m_turns[ranked_point.turn_index];
 369             turn_operation_type const& ranked_op = ranked_turn.operations[ranked_point.operation_index];
 370
 371             if (result && ranked_op.visited.finalized())
 372             {
 373                 // One of the arcs in the same direction as the selected result
 374                 // is already traversed.
 375                 return false;
 376             }
 377
 378             if (! is_touching && ranked_op.visited.finalized())
 379             {
 380                 // Skip this one, go to next
 381                 min_rank = ranked_point.rank;
 382                 continue;
 383             }
 384
 385             if (ranked_point.direction == sort_by_side::dir_to
 386                 && (ranked_point.rank > min_rank
 387                     || ranked_turn.both(operation_continue)))
 388             {
 389                 if ((is_union
 390                      && ranked_op.enriched.count_left == 0
 391                      && ranked_op.enriched.count_right > 0)
 392                 || (is_intersection
 393                      && ranked_op.enriched.count_right == 2))
 394                 {
 395                     if (result && ranked_point.turn_index != start_turn_index)
 396                     {
 397                         // Don't override - only override if arrive at start
 398                         continue;
 399                     }
 400
 401                     turn_index = ranked_point.turn_index;
 402                     op_index = ranked_point.operation_index;
 403
 404                     if (is_intersection
 405                         && ranked_turn.both(operation_intersection)
 406                         && ranked_op.visited.finalized())
 407                     {
 408                         // Override:
 409                         // For a ii turn, even though one operation might be selected,
 410                         // it should take the other one if the first one is used in a completed ring
 411                         op_index = 1 - ranked_point.operation_index;
 412                     }
 413
 414                     result = true;
 415                     selected_rank = ranked_point.rank;
 416                 }
 417                 else if (! is_touching)
 418                 {
 419                     return result;
 420                 }
 421             }
 422         }
 423         return result;
 424     }
 425
 426     inline bool select_turn_from_cluster(signed_size_type& turn_index,
 427             int& op_index, bool& is_touching,
 428             signed_size_type start_turn_index,
 429             segment_identifier const& previous_seg_id) const
 430     {
 431         bool const is_union = target_operation == operation_union;
 432
 433         turn_type const& turn = m_turns[turn_index];
 434         BOOST_ASSERT(turn.cluster_id >= 0);
 435
 436         typename Clusters::const_iterator mit = m_clusters.find(turn.cluster_id);
 437         BOOST_ASSERT(mit != m_clusters.end());
 438
 439         cluster_info const& cinfo = mit->second;
 440         std::set<signed_size_type> const& ids = cinfo.turn_indices;
 441
 442         sbs_type sbs;
 443
 444         bool has_origin = false;
 445
 446         for (typename std::set<signed_size_type>::const_iterator sit = ids.begin();
 447              sit != ids.end(); ++sit)
 448         {
 449             signed_size_type cluster_turn_index = *sit;
 450             turn_type const& cluster_turn = m_turns[cluster_turn_index];
 451             if (cluster_turn.discarded)
 452             {
 453                 // Defensive check, discarded turns should not be in cluster
 454                 continue;
 455             }
 456
 457             for (int i = 0; i < 2; i++)
 458             {
 459                 turn_operation_type const& op = cluster_turn.operations[i];
 460                 bool is_origin = false;
 461                 if (cluster_turn_index == turn_index)
 462                 {
 463                     // Check if this is the origin
 464                     if (OverlayType == overlay_buffer)
 465                     {
 466                         is_origin = op.seg_id.multi_index == previous_seg_id.multi_index;
 467                     }
 468                     else
 469                     {
 470                         is_origin = op.seg_id.source_index
 471                                     == previous_seg_id.source_index;
 472                     }
 473                     if (is_origin)
 474                     {
 475                         has_origin = true;
 476                     }
 477                 }
 478
 479                 sbs.add(op, cluster_turn_index, i, m_geometry1, m_geometry2,
 480                         is_origin);
 481             }
 482         }
 483
 484         if (! has_origin)
 485         {
 486             return false;
 487         }
 488
 489         sbs.apply(turn.point);
 490
 491 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
 492         is_touching = is_union && cinfo.open_count > 1;
 493         if (is_touching)
 494         {
 495             if (cinfo.switch_source)
 496             {
 497                 is_touching = false;
 498                 std::cout << "CLUSTER: SWITCH SOURCES at " << turn_index << std::endl;
 499             }
 500             else
 501             {
 502                 std::cout << "CLUSTER: CONTINUE at " << turn_index << std::endl;
 503             }
 504         }
 505 #else
 506         is_touching = is_union && cinfo.open_count > 1 && ! cinfo.switch_source;
 507 #endif
 508         if (is_touching)
 509         {
 510             sbs.reverse();
 511         }
 512
 513         return select_from_cluster(turn_index, op_index, start_turn_index, sbs,
 514                                    is_touching);
 515     }
 516
 517     inline void change_index_for_self_turn(signed_size_type& to_vertex_index,
 518                 turn_type const& start_turn,
 519                 turn_operation_type const& start_op,
 520                 int start_op_index) const
 521     {
 522         if (OverlayType != overlay_buffer)
 523         {
 524             return;
 525         }
 526
 527         // It travels to itself, can happen. If this is a buffer, it can
 528         // sometimes travel to itself in the following configuration:
 529         //
 530         // +---->--+
 531         // |       |
 532         // |   +---*----+ *: one turn, with segment index 2/7
 533         // |   |   |    |
 534         // |   +---C    | C: closing point (start/end)
 535         // |            |
 536         // +------------+
 537         //
 538         // If it starts on segment 2 and travels to itself on segment 2, that
 539         // should be corrected to 7 because that is the shortest path
 540         //
 541         // Also a uu turn (touching with another buffered ring) might have this
 542         // apparent configuration, but there it should
 543         // always travel the whole ring
 544
 545         turn_operation_type const& other_op
 546                 = start_turn.operations[1 - start_op_index];
 547
 548         bool const correct
 549                 = ! start_turn.both(operation_union)
 550                   && start_op.seg_id.segment_index == to_vertex_index;
 551
 552 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSE)
 553         std::cout << " WARNING: self-buffer "
 554                   << " correct=" << correct
 555                   << " turn=" << operation_char(start_turn.operations[0].operation)
 556                   << operation_char(start_turn.operations[1].operation)
 557                   << " start=" << start_op.seg_id.segment_index
 558                   << " from=" << to_vertex_index
 559                   << " to=" << other_op.enriched.travels_to_vertex_index
 560                   << std::endl;
 561 #endif
 562
 563         if (correct)
 564         {
 565             to_vertex_index = other_op.enriched.travels_to_vertex_index;
 566         }
 567     }
 568
 569     bool select_turn_from_enriched(signed_size_type& turn_index,
 570             segment_identifier& previous_seg_id,
 571             signed_size_type& to_vertex_index,
 572             signed_size_type start_turn_index,
 573             int start_op_index,
 574             turn_type const& previous_turn,
 575             turn_operation_type const& previous_op,
 576             bool is_start) const
 577     {
 578         to_vertex_index = -1;
 579
 580         if (previous_op.enriched.next_ip_index < 0)
 581         {
 582             // There is no next IP on this segment
 583             if (previous_op.enriched.travels_to_vertex_index < 0
 584                 || previous_op.enriched.travels_to_ip_index < 0)
 585             {
 586                 return false;
 587             }
 588
 589             to_vertex_index = previous_op.enriched.travels_to_vertex_index;
 590
 591             if (is_start &&
 592                     previous_op.enriched.travels_to_ip_index == start_turn_index)
 593             {
 594                 change_index_for_self_turn(to_vertex_index, previous_turn,
 595                     previous_op, start_op_index);
 596             }
 597
 598             turn_index = previous_op.enriched.travels_to_ip_index;
 599             previous_seg_id = previous_op.seg_id;
 600         }
 601         else
 602         {
 603             // Take the next IP on this segment
 604             turn_index = previous_op.enriched.next_ip_index;
 605             previous_seg_id = previous_op.seg_id;
 606         }
 607         return true;
 608     }
 609
 610     bool select_turn(signed_size_type start_turn_index,
 611                      signed_size_type& turn_index,
 612                      int& op_index,
 613                      bool& is_touching,
 614                      int previous_op_index,
 615                      signed_size_type previous_turn_index,
 616                      segment_identifier const& previous_seg_id,
 617                      bool is_start)
 618     {
 619         if (m_turns[turn_index].cluster_id >= 0)
 620         {
 621             if (! select_turn_from_cluster(turn_index, op_index, is_touching,
 622                     start_turn_index, previous_seg_id))
 623             {
 624                 return false;
 625             }
 626
 627             if (is_start && turn_index == previous_turn_index)
 628             {
 629                 op_index = previous_op_index;
 630             }
 631         }
 632         else
 633         {
 634             turn_type const& current_turn = m_turns[turn_index];
 635
 636             op_index = starting_operation_index(current_turn);
 637             if (op_index == -1)
 638             {
 639                 if (both_finished(current_turn))
 640                 {
 641                     return false;
 642                 }
 643
 644                 if (! select_operation(current_turn, turn_index,
 645                                 start_turn_index,
 646                                 previous_seg_id,
 647                                 op_index))
 648                 {
 649                     return false;
 650                 }
 651             }
 652         }
 653         return true;
 654     }
 655
 656 private :
 657     Geometry1 const& m_geometry1;
 658     Geometry2 const& m_geometry2;
 659     Turns& m_turns;
 660     Clusters const& m_clusters;
 661     RobustPolicy const& m_robust_policy;
 662     Visitor& m_visitor;
 663 };
 664
 665
 666
 667 }} // namespace detail::overlay
 668 #endif // DOXYGEN_NO_DETAIL
 669
 670 }} // namespace boost::geometry
 671
 672 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_HPP