1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands. 4 5 // This file was modified by Oracle on 2013, 2014, 2015. 6 // Modifications Copyright (c) 2013, 2021, Oracle and/or its affiliates. 7 8 // Use, modification and distribution is subject to the Boost Software License, 9 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 10 // http://www.boost.org/LICENSE_1_0.txt) 11 12 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 13 14 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HELPERS_HPP 15 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HELPERS_HPP 16 17 #include <boost/geometry/policies/robustness/no_rescale_policy.hpp> 18 19 namespace boost { namespace geometry { 20 21 #ifndef DOXYGEN_NO_DETAIL 22 namespace detail { namespace overlay { 23 24 enum turn_position { position_middle, position_front, position_back }; 25 26 template <typename Point, typename SegmentRatio> 27 struct turn_operation_linear 28 : public turn_operation<Point, SegmentRatio> 29 { turn_operation_linearboost::geometry::detail::overlay::turn_operation_linear30 turn_operation_linear() 31 : position(position_middle) 32 , is_collinear(false) 33 {} 34 35 turn_position position; 36 bool is_collinear; // valid only for Linear geometry 37 }; 38 39 template <typename PointP, typename PointQ, 40 typename Pi = PointP, typename Pj = PointP, typename Pk = PointP, 41 typename Qi = PointQ, typename Qj = PointQ, typename Qk = PointQ 42 > 43 struct side_calculator 44 { 45 // todo: get from coordinate system 46 typedef boost::geometry::strategy::side::side_by_triangle<> side; 47 side_calculatorboost::geometry::detail::overlay::side_calculator48 inline side_calculator(Pi const& pi, Pj const& pj, Pk const& pk, 49 Qi const& qi, Qj const& qj, Qk const& qk) 50 : m_pi(pi), m_pj(pj), m_pk(pk) 51 , m_qi(qi), m_qj(qj), m_qk(qk) 52 {} 53 pk_wrt_p1boost::geometry::detail::overlay::side_calculator54 inline int pk_wrt_p1() const { return side::apply(m_pi, m_pj, m_pk); } pk_wrt_q1boost::geometry::detail::overlay::side_calculator55 inline int pk_wrt_q1() const { return side::apply(m_qi, m_qj, m_pk); } qk_wrt_p1boost::geometry::detail::overlay::side_calculator56 inline int qk_wrt_p1() const { return side::apply(m_pi, m_pj, m_qk); } qk_wrt_q1boost::geometry::detail::overlay::side_calculator57 inline int qk_wrt_q1() const { return side::apply(m_qi, m_qj, m_qk); } 58 pk_wrt_q2boost::geometry::detail::overlay::side_calculator59 inline int pk_wrt_q2() const { return side::apply(m_qj, m_qk, m_pk); } qk_wrt_p2boost::geometry::detail::overlay::side_calculator60 inline int qk_wrt_p2() const { return side::apply(m_pj, m_pk, m_qk); } 61 62 Pi const& m_pi; 63 Pj const& m_pj; 64 Pk const& m_pk; 65 Qi const& m_qi; 66 Qj const& m_qj; 67 Qk const& m_qk; 68 }; 69 70 template <typename Point1, typename Point2, typename RobustPolicy> 71 struct robust_points 72 { 73 typedef typename geometry::robust_point_type 74 < 75 Point1, RobustPolicy 76 >::type robust_point1_type; 77 78 // TODO: define robust_point2_type using Point2? 79 typedef robust_point1_type robust_point2_type; 80 robust_pointsboost::geometry::detail::overlay::robust_points81 inline robust_points(Point1 const& pi, Point1 const& pj, Point1 const& pk, 82 Point2 const& qi, Point2 const& qj, Point2 const& qk, 83 RobustPolicy const& robust_policy) 84 { 85 geometry::recalculate(m_rpi, pi, robust_policy); 86 geometry::recalculate(m_rpj, pj, robust_policy); 87 geometry::recalculate(m_rpk, pk, robust_policy); 88 geometry::recalculate(m_rqi, qi, robust_policy); 89 geometry::recalculate(m_rqj, qj, robust_policy); 90 geometry::recalculate(m_rqk, qk, robust_policy); 91 } 92 93 robust_point1_type m_rpi, m_rpj, m_rpk; 94 robust_point2_type m_rqi, m_rqj, m_rqk; 95 }; 96 97 template <typename Point1, typename Point2, typename RobustPolicy> 98 class intersection_info_base 99 : private robust_points<Point1, Point2, RobustPolicy> 100 { 101 typedef robust_points<Point1, Point2, RobustPolicy> base; 102 103 public: 104 typedef Point1 point1_type; 105 typedef Point2 point2_type; 106 107 typedef typename base::robust_point1_type robust_point1_type; 108 typedef typename base::robust_point2_type robust_point2_type; 109 110 typedef side_calculator<robust_point1_type, robust_point2_type> side_calculator_type; 111 intersection_info_base(Point1 const & pi,Point1 const & pj,Point1 const & pk,Point2 const & qi,Point2 const & qj,Point2 const & qk,RobustPolicy const & robust_policy)112 intersection_info_base(Point1 const& pi, Point1 const& pj, Point1 const& pk, 113 Point2 const& qi, Point2 const& qj, Point2 const& qk, 114 RobustPolicy const& robust_policy) 115 : base(pi, pj, pk, qi, qj, qk, robust_policy) 116 , m_side_calc(base::m_rpi, base::m_rpj, base::m_rpk, 117 base::m_rqi, base::m_rqj, base::m_rqk) 118 , m_pi(pi), m_pj(pj), m_pk(pk) 119 , m_qi(qi), m_qj(qj), m_qk(qk) 120 {} 121 pi() const122 inline Point1 const& pi() const { return m_pi; } pj() const123 inline Point1 const& pj() const { return m_pj; } pk() const124 inline Point1 const& pk() const { return m_pk; } 125 qi() const126 inline Point2 const& qi() const { return m_qi; } qj() const127 inline Point2 const& qj() const { return m_qj; } qk() const128 inline Point2 const& qk() const { return m_qk; } 129 rpi() const130 inline robust_point1_type const& rpi() const { return base::m_rpi; } rpj() const131 inline robust_point1_type const& rpj() const { return base::m_rpj; } rpk() const132 inline robust_point1_type const& rpk() const { return base::m_rpk; } 133 rqi() const134 inline robust_point2_type const& rqi() const { return base::m_rqi; } rqj() const135 inline robust_point2_type const& rqj() const { return base::m_rqj; } rqk() const136 inline robust_point2_type const& rqk() const { return base::m_rqk; } 137 sides() const138 inline side_calculator_type const& sides() const { return m_side_calc; } 139 140 private: 141 side_calculator_type m_side_calc; 142 143 point1_type const& m_pi; 144 point1_type const& m_pj; 145 point1_type const& m_pk; 146 point2_type const& m_qi; 147 point2_type const& m_qj; 148 point2_type const& m_qk; 149 }; 150 151 template <typename Point1, typename Point2> 152 class intersection_info_base<Point1, Point2, detail::no_rescale_policy> 153 { 154 public: 155 typedef Point1 point1_type; 156 typedef Point2 point2_type; 157 158 typedef Point1 robust_point1_type; 159 typedef Point2 robust_point2_type; 160 161 typedef side_calculator<Point1, Point2> side_calculator_type; 162 intersection_info_base(Point1 const & pi,Point1 const & pj,Point1 const & pk,Point2 const & qi,Point2 const & qj,Point2 const & qk,no_rescale_policy const &)163 intersection_info_base(Point1 const& pi, Point1 const& pj, Point1 const& pk, 164 Point2 const& qi, Point2 const& qj, Point2 const& qk, 165 no_rescale_policy const& /*robust_policy*/) 166 : m_side_calc(pi, pj, pk, qi, qj, qk) 167 {} 168 pi() const169 inline Point1 const& pi() const { return m_side_calc.m_pi; } pj() const170 inline Point1 const& pj() const { return m_side_calc.m_pj; } pk() const171 inline Point1 const& pk() const { return m_side_calc.m_pk; } 172 qi() const173 inline Point2 const& qi() const { return m_side_calc.m_qi; } qj() const174 inline Point2 const& qj() const { return m_side_calc.m_qj; } qk() const175 inline Point2 const& qk() const { return m_side_calc.m_qk; } 176 rpi() const177 inline Point1 const& rpi() const { return pi(); } rpj() const178 inline Point1 const& rpj() const { return pj(); } rpk() const179 inline Point1 const& rpk() const { return pk(); } 180 rqi() const181 inline Point2 const& rqi() const { return qi(); } rqj() const182 inline Point2 const& rqj() const { return qj(); } rqk() const183 inline Point2 const& rqk() const { return qk(); } 184 sides() const185 inline side_calculator_type const& sides() const { return m_side_calc; } 186 187 private: 188 side_calculator_type m_side_calc; 189 }; 190 191 192 template 193 < 194 typename Point1, 195 typename Point2, 196 typename TurnPoint, 197 typename RobustPolicy 198 > 199 class intersection_info 200 : public intersection_info_base<Point1, Point2, RobustPolicy> 201 { 202 typedef intersection_info_base<Point1, Point2, RobustPolicy> base; 203 204 typedef typename strategy_intersection 205 < 206 typename cs_tag<TurnPoint>::type, 207 Point1, 208 Point2, 209 TurnPoint, 210 RobustPolicy 211 >::segment_intersection_strategy_type strategy; 212 213 public: 214 typedef model::referring_segment<Point1 const> segment_type1; 215 typedef model::referring_segment<Point2 const> segment_type2; 216 typedef typename base::side_calculator_type side_calculator_type; 217 218 typedef typename strategy::return_type result_type; 219 typedef typename boost::tuples::element<0, result_type>::type i_info_type; // intersection_info 220 typedef typename boost::tuples::element<1, result_type>::type d_info_type; // dir_info 221 intersection_info(Point1 const & pi,Point1 const & pj,Point1 const & pk,Point2 const & qi,Point2 const & qj,Point2 const & qk,RobustPolicy const & robust_policy)222 intersection_info(Point1 const& pi, Point1 const& pj, Point1 const& pk, 223 Point2 const& qi, Point2 const& qj, Point2 const& qk, 224 RobustPolicy const& robust_policy) 225 : base(pi, pj, pk, qi, qj, qk, robust_policy) 226 , m_result(strategy::apply(segment_type1(pi, pj), 227 segment_type2(qi, qj), 228 robust_policy, 229 base::rpi(), base::rpj(), 230 base::rqi(), base::rqj())) 231 , m_robust_policy(robust_policy) 232 {} 233 result() const234 inline result_type const& result() const { return m_result; } i_info() const235 inline i_info_type const& i_info() const { return m_result.template get<0>(); } d_info() const236 inline d_info_type const& d_info() const { return m_result.template get<1>(); } 237 238 // TODO: it's more like is_spike_ip_p is_spike_p() const239 inline bool is_spike_p() const 240 { 241 if (base::sides().pk_wrt_p1() == 0) 242 { 243 if (! is_ip_j<0>()) 244 { 245 return false; 246 } 247 248 int const qk_p1 = base::sides().qk_wrt_p1(); 249 int const qk_p2 = base::sides().qk_wrt_p2(); 250 251 if (qk_p1 == -qk_p2) 252 { 253 if (qk_p1 == 0) 254 { 255 return is_spike_of_collinear(base::pi(), base::pj(), 256 base::pk()); 257 } 258 259 return true; 260 } 261 } 262 263 return false; 264 } 265 266 // TODO: it's more like is_spike_ip_q is_spike_q() const267 inline bool is_spike_q() const 268 { 269 if (base::sides().qk_wrt_q1() == 0) 270 { 271 if (! is_ip_j<1>()) 272 { 273 return false; 274 } 275 276 int const pk_q1 = base::sides().pk_wrt_q1(); 277 int const pk_q2 = base::sides().pk_wrt_q2(); 278 279 if (pk_q1 == -pk_q2) 280 { 281 if (pk_q1 == 0) 282 { 283 return is_spike_of_collinear(base::qi(), base::qj(), 284 base::qk()); 285 } 286 287 return true; 288 } 289 } 290 291 return false; 292 } 293 294 private: 295 template <typename Point> is_spike_of_collinear(Point const & i,Point const & j,Point const & k) const296 inline bool is_spike_of_collinear(Point const& i, Point const& j, 297 Point const& k) const 298 { 299 typedef model::referring_segment<Point const> seg; 300 301 typedef strategy_intersection 302 < 303 typename cs_tag<Point>::type, Point, Point, Point, RobustPolicy 304 > si; 305 306 typedef typename si::segment_intersection_strategy_type strategy; 307 308 typename strategy::return_type result 309 = strategy::apply(seg(i, j), seg(j, k), m_robust_policy); 310 311 return result.template get<0>().count == 2; 312 } 313 314 template <std::size_t OpId> is_ip_j() const315 bool is_ip_j() const 316 { 317 int arrival = d_info().arrival[OpId]; 318 bool same_dirs = d_info().dir_a == 0 && d_info().dir_b == 0; 319 320 if (same_dirs) 321 { 322 if (i_info().count == 2) 323 { 324 return arrival != -1; 325 } 326 else 327 { 328 return arrival == 0; 329 } 330 } 331 else 332 { 333 return arrival == 1; 334 } 335 } 336 337 result_type m_result; 338 RobustPolicy const& m_robust_policy; 339 }; 340 341 }} // namespace detail::overlay 342 #endif // DOXYGEN_NO_DETAIL 343 344 }} // namespace boost::geometry 345 346 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HELPERS_HPP 347