geometry/arithmetic/infinite_line_functions.hpp

0001 // Boost.Geometry
0002
0003 // Copyright (c) 2018-2019 Barend Gehrels, Amsterdam, the Netherlands.
0004
0005 // Use, modification and distribution is subject to the Boost Software License,
0006 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008
0009 #ifndef BOOST_GEOMETRY_ARITHMETIC_LINE_FUNCTIONS_HPP
0010 #define BOOST_GEOMETRY_ARITHMETIC_LINE_FUNCTIONS_HPP
0011
0012 #include <boost/geometry/arithmetic/determinant.hpp>
0013 #include <boost/geometry/core/access.hpp>
0014 #include <boost/geometry/core/assert.hpp>
0015 #include <boost/geometry/core/config.hpp>
0016 #include <boost/geometry/geometries/infinite_line.hpp>
0017 #include <boost/geometry/util/math.hpp>
0018 #include <boost/geometry/util/select_most_precise.hpp>
0019
0020 namespace boost { namespace geometry
0021 {
0022
0023 namespace arithmetic
0024 {
0025
0026 template <typename Line, typename Line::type Line::* member1, typename Line::type Line::* member2>
0027 inline auto determinant(Line const& p, Line const& q)
0028 {
0029     return geometry::detail::determinant<typename Line::type>(p.*member1, p.*member2,
0030                                                               q.*member1, q.*member2);
0031 }
0032
0033 template <typename Point, typename Line, typename Type>
0034 inline Point assign_intersection_point(Line const& p, Line const& q, Type const& denominator)
0035 {
0036     BOOST_ASSERT(denominator != Type(0));
0037
0038     // x = | pb pc | / d  and y = | pc pa | / d
0039     //     | qb qc |              | qc qa |
0040
0041     Point result;
0042     geometry::set<0>(result, determinant<Line, &Line::b, &Line::c>(p, q) / denominator);
0043     geometry::set<1>(result, determinant<Line, &Line::c, &Line::a>(p, q) / denominator);
0044     return result;
0045 }
0046
0047 // Calculates intersection point of two infinite lines.
0048 // Returns true if the lines intersect.
0049 // Returns false if lines are parallel (or collinear, possibly opposite)
0050 template <typename Line, typename Point>
0051 inline bool intersection_point(Line const& p, Line const& q, Point& ip)
0052 {
0053     auto const denominator = determinant<Line, &Line::a, &Line::b>(p, q);
0054     constexpr decltype(denominator) const zero = 0;
0055
0056     if (math::equals(denominator, zero))
0057     {
0058         // Lines are parallel
0059         return false;
0060     }
0061
0062     ip = assign_intersection_point<Point>(p, q, denominator);
0063
0064     return true;
0065 }
0066
0067 //! Return a distance-side-measure for a point to a line
0068 //! Point is located left of the line if value is positive,
0069 //! right of the line is value is negative, and on the line if the value
0070 //! is exactly zero
0071 template <typename Type, typename CoordinateType>
0072 inline
0073 typename select_most_precise<Type, CoordinateType>::type
0074 side_value(model::infinite_line<Type> const& line,
0075     CoordinateType const& x, CoordinateType const& y)
0076 {
0077     // https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line#Line_defined_by_an_equation
0078     // Distance from point to line in general form is given as:
0079     // (a * x + b * y + c) / sqrt(a * a + b * b);
0080     // In most use cases comparisons are enough, saving the sqrt
0081     // and often even the division.
0082     // Also, this gives positive values for points left to the line,
0083     // and negative values for points right to the line.
0084     return line.a * x + line.b * y + line.c;
0085 }
0086
0087 template <typename Type, typename Point>
0088 inline
0089 typename select_most_precise
0090 <
0091     Type,
0092     geometry::coordinate_type_t<Point>
0093 >::type
0094 side_value(model::infinite_line<Type> const& line, Point const& p)
0095 {
0096     return side_value(line, geometry::get<0>(p), geometry::get<1>(p));
0097 }
0098
0099 template <typename Type>
0100 inline bool is_degenerate(model::infinite_line<Type> const& line)
0101 {
0102     static Type const zero = 0;
0103     return math::equals(line.a, zero) && math::equals(line.b, zero);
0104 }
0105
0106
0107 } // namespace arithmetic
0108
0109
0110 }} // namespace boost::geometry
0111
0112
0113 #endif // BOOST_GEOMETRY_ARITHMETIC_LINE_FUNCTIONS_HPP