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
   5 // This file was modified by Oracle on 2017.
   6 // Modifications copyright (c) 2017 Oracle and/or its affiliates.
   7
   8 // Contributed and/or modified by Adam Wulkiewicz, 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_ENRICH_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP
  16
  17 #include <cstddef>
  18 #include <algorithm>
  19 #include <map>
  20 #include <set>
  21 #include <vector>
  22
  23 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
  24 #  include <iostream>
  25 #  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
  26 #  include <boost/geometry/io/wkt/wkt.hpp>
  27 #  if ! defined(BOOST_GEOMETRY_DEBUG_IDENTIFIER)
  28 #    define BOOST_GEOMETRY_DEBUG_IDENTIFIER
  29   #endif
  30 #endif
  31
  32 #include <boost/range.hpp>
  33
  34 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
  35 #include <boost/geometry/algorithms/detail/overlay/handle_colocations.hpp>
  36 #include <boost/geometry/algorithms/detail/overlay/handle_self_turns.hpp>
  37 #include <boost/geometry/algorithms/detail/overlay/is_self_turn.hpp>
  38 #include <boost/geometry/algorithms/detail/overlay/less_by_segment_ratio.hpp>
  39 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
  40 #include <boost/geometry/policies/robustness/robust_type.hpp>
  41
  42 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
  43 #  include <boost/geometry/algorithms/detail/overlay/check_enrich.hpp>
  44 #endif
  45
  46
  47 namespace boost { namespace geometry
  48 {
  49
  50 #ifndef DOXYGEN_NO_DETAIL
  51 namespace detail { namespace overlay
  52 {
  53
  54
  55 // Sorts IP-s of this ring on segment-identifier, and if on same segment,
  56 //  on distance.
  57 // Then assigns for each IP which is the next IP on this segment,
  58 // plus the vertex-index to travel to, plus the next IP
  59 // (might be on another segment)
  60 template
  61 <
  62     bool Reverse1, bool Reverse2,
  63     typename Operations,
  64     typename Turns,
  65     typename Geometry1, typename Geometry2,
  66     typename RobustPolicy,
  67     typename SideStrategy
  68 >
  69 inline void enrich_sort(Operations& operations,
  70             Turns const& turns,
  71             operation_type for_operation,
  72             Geometry1 const& geometry1,
  73             Geometry2 const& geometry2,
  74             RobustPolicy const& robust_policy,
  75             SideStrategy const& strategy)
  76 {
  77     std::sort(boost::begin(operations),
  78             boost::end(operations),
  79             less_by_segment_ratio
  80                 <
  81                     Turns,
  82                     typename boost::range_value<Operations>::type,
  83                     Geometry1, Geometry2,
  84                     RobustPolicy,
  85                     SideStrategy,
  86                     Reverse1, Reverse2
  87                 >(turns, for_operation, geometry1, geometry2, robust_policy, strategy));
  88 }
  89
  90
  91 template <typename Operations, typename Turns>
  92 inline void enrich_assign(Operations& operations, Turns& turns)
  93 {
  94     typedef typename boost::range_value<Turns>::type turn_type;
  95     typedef typename turn_type::turn_operation_type op_type;
  96     typedef typename boost::range_iterator<Operations>::type iterator_type;
  97
  98
  99     if (operations.size() > 0)
 100     {
 101         // Assign travel-to-vertex/ip index for each turning point.
 102         // Iterator "next" is circular
 103
 104         geometry::ever_circling_range_iterator<Operations const> next(operations);
 105         ++next;
 106
 107         for (iterator_type it = boost::begin(operations);
 108              it != boost::end(operations); ++it)
 109         {
 110             turn_type& turn = turns[it->turn_index];
 111             op_type& op = turn.operations[it->operation_index];
 112
 113             // Normal behaviour: next should point at next turn:
 114             if (it->turn_index == next->turn_index)
 115             {
 116                 ++next;
 117             }
 118
 119             // Cluster behaviour: next should point after cluster, unless
 120             // their seg_ids are not the same
 121             while (turn.is_clustered()
 122                    && it->turn_index != next->turn_index
 123                    && turn.cluster_id == turns[next->turn_index].cluster_id
 124                    && op.seg_id == turns[next->turn_index].operations[next->operation_index].seg_id)
 125             {
 126                 ++next;
 127             }
 128
 129             turn_type const& next_turn = turns[next->turn_index];
 130             op_type const& next_op = next_turn.operations[next->operation_index];
 131
 132             op.enriched.travels_to_ip_index
 133                     = static_cast<signed_size_type>(next->turn_index);
 134             op.enriched.travels_to_vertex_index
 135                     = next->subject->seg_id.segment_index;
 136
 137             if (op.seg_id.segment_index == next_op.seg_id.segment_index
 138                     && op.fraction < next_op.fraction)
 139             {
 140                 // Next turn is located further on same segment
 141                 // assign next_ip_index
 142                 // (this is one not circular therefore fraction is considered)
 143                 op.enriched.next_ip_index = static_cast<signed_size_type>(next->turn_index);
 144             }
 145         }
 146     }
 147
 148     // DEBUG
 149 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
 150     {
 151         for (iterator_type it = boost::begin(operations);
 152              it != boost::end(operations);
 153              ++it)
 154         {
 155             op_type const& op = turns[it->turn_index]
 156                 .operations[it->operation_index];
 157
 158             std::cout << it->turn_index
 159                 << " cl=" << turns[it->turn_index].cluster_id
 160                 << " meth=" << method_char(turns[it->turn_index].method)
 161                 << " seg=" << op.seg_id
 162                 << " dst=" << op.fraction // needs define
 163                 << " op=" << operation_char(turns[it->turn_index].operations[0].operation)
 164                 << operation_char(turns[it->turn_index].operations[1].operation)
 165                 << " (" << operation_char(op.operation) << ")"
 166                 << " nxt=" << op.enriched.next_ip_index
 167                 << " / " << op.enriched.travels_to_ip_index
 168                 << " [vx " << op.enriched.travels_to_vertex_index << "]"
 169                 << std::boolalpha << turns[it->turn_index].discarded
 170                 << std::endl;
 171                 ;
 172         }
 173     }
 174 #endif
 175     // END DEBUG
 176
 177 }
 178
 179
 180 template <typename Turns, typename MappedVector>
 181 inline void create_map(Turns const& turns, MappedVector& mapped_vector)
 182 {
 183     typedef typename boost::range_value<Turns>::type turn_type;
 184     typedef typename turn_type::container_type container_type;
 185     typedef typename MappedVector::mapped_type mapped_type;
 186     typedef typename boost::range_value<mapped_type>::type indexed_type;
 187
 188     std::size_t index = 0;
 189     for (typename boost::range_iterator<Turns const>::type
 190             it = boost::begin(turns);
 191          it != boost::end(turns);
 192          ++it, ++index)
 193     {
 194         // Add all (non discarded) operations on this ring
 195         // Blocked operations or uu on clusters (for intersection)
 196         // should be included, to block potential paths in clusters
 197         turn_type const& turn = *it;
 198         if (turn.discarded)
 199         {
 200             continue;
 201         }
 202
 203         std::size_t op_index = 0;
 204         for (typename boost::range_iterator<container_type const>::type
 205                 op_it = boost::begin(turn.operations);
 206             op_it != boost::end(turn.operations);
 207             ++op_it, ++op_index)
 208         {
 209             ring_identifier const ring_id
 210                 (
 211                     op_it->seg_id.source_index,
 212                     op_it->seg_id.multi_index,
 213                     op_it->seg_id.ring_index
 214                 );
 215             mapped_vector[ring_id].push_back
 216                 (
 217                     indexed_type(index, op_index, *op_it,
 218                         it->operations[1 - op_index].seg_id)
 219                 );
 220         }
 221     }
 222 }
 223
 224 template <typename Point1, typename Point2>
 225 inline typename geometry::coordinate_type<Point1>::type
 226         distance_measure(Point1 const& a, Point2 const& b)
 227 {
 228     // TODO: use comparable distance for point-point instead - but that
 229     // causes currently cycling include problems
 230     typedef typename geometry::coordinate_type<Point1>::type ctype;
 231     ctype const dx = get<0>(a) - get<0>(b);
 232     ctype const dy = get<1>(a) - get<1>(b);
 233     return dx * dx + dy * dy;
 234 }
 235
 236 template <typename Turns>
 237 inline void calculate_remaining_distance(Turns& turns)
 238 {
 239     typedef typename boost::range_value<Turns>::type turn_type;
 240     typedef typename turn_type::turn_operation_type op_type;
 241
 242     for (typename boost::range_iterator<Turns>::type
 243             it = boost::begin(turns);
 244          it != boost::end(turns);
 245          ++it)
 246     {
 247         turn_type& turn = *it;
 248
 249         op_type& op0 = turn.operations[0];
 250         op_type& op1 = turn.operations[1];
 251
 252         if (op0.remaining_distance != 0
 253          || op1.remaining_distance != 0)
 254         {
 255             continue;
 256         }
 257
 258         int const to_index0 = op0.enriched.get_next_turn_index();
 259         int const to_index1 = op1.enriched.get_next_turn_index();
 260         if (to_index0 >= 0
 261                 && to_index1 >= 0
 262                 && to_index0 != to_index1)
 263         {
 264             op0.remaining_distance = distance_measure(turn.point, turns[to_index0].point);
 265             op1.remaining_distance = distance_measure(turn.point, turns[to_index1].point);
 266         }
 267     }
 268 }
 269
 270
 271 }} // namespace detail::overlay
 272 #endif //DOXYGEN_NO_DETAIL
 273
 274
 275
 276 /*!
 277 \brief All intersection points are enriched with successor information
 278 \ingroup overlay
 279 \tparam Turns type of intersection container
 280             (e.g. vector of "intersection/turn point"'s)
 281 \tparam Clusters type of cluster container
 282 \tparam Geometry1 \tparam_geometry
 283 \tparam Geometry2 \tparam_geometry
 284 \tparam SideStrategy side strategy type
 285 \param turns container containing intersection points
 286 \param clusters container containing clusters
 287 \param geometry1 \param_geometry
 288 \param geometry2 \param_geometry
 289 \param robust_policy policy to handle robustness issues
 290 \param strategy strategy
 291  */
 292 template
 293 <
 294     bool Reverse1, bool Reverse2,
 295     overlay_type OverlayType,
 296     typename Turns,
 297     typename Clusters,
 298     typename Geometry1, typename Geometry2,
 299     typename RobustPolicy,
 300     typename SideStrategy
 301 >
 302 inline void enrich_intersection_points(Turns& turns,
 303     Clusters& clusters,
 304     Geometry1 const& geometry1, Geometry2 const& geometry2,
 305     RobustPolicy const& robust_policy,
 306     SideStrategy const& strategy)
 307 {
 308     static const detail::overlay::operation_type target_operation
 309             = detail::overlay::operation_from_overlay<OverlayType>::value;
 310     static const detail::overlay::operation_type opposite_operation
 311             = target_operation == detail::overlay::operation_union
 312             ? detail::overlay::operation_intersection
 313             : detail::overlay::operation_union;
 314
 315     typedef typename boost::range_value<Turns>::type turn_type;
 316     typedef typename turn_type::turn_operation_type op_type;
 317     typedef detail::overlay::indexed_turn_operation
 318         <
 319             op_type
 320         > indexed_turn_operation;
 321
 322     typedef std::map
 323         <
 324             ring_identifier,
 325             std::vector<indexed_turn_operation>
 326         > mapped_vector_type;
 327
 328     bool has_cc = false;
 329     bool const has_colocations
 330         = detail::overlay::handle_colocations<Reverse1, Reverse2, OverlayType>(turns,
 331         clusters, geometry1, geometry2);
 332
 333     // Discard turns not part of target overlay
 334     for (typename boost::range_iterator<Turns>::type
 335             it = boost::begin(turns);
 336          it != boost::end(turns);
 337          ++it)
 338     {
 339         turn_type& turn = *it;
 340
 341         if (turn.both(detail::overlay::operation_none))
 342         {
 343             turn.discarded = true;
 344             continue;
 345         }
 346
 347         if (turn.both(opposite_operation))
 348         {
 349             // For intersections, remove uu to avoid the need to travel
 350             // a union (during intersection) in uu/cc clusters (e.g. #31,#32,#33)
 351             // Also, for union, discard ii
 352             turn.discarded = true;
 353             turn.cluster_id = -1;
 354             continue;
 355         }
 356
 357         if (detail::overlay::is_self_turn<OverlayType>(turn)
 358             && ! turn.is_clustered()
 359             && ! turn.both(target_operation))
 360         {
 361             // Only keep self-uu-turns or self-ii-turns
 362            turn.discarded = true;
 363            continue;
 364         }
 365
 366         if (! turn.discarded
 367             && turn.both(detail::overlay::operation_continue))
 368         {
 369             has_cc = true;
 370         }
 371     }
 372
 373     detail::overlay::discard_closed_turns
 374         <
 375             OverlayType,
 376             target_operation
 377         >::apply(turns, clusters, geometry1, geometry2);
 378     detail::overlay::discard_open_turns
 379         <
 380             OverlayType,
 381             target_operation
 382         >::apply(turns, clusters, geometry1, geometry2);
 383
 384     // Create a map of vectors of indexed operation-types to be able
 385     // to sort intersection points PER RING
 386     mapped_vector_type mapped_vector;
 387
 388     detail::overlay::create_map(turns, mapped_vector);
 389
 390     // No const-iterator; contents of mapped copy is temporary,
 391     // and changed by enrich
 392     for (typename mapped_vector_type::iterator mit
 393         = mapped_vector.begin();
 394         mit != mapped_vector.end();
 395         ++mit)
 396     {
 397 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
 398     std::cout << "ENRICH-sort Ring "
 399         << mit->first << std::endl;
 400 #endif
 401         detail::overlay::enrich_sort<Reverse1, Reverse2>(
 402                     mit->second, turns, target_operation,
 403                     geometry1, geometry2,
 404                     robust_policy, strategy);
 405     }
 406
 407     for (typename mapped_vector_type::iterator mit
 408         = mapped_vector.begin();
 409         mit != mapped_vector.end();
 410         ++mit)
 411     {
 412 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
 413     std::cout << "ENRICH-assign Ring "
 414         << mit->first << std::endl;
 415 #endif
 416         detail::overlay::enrich_assign(mit->second, turns);
 417     }
 418
 419     // Check some specific type of self-turns (after getting enriched info)
 420     detail::overlay::discard_self_turns_which_loop<OverlayType>(turns);
 421
 422     if (has_colocations)
 423     {
 424         // First gather cluster properties (using even clusters with
 425         // discarded turns - for open turns), then clean up clusters
 426         detail::overlay::gather_cluster_properties
 427             <
 428                 Reverse1,
 429                 Reverse2,
 430                 OverlayType
 431             >(clusters, turns, target_operation,
 432               geometry1, geometry2, strategy);
 433
 434         detail::overlay::cleanup_clusters(turns, clusters);
 435     }
 436
 437     if (has_cc)
 438     {
 439         detail::overlay::calculate_remaining_distance(turns);
 440     }
 441
 442 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
 443     //detail::overlay::check_graph(turns, for_operation);
 444 #endif
 445
 446 }
 447
 448 }} // namespace boost::geometry
 449
 450 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP