update ceph source to reef 18.1.2

[ceph.git] / ceph / src / boost / boost / geometry / algorithms / detail / buffer / line_line_intersection.hpp

diff --git a/ceph/src/boost/boost/geometry/algorithms/detail/buffer/line_line_intersection.hpp b/ceph/src/boost/boost/geometry/algorithms/detail/buffer/line_line_intersection.hpp
index 94c8bf3b3a2034a695ce8a3c251155e65f074e4c..f1014c9bb450975b8b7251d2707d0d62ea75f66c 100644 (file)
--- a/ceph/src/boost/boost/geometry/algorithms/detail/buffer/line_line_intersection.hpp
+++ b/ceph/src/boost/boost/geometry/algorithms/detail/buffer/line_line_intersection.hpp
@@ -9,12 +9,9 @@
 #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_LINE_LINE_INTERSECTION_HPP
 #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_LINE_LINE_INTERSECTION_HPP
 
-#include <boost/geometry/core/assert.hpp>
-#include <boost/geometry/arithmetic/infinite_line_functions.hpp>
 #include <boost/geometry/algorithms/detail/make/make.hpp>
-
-#include <boost/core/ignore_unused.hpp>
-
+#include <boost/geometry/arithmetic/infinite_line_functions.hpp>
+#include <boost/geometry/util/math.hpp>
 
 namespace boost { namespace geometry
 {
@@ -24,23 +21,91 @@ namespace boost { namespace geometry
 namespace detail { namespace buffer
 {
 
-// TODO: this might once be changed to a proper strategy
 struct line_line_intersection
 {
     template <typename Point>
-    static inline bool
-    apply(Point const& pi, Point const& pj, Point const& qi, Point const& qj,
-          Point& ip)
+    static Point between_point(Point const& a, Point const& b)
     {
-        typedef typename coordinate_type<Point>::type ct;
-        typedef model::infinite_line<ct> line_type;
-
-        line_type const p = detail::make::make_infinite_line<ct>(pi, pj);
-        line_type const q = detail::make::make_infinite_line<ct>(qi, qj);
+        Point result;
+        geometry::set<0>(result, (geometry::get<0>(a) + geometry::get<0>(b)) / 2.0);
+        geometry::set<1>(result, (geometry::get<1>(a) + geometry::get<1>(b)) / 2.0);
+        return result;
+    }
 
-        // The input lines are not parallel, they intersect, because
-        // their join type is checked before.
-        return arithmetic::intersection_point(p, q, ip);
+    template <typename Point>
+    static bool
+    apply(Point const& pi, Point const& pj, Point const& qi, Point const& qj,
+          Point const& vertex, bool equidistant, Point& ip)
+    {
+        // Calculates ip (below) by either intersecting p (pi, pj)
+        // with q (qi, qj) or by taking a point between pj and qi (b) and
+        // intersecting r (b, v), where v is the original vertex, with p (or q).
+        // The reason for dual approach: p might be nearly collinear with q,
+        // and in that case the intersection points can lose precision
+        // (or be plainly wrong).
+        // Therefore it takes the most precise option (this is usually p, r)
+        //
+        //             /qj                     |
+        //            /                        |
+        //           /      /                  |
+        //          /      /                   |
+        //         /      /                    |
+        //        /qi    /                     |
+        //              /                      |
+        //   ip *  + b * v                     |
+        //              \                      |
+        //        \pj    \                     |
+        //         \      \                    |
+        //          \      \                   |
+        //           \      \                  |
+        //            \pi    \                 |
+        //
+        // If generated sides along the segments can have an adapted distance,
+        // in a custom strategy, then the calculation of the point in between
+        // might be incorrect and the optimization is not used.
+
+        using ct = typename coordinate_type<Point>::type;
+
+        auto const p = detail::make::make_infinite_line<ct>(pi, pj);
+        auto const q = detail::make::make_infinite_line<ct>(qi, qj);
+
+        using line = decltype(p);
+        using arithmetic::determinant;
+        using arithmetic::assign_intersection_point;
+
+        // The denominator is the determinant of (a,b) values of lines p q
+        // | pa pa |
+        // | qb qb |
+        auto const denominator_pq = determinant<line, &line::a, &line::b>(p, q);
+        constexpr decltype(denominator_pq) const zero = 0;
+
+        if (equidistant)
+        {
+            auto const between = between_point(pj, qi);
+            auto const r = detail::make::make_infinite_line<ct>(vertex, between);
+            auto const denominator_pr = determinant<line, &line::a, &line::b>(p, r);
+
+            if (math::equals(denominator_pq, zero)
+                && math::equals(denominator_pr, zero))
+            {
+                // Degenerate case (for example when length results in <inf>)
+                return false;
+            }
+
+            ip = geometry::math::abs(denominator_pq) > geometry::math::abs(denominator_pr)
+                 ? assign_intersection_point<Point>(p, q, denominator_pq)
+                 : assign_intersection_point<Point>(p, r, denominator_pr);
+        }
+        else
+        {
+            if (math::equals(denominator_pq, zero))
+            {
+                return false;
+            }
+            ip = assign_intersection_point<Point>(p, q, denominator_pq);
+        }
+
+        return true;
     }
 };