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. 6 // Modifications copyright (c) 2017, 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 #if ! defined(BOOST_GEOMETRY_NO_ROBUSTNESS) 17 # define BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION 18 #endif 19 20 #include <cstddef> 21 22 #include <boost/range.hpp> 23 24 #include <boost/geometry/core/coordinate_type.hpp> 25 #include <boost/geometry/core/point_type.hpp> 26 27 #include <boost/geometry/algorithms/covered_by.hpp> 28 #include <boost/geometry/algorithms/detail/overlay/backtrack_check_si.hpp> 29 #include <boost/geometry/algorithms/detail/overlay/turn_info.hpp> 30 31 #include <boost/geometry/strategies/buffer.hpp> 32 33 34 namespace boost { namespace geometry 35 { 36 37 38 #ifndef DOXYGEN_NO_DETAIL 39 namespace detail { namespace buffer 40 { 41 42 43 enum intersection_location_type 44 { 45 location_ok, inside_buffer, location_discard 46 }; 47 48 class backtrack_for_buffer 49 { 50 public : 51 typedef detail::overlay::backtrack_state state_type; 52 53 template 54 < 55 typename Operation, 56 typename Rings, 57 typename Turns, 58 typename Geometry, 59 typename Strategy, 60 typename RobustPolicy, 61 typename Visitor 62 > 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 &)63 static inline void apply(std::size_t size_at_start, 64 Rings& rings, typename boost::range_value<Rings>::type& ring, 65 Turns& turns, 66 typename boost::range_value<Turns>::type const& /*turn*/, 67 Operation& operation, 68 detail::overlay::traverse_error_type /*traverse_error*/, 69 Geometry const& , 70 Geometry const& , 71 Strategy const& , 72 RobustPolicy const& , 73 state_type& state, 74 Visitor& /*visitor*/ 75 ) 76 { 77 #if defined(BOOST_GEOMETRY_COUNT_BACKTRACK_WARNINGS) 78 extern int g_backtrack_warning_count; 79 g_backtrack_warning_count++; 80 #endif 81 //std::cout << "!"; 82 //std::cout << "WARNING " << traverse_error_string(traverse_error) << std::endl; 83 84 state.m_good = false; 85 86 // Make bad output clean 87 rings.resize(size_at_start); 88 ring.clear(); 89 90 // Reject this as a starting point 91 operation.visited.set_rejected(); 92 93 // And clear all visit info 94 clear_visit_info(turns); 95 } 96 }; 97 98 struct buffer_overlay_visitor 99 { 100 public : printboost::geometry::detail::buffer::buffer_overlay_visitor101 void print(char const* /*header*/) 102 { 103 } 104 105 template <typename Turns> printboost::geometry::detail::buffer::buffer_overlay_visitor106 void print(char const* /*header*/, Turns const& /*turns*/, int /*turn_index*/) 107 { 108 } 109 110 template <typename Turns> printboost::geometry::detail::buffer::buffer_overlay_visitor111 void print(char const* /*header*/, Turns const& /*turns*/, int /*turn_index*/, int /*op_index*/) 112 { 113 } 114 115 template <typename Turns> visit_turnsboost::geometry::detail::buffer::buffer_overlay_visitor116 void visit_turns(int , Turns const& ) {} 117 118 template <typename Clusters, typename Turns> visit_clustersboost::geometry::detail::buffer::buffer_overlay_visitor119 void visit_clusters(Clusters const& , Turns const& ) {} 120 121 template <typename Turns, typename Turn, typename Operation> visit_traverseboost::geometry::detail::buffer::buffer_overlay_visitor122 void visit_traverse(Turns const& /*turns*/, Turn const& /*turn*/, Operation const& /*op*/, const char* /*header*/) 123 { 124 } 125 126 template <typename Turns, typename Turn, typename Operation> visit_traverse_rejectboost::geometry::detail::buffer::buffer_overlay_visitor127 void visit_traverse_reject(Turns const& , Turn const& , Operation const& , 128 detail::overlay::traverse_error_type ) 129 {} 130 }; 131 132 133 // Should follow traversal-turn-concept (enrichment, visit structure) 134 // and adds index in piece vector to find it back 135 template <typename Point, typename SegmentRatio> 136 struct buffer_turn_operation 137 : public detail::overlay::traversal_turn_operation<Point, SegmentRatio> 138 { 139 signed_size_type piece_index; 140 signed_size_type index_in_robust_ring; 141 buffer_turn_operationboost::geometry::detail::buffer::buffer_turn_operation142 inline buffer_turn_operation() 143 : piece_index(-1) 144 , index_in_robust_ring(-1) 145 {} 146 }; 147 148 // Version for buffer including type of location, is_opposite, and helper variables 149 template <typename Point, typename RobustPoint, typename SegmentRatio> 150 struct buffer_turn_info 151 : public detail::overlay::turn_info 152 < 153 Point, 154 SegmentRatio, 155 buffer_turn_operation<Point, SegmentRatio> 156 > 157 { 158 typedef Point point_type; 159 typedef RobustPoint robust_point_type; 160 161 std::size_t turn_index; // TODO: this might go if partition can operate on non-const input 162 163 RobustPoint robust_point; 164 #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS) 165 // Will (most probably) be removed later 166 RobustPoint mapped_robust_point; // alas... we still need to adapt our points, offsetting them 1 integer to be co-located with neighbours 167 #endif 168 169 get_robust_pointboost::geometry::detail::buffer::buffer_turn_info170 inline RobustPoint const& get_robust_point() const 171 { 172 #if defined(BOOST_GEOMETRY_BUFFER_ENLARGED_CLUSTERS) 173 return mapped_robust_point; 174 #endif 175 return robust_point; 176 } 177 178 intersection_location_type location; 179 180 #if defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION) 181 robust_point_type rob_pi, rob_pj, rob_qi, rob_qj; 182 #endif 183 184 std::size_t count_within; 185 186 bool within_original; 187 std::size_t count_on_original_boundary; 188 signed_size_type count_in_original; // increased by +1 for in ext.ring, -1 for int.ring 189 190 std::size_t count_on_offsetted; 191 std::size_t count_on_helper; 192 #if ! defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION) 193 std::size_t count_within_near_offsetted; 194 #endif 195 196 bool remove_on_multi; 197 198 // Obsolete: 199 std::size_t count_on_occupied; 200 std::size_t count_on_multi; 201 buffer_turn_infoboost::geometry::detail::buffer::buffer_turn_info202 inline buffer_turn_info() 203 : turn_index(0) 204 , location(location_ok) 205 , count_within(0) 206 , within_original(false) 207 , count_on_original_boundary(0) 208 , count_in_original(0) 209 , count_on_offsetted(0) 210 , count_on_helper(0) 211 #if ! defined(BOOST_GEOMETRY_BUFFER_USE_SIDE_OF_INTERSECTION) 212 , count_within_near_offsetted(0) 213 #endif 214 , remove_on_multi(false) 215 , count_on_occupied(0) 216 , count_on_multi(0) 217 {} 218 }; 219 220 struct buffer_operation_less 221 { 222 template <typename Turn> operator ()boost::geometry::detail::buffer::buffer_operation_less223 inline bool operator()(Turn const& left, Turn const& right) const 224 { 225 segment_identifier const& sl = left.seg_id; 226 segment_identifier const& sr = right.seg_id; 227 228 // Sort them descending 229 return sl == sr 230 ? left.fraction < right.fraction 231 : sl < sr; 232 } 233 }; 234 235 }} // namespace detail::buffer 236 #endif // DOXYGEN_NO_DETAIL 237 238 239 }} // namespace boost::geometry 240 241 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_BUFFER_POLICIES_HPP 242