3 // Copyright (c) 2018-2019 Barend Gehrels, Amsterdam, the Netherlands.
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)
9 #ifndef BOOST_GEOMETRY_ARITHMETIC_LINE_FUNCTIONS_HPP
10 #define BOOST_GEOMETRY_ARITHMETIC_LINE_FUNCTIONS_HPP
12 #include <boost/geometry/core/access.hpp>
13 #include <boost/geometry/core/config.hpp>
14 #include <boost/geometry/geometries/infinite_line.hpp>
15 #include <boost/geometry/util/math.hpp>
16 #include <boost/geometry/util/select_most_precise.hpp>
18 namespace boost { namespace geometry
24 // Calculates intersection point of two infinite lines.
25 // Returns true if the lines intersect.
26 // Returns false if lines are parallel (or collinear, possibly opposite)
27 template <typename Point, typename Type>
28 inline bool intersection_point(model::infinite_line<Type> const& p,
29 model::infinite_line<Type> const& q, Point& ip)
31 Type const denominator = p.b * q.a - p.a * q.b;
33 static Type const zero = 0;
34 if (math::equals(denominator, zero))
40 // Calculate the intersection coordinates
41 geometry::set<0>(ip, (p.c * q.b - p.b * q.c) / denominator);
42 geometry::set<1>(ip, (p.a * q.c - p.c * q.a) / denominator);
47 //! Return a distance-side-measure for a point to a line
48 //! Point is located left of the line if value is positive,
49 //! right of the line is value is negative, and on the line if the value
51 template <typename Type, typename CoordinateType>
53 typename select_most_precise<Type, CoordinateType>::type
54 side_value(model::infinite_line<Type> const& line,
55 CoordinateType const& x, CoordinateType const& y)
57 // https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line#Line_defined_by_an_equation
58 // Distance from point to line in general form is given as:
59 // (a * x + b * y + c) / sqrt(a * a + b * b);
60 // In most use cases comparisons are enough, saving the sqrt
61 // and often even the division.
62 // Also, this gives positive values for points left to the line,
63 // and negative values for points right to the line.
64 return line.a * x + line.b * y + line.c;
67 template <typename Type, typename Point>
69 typename select_most_precise
72 typename geometry::coordinate_type<Point>::type
74 side_value(model::infinite_line<Type> const& line, Point const& p)
76 return side_value(line, geometry::get<0>(p), geometry::get<1>(p));
79 // Returns true for two lines which are supposed to be (close to) collinear
80 // (which is not checked) and have a similar direction
81 // (in practice up to 45 degrees, TO BE VERIFIED)
82 // true: -----------------> p -----------------> q
83 // false: -----------------> p <----------------- q
84 template <typename Type>
86 bool similar_direction(const model::infinite_line<Type>& p,
87 const model::infinite_line<Type>& q)
89 return p.a * q.a >= 0 && p.b * q.b >= 0;
92 template <typename Type>
93 inline bool is_degenerate(const model::infinite_line<Type>& line)
95 static Type const zero = 0;
96 return math::equals(line.a, zero) && math::equals(line.b, zero);
100 } // namespace arithmetic
103 }} // namespace boost::geometry
106 #endif // BOOST_GEOMETRY_ARITHMETIC_LINE_FUNCTIONS_HPP