]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Boost.Geometry (aka GGL, Generic Geometry Library) |
2 | ||
20effc67 | 3 | // Copyright (c) 2012-2020 Barend Gehrels, Amsterdam, the Netherlands. |
7c673cae FG |
4 | |
5 | // Use, modification and distribution is subject to the Boost Software License, | |
6 | // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
7 | // http://www.boost.org/LICENSE_1_0.txt) | |
8 | ||
9 | #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_LINE_LINE_INTERSECTION_HPP | |
10 | #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_LINE_LINE_INTERSECTION_HPP | |
11 | ||
92f5a8d4 | 12 | #include <boost/geometry/algorithms/detail/make/make.hpp> |
1e59de90 TL |
13 | #include <boost/geometry/arithmetic/infinite_line_functions.hpp> |
14 | #include <boost/geometry/util/math.hpp> | |
7c673cae FG |
15 | |
16 | namespace boost { namespace geometry | |
17 | { | |
18 | ||
19 | ||
20 | #ifndef DOXYGEN_NO_DETAIL | |
21 | namespace detail { namespace buffer | |
22 | { | |
23 | ||
7c673cae FG |
24 | struct line_line_intersection |
25 | { | |
7c673cae | 26 | template <typename Point> |
1e59de90 | 27 | static Point between_point(Point const& a, Point const& b) |
7c673cae | 28 | { |
1e59de90 TL |
29 | Point result; |
30 | geometry::set<0>(result, (geometry::get<0>(a) + geometry::get<0>(b)) / 2.0); | |
31 | geometry::set<1>(result, (geometry::get<1>(a) + geometry::get<1>(b)) / 2.0); | |
32 | return result; | |
33 | } | |
7c673cae | 34 | |
1e59de90 TL |
35 | template <typename Point> |
36 | static bool | |
37 | apply(Point const& pi, Point const& pj, Point const& qi, Point const& qj, | |
38 | Point const& vertex, bool equidistant, Point& ip) | |
39 | { | |
40 | // Calculates ip (below) by either intersecting p (pi, pj) | |
41 | // with q (qi, qj) or by taking a point between pj and qi (b) and | |
42 | // intersecting r (b, v), where v is the original vertex, with p (or q). | |
43 | // The reason for dual approach: p might be nearly collinear with q, | |
44 | // and in that case the intersection points can lose precision | |
45 | // (or be plainly wrong). | |
46 | // Therefore it takes the most precise option (this is usually p, r) | |
47 | // | |
48 | // /qj | | |
49 | // / | | |
50 | // / / | | |
51 | // / / | | |
52 | // / / | | |
53 | // /qi / | | |
54 | // / | | |
55 | // ip * + b * v | | |
56 | // \ | | |
57 | // \pj \ | | |
58 | // \ \ | | |
59 | // \ \ | | |
60 | // \ \ | | |
61 | // \pi \ | | |
62 | // | |
63 | // If generated sides along the segments can have an adapted distance, | |
64 | // in a custom strategy, then the calculation of the point in between | |
65 | // might be incorrect and the optimization is not used. | |
66 | ||
67 | using ct = typename coordinate_type<Point>::type; | |
68 | ||
69 | auto const p = detail::make::make_infinite_line<ct>(pi, pj); | |
70 | auto const q = detail::make::make_infinite_line<ct>(qi, qj); | |
71 | ||
72 | using line = decltype(p); | |
73 | using arithmetic::determinant; | |
74 | using arithmetic::assign_intersection_point; | |
75 | ||
76 | // The denominator is the determinant of (a,b) values of lines p q | |
77 | // | pa pa | | |
78 | // | qb qb | | |
79 | auto const denominator_pq = determinant<line, &line::a, &line::b>(p, q); | |
80 | constexpr decltype(denominator_pq) const zero = 0; | |
81 | ||
82 | if (equidistant) | |
83 | { | |
84 | auto const between = between_point(pj, qi); | |
85 | auto const r = detail::make::make_infinite_line<ct>(vertex, between); | |
86 | auto const denominator_pr = determinant<line, &line::a, &line::b>(p, r); | |
87 | ||
88 | if (math::equals(denominator_pq, zero) | |
89 | && math::equals(denominator_pr, zero)) | |
90 | { | |
91 | // Degenerate case (for example when length results in <inf>) | |
92 | return false; | |
93 | } | |
94 | ||
95 | ip = geometry::math::abs(denominator_pq) > geometry::math::abs(denominator_pr) | |
96 | ? assign_intersection_point<Point>(p, q, denominator_pq) | |
97 | : assign_intersection_point<Point>(p, r, denominator_pr); | |
98 | } | |
99 | else | |
100 | { | |
101 | if (math::equals(denominator_pq, zero)) | |
102 | { | |
103 | return false; | |
104 | } | |
105 | ip = assign_intersection_point<Point>(p, q, denominator_pq); | |
106 | } | |
107 | ||
108 | return true; | |
7c673cae FG |
109 | } |
110 | }; | |
111 | ||
112 | ||
113 | }} // namespace detail::buffer | |
114 | #endif // DOXYGEN_NO_DETAIL | |
115 | ||
116 | ||
117 | }} // namespace boost::geometry | |
118 | ||
119 | ||
120 | #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_BUFFER_LINE_LINE_INTERSECTION_HPP |