1 // Boost.Geometry (aka GGL, Generic Geometry Library) 2 3 // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands. 4 // Copyright (c) 2008-2015 Bruno Lalande, Paris, France. 5 // Copyright (c) 2009-2015 Mateusz Loskot, London, UK. 6 7 // This file was modified by Oracle on 2015, 2017, 2018, 2019. 8 // Modifications copyright (c) 2015-2019, Oracle and/or its affiliates. 9 10 // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle 11 // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle 12 13 // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library 14 // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands. 15 16 // Use, modification and distribution is subject to the Boost Software License, 17 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 18 // http://www.boost.org/LICENSE_1_0.txt) 19 20 #ifndef BOOST_GEOMETRY_STRATEGIES_CARTESIAN_SIDE_BY_TRIANGLE_HPP 21 #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_SIDE_BY_TRIANGLE_HPP 22 23 #include <boost/mpl/if.hpp> 24 #include <boost/type_traits/is_integral.hpp> 25 #include <boost/type_traits/is_void.hpp> 26 27 #include <boost/geometry/arithmetic/determinant.hpp> 28 #include <boost/geometry/core/access.hpp> 29 #include <boost/geometry/util/select_coordinate_type.hpp> 30 31 #include <boost/geometry/strategies/cartesian/disjoint_segment_box.hpp> 32 #include <boost/geometry/strategies/cartesian/envelope.hpp> 33 #include <boost/geometry/strategies/cartesian/point_in_point.hpp> 34 #include <boost/geometry/strategies/compare.hpp> 35 #include <boost/geometry/strategies/side.hpp> 36 37 #include <boost/geometry/algorithms/detail/equals/point_point.hpp> 38 39 40 namespace boost { namespace geometry 41 { 42 43 namespace strategy { namespace side 44 { 45 46 /*! 47 \brief Check at which side of a segment a point lies: 48 left of segment (> 0), right of segment (< 0), on segment (0) 49 \ingroup strategies 50 \tparam CalculationType \tparam_calculation 51 */ 52 template <typename CalculationType = void> 53 class side_by_triangle 54 { 55 template <typename Policy> 56 struct eps_policy 57 { eps_policyboost::geometry::strategy::side::side_by_triangle::eps_policy58 eps_policy() {} 59 template <typename Type> eps_policyboost::geometry::strategy::side::side_by_triangle::eps_policy60 eps_policy(Type const& a, Type const& b, Type const& c, Type const& d) 61 : policy(a, b, c, d) 62 {} 63 Policy policy; 64 }; 65 66 struct eps_empty 67 { eps_emptyboost::geometry::strategy::side::side_by_triangle::eps_empty68 eps_empty() {} 69 template <typename Type> eps_emptyboost::geometry::strategy::side::side_by_triangle::eps_empty70 eps_empty(Type const&, Type const&, Type const&, Type const&) {} 71 }; 72 73 public : 74 typedef cartesian_tag cs_tag; 75 76 typedef strategy::envelope::cartesian<CalculationType> envelope_strategy_type; 77 get_envelope_strategy()78 static inline envelope_strategy_type get_envelope_strategy() 79 { 80 return envelope_strategy_type(); 81 } 82 83 typedef strategy::disjoint::segment_box disjoint_strategy_type; 84 get_disjoint_strategy()85 static inline disjoint_strategy_type get_disjoint_strategy() 86 { 87 return disjoint_strategy_type(); 88 } 89 90 typedef strategy::within::cartesian_point_point equals_point_point_strategy_type; get_equals_point_point_strategy()91 static inline equals_point_point_strategy_type get_equals_point_point_strategy() 92 { 93 return equals_point_point_strategy_type(); 94 } 95 96 // Template member function, because it is not always trivial 97 // or convenient to explicitly mention the typenames in the 98 // strategy-struct itself. 99 100 // Types can be all three different. Therefore it is 101 // not implemented (anymore) as "segment" 102 103 template 104 < 105 typename CoordinateType, 106 typename PromotedType, 107 typename P1, 108 typename P2, 109 typename P, 110 typename EpsPolicy 111 > 112 static inline side_value(P1 const & p1,P2 const & p2,P const & p,EpsPolicy & eps_policy)113 PromotedType side_value(P1 const& p1, P2 const& p2, P const& p, EpsPolicy & eps_policy) 114 { 115 CoordinateType const x = get<0>(p); 116 CoordinateType const y = get<1>(p); 117 118 CoordinateType const sx1 = get<0>(p1); 119 CoordinateType const sy1 = get<1>(p1); 120 CoordinateType const sx2 = get<0>(p2); 121 CoordinateType const sy2 = get<1>(p2); 122 123 PromotedType const dx = sx2 - sx1; 124 PromotedType const dy = sy2 - sy1; 125 PromotedType const dpx = x - sx1; 126 PromotedType const dpy = y - sy1; 127 128 eps_policy = EpsPolicy(dx, dy, dpx, dpy); 129 130 return geometry::detail::determinant<PromotedType> 131 ( 132 dx, dy, 133 dpx, dpy 134 ); 135 136 } 137 138 template 139 < 140 typename CoordinateType, 141 typename PromotedType, 142 typename P1, 143 typename P2, 144 typename P 145 > 146 static inline side_value(P1 const & p1,P2 const & p2,P const & p)147 PromotedType side_value(P1 const& p1, P2 const& p2, P const& p) 148 { 149 eps_empty dummy; 150 return side_value<CoordinateType, PromotedType>(p1, p2, p, dummy); 151 } 152 153 154 template 155 < 156 typename CoordinateType, 157 typename PromotedType, 158 bool AreAllIntegralCoordinates 159 > 160 struct compute_side_value 161 { 162 template <typename P1, typename P2, typename P, typename EpsPolicy> applyboost::geometry::strategy::side::side_by_triangle::compute_side_value163 static inline PromotedType apply(P1 const& p1, P2 const& p2, P const& p, EpsPolicy & epsp) 164 { 165 return side_value<CoordinateType, PromotedType>(p1, p2, p, epsp); 166 } 167 }; 168 169 template <typename CoordinateType, typename PromotedType> 170 struct compute_side_value<CoordinateType, PromotedType, false> 171 { 172 template <typename P1, typename P2, typename P, typename EpsPolicy> applyboost::geometry::strategy::side::side_by_triangle::compute_side_value173 static inline PromotedType apply(P1 const& p1, P2 const& p2, P const& p, EpsPolicy & epsp) 174 { 175 // For robustness purposes, first check if any two points are 176 // the same; in this case simply return that the points are 177 // collinear 178 if (equals_point_point(p1, p2) 179 || equals_point_point(p1, p) 180 || equals_point_point(p2, p)) 181 { 182 return PromotedType(0); 183 } 184 185 // The side_by_triangle strategy computes the signed area of 186 // the point triplet (p1, p2, p); as such it is (in theory) 187 // invariant under cyclic permutations of its three arguments. 188 // 189 // In the context of numerical errors that arise in 190 // floating-point computations, and in order to make the strategy 191 // consistent with respect to cyclic permutations of its three 192 // arguments, we cyclically permute them so that the first 193 // argument is always the lexicographically smallest point. 194 195 typedef compare::cartesian<compare::less> less; 196 197 if (less::apply(p, p1)) 198 { 199 if (less::apply(p, p2)) 200 { 201 // p is the lexicographically smallest 202 return side_value<CoordinateType, PromotedType>(p, p1, p2, epsp); 203 } 204 else 205 { 206 // p2 is the lexicographically smallest 207 return side_value<CoordinateType, PromotedType>(p2, p, p1, epsp); 208 } 209 } 210 211 if (less::apply(p1, p2)) 212 { 213 // p1 is the lexicographically smallest 214 return side_value<CoordinateType, PromotedType>(p1, p2, p, epsp); 215 } 216 else 217 { 218 // p2 is the lexicographically smallest 219 return side_value<CoordinateType, PromotedType>(p2, p, p1, epsp); 220 } 221 } 222 }; 223 224 225 template <typename P1, typename P2, typename P> apply(P1 const & p1,P2 const & p2,P const & p)226 static inline int apply(P1 const& p1, P2 const& p2, P const& p) 227 { 228 typedef typename coordinate_type<P1>::type coordinate_type1; 229 typedef typename coordinate_type<P2>::type coordinate_type2; 230 typedef typename coordinate_type<P>::type coordinate_type3; 231 232 typedef typename boost::mpl::if_c 233 < 234 boost::is_void<CalculationType>::type::value, 235 typename select_most_precise 236 < 237 typename select_most_precise 238 < 239 coordinate_type1, coordinate_type2 240 >::type, 241 coordinate_type3 242 >::type, 243 CalculationType 244 >::type coordinate_type; 245 246 // Promote float->double, small int->int 247 typedef typename select_most_precise 248 < 249 coordinate_type, 250 double 251 >::type promoted_type; 252 253 bool const are_all_integral_coordinates = 254 boost::is_integral<coordinate_type1>::value 255 && boost::is_integral<coordinate_type2>::value 256 && boost::is_integral<coordinate_type3>::value; 257 258 eps_policy< math::detail::equals_factor_policy<promoted_type> > epsp; 259 promoted_type s = compute_side_value 260 < 261 coordinate_type, promoted_type, are_all_integral_coordinates 262 >::apply(p1, p2, p, epsp); 263 264 promoted_type const zero = promoted_type(); 265 return math::detail::equals_by_policy(s, zero, epsp.policy) ? 0 266 : s > zero ? 1 267 : -1; 268 } 269 270 private: 271 template <typename P1, typename P2> equals_point_point(P1 const & p1,P2 const & p2)272 static inline bool equals_point_point(P1 const& p1, P2 const& p2) 273 { 274 typedef equals_point_point_strategy_type strategy_t; 275 return geometry::detail::equals::equals_point_point(p1, p2, strategy_t()); 276 } 277 }; 278 279 280 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS 281 namespace services 282 { 283 284 template <typename CalculationType> 285 struct default_strategy<cartesian_tag, CalculationType> 286 { 287 typedef side_by_triangle<CalculationType> type; 288 }; 289 290 } 291 #endif 292 293 }} // namespace strategy::side 294 295 }} // namespace boost::geometry 296 297 298 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_SIDE_BY_TRIANGLE_HPP 299