ceph/src/boost/boost/geometry/algorithms/detail/buffer/turn_in_piece_visitor.hpp

   1 // Boost.Geometry (aka GGL, Generic Geometry Library)
   2
   3 // Copyright (c) 2012-2020 Barend Gehrels, Amsterdam, the Netherlands.
   4 // Copyright (c) 2017 Adam Wulkiewicz, Lodz, Poland.
   5
   6 // This file was modified by Oracle on 2016, 2018.
   7 // Modifications copyright (c) 2016-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_TURN_IN_PIECE_VISITOR_HPP
  15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_PIECE_VISITOR_HPP
  16
  17 #include <boost/geometry/core/assert.hpp>
  18 #include <boost/geometry/core/config.hpp>
  19
  20 #include <boost/geometry/algorithms/comparable_distance.hpp>
  21 #include <boost/geometry/algorithms/covered_by.hpp>
  22 #include <boost/geometry/algorithms/detail/disjoint/point_box.hpp>
  23 #include <boost/geometry/algorithms/detail/disjoint/box_box.hpp>
  24 #include <boost/geometry/algorithms/detail/buffer/buffer_policies.hpp>
  25 #include <boost/geometry/geometries/box.hpp>
  26
  27
  28 namespace boost { namespace geometry
  29 {
  30
  31 #ifndef DOXYGEN_NO_DETAIL
  32
  33 namespace detail { namespace buffer
  34 {
  35
  36 template
  37 <
  38     typename CsTag,
  39     typename Turns,
  40     typename Pieces,
  41     typename DistanceStrategy
  42
  43 >
  44 class turn_in_piece_visitor
  45 {
  46     Turns& m_turns; // because partition is currently operating on const input only
  47     Pieces const& m_pieces; // to check for piece-type
  48     DistanceStrategy const& m_distance_strategy; // to check if point is on original or one_sided
  49
  50     template <typename Operation, typename Piece>
  51     inline bool skip(Operation const& op, Piece const& piece) const
  52     {
  53         if (op.piece_index == piece.index)
  54         {
  55             return true;
  56         }
  57         Piece const& pc = m_pieces[op.piece_index];
  58         if (pc.left_index == piece.index || pc.right_index == piece.index)
  59         {
  60             if (pc.type == strategy::buffer::buffered_flat_end)
  61             {
  62                 // If it is a flat end, don't compare against its neighbor:
  63                 // it will always be located on one of the helper segments
  64                 return true;
  65             }
  66             if (pc.type == strategy::buffer::buffered_concave)
  67             {
  68                 // If it is concave, the same applies: the IP will be
  69                 // located on one of the helper segments
  70                 return true;
  71             }
  72         }
  73
  74         return false;
  75     }
  76
  77     template <typename NumericType>
  78     inline bool is_one_sided(NumericType const& left, NumericType const& right) const
  79     {
  80         static NumericType const zero = 0;
  81         return geometry::math::equals(left, zero)
  82             || geometry::math::equals(right, zero);
  83     }
  84
  85     template <typename Point>
  86     inline bool has_zero_distance_at(Point const& point) const
  87     {
  88         return is_one_sided(m_distance_strategy.apply(point, point,
  89                 strategy::buffer::buffer_side_left),
  90             m_distance_strategy.apply(point, point,
  91                 strategy::buffer::buffer_side_right));
  92     }
  93
  94 public:
  95
  96     inline turn_in_piece_visitor(Turns& turns, Pieces const& pieces,
  97                                  DistanceStrategy const& distance_strategy)
  98         : m_turns(turns)
  99         , m_pieces(pieces)
 100         , m_distance_strategy(distance_strategy)
 101     {}
 102
 103     template <typename Turn, typename Piece>
 104     inline bool apply(Turn const& turn, Piece const& piece)
 105     {
 106         if (! turn.is_turn_traversable)
 107         {
 108             // Already handled
 109             return true;
 110         }
 111
 112         if (piece.type == strategy::buffer::buffered_flat_end
 113             || piece.type == strategy::buffer::buffered_concave)
 114         {
 115             // Turns cannot be located within flat-end or concave pieces
 116             return true;
 117         }
 118
 119         if (skip(turn.operations[0], piece) || skip(turn.operations[1], piece))
 120         {
 121             return true;
 122         }
 123
 124         return apply(turn, piece, piece.m_piece_border);
 125     }
 126
 127     template <typename Turn, typename Piece, typename Border>
 128     inline bool apply(Turn const& turn, Piece const& piece, Border const& border)
 129     {
 130         if (! geometry::covered_by(turn.point, border.m_envelope))
 131         {
 132             // Easy check: if turn is not in the (expanded) envelope
 133             return true;
 134         }
 135
 136         if (piece.type == geometry::strategy::buffer::buffered_point)
 137         {
 138             // Optimization for a buffer around points: if distance from center
 139             // is not between min/max radius, it is either inside or outside,
 140             // and more expensive checks are not necessary.
 141             typedef typename Border::radius_type radius_type;
 142
 143             radius_type const d = geometry::comparable_distance(piece.m_center, turn.point);
 144
 145             if (d < border.m_min_comparable_radius)
 146             {
 147                 Turn& mutable_turn = m_turns[turn.turn_index];
 148                 mutable_turn.is_turn_traversable = false;
 149                 return true;
 150             }
 151             if (d > border.m_max_comparable_radius)
 152             {
 153                 return true;
 154             }
 155         }
 156
 157         // Check if buffer is one-sided (at this point), because then a point
 158         // on the original is not considered as within.
 159         bool const one_sided = has_zero_distance_at(turn.point);
 160
 161         typename Border::state_type state;
 162         if (! border.point_on_piece(turn.point, one_sided, turn.is_linear_end_point, state))
 163         {
 164             return true;
 165         }
 166
 167         if (state.code() == 1)
 168         {
 169             // It is WITHIN a piece, or on the piece border, but not
 170             // on the offsetted part of it.
 171
 172             // TODO - at further removing rescaling, this threshold can be
 173             // adapted, or ideally, go.
 174             // This threshold is minimized to the point where fragile
 175             // unit tests of hard cases start to fail (5 in multi_polygon)
 176             // But it is acknowlegded that such a threshold depends on the
 177             // scale of the input.
 178             if (state.m_min_distance > 1.0e-5 || ! state.m_close_to_offset)
 179             {
 180                 Turn& mutable_turn = m_turns[turn.turn_index];
 181                 mutable_turn.is_turn_traversable = false;
 182
 183                 // Keep track of the information if this turn was close
 184                 // to an offset (without threshold). Because if it was,
 185                 // it might have been classified incorrectly and in the
 186                 // pretraversal step, it can in hindsight be classified
 187                 // as "outside".
 188                 mutable_turn.close_to_offset = state.m_close_to_offset;
 189             }
 190         }
 191
 192         return true;
 193     }
 194 };
 195
 196
 197 }} // namespace detail::buffer
 198 #endif // DOXYGEN_NO_DETAIL
 199
 200
 201 }} // namespace boost::geometry
 202
 203 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_TURN_IN_PIECE_VISITOR_HPP