114 lines
3.7 KiB
C++
114 lines
3.7 KiB
C++
|
// Boost.Geometry
|
||
|
|
|
||
|
|
// Copyright (c) 2018-2019 Barend Gehrels, Amsterdam, the Netherlands.
|
||
|
|
|
||
|
|
// Use, modification and distribution is subject to the Boost Software License,
|
||
|
|
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
|
||
|
|
// http://www.boost.org/LICENSE_1_0.txt)
|
||
|
|
|
||
|
|
#ifndef BOOST_GEOMETRY_ARITHMETIC_LINE_FUNCTIONS_HPP
|
||
|
|
#define BOOST_GEOMETRY_ARITHMETIC_LINE_FUNCTIONS_HPP
|
||
|
|
|
||
|
|
#include <boost/geometry/arithmetic/determinant.hpp>
|
||
|
|
#include <boost/geometry/core/access.hpp>
|
||
|
|
#include <boost/geometry/core/assert.hpp>
|
||
|
|
#include <boost/geometry/core/config.hpp>
|
||
|
|
#include <boost/geometry/geometries/infinite_line.hpp>
|
||
|
|
#include <boost/geometry/util/math.hpp>
|
||
|
|
#include <boost/geometry/util/select_most_precise.hpp>
|
||
|
|
|
||
|
|
namespace boost { namespace geometry
|
||
|
|
{
|
||
|
|
|
||
|
|
namespace arithmetic
|
||
|
|
{
|
||
|
|
|
||
|
|
template <typename Line, typename Line::type Line::* member1, typename Line::type Line::* member2>
|
||
|
|
inline auto determinant(Line const& p, Line const& q)
|
||
|
|
{
|
||
|
|
return geometry::detail::determinant<typename Line::type>(p.*member1, p.*member2,
|
||
|
|
q.*member1, q.*member2);
|
||
|
|
}
|
||
|
|
|
||
|
|
template <typename Point, typename Line, typename Type>
|
||
|
|
inline Point assign_intersection_point(Line const& p, Line const& q, Type const& denominator)
|
||
|
|
{
|
||
|
|
BOOST_ASSERT(denominator != Type(0));
|
||
|
|
|
||
|
|
// x = | pb pc | / d and y = | pc pa | / d
|
||
|
|
// | qb qc | | qc qa |
|
||
|
|
|
||
|
|
Point result;
|
||
|
|
geometry::set<0>(result, determinant<Line, &Line::b, &Line::c>(p, q) / denominator);
|
||
|
|
geometry::set<1>(result, determinant<Line, &Line::c, &Line::a>(p, q) / denominator);
|
||
|
|
return result;
|
||
|
|
}
|
||
|
|
|
||
|
|
// Calculates intersection point of two infinite lines.
|
||
|
|
// Returns true if the lines intersect.
|
||
|
|
// Returns false if lines are parallel (or collinear, possibly opposite)
|
||
|
|
template <typename Line, typename Point>
|
||
|
|
inline bool intersection_point(Line const& p, Line const& q, Point& ip)
|
||
|
|
{
|
||
|
|
auto const denominator = determinant<Line, &Line::a, &Line::b>(p, q);
|
||
|
|
constexpr decltype(denominator) const zero = 0;
|
||
|
|
|
||
|
|
if (math::equals(denominator, zero))
|
||
|
|
{
|
||
|
|
// Lines are parallel
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
|
||
|
|
ip = assign_intersection_point<Point>(p, q, denominator);
|
||
|
|
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
|
||
|
|
//! Return a distance-side-measure for a point to a line
|
||
|
|
//! Point is located left of the line if value is positive,
|
||
|
|
//! right of the line is value is negative, and on the line if the value
|
||
|
|
//! is exactly zero
|
||
|
|
template <typename Type, typename CoordinateType>
|
||
|
|
inline
|
||
|
|
typename select_most_precise<Type, CoordinateType>::type
|
||
|
|
side_value(model::infinite_line<Type> const& line,
|
||
|
|
CoordinateType const& x, CoordinateType const& y)
|
||
|
|
{
|
||
|
|
// https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line#Line_defined_by_an_equation
|
||
|
|
// Distance from point to line in general form is given as:
|
||
|
|
// (a * x + b * y + c) / sqrt(a * a + b * b);
|
||
|
|
// In most use cases comparisons are enough, saving the sqrt
|
||
|
|
// and often even the division.
|
||
|
|
// Also, this gives positive values for points left to the line,
|
||
|
|
// and negative values for points right to the line.
|
||
|
|
return line.a * x + line.b * y + line.c;
|
||
|
|
}
|
||
|
|
|
||
|
|
template <typename Type, typename Point>
|
||
|
|
inline
|
||
|
|
typename select_most_precise
|
||
|
|
<
|
||
|
|
Type,
|
||
|
|
typename geometry::coordinate_type<Point>::type
|
||
|
|
>::type
|
||
|
|
side_value(model::infinite_line<Type> const& line, Point const& p)
|
||
|
|
{
|
||
|
|
return side_value(line, geometry::get<0>(p), geometry::get<1>(p));
|
||
|
|
}
|
||
|
|
|
||
|
|
template <typename Type>
|
||
|
|
inline bool is_degenerate(const model::infinite_line<Type>& line)
|
||
|
|
{
|
||
|
|
static Type const zero = 0;
|
||
|
|
return math::equals(line.a, zero) && math::equals(line.b, zero);
|
||
|
|
}
|
||
|
|
|
||
|
|
|
||
|
|
} // namespace arithmetic
|
||
|
|
|
||
|
|
|
||
|
|
}} // namespace boost::geometry
|
||
|
|
|
||
|
|
|
||
|
|
#endif // BOOST_GEOMETRY_ARITHMETIC_LINE_FUNCTIONS_HPP
|