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> skip(Operation const & op,Piece const & piece) const51 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> is_one_sided(NumericType const & left,NumericType const & right) const78 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> has_zero_distance_at(Point const & point) const86 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 turn_in_piece_visitor(Turns & turns,Pieces const & pieces,DistanceStrategy const & distance_strategy)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> apply(Turn const & turn,Piece const & 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> apply(Turn const & turn,Piece const & piece,Border const & 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 204