Chris@16: // Boost.Geometry (aka GGL, Generic Geometry Library)
Chris@16: 
Chris@101: // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
Chris@101: // Copyright (c) 2008-2015 Bruno Lalande, Paris, France.
Chris@101: // Copyright (c) 2009-2015 Mateusz Loskot, London, UK.
Chris@101: 
Chris@101: // This file was modified by Oracle on 2015.
Chris@101: // Modifications copyright (c) 2015, Oracle and/or its affiliates.
Chris@101: 
Chris@101: // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
Chris@16: 
Chris@16: // Parts of Boost.Geometry are redesigned from Geodan's Geographic Library
Chris@16: // (geolib/GGL), copyright (c) 1995-2010 Geodan, Amsterdam, the Netherlands.
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software License,
Chris@16: // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GEOMETRY_STRATEGIES_CARTESIAN_SIDE_BY_TRIANGLE_HPP
Chris@16: #define BOOST_GEOMETRY_STRATEGIES_CARTESIAN_SIDE_BY_TRIANGLE_HPP
Chris@16: 
Chris@16: #include <boost/mpl/if.hpp>
Chris@16: #include <boost/type_traits.hpp>
Chris@16: 
Chris@16: #include <boost/geometry/arithmetic/determinant.hpp>
Chris@16: #include <boost/geometry/core/access.hpp>
Chris@16: #include <boost/geometry/util/select_coordinate_type.hpp>
Chris@16: #include <boost/geometry/strategies/side.hpp>
Chris@16: 
Chris@101: #include <boost/geometry/algorithms/detail/relate/less.hpp>
Chris@101: #include <boost/geometry/algorithms/detail/equals/point_point.hpp>
Chris@101: 
Chris@16: 
Chris@16: namespace boost { namespace geometry
Chris@16: {
Chris@16: 
Chris@16: namespace strategy { namespace side
Chris@16: {
Chris@16: 
Chris@16: /*!
Chris@16: \brief Check at which side of a segment a point lies:
Chris@16:     left of segment (> 0), right of segment (< 0), on segment (0)
Chris@16: \ingroup strategies
Chris@16: \tparam CalculationType \tparam_calculation
Chris@16:  */
Chris@16: template <typename CalculationType = void>
Chris@16: class side_by_triangle
Chris@16: {
Chris@101:     template <typename Policy>
Chris@101:     struct eps_policy
Chris@101:     {
Chris@101:         eps_policy() {}
Chris@101:         template <typename Type>
Chris@101:         eps_policy(Type const& a, Type const& b, Type const& c, Type const& d)
Chris@101:             : policy(a, b, c, d)
Chris@101:         {}
Chris@101:         Policy policy;
Chris@101:     };
Chris@101: 
Chris@101:     struct eps_empty
Chris@101:     {
Chris@101:         eps_empty() {}
Chris@101:         template <typename Type>
Chris@101:         eps_empty(Type const&, Type const&, Type const&, Type const&) {}
Chris@101:     };
Chris@101: 
Chris@16: public :
Chris@16: 
Chris@16:     // Template member function, because it is not always trivial
Chris@16:     // or convenient to explicitly mention the typenames in the
Chris@16:     // strategy-struct itself.
Chris@16: 
Chris@16:     // Types can be all three different. Therefore it is
Chris@16:     // not implemented (anymore) as "segment"
Chris@16: 
Chris@101:     template
Chris@101:     <
Chris@101:         typename CoordinateType,
Chris@101:         typename PromotedType,
Chris@101:         typename P1,
Chris@101:         typename P2,
Chris@101:         typename P,
Chris@101:         typename EpsPolicy
Chris@101:     >
Chris@101:     static inline
Chris@101:     PromotedType side_value(P1 const& p1, P2 const& p2, P const& p, EpsPolicy & eps_policy)
Chris@101:     {
Chris@101:         CoordinateType const x = get<0>(p);
Chris@101:         CoordinateType const y = get<1>(p);
Chris@101: 
Chris@101:         CoordinateType const sx1 = get<0>(p1);
Chris@101:         CoordinateType const sy1 = get<1>(p1);
Chris@101:         CoordinateType const sx2 = get<0>(p2);
Chris@101:         CoordinateType const sy2 = get<1>(p2);
Chris@101: 
Chris@101:         PromotedType const dx = sx2 - sx1;
Chris@101:         PromotedType const dy = sy2 - sy1;
Chris@101:         PromotedType const dpx = x - sx1;
Chris@101:         PromotedType const dpy = y - sy1;
Chris@101: 
Chris@101:         eps_policy = EpsPolicy(dx, dy, dpx, dpy);
Chris@101: 
Chris@101:         return geometry::detail::determinant<PromotedType>
Chris@101:                 (
Chris@101:                     dx, dy,
Chris@101:                     dpx, dpy
Chris@101:                 );
Chris@101: 
Chris@101:     }
Chris@101: 
Chris@101:     template
Chris@101:     <
Chris@101:         typename CoordinateType,
Chris@101:         typename PromotedType,
Chris@101:         typename P1,
Chris@101:         typename P2,
Chris@101:         typename P
Chris@101:     >
Chris@101:     static inline
Chris@101:     PromotedType side_value(P1 const& p1, P2 const& p2, P const& p)
Chris@101:     {
Chris@101:         eps_empty dummy;
Chris@101:         return side_value<CoordinateType, PromotedType>(p1, p2, p, dummy);
Chris@101:     }
Chris@101: 
Chris@101: 
Chris@101:     template
Chris@101:     <
Chris@101:         typename CoordinateType,
Chris@101:         typename PromotedType,
Chris@101:         bool AreAllIntegralCoordinates
Chris@101:     >
Chris@101:     struct compute_side_value
Chris@101:     {
Chris@101:         template <typename P1, typename P2, typename P, typename EpsPolicy>
Chris@101:         static inline PromotedType apply(P1 const& p1, P2 const& p2, P const& p, EpsPolicy & epsp)
Chris@101:         {
Chris@101:             return side_value<CoordinateType, PromotedType>(p1, p2, p, epsp);
Chris@101:         }
Chris@101:     };
Chris@101: 
Chris@101:     template <typename CoordinateType, typename PromotedType>
Chris@101:     struct compute_side_value<CoordinateType, PromotedType, false>
Chris@101:     {
Chris@101:         template <typename P1, typename P2, typename P, typename EpsPolicy>
Chris@101:         static inline PromotedType apply(P1 const& p1, P2 const& p2, P const& p, EpsPolicy & epsp)
Chris@101:         {
Chris@101:             // For robustness purposes, first check if any two points are
Chris@101:             // the same; in this case simply return that the points are
Chris@101:             // collinear
Chris@101:             if (geometry::detail::equals::equals_point_point(p1, p2)
Chris@101:                 || geometry::detail::equals::equals_point_point(p1, p)
Chris@101:                 || geometry::detail::equals::equals_point_point(p2, p))
Chris@101:             {
Chris@101:                 return PromotedType(0);
Chris@101:             }
Chris@101: 
Chris@101:             // The side_by_triangle strategy computes the signed area of
Chris@101:             // the point triplet (p1, p2, p); as such it is (in theory)
Chris@101:             // invariant under cyclic permutations of its three arguments.
Chris@101:             //
Chris@101:             // In the context of numerical errors that arise in
Chris@101:             // floating-point computations, and in order to make the strategy
Chris@101:             // consistent with respect to cyclic permutations of its three
Chris@101:             // arguments, we cyclically permute them so that the first
Chris@101:             // argument is always the lexicographically smallest point.
Chris@101: 
Chris@101:             geometry::detail::relate::less less;
Chris@101:             if (less(p, p1))
Chris@101:             {
Chris@101:                 if (less(p, p2))
Chris@101:                 {
Chris@101:                     // p is the lexicographically smallest
Chris@101:                     return side_value<CoordinateType, PromotedType>(p, p1, p2, epsp);
Chris@101:                 }
Chris@101:                 else
Chris@101:                 {
Chris@101:                     // p2 is the lexicographically smallest
Chris@101:                     return side_value<CoordinateType, PromotedType>(p2, p, p1, epsp);
Chris@101:                 }
Chris@101:             }
Chris@101: 
Chris@101:             if (less(p1, p2))
Chris@101:             {
Chris@101:                 // p1 is the lexicographically smallest
Chris@101:                 return side_value<CoordinateType, PromotedType>(p1, p2, p, epsp);
Chris@101:             }
Chris@101:             else
Chris@101:             {
Chris@101:                 // p2 is the lexicographically smallest
Chris@101:                 return side_value<CoordinateType, PromotedType>(p2, p, p1, epsp);
Chris@101:             }
Chris@101:         }
Chris@101:     };
Chris@101: 
Chris@101: 
Chris@16:     template <typename P1, typename P2, typename P>
Chris@16:     static inline int apply(P1 const& p1, P2 const& p2, P const& p)
Chris@16:     {
Chris@101:         typedef typename coordinate_type<P1>::type coordinate_type1;
Chris@101:         typedef typename coordinate_type<P2>::type coordinate_type2;
Chris@101:         typedef typename coordinate_type<P>::type coordinate_type3;
Chris@101: 
Chris@16:         typedef typename boost::mpl::if_c
Chris@16:             <
Chris@16:                 boost::is_void<CalculationType>::type::value,
Chris@16:                 typename select_most_precise
Chris@16:                     <
Chris@16:                         typename select_most_precise
Chris@16:                             <
Chris@101:                                 coordinate_type1, coordinate_type2
Chris@16:                             >::type,
Chris@101:                         coordinate_type3
Chris@16:                     >::type,
Chris@16:                 CalculationType
Chris@16:             >::type coordinate_type;
Chris@16: 
Chris@16:         // Promote float->double, small int->int
Chris@16:         typedef typename select_most_precise
Chris@16:             <
Chris@16:                 coordinate_type,
Chris@16:                 double
Chris@16:             >::type promoted_type;
Chris@16: 
Chris@101:         bool const are_all_integral_coordinates =
Chris@101:             boost::is_integral<coordinate_type1>::value
Chris@101:             && boost::is_integral<coordinate_type2>::value
Chris@101:             && boost::is_integral<coordinate_type3>::value;
Chris@16: 
Chris@101:         eps_policy< math::detail::equals_factor_policy<promoted_type> > epsp;
Chris@101:         promoted_type s = compute_side_value
Chris@101:             <
Chris@101:                 coordinate_type, promoted_type, are_all_integral_coordinates
Chris@101:             >::apply(p1, p2, p, epsp);
Chris@16: 
Chris@16:         promoted_type const zero = promoted_type();
Chris@101:         return math::detail::equals_by_policy(s, zero, epsp.policy) ? 0
Chris@101:             : s > zero ? 1
Chris@16:             : -1;
Chris@16:     }
Chris@101: 
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: #ifndef DOXYGEN_NO_STRATEGY_SPECIALIZATIONS
Chris@16: namespace services
Chris@16: {
Chris@16: 
Chris@16: template <typename CalculationType>
Chris@16: struct default_strategy<cartesian_tag, CalculationType>
Chris@16: {
Chris@16:     typedef side_by_triangle<CalculationType> type;
Chris@16: };
Chris@16: 
Chris@16: }
Chris@16: #endif
Chris@16: 
Chris@16: }} // namespace strategy::side
Chris@16: 
Chris@16: }} // namespace boost::geometry
Chris@16: 
Chris@16: 
Chris@16: #endif // BOOST_GEOMETRY_STRATEGIES_CARTESIAN_SIDE_BY_TRIANGLE_HPP