ceph/src/boost/boost/geometry/strategies/cartesian/side_by_triangle.hpp

   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     {
  58         eps_policy() {}
  59         template <typename Type>
  60         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     {
  68         eps_empty() {}
  69         template <typename Type>
  70         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
  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
  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;
  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
 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
 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>
 163         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>
 173         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>
 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>
 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