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