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 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
   5
   6 // This file was modified by Oracle on 2017, 2018.
   7 // Modifications copyright (c) 2017-2018 Oracle and/or its affiliates.
   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_BUFFER_GET_PIECE_TURNS_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_GET_PIECE_TURNS_HPP
  16
  17 #include <boost/core/ignore_unused.hpp>
  18 #include <boost/range.hpp>
  19
  20 #include <boost/geometry/core/assert.hpp>
  21 #include <boost/geometry/algorithms/equals.hpp>
  22 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
  23 #include <boost/geometry/algorithms/detail/overlay/segment_identifier.hpp>
  24 #include <boost/geometry/algorithms/detail/overlay/get_turn_info.hpp>
  25 #include <boost/geometry/algorithms/detail/sections/section_functions.hpp>
  26 #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp>
  27
  28
  29 namespace boost { namespace geometry
  30 {
  31
  32
  33 #ifndef DOXYGEN_NO_DETAIL
  34 namespace detail { namespace buffer
  35 {
  36
  37 // Implements a unique_sub_range for a buffered piece,
  38 // the range can return subsequent points
  39 // known as "i", "j" and "k" (and further),  indexed as 0,1,2,3
  40 template <typename Ring>
  41 struct unique_sub_range_from_piece
  42 {
  43     typedef typename boost::range_iterator<Ring const>::type iterator_type;
  44     typedef typename geometry::point_type<Ring const>::type point_type;
  45
  46     unique_sub_range_from_piece(Ring const& ring,
  47                                 iterator_type iterator_at_i, iterator_type iterator_at_j)
  48         : m_ring(ring)
  49         , m_iterator_at_i(iterator_at_i)
  50         , m_iterator_at_j(iterator_at_j)
  51         , m_point_retrieved(false)
  52     {}
  53
  54     static inline bool is_first_segment() { return false; }
  55     static inline bool is_last_segment() { return false; }
  56
  57     static inline std::size_t size() { return 3u; }
  58
  59     inline point_type const& at(std::size_t index) const
  60     {
  61         BOOST_GEOMETRY_ASSERT(index < size());
  62         switch (index)
  63         {
  64             case 0 : return *m_iterator_at_i;
  65             case 1 : return *m_iterator_at_j;
  66             case 2 : return get_point_k();
  67             default : return *m_iterator_at_i;
  68         }
  69     }
  70
  71 private :
  72
  73     inline point_type const& get_point_k() const
  74     {
  75         if (! m_point_retrieved)
  76         {
  77             m_iterator_at_k = advance_one(m_iterator_at_j);
  78             m_point_retrieved = true;
  79         }
  80         return *m_iterator_at_k;
  81     }
  82
  83     inline void circular_advance_one(iterator_type& next) const
  84     {
  85         ++next;
  86         if (next == boost::end(m_ring))
  87         {
  88             next = boost::begin(m_ring) + 1;
  89         }
  90     }
  91
  92     inline iterator_type advance_one(iterator_type it) const
  93     {
  94         iterator_type result = it;
  95         circular_advance_one(result);
  96
  97         // TODO: we could also use piece-boundaries
  98         // to check if the point equals the last one
  99         while (geometry::equals(*it, *result))
 100         {
 101             circular_advance_one(result);
 102         }
 103         return result;
 104     }
 105
 106     Ring const& m_ring;
 107     iterator_type m_iterator_at_i;
 108     iterator_type m_iterator_at_j;
 109     mutable iterator_type m_iterator_at_k;
 110     mutable bool m_point_retrieved;
 111 };
 112
 113 template
 114 <
 115     typename Pieces,
 116     typename Rings,
 117     typename Turns,
 118     typename IntersectionStrategy,
 119     typename RobustPolicy
 120 >
 121 class piece_turn_visitor
 122 {
 123     Pieces const& m_pieces;
 124     Rings const& m_rings;
 125     Turns& m_turns;
 126     IntersectionStrategy const& m_intersection_strategy;
 127     RobustPolicy const& m_robust_policy;
 128
 129     template <typename Piece>
 130     inline bool is_adjacent(Piece const& piece1, Piece const& piece2) const
 131     {
 132         if (piece1.first_seg_id.multi_index != piece2.first_seg_id.multi_index)
 133         {
 134             return false;
 135         }
 136
 137         return piece1.index == piece2.left_index
 138             || piece1.index == piece2.right_index;
 139     }
 140
 141     template <typename Piece>
 142     inline bool is_on_same_convex_ring(Piece const& piece1, Piece const& piece2) const
 143     {
 144         if (piece1.first_seg_id.multi_index != piece2.first_seg_id.multi_index)
 145         {
 146             return false;
 147         }
 148
 149         return ! m_rings[piece1.first_seg_id.multi_index].has_concave;
 150     }
 151
 152
 153     template <std::size_t Dimension, typename Iterator, typename Box>
 154     inline void move_begin_iterator(Iterator& it_begin, Iterator it_beyond,
 155                                     signed_size_type& index, int dir,
 156                                     Box const& this_bounding_box,
 157                                     Box const& other_bounding_box)
 158     {
 159         for(; it_begin != it_beyond
 160                 && it_begin + 1 != it_beyond
 161                 && detail::section::preceding<Dimension>(dir, *(it_begin + 1),
 162                                                          this_bounding_box,
 163                                                          other_bounding_box,
 164                                                          m_robust_policy);
 165             ++it_begin, index++)
 166         {}
 167     }
 168
 169     template <std::size_t Dimension, typename Iterator, typename Box>
 170     inline void move_end_iterator(Iterator it_begin, Iterator& it_beyond,
 171                                   int dir, Box const& this_bounding_box,
 172                                   Box const& other_bounding_box)
 173     {
 174         while (it_beyond != it_begin
 175             && it_beyond - 1 != it_begin
 176             && it_beyond - 2 != it_begin)
 177         {
 178             if (detail::section::exceeding<Dimension>(dir, *(it_beyond - 2),
 179                         this_bounding_box, other_bounding_box, m_robust_policy))
 180             {
 181                 --it_beyond;
 182             }
 183             else
 184             {
 185                 return;
 186             }
 187         }
 188     }
 189
 190     template <typename Piece, typename Section>
 191     inline void calculate_turns(Piece const& piece1, Piece const& piece2,
 192         Section const& section1, Section const& section2)
 193     {
 194         typedef typename boost::range_value<Rings const>::type ring_type;
 195         typedef typename boost::range_value<Turns const>::type turn_type;
 196         typedef typename boost::range_iterator<ring_type const>::type iterator;
 197
 198         signed_size_type const piece1_first_index = piece1.first_seg_id.segment_index;
 199         signed_size_type const piece2_first_index = piece2.first_seg_id.segment_index;
 200         if (piece1_first_index < 0 || piece2_first_index < 0)
 201         {
 202             return;
 203         }
 204
 205         // Get indices of part of offsetted_rings for this monotonic section:
 206         signed_size_type const sec1_first_index = piece1_first_index + section1.begin_index;
 207         signed_size_type const sec2_first_index = piece2_first_index + section2.begin_index;
 208
 209         // index of last point in section, beyond-end is one further
 210         signed_size_type const sec1_last_index = piece1_first_index + section1.end_index;
 211         signed_size_type const sec2_last_index = piece2_first_index + section2.end_index;
 212
 213         // get geometry and iterators over these sections
 214         ring_type const& ring1 = m_rings[piece1.first_seg_id.multi_index];
 215         iterator it1_first = boost::begin(ring1) + sec1_first_index;
 216         iterator it1_beyond = boost::begin(ring1) + sec1_last_index + 1;
 217
 218         ring_type const& ring2 = m_rings[piece2.first_seg_id.multi_index];
 219         iterator it2_first = boost::begin(ring2) + sec2_first_index;
 220         iterator it2_beyond = boost::begin(ring2) + sec2_last_index + 1;
 221
 222         // Set begin/end of monotonic ranges, in both x/y directions
 223         signed_size_type index1 = sec1_first_index;
 224         move_begin_iterator<0>(it1_first, it1_beyond, index1,
 225                     section1.directions[0], section1.bounding_box, section2.bounding_box);
 226         move_end_iterator<0>(it1_first, it1_beyond,
 227                     section1.directions[0], section1.bounding_box, section2.bounding_box);
 228         move_begin_iterator<1>(it1_first, it1_beyond, index1,
 229                     section1.directions[1], section1.bounding_box, section2.bounding_box);
 230         move_end_iterator<1>(it1_first, it1_beyond,
 231                     section1.directions[1], section1.bounding_box, section2.bounding_box);
 232
 233         signed_size_type index2 = sec2_first_index;
 234         move_begin_iterator<0>(it2_first, it2_beyond, index2,
 235                     section2.directions[0], section2.bounding_box, section1.bounding_box);
 236         move_end_iterator<0>(it2_first, it2_beyond,
 237                     section2.directions[0], section2.bounding_box, section1.bounding_box);
 238         move_begin_iterator<1>(it2_first, it2_beyond, index2,
 239                     section2.directions[1], section2.bounding_box, section1.bounding_box);
 240         move_end_iterator<1>(it2_first, it2_beyond,
 241                     section2.directions[1], section2.bounding_box, section1.bounding_box);
 242
 243         turn_type the_model;
 244         the_model.operations[0].piece_index = piece1.index;
 245         the_model.operations[0].seg_id = piece1.first_seg_id;
 246         the_model.operations[0].seg_id.segment_index = index1; // override
 247
 248         iterator it1 = it1_first;
 249         for (iterator prev1 = it1++;
 250                 it1 != it1_beyond;
 251                 prev1 = it1++, the_model.operations[0].seg_id.segment_index++)
 252         {
 253             the_model.operations[1].piece_index = piece2.index;
 254             the_model.operations[1].seg_id = piece2.first_seg_id;
 255             the_model.operations[1].seg_id.segment_index = index2; // override
 256             geometry::recalculate(the_model.rob_pi, *prev1, m_robust_policy);
 257             geometry::recalculate(the_model.rob_pj, *it1, m_robust_policy);
 258
 259             unique_sub_range_from_piece<ring_type> unique_sub_range1(ring1, prev1, it1);
 260
 261             iterator it2 = it2_first;
 262             for (iterator prev2 = it2++;
 263                     it2 != it2_beyond;
 264                     prev2 = it2++, the_model.operations[1].seg_id.segment_index++)
 265             {
 266                 unique_sub_range_from_piece<ring_type> unique_sub_range2(ring2, prev2, it2);
 267                 geometry::recalculate(the_model.rob_qi, *prev2, m_robust_policy);
 268                 geometry::recalculate(the_model.rob_qj, *it2, m_robust_policy);
 269
 270                 // TODO: internally get_turn_info calculates robust points.
 271                 // But they are already calculated.
 272                 // We should be able to use them.
 273                 // this means passing them to this visitor,
 274                 // and iterating in sync with them...
 275                 typedef detail::overlay::get_turn_info
 276                     <
 277                         detail::overlay::assign_null_policy
 278                     > turn_policy;
 279
 280                 turn_policy::apply(unique_sub_range1, unique_sub_range2,
 281                                    the_model,
 282                                    m_intersection_strategy,
 283                                    m_robust_policy,
 284                                    std::back_inserter(m_turns));
 285             }
 286         }
 287     }
 288
 289 public:
 290
 291     piece_turn_visitor(Pieces const& pieces,
 292             Rings const& ring_collection,
 293             Turns& turns,
 294             IntersectionStrategy const& intersection_strategy,
 295             RobustPolicy const& robust_policy)
 296         : m_pieces(pieces)
 297         , m_rings(ring_collection)
 298         , m_turns(turns)
 299         , m_intersection_strategy(intersection_strategy)
 300         , m_robust_policy(robust_policy)
 301     {}
 302
 303     template <typename Section>
 304     inline bool apply(Section const& section1, Section const& section2,
 305                     bool first = true)
 306     {
 307         boost::ignore_unused(first);
 308
 309         typedef typename boost::range_value<Pieces const>::type piece_type;
 310         piece_type const& piece1 = m_pieces[section1.ring_id.source_index];
 311         piece_type const& piece2 = m_pieces[section2.ring_id.source_index];
 312
 313         if ( piece1.index == piece2.index
 314           || is_adjacent(piece1, piece2)
 315           || is_on_same_convex_ring(piece1, piece2)
 316           || detail::disjoint::disjoint_box_box(section1.bounding_box,
 317                                                 section2.bounding_box,
 318                                                 m_intersection_strategy.get_disjoint_box_box_strategy()) )
 319         {
 320             return true;
 321         }
 322
 323         calculate_turns(piece1, piece2, section1, section2);
 324
 325         return true;
 326     }
 327 };
 328
 329
 330 }} // namespace detail::buffer
 331 #endif // DOXYGEN_NO_DETAIL
 332
 333
 334 }} // namespace boost::geometry
 335
 336 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_GET_PIECE_TURNS_HPP