ceph/src/boost/libs/geometry/include/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 // 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_ENRICH_HPP
  10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP
  11
  12 #include <cstddef>
  13 #include <algorithm>
  14 #include <map>
  15 #include <set>
  16 #include <vector>
  17
  18 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
  19 #  include <iostream>
  20 #  include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
  21 #  include <boost/geometry/io/wkt/wkt.hpp>
  22 #  define BOOST_GEOMETRY_DEBUG_IDENTIFIER
  23 #endif
  24
  25 #include <boost/range.hpp>
  26
  27 #include <boost/geometry/iterators/ever_circling_iterator.hpp>
  28 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
  29 #include <boost/geometry/algorithms/detail/overlay/copy_segment_point.hpp>
  30 #include <boost/geometry/algorithms/detail/overlay/handle_colocations.hpp>
  31 #include <boost/geometry/algorithms/detail/overlay/less_by_segment_ratio.hpp>
  32 #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
  33 #include <boost/geometry/algorithms/detail/overlay/sort_by_side.hpp>
  34 #include <boost/geometry/policies/robustness/robust_type.hpp>
  35 #include <boost/geometry/strategies/side.hpp>
  36 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
  37 #  include <boost/geometry/algorithms/detail/overlay/check_enrich.hpp>
  38 #endif
  39
  40
  41 namespace boost { namespace geometry
  42 {
  43
  44 #ifndef DOXYGEN_NO_DETAIL
  45 namespace detail { namespace overlay
  46 {
  47
  48
  49 // Sorts IP-s of this ring on segment-identifier, and if on same segment,
  50 //  on distance.
  51 // Then assigns for each IP which is the next IP on this segment,
  52 // plus the vertex-index to travel to, plus the next IP
  53 // (might be on another segment)
  54 template
  55 <
  56     bool Reverse1, bool Reverse2,
  57     typename Operations,
  58     typename Turns,
  59     typename Geometry1, typename Geometry2,
  60     typename RobustPolicy,
  61     typename Strategy
  62 >
  63 inline void enrich_sort(Operations& operations,
  64             Turns const& turns,
  65             operation_type for_operation,
  66             Geometry1 const& geometry1,
  67             Geometry2 const& geometry2,
  68             RobustPolicy const& robust_policy,
  69             Strategy const& /*strategy*/)
  70 {
  71     std::sort(boost::begin(operations),
  72             boost::end(operations),
  73             less_by_segment_ratio
  74                 <
  75                     Turns,
  76                     typename boost::range_value<Operations>::type,
  77                     Geometry1, Geometry2,
  78                     RobustPolicy,
  79                     Reverse1, Reverse2
  80                 >(turns, for_operation, geometry1, geometry2, robust_policy));
  81 }
  82
  83
  84 template <typename Operations, typename Turns>
  85 inline void enrich_assign(Operations& operations, Turns& turns)
  86 {
  87     typedef typename boost::range_value<Turns>::type turn_type;
  88     typedef typename turn_type::turn_operation_type op_type;
  89     typedef typename boost::range_iterator<Operations>::type iterator_type;
  90
  91
  92     if (operations.size() > 0)
  93     {
  94         // Assign travel-to-vertex/ip index for each turning point.
  95         // Iterator "next" is circular
  96
  97         geometry::ever_circling_range_iterator<Operations const> next(operations);
  98         ++next;
  99
 100         for (iterator_type it = boost::begin(operations);
 101              it != boost::end(operations); ++it)
 102         {
 103             turn_type& turn = turns[it->turn_index];
 104             op_type& op = turn.operations[it->operation_index];
 105
 106             // Normal behaviour: next should point at next turn:
 107             if (it->turn_index == next->turn_index)
 108             {
 109                 ++next;
 110             }
 111
 112             // Cluster behaviour: next should point after cluster, unless
 113             // their seg_ids are not the same
 114             while (turn.cluster_id != -1
 115                    && it->turn_index != next->turn_index
 116                    && turn.cluster_id == turns[next->turn_index].cluster_id
 117                    && op.seg_id == turns[next->turn_index].operations[next->operation_index].seg_id)
 118             {
 119                 ++next;
 120             }
 121
 122             turn_type const& next_turn = turns[next->turn_index];
 123             op_type const& next_op = next_turn.operations[next->operation_index];
 124
 125             op.enriched.travels_to_ip_index
 126                     = static_cast<signed_size_type>(next->turn_index);
 127             op.enriched.travels_to_vertex_index
 128                     = next->subject->seg_id.segment_index;
 129
 130             if (op.seg_id.segment_index == next_op.seg_id.segment_index
 131                     && op.fraction < next_op.fraction)
 132             {
 133                 // Next turn is located further on same segment
 134                 // assign next_ip_index
 135                 // (this is one not circular therefore fraction is considered)
 136                 op.enriched.next_ip_index = static_cast<signed_size_type>(next->turn_index);
 137             }
 138         }
 139     }
 140
 141     // DEBUG
 142 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
 143     {
 144         for (iterator_type it = boost::begin(operations);
 145              it != boost::end(operations);
 146              ++it)
 147         {
 148             op_type& op = turns[it->turn_index]
 149                 .operations[it->operation_index];
 150
 151             std::cout << it->turn_index
 152                 << " cl=" << turns[it->turn_index].cluster_id
 153                 << " meth=" << method_char(turns[it->turn_index].method)
 154                 << " seg=" << op.seg_id
 155                 << " dst=" << op.fraction // needs define
 156                 << " op=" << operation_char(turns[it->turn_index].operations[0].operation)
 157                 << operation_char(turns[it->turn_index].operations[1].operation)
 158                 << " (" << operation_char(op.operation) << ")"
 159                 << " nxt=" << op.enriched.next_ip_index
 160                 << " / " << op.enriched.travels_to_ip_index
 161                 << " [vx " << op.enriched.travels_to_vertex_index << "]"
 162                 << std::boolalpha << turns[it->turn_index].discarded
 163                 << std::endl;
 164                 ;
 165         }
 166     }
 167 #endif
 168     // END DEBUG
 169
 170 }
 171
 172
 173 template <typename Turns, typename MappedVector>
 174 inline void create_map(Turns const& turns,
 175         detail::overlay::operation_type for_operation,
 176         MappedVector& mapped_vector)
 177 {
 178     typedef typename boost::range_value<Turns>::type turn_type;
 179     typedef typename turn_type::container_type container_type;
 180     typedef typename MappedVector::mapped_type mapped_type;
 181     typedef typename boost::range_value<mapped_type>::type indexed_type;
 182
 183     std::size_t index = 0;
 184     for (typename boost::range_iterator<Turns const>::type
 185             it = boost::begin(turns);
 186          it != boost::end(turns);
 187          ++it, ++index)
 188     {
 189         // Add all (non discarded) operations on this ring
 190         // Blocked operations or uu on clusters (for intersection)
 191         // should be included, to block potential paths in clusters
 192         turn_type const& turn = *it;
 193         if (turn.discarded)
 194         {
 195             continue;
 196         }
 197
 198         if (for_operation == operation_intersection
 199             && turn.cluster_id == -1
 200             && turn.both(operation_union))
 201         {
 202             // Only include uu turns if part of cluster (to block potential paths),
 203             // otherwise they can block possibly viable paths
 204             continue;
 205         }
 206
 207         std::size_t op_index = 0;
 208         for (typename boost::range_iterator<container_type const>::type
 209                 op_it = boost::begin(turn.operations);
 210             op_it != boost::end(turn.operations);
 211             ++op_it, ++op_index)
 212         {
 213             ring_identifier const ring_id
 214                 (
 215                     op_it->seg_id.source_index,
 216                     op_it->seg_id.multi_index,
 217                     op_it->seg_id.ring_index
 218                 );
 219             mapped_vector[ring_id].push_back
 220                 (
 221                     indexed_type(index, op_index, *op_it,
 222                         it->operations[1 - op_index].seg_id)
 223                 );
 224         }
 225     }
 226 }
 227
 228
 229 }} // namespace detail::overlay
 230 #endif //DOXYGEN_NO_DETAIL
 231
 232
 233
 234 /*!
 235 \brief All intersection points are enriched with successor information
 236 \ingroup overlay
 237 \tparam Turns type of intersection container
 238             (e.g. vector of "intersection/turn point"'s)
 239 \tparam Clusters type of cluster container
 240 \tparam Geometry1 \tparam_geometry
 241 \tparam Geometry2 \tparam_geometry
 242 \tparam Strategy side strategy type
 243 \param turns container containing intersection points
 244 \param clusters container containing clusters
 245 \param geometry1 \param_geometry
 246 \param geometry2 \param_geometry
 247 \param robust_policy policy to handle robustness issues
 248 \param strategy strategy
 249  */
 250 template
 251 <
 252     bool Reverse1, bool Reverse2,
 253     overlay_type OverlayType,
 254     typename Turns,
 255     typename Clusters,
 256     typename Geometry1, typename Geometry2,
 257     typename RobustPolicy,
 258     typename Strategy
 259 >
 260 inline void enrich_intersection_points(Turns& turns,
 261     Clusters& clusters,
 262     Geometry1 const& geometry1, Geometry2 const& geometry2,
 263     RobustPolicy const& robust_policy,
 264     Strategy const& strategy)
 265 {
 266     static const detail::overlay::operation_type for_operation
 267             = detail::overlay::operation_from_overlay<OverlayType>::value;
 268     typedef typename boost::range_value<Turns>::type turn_type;
 269     typedef typename turn_type::turn_operation_type op_type;
 270     typedef detail::overlay::indexed_turn_operation
 271         <
 272             op_type
 273         > indexed_turn_operation;
 274
 275     typedef std::map
 276         <
 277             ring_identifier,
 278             std::vector<indexed_turn_operation>
 279         > mapped_vector_type;
 280
 281     bool const has_colocations
 282         = detail::overlay::handle_colocations<Reverse1, Reverse2>(turns,
 283         clusters, geometry1, geometry2);
 284
 285     // Discard none turns, if any
 286     for (typename boost::range_iterator<Turns>::type
 287             it = boost::begin(turns);
 288          it != boost::end(turns);
 289          ++it)
 290     {
 291         if (it->both(detail::overlay::operation_none))
 292         {
 293             it->discarded = true;
 294         }
 295     }
 296
 297     // Create a map of vectors of indexed operation-types to be able
 298     // to sort intersection points PER RING
 299     mapped_vector_type mapped_vector;
 300
 301     detail::overlay::create_map(turns, for_operation, mapped_vector);
 302
 303     // No const-iterator; contents of mapped copy is temporary,
 304     // and changed by enrich
 305     for (typename mapped_vector_type::iterator mit
 306         = mapped_vector.begin();
 307         mit != mapped_vector.end();
 308         ++mit)
 309     {
 310 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
 311     std::cout << "ENRICH-sort Ring "
 312         << mit->first << std::endl;
 313 #endif
 314         detail::overlay::enrich_sort<Reverse1, Reverse2>(
 315                     mit->second, turns, for_operation,
 316                     geometry1, geometry2,
 317                     robust_policy, strategy);
 318     }
 319
 320     for (typename mapped_vector_type::iterator mit
 321         = mapped_vector.begin();
 322         mit != mapped_vector.end();
 323         ++mit)
 324     {
 325 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
 326     std::cout << "ENRICH-assign Ring "
 327         << mit->first << std::endl;
 328 #endif
 329         detail::overlay::enrich_assign(mit->second, turns);
 330     }
 331
 332     if (has_colocations)
 333     {
 334         detail::overlay::gather_cluster_properties<Reverse1, Reverse2>(
 335                 clusters, turns, for_operation, geometry1, geometry2);
 336     }
 337
 338 #ifdef BOOST_GEOMETRY_DEBUG_ENRICH
 339     //detail::overlay::check_graph(turns, for_operation);
 340 #endif
 341
 342 }
 343
 344 }} // namespace boost::geometry
 345
 346 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_ENRICH_HPP