1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. 4 // Copyright (c) 2013 Adam Wulkiewicz, Lodz, Poland. 5 6 // This file was modified by Oracle on 2013-2020. 7 // Modifications copyright (c) 2013-2020 Oracle and/or its affiliates. 8 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 9 10 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library 11 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. 12 13 // Use, modification and distribution is subject to the Boost Software License, 14 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 15 // http://www.boost.org/LICENSE_1_0.txt) 16 17 #ifndef BOOST_GEOMETRY_STRATEGY_CARTESIAN_POINT_IN_POLY_WINDING_HPP 18 #define BOOST_GEOMETRY_STRATEGY_CARTESIAN_POINT_IN_POLY_WINDING_HPP 19 20 21 #include <boost/geometry/core/tags.hpp> 22 23 #include <boost/geometry/util/math.hpp> 24 #include <boost/geometry/util/select_calculation_type.hpp> 25 26 #include <boost/geometry/strategy/cartesian/expand_point.hpp> 27 28 #include <boost/geometry/strategies/cartesian/point_in_box.hpp> 29 #include <boost/geometry/strategies/cartesian/disjoint_box_box.hpp> 30 #include <boost/geometry/strategies/cartesian/side_by_triangle.hpp> 31 #include <boost/geometry/strategies/covered_by.hpp> 32 #include <boost/geometry/strategies/within.hpp> 33 34 35 namespace boost { namespace geometry 36 { 37 38 namespace strategy { namespace within 39 { 40 41 42 /*! 43 \brief Within detection using winding rule in cartesian coordinate system. 44 \ingroup strategies 45 \tparam Point_ \tparam_point 46 \tparam PointOfSegment_ \tparam_segment_point 47 \tparam CalculationType \tparam_calculation 48 \author Barend Gehrels 49 50 \qbk{ 51 [heading See also] 52 [link geometry.reference.algorithms.within.within_3_with_strategy within (with strategy)] 53 } 54 */ 55 template 56 < 57 typename Point_ = void, // for backward compatibility 58 typename PointOfSegment_ = Point_, // for backward compatibility 59 typename CalculationType = void 60 > 61 class cartesian_winding 62 { 63 template <typename Point, typename PointOfSegment> 64 struct calculation_type 65 : select_calculation_type 66 < 67 Point, 68 PointOfSegment, 69 CalculationType 70 > 71 {}; 72 73 /*! subclass to keep state */ 74 class counter 75 { 76 int m_count; 77 bool m_touches; 78 code() const79 inline int code() const 80 { 81 return m_touches ? 0 : m_count == 0 ? -1 : 1; 82 } 83 84 public : 85 friend class cartesian_winding; 86 counter()87 inline counter() 88 : m_count(0) 89 , m_touches(false) 90 {} 91 92 }; 93 94 public: 95 typedef cartesian_tag cs_tag; 96 97 typedef side::side_by_triangle<CalculationType> side_strategy_type; 98 get_side_strategy()99 static inline side_strategy_type get_side_strategy() 100 { 101 return side_strategy_type(); 102 } 103 104 typedef expand::cartesian_point expand_point_strategy_type; 105 106 typedef typename side_strategy_type::envelope_strategy_type envelope_strategy_type; 107 get_envelope_strategy()108 static inline envelope_strategy_type get_envelope_strategy() 109 { 110 return side_strategy_type::get_envelope_strategy(); 111 } 112 113 typedef typename side_strategy_type::disjoint_strategy_type disjoint_strategy_type; 114 get_disjoint_strategy()115 static inline disjoint_strategy_type get_disjoint_strategy() 116 { 117 return side_strategy_type::get_disjoint_strategy(); 118 } 119 120 typedef typename side_strategy_type::equals_point_point_strategy_type equals_point_point_strategy_type; get_equals_point_point_strategy()121 static inline equals_point_point_strategy_type get_equals_point_point_strategy() 122 { 123 return side_strategy_type::get_equals_point_point_strategy(); 124 } 125 126 typedef disjoint::cartesian_box_box disjoint_box_box_strategy_type; get_disjoint_box_box_strategy()127 static inline disjoint_box_box_strategy_type get_disjoint_box_box_strategy() 128 { 129 return disjoint_box_box_strategy_type(); 130 } 131 132 typedef covered_by::cartesian_point_box disjoint_point_box_strategy_type; 133 134 // Typedefs and static methods to fulfill the concept 135 typedef counter state_type; 136 137 template <typename Point, typename PointOfSegment> apply(Point const & point,PointOfSegment const & s1,PointOfSegment const & s2,counter & state)138 static inline bool apply(Point const& point, 139 PointOfSegment const& s1, PointOfSegment const& s2, 140 counter& state) 141 { 142 bool eq1 = false; 143 bool eq2 = false; 144 145 int count = check_segment(point, s1, s2, state, eq1, eq2); 146 if (count != 0) 147 { 148 int side = 0; 149 if (count == 1 || count == -1) 150 { 151 side = side_equal(point, eq1 ? s1 : s2, count); 152 } 153 else // count == 2 || count == -2 154 { 155 // 1 left, -1 right 156 side = side_strategy_type::apply(s1, s2, point); 157 } 158 159 if (side == 0) 160 { 161 // Point is lying on segment 162 state.m_touches = true; 163 state.m_count = 0; 164 return false; 165 } 166 167 // Side is NEG for right, POS for left. 168 // The count is -2 for left, 2 for right (or -1/1) 169 // Side positive thus means RIGHT and LEFTSIDE or LEFT and RIGHTSIDE 170 // See accompagnying figure (TODO) 171 if (side * count > 0) 172 { 173 state.m_count += count; 174 } 175 } 176 return ! state.m_touches; 177 } 178 result(counter const & state)179 static inline int result(counter const& state) 180 { 181 return state.code(); 182 } 183 184 private: 185 template <typename Point, typename PointOfSegment> check_segment(Point const & point,PointOfSegment const & seg1,PointOfSegment const & seg2,counter & state,bool & eq1,bool & eq2)186 static inline int check_segment(Point const& point, 187 PointOfSegment const& seg1, 188 PointOfSegment const& seg2, 189 counter& state, 190 bool& eq1, bool& eq2) 191 { 192 if (check_touch(point, seg1, seg2, state, eq1, eq2)) 193 { 194 return 0; 195 } 196 197 return calculate_count(point, seg1, seg2, eq1, eq2); 198 } 199 200 template <typename Point, typename PointOfSegment> check_touch(Point const & point,PointOfSegment const & seg1,PointOfSegment const & seg2,counter & state,bool & eq1,bool & eq2)201 static inline bool check_touch(Point const& point, 202 PointOfSegment const& seg1, 203 PointOfSegment const& seg2, 204 counter& state, 205 bool& eq1, bool& eq2) 206 { 207 typedef typename calculation_type<Point, PointOfSegment>::type calc_t; 208 209 calc_t const px = get<0>(point); 210 calc_t const s1x = get<0>(seg1); 211 calc_t const s2x = get<0>(seg2); 212 213 eq1 = math::equals(s1x, px); 214 eq2 = math::equals(s2x, px); 215 216 // Both equal p -> segment vertical 217 // The only thing which has to be done is check if point is ON segment 218 if (eq1 && eq2) 219 { 220 calc_t const py = get<1>(point); 221 calc_t const s1y = get<1>(seg1); 222 calc_t const s2y = get<1>(seg2); 223 if ((s1y <= py && s2y >= py) || (s2y <= py && s1y >= py)) 224 { 225 state.m_touches = true; 226 } 227 return true; 228 } 229 return false; 230 } 231 232 template <typename Point, typename PointOfSegment> calculate_count(Point const & point,PointOfSegment const & seg1,PointOfSegment const & seg2,bool eq1,bool eq2)233 static inline int calculate_count(Point const& point, 234 PointOfSegment const& seg1, 235 PointOfSegment const& seg2, 236 bool eq1, bool eq2) 237 { 238 typedef typename calculation_type<Point, PointOfSegment>::type calc_t; 239 240 calc_t const p = get<0>(point); 241 calc_t const s1 = get<0>(seg1); 242 calc_t const s2 = get<0>(seg2); 243 244 return eq1 ? (s2 > p ? 1 : -1) // Point on level s1, E/W depending on s2 245 : eq2 ? (s1 > p ? -1 : 1) // idem 246 : s1 < p && s2 > p ? 2 // Point between s1 -> s2 --> E 247 : s2 < p && s1 > p ? -2 // Point between s2 -> s1 --> W 248 : 0; 249 } 250 251 template <typename Point, typename PointOfSegment> side_equal(Point const & point,PointOfSegment const & se,int count)252 static inline int side_equal(Point const& point, 253 PointOfSegment const& se, 254 int count) 255 { 256 // NOTE: for D=0 the signs would be reversed 257 return math::equals(get<1>(point), get<1>(se)) ? 258 0 : 259 get<1>(point) < get<1>(se) ? 260 // assuming count is equal to 1 or -1 261 -count : // ( count > 0 ? -1 : 1) : 262 count; // ( count > 0 ? 1 : -1) ; 263 } 264 }; 265 266 267 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS 268 269 namespace services 270 { 271 272 template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2> 273 struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, polygonal_tag, cartesian_tag, cartesian_tag> 274 { 275 typedef cartesian_winding<> type; 276 }; 277 278 template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2> 279 struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, linear_tag, cartesian_tag, cartesian_tag> 280 { 281 typedef cartesian_winding<> type; 282 }; 283 284 } // namespace services 285 286 #endif 287 288 289 }} // namespace strategy::within 290 291 292 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS 293 namespace strategy { namespace covered_by { namespace services 294 { 295 296 template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2> 297 struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, polygonal_tag, cartesian_tag, cartesian_tag> 298 { 299 typedef within::cartesian_winding<> type; 300 }; 301 302 template <typename PointLike, typename Geometry, typename AnyTag1, typename AnyTag2> 303 struct default_strategy<PointLike, Geometry, AnyTag1, AnyTag2, pointlike_tag, linear_tag, cartesian_tag, cartesian_tag> 304 { 305 typedef within::cartesian_winding<> type; 306 }; 307 308 }}} // namespace strategy::covered_by::services 309 #endif 310 311 312 }} // namespace boost::geometry 313 314 315 #endif // BOOST_GEOMETRY_STRATEGY_CARTESIAN_POINT_IN_POLY_WINDING_HPP 316