boost/geometry/arithmetic/infinite_line_functions.hpp

   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>
  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
  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
  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 // 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>
  85 inline
  86 bool similar_direction(const model::infinite_line<Type>& p,
  87                        const model::infinite_line<Type>& q)
  88 {
  89     return p.a * q.a >= 0 && p.b * q.b >= 0;
  90 }
  91
  92 template <typename Type>
  93 inline bool is_degenerate(const model::infinite_line<Type>& line)
  94 {
  95     static Type const zero = 0;
  96     return math::equals(line.a, zero) && math::equals(line.b, zero);
  97 }
  98
  99
 100 } // namespace arithmetic
 101
 102
 103 }} // namespace boost::geometry
 104
 105
 106 #endif // BOOST_GEOMETRY_ARITHMETIC_LINE_FUNCTIONS_HPP