strategy/cartesian/in_circle_robust.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2019 Tinko Bartels, Berlin, Germany.
0004
0005 // Contributed and/or modified by Tinko Bartels,
0006 //   as part of Google Summer of Code 2019 program.
0007
0008 // Use, modification and distribution is subject to the Boost Software License,
0009 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0010 // http://www.boost.org/LICENSE_1_0.txt)
0011
0012 #ifndef BOOST_GEOMETRY_STRATEGY_CARTESIAN_IN_CIRCLE_ROBUST_HPP
0013 #define BOOST_GEOMETRY_STRATEGY_CARTESIAN_IN_CIRCLE_ROBUST_HPP
0014
0015 #include<boost/geometry/util/precise_math.hpp>
0016
0017 namespace boost { namespace geometry
0018 {
0019
0020 namespace strategy { namespace in_circle
0021 {
0022
0023 /*!
0024 \brief Adaptive precision predicate to check whether a fourth point lies inside the circumcircle of the first three points:
0025     inside (>0), outside (< 0), on the boundary (0).
0026 \ingroup strategies
0027 \tparam CalculationType \tparam_calculation (numeric_limits<ct>::epsilon() and numeric_limits<ct>::digits must be supported for calculation type ct)
0028 \tparam Robustness std::size_t value from 0 (fastest) to 2 (default, most precise).
0029 \details This predicate determines whether a fourth point lies inside the circumcircle of the first three points using an algorithm that is adapted from incircle as described in "Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates" by Jonathan Richard Shewchuk ( https://dl.acm.org/citation.cfm?doid=237218.237337 ). More information and copies of the paper can also be found at https://www.cs.cmu.edu/~quake/robust.html . It is designed to be adaptive in the sense that it should be fast for inputs that lead to correct results with plain float operations but robust for inputs that require higher precision arithmetics.
0030  */
0031 template <typename CalculationType = double, std::size_t Robustness = 2>
0032 class in_circle_robust
0033 {
0034 public:
0035     template <typename P1, typename P2, typename P3, typename P>
0036     static inline int apply(P1 const& p1, P2 const& p2, P3 const& p3, P const& p)
0037     {
0038         std::array<CalculationType, 2> pa {
0039             { boost::geometry::get<0>(p1), boost::geometry::get<1>(p1) }};
0040         std::array<CalculationType, 2> pb {
0041             { boost::geometry::get<0>(p2), boost::geometry::get<1>(p2) }};
0042         std::array<CalculationType, 2> pc {
0043             { boost::geometry::get<0>(p3), boost::geometry::get<1>(p3) }};
0044         std::array<CalculationType, 2> pd {
0045             { boost::geometry::get<0>(p), boost::geometry::get<1>(p) }};
0046         CalculationType det =
0047             boost::geometry::detail::precise_math::incircle
0048                 <
0049                     CalculationType,
0050                     Robustness
0051                 >(pa, pb, pc, pd);
0052         return det > 0 ? 1
0053                        : det < 0 ? -1 : 0;
0054     }
0055
0056 };
0057
0058 } // namespace in_circle
0059
0060 } // namespace strategy
0061
0062 }} // namespace boost::geometry::strategy
0063
0064 #endif // BOOST_GEOMETRY_STRATEGY_CARTESIAN_IN_CIRCLE_ROBUST_HPP