strategy/cartesian/side_non_robust.hpp

0001 // Boost.Geometry
0002
0003 // Copyright (c) 2020-2021, Oracle and/or its affiliates.
0004
0005 // Contributed and/or modified by Vissarion Fysikopoulos, on behalf of Oracle
0006
0007 // Licensed under the Boost Software License version 1.0.
0008 // http://www.boost.org/users/license.html
0009
0010 #ifndef BOOST_GEOMETRY_STRATEGY_CARTESIAN_SIDE_NON_ROBUST_HPP
0011 #define BOOST_GEOMETRY_STRATEGY_CARTESIAN_SIDE_NON_ROBUST_HPP
0012
0013 #include <boost/geometry/util/select_most_precise.hpp>
0014 #include <boost/geometry/util/select_calculation_type.hpp>
0015 #include <boost/geometry/util/precise_math.hpp>
0016
0017 #include <boost/geometry/arithmetic/determinant.hpp>
0018
0019 namespace boost { namespace geometry
0020 {
0021
0022 namespace strategy { namespace side
0023 {
0024
0025 /*!
0026 \brief Predicate to check at which side of a segment a point lies:
0027     left of segment (>0), right of segment (< 0), on segment (0).
0028 \ingroup strategies
0029 \tparam CalculationType \tparam_calculation
0030 \details This predicate determines at which side of a segment a point lies
0031 */
0032 template
0033 <
0034     typename CalculationType = void
0035 >
0036 struct side_non_robust
0037 {
0038 public:
0039     //! \brief Computes double the signed area of the CCW triangle p1, p2, p
0040     template
0041     <
0042         typename P1,
0043         typename P2,
0044         typename P
0045     >
0046     static inline int apply(P1 const& p1, P2 const& p2, P const& p)
0047     {
0048         typedef typename select_calculation_type_alt
0049             <
0050                 CalculationType,
0051                 P1,
0052                 P2,
0053                 P
0054             >::type CoordinateType;
0055         typedef typename select_most_precise
0056             <
0057                 CoordinateType,
0058                 double
0059             >::type PromotedType;
0060
0061         CoordinateType const x = get<0>(p);
0062         CoordinateType const y = get<1>(p);
0063
0064         CoordinateType const sx1 = get<0>(p1);
0065         CoordinateType const sy1 = get<1>(p1);
0066         CoordinateType const sx2 = get<0>(p2);
0067         CoordinateType const sy2 = get<1>(p2);
0068
0069         //non-robust 1
0070         //the following is 2x slower in some generic cases when compiled with g++
0071         //(tested versions 9 and 10)
0072         //
0073         //auto detleft = (sx1 - x) * (sy2 - y);
0074         //auto detright = (sy1 - y) * (sx2 - x);
0075         //return detleft > detright ? 1 : (detleft < detright ? -1 : 0 );
0076
0077         //non-robust 2
0078         PromotedType const dx = sx2 - sx1;
0079         PromotedType const dy = sy2 - sy1;
0080         PromotedType const dpx = x - sx1;
0081         PromotedType const dpy = y - sy1;
0082
0083         PromotedType sv = geometry::detail::determinant<PromotedType>
0084                 (
0085                     dx, dy,
0086                     dpx, dpy
0087                 );
0088         PromotedType const zero = PromotedType();
0089
0090         return sv == zero ? 0 : sv > zero ? 1 : -1;
0091     }
0092
0093 };
0094
0095 }} // namespace strategy::side
0096
0097 }} // namespace boost::geometry
0098
0099 #endif // BOOST_GEOMETRY_STRATEGY_CARTESIAN_SIDE_NON_ROBUST_HPP