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.
   8 // Modifications copyright (c) 2015-2017, 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_segment.hpp>
  33 #include <boost/geometry/strategies/compare.hpp>
  34 #include <boost/geometry/strategies/side.hpp>
  35
  36 #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
  37
  38
  39 namespace boost { namespace geometry
  40 {
  41
  42 namespace strategy { namespace side
  43 {
  44
  45 /*!
  46 \brief Check at which side of a segment a point lies:
  47     left of segment (> 0), right of segment (< 0), on segment (0)
  48 \ingroup strategies
  49 \tparam CalculationType \tparam_calculation
  50  */
  51 template <typename CalculationType = void>
  52 class side_by_triangle
  53 {
  54     template <typename Policy>
  55     struct eps_policy
  56     {
  57         eps_policy() {}
  58         template <typename Type>
  59         eps_policy(Type const& a, Type const& b, Type const& c, Type const& d)
  60             : policy(a, b, c, d)
  61         {}
  62         Policy policy;
  63     };
  64
  65     struct eps_empty
  66     {
  67         eps_empty() {}
  68         template <typename Type>
  69         eps_empty(Type const&, Type const&, Type const&, Type const&) {}
  70     };
  71
  72 public :
  73     typedef strategy::envelope::cartesian_segment<CalculationType> envelope_strategy_type;
  74
  75     static inline envelope_strategy_type get_envelope_strategy()
  76     {
  77         return envelope_strategy_type();
  78     }
  79
  80     typedef strategy::disjoint::segment_box disjoint_strategy_type;
  81
  82     static inline disjoint_strategy_type get_disjoint_strategy()
  83     {
  84         return disjoint_strategy_type();
  85     }
  86
  87     // Template member function, because it is not always trivial
  88     // or convenient to explicitly mention the typenames in the
  89     // strategy-struct itself.
  90
  91     // Types can be all three different. Therefore it is
  92     // not implemented (anymore) as "segment"
  93
  94     template
  95     <
  96         typename CoordinateType,
  97         typename PromotedType,
  98         typename P1,
  99         typename P2,
 100         typename P,
 101         typename EpsPolicy
 102     >
 103     static inline
 104     PromotedType side_value(P1 const& p1, P2 const& p2, P const& p, EpsPolicy & eps_policy)
 105     {
 106         CoordinateType const x = get<0>(p);
 107         CoordinateType const y = get<1>(p);
 108
 109         CoordinateType const sx1 = get<0>(p1);
 110         CoordinateType const sy1 = get<1>(p1);
 111         CoordinateType const sx2 = get<0>(p2);
 112         CoordinateType const sy2 = get<1>(p2);
 113
 114         PromotedType const dx = sx2 - sx1;
 115         PromotedType const dy = sy2 - sy1;
 116         PromotedType const dpx = x - sx1;
 117         PromotedType const dpy = y - sy1;
 118
 119         eps_policy = EpsPolicy(dx, dy, dpx, dpy);
 120
 121         return geometry::detail::determinant<PromotedType>
 122                 (
 123                     dx, dy,
 124                     dpx, dpy
 125                 );
 126
 127     }
 128
 129     template
 130     <
 131         typename CoordinateType,
 132         typename PromotedType,
 133         typename P1,
 134         typename P2,
 135         typename P
 136     >
 137     static inline
 138     PromotedType side_value(P1 const& p1, P2 const& p2, P const& p)
 139     {
 140         eps_empty dummy;
 141         return side_value<CoordinateType, PromotedType>(p1, p2, p, dummy);
 142     }
 143
 144
 145     template
 146     <
 147         typename CoordinateType,
 148         typename PromotedType,
 149         bool AreAllIntegralCoordinates
 150     >
 151     struct compute_side_value
 152     {
 153         template <typename P1, typename P2, typename P, typename EpsPolicy>
 154         static inline PromotedType apply(P1 const& p1, P2 const& p2, P const& p, EpsPolicy & epsp)
 155         {
 156             return side_value<CoordinateType, PromotedType>(p1, p2, p, epsp);
 157         }
 158     };
 159
 160     template <typename CoordinateType, typename PromotedType>
 161     struct compute_side_value<CoordinateType, PromotedType, false>
 162     {
 163         template <typename P1, typename P2, typename P, typename EpsPolicy>
 164         static inline PromotedType apply(P1 const& p1, P2 const& p2, P const& p, EpsPolicy & epsp)
 165         {
 166             // For robustness purposes, first check if any two points are
 167             // the same; in this case simply return that the points are
 168             // collinear
 169             if (geometry::detail::equals::equals_point_point(p1, p2)
 170                 || geometry::detail::equals::equals_point_point(p1, p)
 171                 || geometry::detail::equals::equals_point_point(p2, p))
 172             {
 173                 return PromotedType(0);
 174             }
 175
 176             // The side_by_triangle strategy computes the signed area of
 177             // the point triplet (p1, p2, p); as such it is (in theory)
 178             // invariant under cyclic permutations of its three arguments.
 179             //
 180             // In the context of numerical errors that arise in
 181             // floating-point computations, and in order to make the strategy
 182             // consistent with respect to cyclic permutations of its three
 183             // arguments, we cyclically permute them so that the first
 184             // argument is always the lexicographically smallest point.
 185
 186             typedef compare::cartesian<compare::less> less;
 187
 188             if (less::apply(p, p1))
 189             {
 190                 if (less::apply(p, p2))
 191                 {
 192                     // p is the lexicographically smallest
 193                     return side_value<CoordinateType, PromotedType>(p, p1, p2, epsp);
 194                 }
 195                 else
 196                 {
 197                     // p2 is the lexicographically smallest
 198                     return side_value<CoordinateType, PromotedType>(p2, p, p1, epsp);
 199                 }
 200             }
 201
 202             if (less::apply(p1, p2))
 203             {
 204                 // p1 is the lexicographically smallest
 205                 return side_value<CoordinateType, PromotedType>(p1, p2, p, epsp);
 206             }
 207             else
 208             {
 209                 // p2 is the lexicographically smallest
 210                 return side_value<CoordinateType, PromotedType>(p2, p, p1, epsp);
 211             }
 212         }
 213     };
 214
 215
 216     template <typename P1, typename P2, typename P>
 217     static inline int apply(P1 const& p1, P2 const& p2, P const& p)
 218     {
 219         typedef typename coordinate_type<P1>::type coordinate_type1;
 220         typedef typename coordinate_type<P2>::type coordinate_type2;
 221         typedef typename coordinate_type<P>::type coordinate_type3;
 222
 223         typedef typename boost::mpl::if_c
 224             <
 225                 boost::is_void<CalculationType>::type::value,
 226                 typename select_most_precise
 227                     <
 228                         typename select_most_precise
 229                             <
 230                                 coordinate_type1, coordinate_type2
 231                             >::type,
 232                         coordinate_type3
 233                     >::type,
 234                 CalculationType
 235             >::type coordinate_type;
 236
 237         // Promote float->double, small int->int
 238         typedef typename select_most_precise
 239             <
 240                 coordinate_type,
 241                 double
 242             >::type promoted_type;
 243
 244         bool const are_all_integral_coordinates =
 245             boost::is_integral<coordinate_type1>::value
 246             && boost::is_integral<coordinate_type2>::value
 247             && boost::is_integral<coordinate_type3>::value;
 248
 249         eps_policy< math::detail::equals_factor_policy<promoted_type> > epsp;
 250         promoted_type s = compute_side_value
 251             <
 252                 coordinate_type, promoted_type, are_all_integral_coordinates
 253             >::apply(p1, p2, p, epsp);
 254
 255         promoted_type const zero = promoted_type();
 256         return math::detail::equals_by_policy(s, zero, epsp.policy) ? 0
 257             : s > zero ? 1
 258             : -1;
 259     }
 260
 261 };
 262
 263
 264 #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
 265 namespace services
 266 {
 267
 268 template <typename CalculationType>
 269 struct default_strategy<cartesian_tag, CalculationType>
 270 {
 271     typedef side_by_triangle<CalculationType> type;
 272 };
 273
 274 }
 275 #endif
 276
 277 }} // namespace strategy::side
 278
 279 }} // namespace boost::geometry
 280
 281
 282 #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_SIDE_BY_TRIANGLE_HPP