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