1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2012-2014 Barend Gehrels, Amsterdam, the Netherlands. 4 5 // This file was modified by Oracle on 2017, 2018. 6 // Modifications copyright (c) 2017-2018, Oracle and/or its affiliates. 7 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 8 9 // Use, modification and distribution is subject to the Boost Software License, 10 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 11 // http://www.boost.org/LICENSE_1_0.txt) 12 13 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFER_POLICIES_HPP 14 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFER_POLICIES_HPP 15 16 #include <cstddef> 17 18 #include <boost/range.hpp> 19 20 #include <boost/geometry/core/coordinate_type.hpp> 21 #include <boost/geometry/core/point_type.hpp> 22 23 #include <boost/geometry/algorithms/detail/overlay/backtrack_check_si.hpp> 24 #include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp> 25 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> 26 27 #include <boost/geometry/strategies/buffer.hpp> 28 29 30 namespace boost { namespace geometry 31 { 32 33 34 #ifndef DOXYGEN_NO_DETAIL 35 namespace detail { namespace buffer 36 { 37 38 class backtrack_for_buffer 39 { 40 public : 41 typedef detail::overlay::backtrack_state state_type; 42 43 template 44 < 45 typename Operation, 46 typename Rings, 47 typename Turns, 48 typename Geometry, 49 typename Strategy, 50 typename RobustPolicy, 51 typename Visitor 52 > apply(std::size_t size_at_start,Rings & rings,typename boost::range_value<Rings>::type & ring,Turns & turns,typename boost::range_value<Turns>::type const &,Operation & operation,detail::overlay::traverse_error_type,Geometry const &,Geometry const &,Strategy const &,RobustPolicy const &,state_type & state,Visitor &)53 static inline void apply(std::size_t size_at_start, 54 Rings& rings, typename boost::range_value<Rings>::type& ring, 55 Turns& turns, 56 typename boost::range_value<Turns>::type const& /*turn*/, 57 Operation& operation, 58 detail::overlay::traverse_error_type /*traverse_error*/, 59 Geometry const& , 60 Geometry const& , 61 Strategy const& , 62 RobustPolicy const& , 63 state_type& state, 64 Visitor& /*visitor*/ 65 ) 66 { 67 #if defined(BOOST_GEOMETRY_COUNT_BACKTRACK_WARNINGS) 68 extern int g_backtrack_warning_count; 69 g_backtrack_warning_count++; 70 #endif 71 //std::cout << "!"; 72 //std::cout << "WARNING " << traverse_error_string(traverse_error) << std::endl; 73 74 state.m_good = false; 75 76 // Make bad output clean 77 rings.resize(size_at_start); 78 ring.clear(); 79 80 // Reject this as a starting point 81 operation.visited.set_rejected(); 82 83 // And clear all visit info 84 clear_visit_info(turns); 85 } 86 }; 87 88 struct buffer_overlay_visitor 89 { 90 public : printboost::geometry::detail::buffer::buffer_overlay_visitor91 void print(char const* /*header*/) 92 { 93 } 94 95 template <typename Turns> printboost::geometry::detail::buffer::buffer_overlay_visitor96 void print(char const* /*header*/, Turns const& /*turns*/, int /*turn_index*/) 97 { 98 } 99 100 template <typename Turns> printboost::geometry::detail::buffer::buffer_overlay_visitor101 void print(char const* /*header*/, Turns const& /*turns*/, int /*turn_index*/, int /*op_index*/) 102 { 103 } 104 105 template <typename Turns> visit_turnsboost::geometry::detail::buffer::buffer_overlay_visitor106 void visit_turns(int , Turns const& ) {} 107 108 template <typename Clusters, typename Turns> visit_clustersboost::geometry::detail::buffer::buffer_overlay_visitor109 void visit_clusters(Clusters const& , Turns const& ) {} 110 111 template <typename Turns, typename Turn, typename Operation> visit_traverseboost::geometry::detail::buffer::buffer_overlay_visitor112 void visit_traverse(Turns const& /*turns*/, Turn const& /*turn*/, Operation const& /*op*/, const char* /*header*/) 113 { 114 } 115 116 template <typename Turns, typename Turn, typename Operation> visit_traverse_rejectboost::geometry::detail::buffer::buffer_overlay_visitor117 void visit_traverse_reject(Turns const& , Turn const& , Operation const& , 118 detail::overlay::traverse_error_type ) 119 {} 120 121 template <typename Rings> visit_generated_ringsboost::geometry::detail::buffer::buffer_overlay_visitor122 void visit_generated_rings(Rings const& ) 123 {} 124 }; 125 126 127 // Should follow traversal-turn-concept (enrichment, visit structure) 128 // and adds index in piece vector to find it back 129 template <typename Point, typename SegmentRatio> 130 struct buffer_turn_operation 131 : public detail::overlay::traversal_turn_operation<Point, SegmentRatio> 132 { 133 signed_size_type piece_index; 134 signed_size_type index_in_robust_ring; 135 buffer_turn_operationboost::geometry::detail::buffer::buffer_turn_operation136 inline buffer_turn_operation() 137 : piece_index(-1) 138 , index_in_robust_ring(-1) 139 {} 140 }; 141 142 // Version of turn_info for buffer with its turn index and other helper variables 143 template <typename Point, typename SegmentRatio> 144 struct buffer_turn_info 145 : public detail::overlay::turn_info 146 < 147 Point, 148 SegmentRatio, 149 buffer_turn_operation<Point, SegmentRatio> 150 > 151 { 152 typedef Point point_type; 153 154 std::size_t turn_index; 155 156 // Information if turn can be used. It is not traversable if it is within 157 // another piece, or within the original (depending on deflation), 158 // or (for deflate) if there are not enough points to traverse it. 159 bool is_turn_traversable; 160 161 bool close_to_offset; 162 bool is_linear_end_point; 163 bool within_original; 164 signed_size_type count_in_original; // increased by +1 for in ext.ring, -1 for int.ring 165 buffer_turn_infoboost::geometry::detail::buffer::buffer_turn_info166 inline buffer_turn_info() 167 : turn_index(0) 168 , is_turn_traversable(true) 169 , close_to_offset(false) 170 , is_linear_end_point(false) 171 , within_original(false) 172 , count_in_original(0) 173 {} 174 }; 175 176 struct buffer_less 177 { 178 template <typename Indexed> operator ()boost::geometry::detail::buffer::buffer_less179 inline bool operator()(Indexed const& left, Indexed const& right) const 180 { 181 if (! (left.subject->seg_id == right.subject->seg_id)) 182 { 183 return left.subject->seg_id < right.subject->seg_id; 184 } 185 186 // Both left and right are located on the SAME segment. 187 if (! (left.subject->fraction == right.subject->fraction)) 188 { 189 return left.subject->fraction < right.subject->fraction; 190 } 191 192 return left.turn_index < right.turn_index; 193 } 194 }; 195 196 struct piece_get_box 197 { 198 template <typename Box, typename Piece> applyboost::geometry::detail::buffer::piece_get_box199 static inline void apply(Box& total, Piece const& piece) 200 { 201 typedef typename strategy::expand::services::default_strategy 202 < 203 box_tag, typename cs_tag<Box>::type 204 >::type expand_strategy_type; 205 206 if (piece.m_piece_border.m_has_envelope) 207 { 208 geometry::expand(total, piece.m_piece_border.m_envelope, 209 expand_strategy_type()); 210 } 211 } 212 }; 213 214 template <typename DisjointBoxBoxStrategy> 215 struct piece_ovelaps_box 216 { 217 template <typename Box, typename Piece> applyboost::geometry::detail::buffer::piece_ovelaps_box218 static inline bool apply(Box const& box, Piece const& piece) 219 { 220 if (piece.type == strategy::buffer::buffered_flat_end 221 || piece.type == strategy::buffer::buffered_concave) 222 { 223 // Turns cannot be inside a flat end (though they can be on border) 224 // Neither we need to check if they are inside concave helper pieces 225 226 // Skip all pieces not used as soon as possible 227 return false; 228 } 229 if (! piece.m_piece_border.m_has_envelope) 230 { 231 return false; 232 } 233 234 return ! geometry::detail::disjoint::disjoint_box_box(box, piece.m_piece_border.m_envelope, 235 DisjointBoxBoxStrategy()); 236 } 237 }; 238 239 struct turn_get_box 240 { 241 template <typename Box, typename Turn> applyboost::geometry::detail::buffer::turn_get_box242 static inline void apply(Box& total, Turn const& turn) 243 { 244 typedef typename strategy::expand::services::default_strategy 245 < 246 point_tag, typename cs_tag<Box>::type 247 >::type expand_strategy_type; 248 geometry::expand(total, turn.point, expand_strategy_type()); 249 } 250 }; 251 252 template <typename DisjointPointBoxStrategy> 253 struct turn_ovelaps_box 254 { 255 template <typename Box, typename Turn> applyboost::geometry::detail::buffer::turn_ovelaps_box256 static inline bool apply(Box const& box, Turn const& turn) 257 { 258 return ! geometry::detail::disjoint::disjoint_point_box(turn.point, box, 259 DisjointPointBoxStrategy()); 260 } 261 }; 262 263 struct enriched_map_buffer_include_policy 264 { 265 template <typename Operation> includeboost::geometry::detail::buffer::enriched_map_buffer_include_policy266 static inline bool include(Operation const& op) 267 { 268 return op != detail::overlay::operation_intersection 269 && op != detail::overlay::operation_blocked; 270 } 271 }; 272 273 }} // namespace detail::buffer 274 #endif // DOXYGEN_NO_DETAIL 275 276 277 }} // namespace boost::geometry 278 279 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFER_POLICIES_HPP 280