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

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2015-2016 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_SWITCH_DETECTOR_HPP
  10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_SWITCH_DETECTOR_HPP
  11
  12 #include <cstddef>
  13
  14 #include <boost/range.hpp>
  15
  16 #include <boost/geometry/algorithms/detail/ring_identifier.hpp>
  17 #include <boost/geometry/algorithms/detail/overlay/copy_segments.hpp>
  18 #include <boost/geometry/algorithms/detail/overlay/cluster_info.hpp>
  19 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
  20 #include <boost/geometry/core/access.hpp>
  21 #include <boost/geometry/core/assert.hpp>
  22
  23 namespace boost { namespace geometry
  24 {
  25
  26 #ifndef DOXYGEN_NO_DETAIL
  27 namespace detail { namespace overlay
  28 {
  29
  30 // Generic function (is this used somewhere else too?)
  31 inline ring_identifier ring_id_by_seg_id(segment_identifier const& seg_id)
  32 {
  33     return ring_identifier(seg_id.source_index, seg_id.multi_index, seg_id.ring_index);
  34 }
  35
  36 template
  37 <
  38     bool Reverse1,
  39     bool Reverse2,
  40     overlay_type OverlayType,
  41     typename Geometry1,
  42     typename Geometry2,
  43     typename Turns,
  44     typename Clusters,
  45     typename RobustPolicy,
  46     typename Visitor
  47 >
  48 struct traversal_switch_detector
  49 {
  50     typedef typename boost::range_value<Turns>::type turn_type;
  51     typedef typename turn_type::turn_operation_type turn_operation_type;
  52
  53     // For convenience
  54     typedef std::set<signed_size_type>::const_iterator set_iterator;
  55
  56     inline traversal_switch_detector(Geometry1 const& geometry1, Geometry2 const& geometry2,
  57             Turns& turns, Clusters& clusters,
  58             RobustPolicy const& robust_policy, Visitor& visitor)
  59         : m_geometry1(geometry1)
  60         , m_geometry2(geometry2)
  61         , m_turns(turns)
  62         , m_clusters(clusters)
  63         , m_robust_policy(robust_policy)
  64         , m_visitor(visitor)
  65         , m_region_id(0)
  66     {
  67
  68     }
  69
  70     static inline bool connects_same_zone(turn_type const& turn)
  71     {
  72         if (turn.cluster_id == -1)
  73         {
  74             // If it is a uu-turn (non clustered), it is never same zone
  75             return ! turn.both(operation_union);
  76         }
  77
  78         // It is a cluster, check zones of both operations
  79         return turn.operations[0].enriched.zone
  80                 == turn.operations[1].enriched.zone;
  81     }
  82
  83     inline int get_region_id(turn_operation_type const& op) const
  84     {
  85         std::map<ring_identifier, int>::const_iterator it
  86                     = m_regions.find(ring_id_by_seg_id(op.seg_id));
  87         return it == m_regions.end() ? -1 : it->second;
  88     }
  89
  90     void create_region(ring_identifier const& ring_id, std::set<signed_size_type> const& ring_turn_indices, int region_id = -1)
  91     {
  92         std::map<ring_identifier, int>::const_iterator it = m_regions.find(ring_id);
  93         if (it != m_regions.end())
  94         {
  95             // The ring is already gathered in a region, quit
  96             return;
  97         }
  98         if (region_id == -1)
  99         {
 100             region_id = m_region_id++;
 101         }
 102
 103         // Assign this ring to specified region
 104         m_regions[ring_id] = region_id;
 105 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
 106         std::cout << " ADD " << ring_id << "  TO REGION " << region_id << std::endl;
 107 #endif
 108
 109         // Find connecting rings, recursively
 110         for (set_iterator sit = ring_turn_indices.begin();
 111              sit != ring_turn_indices.end(); ++sit)
 112         {
 113             int const turn_index = *sit;
 114             turn_type const& turn = m_turns[turn_index];
 115             if (! connects_same_zone(turn))
 116             {
 117                 // This is a non clustered uu-turn, or a cluster connecting different 'zones'
 118                 continue;
 119             }
 120
 121             // This turn connects two rings (interior connected), create the
 122             // same region
 123             for (int op_index = 0; op_index < 2; op_index++)
 124             {
 125                 turn_operation_type const& op = turn.operations[op_index];
 126                 ring_identifier connected_ring_id = ring_id_by_seg_id(op.seg_id);
 127                 if (connected_ring_id != ring_id)
 128                 {
 129                     propagate_region(connected_ring_id, region_id);
 130                 }
 131             }
 132         }
 133     }
 134
 135     void propagate_region(ring_identifier const& ring_id, int region_id)
 136     {
 137         std::map<ring_identifier, std::set<signed_size_type> >::const_iterator it = m_turns_per_ring.find(ring_id);
 138         if (it != m_turns_per_ring.end())
 139         {
 140             create_region(ring_id, it->second, region_id);
 141         }
 142     }
 143
 144     void iterate()
 145     {
 146 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
 147         std::cout << "SWITCH BEGIN ITERATION" << std::endl;
 148 #endif
 149
 150         // Collect turns per ring
 151         m_turns_per_ring.clear();
 152         m_regions.clear();
 153         m_region_id = 1;
 154
 155         for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
 156         {
 157             turn_type const& turn = m_turns[turn_index];
 158
 159             for (int op_index = 0; op_index < 2; op_index++)
 160             {
 161                 turn_operation_type const& op = turn.operations[op_index];
 162                 m_turns_per_ring[ring_id_by_seg_id(op.seg_id)].insert(turn_index);
 163             }
 164         }
 165
 166         // All rings having turns are in the map. Now iterate them
 167         for (std::map<ring_identifier, std::set<signed_size_type> >::const_iterator it
 168              = m_turns_per_ring.begin(); it != m_turns_per_ring.end(); ++it)
 169         {
 170             create_region(it->first, it->second);
 171         }
 172
 173         // Now that all regions are filled, assign switch_source property
 174         // Iterate through all clusters
 175         for (typename Clusters::iterator it = m_clusters.begin(); it != m_clusters.end(); ++it)
 176         {
 177             cluster_info& cinfo = it->second;
 178             if (cinfo.open_count <= 1)
 179             {
 180                 // Not a touching cluster
 181                 continue;
 182             }
 183
 184             // A touching cluster, gather regions
 185             std::set<int> regions;
 186
 187             std::set<signed_size_type> const& ids = cinfo.turn_indices;
 188
 189 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
 190                 std::cout << "SWITCH EXAMINE CLUSTER " << it->first << std::endl;
 191 #endif
 192
 193             for (set_iterator sit = ids.begin(); sit != ids.end(); ++sit)
 194             {
 195                 signed_size_type turn_index = *sit;
 196                 turn_type const& turn = m_turns[turn_index];
 197                 for (int oi = 0; oi < 2; oi++)
 198                 {
 199                     int const region = get_region_id(turn.operations[oi]);
 200                     regions.insert(region);
 201                 }
 202             }
 203             // Switch source if this cluster connects the same region
 204             cinfo.switch_source = regions.size() == 1;
 205         }
 206
 207         // Iterate through all uu turns (non-clustered)
 208         for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
 209         {
 210             turn_type& turn = m_turns[turn_index];
 211
 212             if (turn.discarded
 213                     || turn.blocked()
 214                     || turn.cluster_id >= 0
 215                     || ! turn.both(operation_union))
 216             {
 217                 // Skip discarded, blocked, non-uu and clustered turns
 218                 continue;
 219             }
 220
 221             if (OverlayType == overlay_buffer)
 222             {
 223                 // For deflate, the region approach does not work because many
 224                 // pieces are outside the real polygons
 225                 // TODO: implement this in another way for buffer
 226                 // (because now buffer might output invalid geometries)
 227                 continue;
 228             }
 229
 230             int const region0 = get_region_id(turn.operations[0]);
 231             int const region1 = get_region_id(turn.operations[1]);
 232
 233             // Switch sources for same region
 234             turn.switch_source = region0 == region1;
 235         }
 236
 237
 238 #if defined(BOOST_GEOMETRY_DEBUG_TRAVERSAL_SWITCH_DETECTOR)
 239         std::cout << "SWITCH END ITERATION" << std::endl;
 240
 241         for (std::size_t turn_index = 0; turn_index < m_turns.size(); ++turn_index)
 242         {
 243             turn_type const& turn = m_turns[turn_index];
 244
 245             if (turn.both(operation_union) && turn.cluster_id < 0)
 246             {
 247                 std::cout << "UU SWITCH RESULT "
 248                              << turn_index << " -> "
 249                           << turn.switch_source << std::endl;
 250             }
 251         }
 252
 253         for (typename Clusters::const_iterator it = m_clusters.begin(); it != m_clusters.end(); ++it)
 254         {
 255             cluster_info const& cinfo = it->second;
 256             if (cinfo.open_count > 1)
 257             {
 258                 std::cout << "CL SWITCH RESULT " << it->first
 259                              << " -> " << cinfo.switch_source << std::endl;
 260             }
 261             else
 262             {
 263                 std::cout << "CL SWITCH RESULT " << it->first
 264                           << " is not registered as open" << std::endl;
 265             }
 266         }
 267 #endif
 268
 269     }
 270
 271 private:
 272
 273     Geometry1 const& m_geometry1;
 274     Geometry2 const& m_geometry2;
 275     Turns& m_turns;
 276     Clusters& m_clusters;
 277     RobustPolicy const& m_robust_policy;
 278     Visitor& m_visitor;
 279
 280     std::map<ring_identifier, int> m_regions;
 281     std::map<ring_identifier, std::set<signed_size_type> > m_turns_per_ring;
 282     int m_region_id;
 283
 284 };
 285
 286 }} // namespace detail::overlay
 287 #endif // DOXYGEN_NO_DETAIL
 288
 289 }} // namespace boost::geometry
 290
 291 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_TRAVERSAL_SWITCH_DETECTOR_HPP