ceph/src/boost/boost/geometry/algorithms/detail/overlay/enrich_intersection_points.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
   5
   6 // This file was modified by Oracle on 2017-2020.
   7 // Modifications copyright (c) 2017-2020 Oracle and/or its affiliates.
   8
   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_ENRICH_HPP
  16 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP
  17
  18 #include <cstddef>
  19 #include <algorithm>
  20 #include <map>
  21 #include <set>
  22 #include <vector>
  23
  24 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
  25 #  include <iostream>
  26 #  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
  27 #  include <boost/geometry/io/wkt/wkt.hpp>
  28 #  if ! defined(BOOST_GEOMETRY_DEBUG_IDENTIFIER)
  29 #    define BOOST_GEOMETRY_DEBUG_IDENTIFIER
  30   #endif
  31 #endif
  32
  33 #include <boost/range/begin.hpp>
  34 #include <boost/range/end.hpp>
  35 #include <boost/range/value_type.hpp>
  36
  37 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
  38 #include <boost/geometry/algorithms/detail/overlay/handle_colocations.hpp>
  39 #include <boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp>
  40 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
  41 #include <boost/geometry/algorithms/detail/overlay/less_by_segment_ratio.hpp>
  42 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
  43 #include <boost/geometry/policies/robustness/robust_type.hpp>
  44
  45 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
  46 #  include <boost/geometry/algorithms/detail/overlay/check_enrich.hpp>
  47 #endif
  48
  49
  50 namespace boost { namespace geometry
  51 {
  52
  53 #ifndef DOXYGEN_NO_DETAIL
  54 namespace detail { namespace overlay
  55 {
  56
  57 template <typename Turns>
  58 struct discarded_indexed_turn
  59 {
  60     discarded_indexed_turn(Turns const& turns)
  61         : m_turns(turns)
  62     {}
  63
  64     template <typename IndexedTurn>
  65     inline bool operator()(IndexedTurn const& indexed) const
  66     {
  67         return m_turns[indexed.turn_index].discarded;
  68     }
  69
  70     Turns const& m_turns;
  71 };
  72
  73 // Sorts IP-s of this ring on segment-identifier, and if on same segment,
  74 //  on distance.
  75 // Then assigns for each IP which is the next IP on this segment,
  76 // plus the vertex-index to travel to, plus the next IP
  77 // (might be on another segment)
  78 template
  79 <
  80     bool Reverse1, bool Reverse2,
  81     typename Operations,
  82     typename Turns,
  83     typename Geometry1, typename Geometry2,
  84     typename RobustPolicy,
  85     typename SideStrategy
  86 >
  87 inline void enrich_sort(Operations& operations,
  88             Turns const& turns,
  89             Geometry1 const& geometry1,
  90             Geometry2 const& geometry2,
  91             RobustPolicy const& robust_policy,
  92             SideStrategy const& strategy)
  93 {
  94     std::sort(boost::begin(operations),
  95             boost::end(operations),
  96             less_by_segment_ratio
  97                 <
  98                     Turns,
  99                     typename boost::range_value<Operations>::type,
 100                     Geometry1, Geometry2,
 101                     RobustPolicy,
 102                     SideStrategy,
 103                     Reverse1, Reverse2
 104                 >(turns, geometry1, geometry2, robust_policy, strategy));
 105 }
 106
 107
 108 template <typename Operations, typename Turns>
 109 inline void enrich_assign(Operations& operations, Turns& turns,
 110                           bool check_turns)
 111 {
 112     typedef typename boost::range_value<Turns>::type turn_type;
 113     typedef typename turn_type::turn_operation_type op_type;
 114     typedef typename boost::range_iterator<Operations>::type iterator_type;
 115
 116
 117     if (operations.size() > 0)
 118     {
 119         // Assign travel-to-vertex/ip index for each turning point.
 120         // Iterator "next" is circular
 121
 122         geometry::ever_circling_range_iterator<Operations const> next(operations);
 123         ++next;
 124
 125         for (iterator_type it = boost::begin(operations);
 126              it != boost::end(operations); ++it)
 127         {
 128             turn_type& turn = turns[it->turn_index];
 129             op_type& op = turn.operations[it->operation_index];
 130
 131             if (check_turns && it->turn_index == next->turn_index)
 132             {
 133                 // Normal behaviour: next points at next turn, increase next.
 134                 // For dissolve this should not be done, turn_index is often
 135                 // the same for two consecutive operations
 136                 ++next;
 137             }
 138
 139             // Cluster behaviour: next should point after cluster, unless
 140             // their seg_ids are not the same
 141             // (For dissolve, this is still to be examined - TODO)
 142             while (turn.is_clustered()
 143                    && it->turn_index != next->turn_index
 144                    && turn.cluster_id == turns[next->turn_index].cluster_id
 145                    && op.seg_id == turns[next->turn_index].operations[next->operation_index].seg_id)
 146             {
 147                 ++next;
 148             }
 149
 150             turn_type const& next_turn = turns[next->turn_index];
 151             op_type const& next_op = next_turn.operations[next->operation_index];
 152
 153             op.enriched.travels_to_ip_index
 154                     = static_cast<signed_size_type>(next->turn_index);
 155             op.enriched.travels_to_vertex_index
 156                     = next->subject->seg_id.segment_index;
 157
 158             if (op.seg_id.segment_index == next_op.seg_id.segment_index
 159                     && op.fraction < next_op.fraction)
 160             {
 161                 // Next turn is located further on same segment
 162                 // assign next_ip_index
 163                 // (this is one not circular therefore fraction is considered)
 164                 op.enriched.next_ip_index = static_cast<signed_size_type>(next->turn_index);
 165             }
 166
 167             if (! check_turns)
 168             {
 169                 ++next;
 170             }
 171         }
 172     }
 173
 174     // DEBUG
 175 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
 176     {
 177         for (iterator_type it = boost::begin(operations);
 178              it != boost::end(operations);
 179              ++it)
 180         {
 181             op_type const& op = turns[it->turn_index]
 182                 .operations[it->operation_index];
 183
 184             std::cout << it->turn_index
 185                 << " cl=" << turns[it->turn_index].cluster_id
 186                 << " meth=" << method_char(turns[it->turn_index].method)
 187                 << " seg=" << op.seg_id
 188                 << " dst=" << op.fraction // needs define
 189                 << " op=" << operation_char(turns[it->turn_index].operations[0].operation)
 190                 << operation_char(turns[it->turn_index].operations[1].operation)
 191                 << " (" << operation_char(op.operation) << ")"
 192                 << " nxt=" << op.enriched.next_ip_index
 193                 << " / " << op.enriched.travels_to_ip_index
 194                 << " [vx " << op.enriched.travels_to_vertex_index << "]"
 195                 << std::boolalpha << turns[it->turn_index].discarded
 196                 << std::endl;
 197                 ;
 198         }
 199     }
 200 #endif
 201     // END DEBUG
 202
 203 }
 204
 205 template <typename Operations, typename Turns>
 206 inline void enrich_adapt(Operations& operations, Turns& turns)
 207 {
 208     typedef typename boost::range_value<Turns>::type turn_type;
 209     typedef typename turn_type::turn_operation_type op_type;
 210     typedef typename boost::range_value<Operations>::type indexed_turn_type;
 211
 212     if (operations.size() < 3)
 213     {
 214         // If it is empty, or contains one or two turns, it makes no sense
 215         return;
 216     }
 217
 218     // Operations is a vector of indexed_turn_operation<>
 219
 220     // Last index:
 221     std::size_t const x = operations.size() - 1;
 222     bool next_phase = false;
 223
 224     for (std::size_t i = 0; i < operations.size(); i++)
 225     {
 226         indexed_turn_type const& indexed = operations[i];
 227
 228         turn_type& turn = turns[indexed.turn_index];
 229         op_type& op = turn.operations[indexed.operation_index];
 230
 231         // Previous/next index
 232         std::size_t const p = i > 0 ? i - 1 : x;
 233         std::size_t const n = i < x ? i + 1 : 0;
 234
 235         turn_type const& next_turn = turns[operations[n].turn_index];
 236         op_type const& next_op = next_turn.operations[operations[n].operation_index];
 237
 238         if (op.seg_id.segment_index == next_op.seg_id.segment_index)
 239         {
 240             turn_type const& prev_turn = turns[operations[p].turn_index];
 241             op_type const& prev_op = prev_turn.operations[operations[p].operation_index];
 242             if (op.seg_id.segment_index == prev_op.seg_id.segment_index)
 243             {
 244                 op.enriched.startable = false;
 245                 next_phase = true;
 246             }
 247         }
 248     }
 249
 250     if (! next_phase)
 251     {
 252         return;
 253     }
 254
 255     // Discard turns which are both non-startable
 256     next_phase = false;
 257     for (typename boost::range_iterator<Turns>::type
 258             it = boost::begin(turns);
 259          it != boost::end(turns);
 260          ++it)
 261     {
 262         turn_type& turn = *it;
 263         if (! turn.operations[0].enriched.startable
 264             && ! turn.operations[1].enriched.startable)
 265         {
 266             turn.discarded = true;
 267             next_phase = true;
 268         }
 269     }
 270
 271     if (! next_phase)
 272     {
 273         return;
 274     }
 275
 276     // Remove discarded turns from operations to avoid having them as next turn
 277     discarded_indexed_turn<Turns> const predicate(turns);
 278     operations.erase(std::remove_if(boost::begin(operations),
 279         boost::end(operations), predicate), boost::end(operations));
 280 }
 281
 282 struct enriched_map_default_include_policy
 283 {
 284     template <typename Operation>
 285     static inline bool include(Operation const& )
 286     {
 287         // By default include all operations
 288         return true;
 289     }
 290 };
 291
 292 template <typename Turns, typename MappedVector, typename IncludePolicy>
 293 inline void create_map(Turns const& turns, MappedVector& mapped_vector,
 294                        IncludePolicy const& include_policy)
 295 {
 296     typedef typename boost::range_value<Turns>::type turn_type;
 297     typedef typename turn_type::container_type container_type;
 298     typedef typename MappedVector::mapped_type mapped_type;
 299     typedef typename boost::range_value<mapped_type>::type indexed_type;
 300
 301     std::size_t index = 0;
 302     for (typename boost::range_iterator<Turns const>::type
 303             it = boost::begin(turns);
 304          it != boost::end(turns);
 305          ++it, ++index)
 306     {
 307         // Add all (non discarded) operations on this ring
 308         // Blocked operations or uu on clusters (for intersection)
 309         // should be included, to block potential paths in clusters
 310         turn_type const& turn = *it;
 311         if (turn.discarded)
 312         {
 313             continue;
 314         }
 315
 316         std::size_t op_index = 0;
 317         for (typename boost::range_iterator<container_type const>::type
 318                 op_it = boost::begin(turn.operations);
 319             op_it != boost::end(turn.operations);
 320             ++op_it, ++op_index)
 321         {
 322             if (include_policy.include(op_it->operation))
 323             {
 324                 ring_identifier const ring_id
 325                     (
 326                         op_it->seg_id.source_index,
 327                         op_it->seg_id.multi_index,
 328                         op_it->seg_id.ring_index
 329                     );
 330                 mapped_vector[ring_id].push_back
 331                     (
 332                         indexed_type(index, op_index, *op_it,
 333                             it->operations[1 - op_index].seg_id)
 334                     );
 335             }
 336         }
 337     }
 338 }
 339
 340 template <typename Point1, typename Point2>
 341 inline typename geometry::coordinate_type<Point1>::type
 342         distance_measure(Point1 const& a, Point2 const& b)
 343 {
 344     // TODO: use comparable distance for point-point instead - but that
 345     // causes currently cycling include problems
 346     typedef typename geometry::coordinate_type<Point1>::type ctype;
 347     ctype const dx = get<0>(a) - get<0>(b);
 348     ctype const dy = get<1>(a) - get<1>(b);
 349     return dx * dx + dy * dy;
 350 }
 351
 352 template <typename Turns>
 353 inline void calculate_remaining_distance(Turns& turns)
 354 {
 355     typedef typename boost::range_value<Turns>::type turn_type;
 356     typedef typename turn_type::turn_operation_type op_type;
 357
 358     for (typename boost::range_iterator<Turns>::type
 359             it = boost::begin(turns);
 360          it != boost::end(turns);
 361          ++it)
 362     {
 363         turn_type& turn = *it;
 364
 365         op_type& op0 = turn.operations[0];
 366         op_type& op1 = turn.operations[1];
 367
 368         if (op0.remaining_distance != 0
 369          || op1.remaining_distance != 0)
 370         {
 371             continue;
 372         }
 373
 374         signed_size_type const to_index0 = op0.enriched.get_next_turn_index();
 375         signed_size_type const to_index1 = op1.enriched.get_next_turn_index();
 376         if (to_index0 >= 0
 377                 && to_index1 >= 0
 378                 && to_index0 != to_index1)
 379         {
 380             op0.remaining_distance = distance_measure(turn.point, turns[to_index0].point);
 381             op1.remaining_distance = distance_measure(turn.point, turns[to_index1].point);
 382         }
 383     }
 384 }
 385
 386
 387 }} // namespace detail::overlay
 388 #endif //DOXYGEN_NO_DETAIL
 389
 390
 391
 392 /*!
 393 \brief All intersection points are enriched with successor information
 394 \ingroup overlay
 395 \tparam Turns type of intersection container
 396             (e.g. vector of "intersection/turn point"'s)
 397 \tparam Clusters type of cluster container
 398 \tparam Geometry1 \tparam_geometry
 399 \tparam Geometry2 \tparam_geometry
 400 \tparam PointInGeometryStrategy point in geometry strategy type
 401 \param turns container containing intersection points
 402 \param clusters container containing clusters
 403 \param geometry1 \param_geometry
 404 \param geometry2 \param_geometry
 405 \param robust_policy policy to handle robustness issues
 406 \param strategy point in geometry strategy
 407  */
 408 template
 409 <
 410     bool Reverse1, bool Reverse2,
 411     overlay_type OverlayType,
 412     typename Turns,
 413     typename Clusters,
 414     typename Geometry1, typename Geometry2,
 415     typename RobustPolicy,
 416     typename IntersectionStrategy
 417 >
 418 inline void enrich_intersection_points(Turns& turns,
 419     Clusters& clusters,
 420     Geometry1 const& geometry1, Geometry2 const& geometry2,
 421     RobustPolicy const& robust_policy,
 422     IntersectionStrategy const& strategy)
 423 {
 424     static const detail::overlay::operation_type target_operation
 425             = detail::overlay::operation_from_overlay<OverlayType>::value;
 426     static const detail::overlay::operation_type opposite_operation
 427             = target_operation == detail::overlay::operation_union
 428             ? detail::overlay::operation_intersection
 429             : detail::overlay::operation_union;
 430     static const bool is_dissolve = OverlayType == overlay_dissolve;
 431
 432     typedef typename boost::range_value<Turns>::type turn_type;
 433     typedef typename turn_type::turn_operation_type op_type;
 434     typedef detail::overlay::indexed_turn_operation
 435         <
 436             op_type
 437         > indexed_turn_operation;
 438
 439     typedef std::map
 440         <
 441             ring_identifier,
 442             std::vector<indexed_turn_operation>
 443         > mapped_vector_type;
 444
 445     // From here on, turn indexes are used (in clusters, next_index, etc)
 446     // and may only be flagged as discarded
 447
 448     bool has_cc = false;
 449     bool const has_colocations
 450         = detail::overlay::handle_colocations<Reverse1, Reverse2, OverlayType>(turns,
 451         clusters, geometry1, geometry2);
 452
 453     // Discard turns not part of target overlay
 454     for (typename boost::range_iterator<Turns>::type
 455             it = boost::begin(turns);
 456          it != boost::end(turns);
 457          ++it)
 458     {
 459         turn_type& turn = *it;
 460
 461         if (turn.both(detail::overlay::operation_none)
 462             || turn.both(opposite_operation)
 463             || turn.both(detail::overlay::operation_blocked)
 464             || (detail::overlay::is_self_turn<OverlayType>(turn)
 465                 && ! turn.is_clustered()
 466                 && ! turn.both(target_operation)))
 467         {
 468             // For all operations, discard xx and none/none
 469             // For intersections, remove uu to avoid the need to travel
 470             // a union (during intersection) in uu/cc clusters (e.g. #31,#32,#33)
 471             // The ux is necessary to indicate impossible paths
 472             // (especially if rescaling is removed)
 473
 474             // Similarly, for union, discard ii and ix
 475
 476             // For self-turns, only keep uu / ii
 477
 478             turn.discarded = true;
 479             turn.cluster_id = -1;
 480             continue;
 481         }
 482
 483         if (! turn.discarded
 484             && turn.both(detail::overlay::operation_continue))
 485         {
 486             has_cc = true;
 487         }
 488     }
 489
 490     if (! is_dissolve)
 491     {
 492         detail::overlay::discard_closed_turns
 493             <
 494                 OverlayType,
 495                 target_operation
 496             >::apply(turns, clusters, geometry1, geometry2,
 497                      strategy);
 498         detail::overlay::discard_open_turns
 499             <
 500                 OverlayType,
 501                 target_operation
 502             >::apply(turns, clusters, geometry1, geometry2,
 503                      strategy);
 504     }
 505
 506     // Create a map of vectors of indexed operation-types to be able
 507     // to sort intersection points PER RING
 508     mapped_vector_type mapped_vector;
 509
 510     detail::overlay::create_map(turns, mapped_vector,
 511                                 detail::overlay::enriched_map_default_include_policy());
 512
 513     // No const-iterator; contents of mapped copy is temporary,
 514     // and changed by enrich
 515     for (typename mapped_vector_type::iterator mit
 516         = mapped_vector.begin();
 517         mit != mapped_vector.end();
 518         ++mit)
 519     {
 520 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
 521     std::cout << "ENRICH-sort Ring "
 522         << mit->first << std::endl;
 523 #endif
 524         detail::overlay::enrich_sort<Reverse1, Reverse2>(
 525                     mit->second, turns,
 526                     geometry1, geometry2,
 527                     robust_policy, strategy.get_side_strategy());
 528     }
 529
 530     for (typename mapped_vector_type::iterator mit
 531         = mapped_vector.begin();
 532         mit != mapped_vector.end();
 533         ++mit)
 534     {
 535 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
 536     std::cout << "ENRICH-assign Ring "
 537         << mit->first << std::endl;
 538 #endif
 539         if (is_dissolve)
 540         {
 541             detail::overlay::enrich_adapt(mit->second, turns);
 542         }
 543
 544         detail::overlay::enrich_assign(mit->second, turns, ! is_dissolve);
 545     }
 546
 547     if (has_colocations)
 548     {
 549         // First gather cluster properties (using even clusters with
 550         // discarded turns - for open turns), then clean up clusters
 551         detail::overlay::gather_cluster_properties
 552             <
 553                 Reverse1,
 554                 Reverse2,
 555                 OverlayType
 556             >(clusters, turns, target_operation,
 557               geometry1, geometry2, strategy.get_side_strategy());
 558
 559         detail::overlay::cleanup_clusters(turns, clusters);
 560     }
 561
 562     if (has_cc)
 563     {
 564         detail::overlay::calculate_remaining_distance(turns);
 565     }
 566
 567 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
 568     //detail::overlay::check_graph(turns, for_operation);
 569 #endif
 570
 571 }
 572
 573 }} // namespace boost::geometry
 574
 575 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP