ceph/src/boost/libs/geometry/include/boost/geometry/algorithms/detail/buffer/get_piece_turns.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2012-2014 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_BUFFER_GET_PIECE_TURNS_HPP
  10 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_GET_PIECE_TURNS_HPP
  11
  12 #include <boost/range.hpp>
  13
  14 #include <boost/geometry/algorithms/equals.hpp>
  15 #include <boost/geometry/algorithms/expand.hpp>
  16 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
  17 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
  18 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
  19 #include <boost/geometry/algorithms/detail/sections/section_functions.hpp>
  20 #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp>
  21
  22
  23 namespace boost { namespace geometry
  24 {
  25
  26
  27 #ifndef DOXYGEN_NO_DETAIL
  28 namespace detail { namespace buffer
  29 {
  30
  31
  32 #if defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION)
  33 struct buffer_assign_turn
  34 {
  35     static bool const include_no_turn = false;
  36     static bool const include_degenerate = false;
  37     static bool const include_opposite = false;
  38
  39     template
  40     <
  41         typename Info,
  42         typename Point1,
  43         typename Point2,
  44         typename IntersectionInfo
  45     >
  46     static inline void apply(Info& info,
  47                              Point1 const& /*p1*/,
  48                              Point2 const& /*p2*/,
  49                              IntersectionInfo const& iinfo)
  50     {
  51         info.rob_pi = iinfo.rpi();
  52         info.rob_pj = iinfo.rpj();
  53         info.rob_qi = iinfo.rqi();
  54         info.rob_qj = iinfo.rqj();
  55     }
  56
  57 };
  58 #endif
  59
  60 template
  61 <
  62     typename Pieces,
  63     typename Rings,
  64     typename Turns,
  65     typename RobustPolicy
  66 >
  67 class piece_turn_visitor
  68 {
  69     Pieces const& m_pieces;
  70     Rings const& m_rings;
  71     Turns& m_turns;
  72     RobustPolicy const& m_robust_policy;
  73
  74     template <typename Piece>
  75     inline bool is_adjacent(Piece const& piece1, Piece const& piece2) const
  76     {
  77         if (piece1.first_seg_id.multi_index != piece2.first_seg_id.multi_index)
  78         {
  79             return false;
  80         }
  81
  82         return piece1.index == piece2.left_index
  83             || piece1.index == piece2.right_index;
  84     }
  85
  86     template <typename Piece>
  87     inline bool is_on_same_convex_ring(Piece const& piece1, Piece const& piece2) const
  88     {
  89         if (piece1.first_seg_id.multi_index != piece2.first_seg_id.multi_index)
  90         {
  91             return false;
  92         }
  93
  94         return ! m_rings[piece1.first_seg_id.multi_index].has_concave;
  95     }
  96
  97     template <typename Range, typename Iterator>
  98     inline void move_to_next_point(Range const& range, Iterator& next) const
  99     {
 100         ++next;
 101         if (next == boost::end(range))
 102         {
 103             next = boost::begin(range) + 1;
 104         }
 105     }
 106
 107     template <typename Range, typename Iterator>
 108     inline Iterator next_point(Range const& range, Iterator it) const
 109     {
 110         Iterator result = it;
 111         move_to_next_point(range, result);
 112         // TODO: we could use either piece-boundaries, or comparison with
 113         // robust points, to check if the point equals the last one
 114         while(geometry::equals(*it, *result))
 115         {
 116             move_to_next_point(range, result);
 117         }
 118         return result;
 119     }
 120
 121     template <std::size_t Dimension, typename Iterator, typename Box>
 122     inline void move_begin_iterator(Iterator& it_begin, Iterator it_beyond,
 123             signed_size_type& index, int dir, Box const& other_bounding_box)
 124     {
 125         for(; it_begin != it_beyond
 126                 && it_begin + 1 != it_beyond
 127                 && detail::section::preceding<Dimension>(dir, *(it_begin + 1),
 128                     other_bounding_box, m_robust_policy);
 129             ++it_begin, index++)
 130         {}
 131     }
 132
 133     template <std::size_t Dimension, typename Iterator, typename Box>
 134     inline void move_end_iterator(Iterator it_begin, Iterator& it_beyond,
 135             int dir, Box const& other_bounding_box)
 136     {
 137         while (it_beyond != it_begin
 138             && it_beyond - 1 != it_begin
 139             && it_beyond - 2 != it_begin)
 140         {
 141             if (detail::section::exceeding<Dimension>(dir, *(it_beyond - 2),
 142                         other_bounding_box, m_robust_policy))
 143             {
 144                 --it_beyond;
 145             }
 146             else
 147             {
 148                 return;
 149             }
 150         }
 151     }
 152
 153     template <typename Piece, typename Section>
 154     inline void calculate_turns(Piece const& piece1, Piece const& piece2,
 155         Section const& section1, Section const& section2)
 156     {
 157         typedef typename boost::range_value<Rings const>::type ring_type;
 158         typedef typename boost::range_value<Turns const>::type turn_type;
 159         typedef typename boost::range_iterator<ring_type const>::type iterator;
 160
 161         signed_size_type const piece1_first_index = piece1.first_seg_id.segment_index;
 162         signed_size_type const piece2_first_index = piece2.first_seg_id.segment_index;
 163         if (piece1_first_index < 0 || piece2_first_index < 0)
 164         {
 165             return;
 166         }
 167
 168         // Get indices of part of offsetted_rings for this monotonic section:
 169         signed_size_type const sec1_first_index = piece1_first_index + section1.begin_index;
 170         signed_size_type const sec2_first_index = piece2_first_index + section2.begin_index;
 171
 172         // index of last point in section, beyond-end is one further
 173         signed_size_type const sec1_last_index = piece1_first_index + section1.end_index;
 174         signed_size_type const sec2_last_index = piece2_first_index + section2.end_index;
 175
 176         // get geometry and iterators over these sections
 177         ring_type const& ring1 = m_rings[piece1.first_seg_id.multi_index];
 178         iterator it1_first = boost::begin(ring1) + sec1_first_index;
 179         iterator it1_beyond = boost::begin(ring1) + sec1_last_index + 1;
 180
 181         ring_type const& ring2 = m_rings[piece2.first_seg_id.multi_index];
 182         iterator it2_first = boost::begin(ring2) + sec2_first_index;
 183         iterator it2_beyond = boost::begin(ring2) + sec2_last_index + 1;
 184
 185         // Set begin/end of monotonic ranges, in both x/y directions
 186         signed_size_type index1 = sec1_first_index;
 187         move_begin_iterator<0>(it1_first, it1_beyond, index1,
 188                     section1.directions[0], section2.bounding_box);
 189         move_end_iterator<0>(it1_first, it1_beyond,
 190                     section1.directions[0], section2.bounding_box);
 191         move_begin_iterator<1>(it1_first, it1_beyond, index1,
 192                     section1.directions[1], section2.bounding_box);
 193         move_end_iterator<1>(it1_first, it1_beyond,
 194                     section1.directions[1], section2.bounding_box);
 195
 196         signed_size_type index2 = sec2_first_index;
 197         move_begin_iterator<0>(it2_first, it2_beyond, index2,
 198                     section2.directions[0], section1.bounding_box);
 199         move_end_iterator<0>(it2_first, it2_beyond,
 200                     section2.directions[0], section1.bounding_box);
 201         move_begin_iterator<1>(it2_first, it2_beyond, index2,
 202                     section2.directions[1], section1.bounding_box);
 203         move_end_iterator<1>(it2_first, it2_beyond,
 204                     section2.directions[1], section1.bounding_box);
 205
 206         turn_type the_model;
 207         the_model.operations[0].piece_index = piece1.index;
 208         the_model.operations[0].seg_id = piece1.first_seg_id;
 209         the_model.operations[0].seg_id.segment_index = index1; // override
 210
 211         iterator it1 = it1_first;
 212         for (iterator prev1 = it1++;
 213                 it1 != it1_beyond;
 214                 prev1 = it1++, the_model.operations[0].seg_id.segment_index++)
 215         {
 216             the_model.operations[1].piece_index = piece2.index;
 217             the_model.operations[1].seg_id = piece2.first_seg_id;
 218             the_model.operations[1].seg_id.segment_index = index2; // override
 219
 220             iterator next1 = next_point(ring1, it1);
 221
 222             iterator it2 = it2_first;
 223             for (iterator prev2 = it2++;
 224                     it2 != it2_beyond;
 225                     prev2 = it2++, the_model.operations[1].seg_id.segment_index++)
 226             {
 227                 iterator next2 = next_point(ring2, it2);
 228
 229                 // TODO: internally get_turn_info calculates robust points.
 230                 // But they are already calculated.
 231                 // We should be able to use them.
 232                 // this means passing them to this visitor,
 233                 // and iterating in sync with them...
 234                 typedef detail::overlay::get_turn_info
 235                     <
 236 #if defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION)
 237                         buffer_assign_turn
 238 #else
 239                         detail::overlay::assign_null_policy
 240 #endif
 241                     > turn_policy;
 242
 243                 turn_policy::apply(*prev1, *it1, *next1,
 244                                     *prev2, *it2, *next2,
 245                                     false, false, false, false,
 246                                     the_model, m_robust_policy,
 247                                     std::back_inserter(m_turns));
 248             }
 249         }
 250     }
 251
 252 public:
 253
 254     piece_turn_visitor(Pieces const& pieces,
 255             Rings const& ring_collection,
 256             Turns& turns,
 257             RobustPolicy const& robust_policy)
 258         : m_pieces(pieces)
 259         , m_rings(ring_collection)
 260         , m_turns(turns)
 261         , m_robust_policy(robust_policy)
 262     {}
 263
 264     template <typename Section>
 265     inline void apply(Section const& section1, Section const& section2,
 266                     bool first = true)
 267     {
 268         boost::ignore_unused_variable_warning(first);
 269
 270         typedef typename boost::range_value<Pieces const>::type piece_type;
 271         piece_type const& piece1 = m_pieces[section1.ring_id.source_index];
 272         piece_type const& piece2 = m_pieces[section2.ring_id.source_index];
 273
 274         if ( piece1.index == piece2.index
 275           || is_adjacent(piece1, piece2)
 276           || is_on_same_convex_ring(piece1, piece2)
 277           || detail::disjoint::disjoint_box_box(section1.bounding_box,
 278                     section2.bounding_box) )
 279         {
 280             return;
 281         }
 282
 283         calculate_turns(piece1, piece2, section1, section2);
 284     }
 285 };
 286
 287
 288 }} // namespace detail::buffer
 289 #endif // DOXYGEN_NO_DETAIL
 290
 291
 292 }} // namespace boost::geometry
 293
 294 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_GET_PIECE_TURNS_HPP