detail/overlay/approximately_equals.hpp

0001 // Boost.Geometry (aka GGL, Generic Geometry Library)
0002
0003 // Copyright (c) 2021 Barend Gehrels, Amsterdam, the Netherlands.
0004
0005 // Use, modification and distribution is subject to the Boost Software License,
0006 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008
0009 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_APPROXIMATELY_EQUALS_HPP
0010 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_APPROXIMATELY_EQUALS_HPP
0011
0012 #include <boost/geometry/core/access.hpp>
0013 #include <boost/geometry/util/math.hpp>
0014 #include <boost/geometry/util/select_coordinate_type.hpp>
0015 #include <boost/geometry/util/select_most_precise.hpp>
0016
0017 namespace boost { namespace geometry
0018 {
0019
0020 #ifndef DOXYGEN_NO_DETAIL
0021 namespace detail { namespace overlay
0022 {
0023
0024 // Value for approximately_equals used by get_cluster and sort_by_side
0025 // This is an "epsilon_multiplier" and, therefore, multiplied the epsilon
0026 // belonging to the used floating point type with this value.
0027 template <typename T>
0028 struct common_approximately_equals_epsilon_multiplier
0029 {
0030     static T value()
0031     {
0032         // The value is (a bit) arbitrary. For sort_by_side it should be large
0033         // enough to not take a point which is too close by, to calculate the
0034         // side value correctly. For get_cluster it is arbitrary as well, points
0035         // close to each other should form a cluster, which is also important
0036         // for subsequent side calculations. Points too far apart should not be
0037         // clustered.
0038         //
0039         // The value of 100 is currently considered as a sweet spot.
0040         // If the value changes (as of 2023-09-13):
0041         //   10: too small, failing unit test(s):
0042         //     - union: issue_1108
0043         //   50: this would be fine, no tests failing
0044         //   1000: this would be fine, no tests failing
0045         return T(100);
0046     }
0047 };
0048
0049 template <typename Point1, typename Point2, typename E>
0050 inline bool approximately_equals(Point1 const& a, Point2 const& b,
0051                                  E const& epsilon_multiplier)
0052 {
0053     using coor_t = typename select_coordinate_type<Point1, Point2>::type;
0054     using calc_t = typename geometry::select_most_precise<coor_t, E>::type;
0055
0056     calc_t const& a0 = geometry::get<0>(a);
0057     calc_t const& b0 = geometry::get<0>(b);
0058     calc_t const& a1 = geometry::get<1>(a);
0059     calc_t const& b1 = geometry::get<1>(b);
0060
0061     math::detail::equals_factor_policy<calc_t> policy(a0, b0, a1, b1);
0062     policy.multiply_epsilon(epsilon_multiplier);
0063
0064     return math::detail::equals_by_policy(a0, b0, policy)
0065         && math::detail::equals_by_policy(a1, b1, policy);
0066 }
0067
0068 }} // namespace detail::overlay
0069 #endif //DOXYGEN_NO_DETAIL
0070
0071
0072 }} // namespace boost::geometry
0073
0074 #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_APPROXIMATELY_EQUALS_HPP