MRLineSegm.h

Go to the documentation of this file.

#pragma once
 
#include "MRMeshFwd.h"
#include "MRVector2.h"
 
namespace MR
{
 
// a segment of straight dimensional line
template <typename V> 
struct LineSegm
{
    using T = typename V::ValueType;
    V a, b;
 
    [[nodiscard]] constexpr LineSegm() noexcept = default;
    [[nodiscard]] constexpr LineSegm( const V & a, const V & b ) noexcept : a( a ), b( b ) { }
    template <typename U>
    [[nodiscard]] constexpr explicit LineSegm( const LineSegm<U> & p ) noexcept : a( p.a ), b( p.b ) { }
    [[nodiscard]] V dir() const { return b - a; }
    [[nodiscard]] T lengthSq() const { return dir().lengthSq(); }
    [[nodiscard]] T length() const { return dir().length(); }
    [[nodiscard]] V operator()( T param ) const { return ( 1 - param ) * a + param * b; }
};
 
template <typename V> 
[[nodiscard]] inline bool operator == ( const LineSegm<V> & a, const LineSegm<V> & b )
{
    return a.a == b.a && a.b == b.b;
}
 
template <typename V> 
[[nodiscard]] V closestPointOnLineSegm( const V& pt, const LineSegm<V> & l )
{
    auto ab = l.b - l.a;
    auto dt = dot( pt - l.a, ab );
    auto abLengthSq = ab.lengthSq();
    if ( dt <= 0 )
        return l.a;
    if ( dt >= abLengthSq )
        return l.b;
    auto ratio = dt / abLengthSq;
    return l.a * ( 1 - ratio ) + l.b * ratio;
}
 
template <typename V> 
[[nodiscard]] bool doSegmentsIntersect( const LineSegm<V> & x, const LineSegm<V> & y,
    typename V::ValueType * xPos = nullptr, typename V::ValueType * yPos = nullptr )
{
    // check whether infinite line x intersect segment y
    const auto xvec = x.b - x.a;
    const auto ya = cross( xvec, y.a - x.a );
    const auto yb = cross( xvec, y.b - x.a );
    if ( ya * yb > 0 )
        return false;
 
    // check whether infinite line y intersect segment x
    const auto yvec = y.b - y.a;
    const auto xa = cross( yvec, x.a - y.a );
    const auto xb = cross( yvec, x.b - y.a );
    if ( xa * xb > 0 )
        return false;
 
    // degenerate cases
    if ( cross( xvec, yvec ) == 0 )
    {
        // on the same line
        if ( xvec != V() )
        {
            if ( dot( xvec, y.a - x.a ) * dot( xvec, y.b - x.a ) > 0 &&
                dot( -xvec, y.a - x.b ) * dot( -xvec, y.b - x.b ) > 0 )
                return false; // segments does not overlap
        }
        else if ( yvec != V() )
        {
            if ( dot( yvec, x.a - y.a ) * dot( yvec, x.b - y.a ) > 0 &&
                dot( -yvec, x.a - y.b ) * dot( -yvec, x.b - y.b ) > 0 )
                return false; // segments does not overlap
        }
        else if ( x.a != y.a )
            return false; // fully degenerated
    }
 
    if ( xPos )
    {
        // calculates intersection position on segment x
        const auto denom = xa - xb;
        *xPos = denom == 0 ? 0 : xa / denom;
    }
    if ( yPos )
    {
        // calculates intersection position on segment y
        const auto denom = ya - yb;
        *yPos = denom == 0 ? 0 : ya / denom;
    }
    return true;
}
 
template <typename V> 
[[nodiscard]] bool doSegmentLineIntersect( const LineSegm<V> & x, const Line<V> & y,
    typename V::ValueType * xPos = nullptr, typename V::ValueType * yPos = nullptr )
{
    // check whether infinite line y intersect segment x
    const auto xa = cross( y.d, x.a - y.p );
    const auto xb = cross( y.d, x.b - y.p );
    
    // if several line segments are connected in polyline, this ensures that only one of them will be intersected,
    // even is the line passes exactly through segment's end
    if ( ( xa <= 0 ) == ( xb <= 0 ) )
        return false; // both ends of the segment are at the same side of the line
 
    if ( xPos )
    {
        // calculates intersection position on segment x
        const auto denom = xa - xb;
        *xPos = denom == 0 ? 0 : xa / denom;
    }
    if ( yPos )
    {
        // calculates intersection position on line y
        const auto xvec = x.b - x.a;
        const auto ya = cross( xvec, y.p - x.a );
        const auto yb = cross( xvec, y.p + y.d - x.a );
 
        const auto denom = ya - yb;
        *yPos = denom == 0 ? 0 : ya / denom;
    }
    return true;
}
 
MR_BIND_TEMPLATE( bool doSegmentsIntersect( const LineSegm<Vector2<float>>& x, const LineSegm<Vector2<float>>& y, float* xPos, float* yPos ) )
MR_BIND_TEMPLATE( bool doSegmentsIntersect( const LineSegm<Vector2<double>>& x, const LineSegm<Vector2<double>>& y, double* xPos, double* yPos ) )
 
MR_BIND_TEMPLATE( bool doSegmentLineIntersect( const LineSegm<Vector2<float>>& x, const Line<Vector2<float>>& y, float* xPos, float* yPos ) )
MR_BIND_TEMPLATE( bool doSegmentLineIntersect( const LineSegm<Vector2<double>>& x, const Line<Vector2<double>>& y, double* xPos, double* yPos ) )
 
} //namespace MR