1 // Boost.Geometry
2
3 // Copyright (c) 2018-2019 Barend Gehrels, Amsterdam, the Netherlands.
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_ARITHMETIC_LINE_FUNCTIONS_HPP
10 #define BOOST_GEOMETRY_ARITHMETIC_LINE_FUNCTIONS_HPP
11
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>
17
18 namespace boost { namespace geometry
19 {
20
21 namespace arithmetic
22 {
23
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>
intersection_point(model::infinite_line<Type> const & p,model::infinite_line<Type> const & q,Point & ip)28 inline bool intersection_point(model::infinite_line<Type> const& p,
29 model::infinite_line<Type> const& q, Point& ip)
30 {
31 Type const denominator = p.b * q.a - p.a * q.b;
32
33 static Type const zero = 0;
34 if (math::equals(denominator, zero))
35 {
36 // Lines are parallel
37 return false;
38 }
39
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);
43
44 return true;
45 }
46
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
50 //! is exactly zero
51 template <typename Type, typename CoordinateType>
52 inline
53 typename select_most_precise<Type, CoordinateType>::type
side_value(model::infinite_line<Type> const & line,CoordinateType const & x,CoordinateType const & y)54 side_value(model::infinite_line<Type> const& line,
55 CoordinateType const& x, CoordinateType const& y)
56 {
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;
65 }
66
67 template <typename Type, typename Point>
68 inline
69 typename select_most_precise
70 <
71 Type,
72 typename geometry::coordinate_type<Point>::type
73 >::type
side_value(model::infinite_line<Type> const & line,Point const & p)74 side_value(model::infinite_line<Type> const& line, Point const& p)
75 {
76 return side_value(line, geometry::get<0>(p), geometry::get<1>(p));
77 }
78
79 template <typename Type>
is_degenerate(const model::infinite_line<Type> & line)80 inline bool is_degenerate(const model::infinite_line<Type>& line)
81 {
82 static Type const zero = 0;
83 return math::equals(line.a, zero) && math::equals(line.b, zero);
84 }
85
86
87 } // namespace arithmetic
88
89
90 }} // namespace boost::geometry
91
92
93 #endif // BOOST_GEOMETRY_ARITHMETIC_LINE_FUNCTIONS_HPP
94