ratpoint.h

Go to the documentation of this file.

/*
 * $Id: ratpoint.h 18278 2014-11-25 01:42:10Z ksimek $
 */

#ifndef QD_CPP_RATPOINT_INCLUDED_IVILAB_UARIZONAVISION
#define QD_CPP_RATPOINT_INCLUDED_IVILAB_UARIZONAVISION 1

#include <l_cpp/l_exception.h>
#include <qd_cpp/pixpoint.h>

#include <iosfwd>
#include <l_cpp/l_util.h>
#include <l/l_sys_lib.h>
#include <l/l_sys_io.h>

#ifndef UNLIMITED_RATIONAL_PRECISION_QD_CPP_IVILAB
#define UNLIMITED_RATIONAL_PRECISION_QD_CPP_IVILAB 0
#endif

#if UNLIMITED_RATIONAL_PRECISION_QD_CPP_IVILAB
#include <boost/multiprecision/cpp_int.hpp>
#else
#include <boost/rational.hpp>
#endif

namespace kjb
{
namespace qd
{


struct RatPoint
{
#if UNLIMITED_RATIONAL_PRECISION_QD_CPP_IVILAB
    typedef boost::multiprecision::cpp_rational Rat;
#else
#if 0
    // TOO SMALL
    typedef boost::rational< PixPoint::Integer > Rat;
#else
    // SOMEWHAT BIGGER
    typedef boost::rational< long long > Rat;
#endif
#endif

    Rat x, y;

    RatPoint(const PixPoint& p)
    :   x(p.x),
        y(p.y)
    {}

    RatPoint(const Rat& rx, const Rat& ry)
    :   x(rx),
        y(ry)
    {}

};


inline bool operator==(const RatPoint& a, const RatPoint& b)
{
    return a.x == b.x && a.y == b.y;
}

inline bool operator!=(const RatPoint& a, const RatPoint& b)
{
    return ! (a==b);
}

inline bool operator<(const RatPoint& a, const RatPoint& b)
{
    return a.y < b.y || (a.y==b.y && a.x < b.x);
}


inline bool operator<=(const RatPoint& a, const RatPoint& b)
{
    return a==b || a < b;
}


inline RatPoint operator-(const RatPoint& a, const RatPoint& b)
{
    return RatPoint(a.x - b.x, a.y - b.y);
}


inline std::ostream& operator<<(std::ostream& s, const RatPoint& p)
{
    s << p.x.numerator();
    if (p.x.denominator() > 1) s << '/' << p.x.denominator();

    s << ", " << p.y.numerator();
    if (p.y.denominator() > 1) s << '/' << p.y.denominator();
    return s;
}


struct PixPoint_line_segment
{
    PixPoint a, b;

    PixPoint_line_segment(const PixPoint& p, const PixPoint& q)
    :   a(p),
        b(q)
    {}
};


inline bool is_degenerate(const PixPoint_line_segment& s)
{
    return s.a == s.b;
}


inline
bool are_parallel(
    const PixPoint_line_segment& s,
    const PixPoint_line_segment& t
)
{
    // test if corresponding matrix is singular (zero determinant).
    return (s.b.x - s.a.x)*(t.a.y - t.b.y) == (s.b.y - s.a.y)*(t.a.x - t.b.x);
}


bool is_intersecting(
    const PixPoint_line_segment&,
    const PixPoint_line_segment& 
);



template <typename LINE_SEGMENT>
inline bool are_sharing_a_continuum(
    const LINE_SEGMENT& s,
    const LINE_SEGMENT& t
)
{
    return      !is_degenerate(s)
            &&  !is_degenerate(t)
            &&  are_parallel(s,t)
            &&  is_intersecting(s,t)
            &&  (   (is_on(s, t.a) && t.a != s.a && t.a != s.b) // t.a inside s
                ||  (is_on(s, t.b) && t.b != s.a && t.b != s.b) // t.b inside s
                ||  (is_on(t, s.a) && s.a != t.a && s.a != t.b) // s.a inside t
                ||  (is_on(t, s.b) && s.b != t.a && s.b != t.b) // s.b inside t
                ||  (t.a==s.a && t.b==s.b)                      // identical
                ||  (t.a==s.b && t.b==s.a)                      // reversed
                );
}


template <typename LINE_SEGMENT>
inline bool are_sharing_a_continuum(
    const LINE_SEGMENT& s,
    const LINE_SEGMENT& t,
    LINE_SEGMENT* shared_continuum 
)
{
    if (    is_degenerate(s)
        ||  is_degenerate(t)
        ||  !are_parallel(s,t)
        ||  !is_intersecting(s,t)
       )
    {
        return false;
    }

    if ((t.a==s.a && t.b==s.b) || (t.a==s.b && t.b==s.a))
    {
        *shared_continuum = s;
        return true;
    }

    if (is_on(s, t.a) && t.a != s.a && t.a != s.b) // t.a inside s
    {
        if (is_on(t, s.a))
        {
            *shared_continuum = LINE_SEGMENT(s.a, t.a);
        }
        else if (is_on(t, s.b))
        {
            *shared_continuum = LINE_SEGMENT(t.a, s.b);
        }
        else
        {
            *shared_continuum = t;
        }
        return true;
    }

    if (is_on(s, t.b) && t.b != s.a && t.b != s.b) // t.b inside s
    {
        if (is_on(t, s.a))
        {
            *shared_continuum = LINE_SEGMENT(s.a, t.b);
        }
        else if (is_on(t, s.b))
        {
            *shared_continuum = LINE_SEGMENT(t.b, s.b);
        }
        else
        {
            *shared_continuum = t;
        }
        return true;
    }

    if (is_on(t, s.a) && s.a != t.a && s.a != t.b) // s.a inside t
    {
        if (is_on(s, t.a))
        {
            *shared_continuum = LINE_SEGMENT(s.a, t.a);
        }
        else if (is_on(s, t.b))
        {
            *shared_continuum = LINE_SEGMENT(s.a, t.b);
        }
        else
        {
            *shared_continuum = s;
        }
        return true;
    }
    if (is_on(t, s.b) && s.b != t.a && s.b != t.b) // s.b inside t
    {
        if (is_on(s, t.a))
        {
            *shared_continuum = LINE_SEGMENT(s.b, t.a);
        }
        else if (is_on(s, t.b))
        {
            *shared_continuum = LINE_SEGMENT(s.b, t.b);
        }
        else
        {
            *shared_continuum = s;
        }
        return true;
    }
    return false; // overlap only at the endpoint, not over a continuum
}



struct RatPoint_line_segment
{
    RatPoint a, b;

    RatPoint_line_segment(const RatPoint& p, const RatPoint& q)
    :   a(p),
        b(q)
    {}

    RatPoint_line_segment(const PixPoint_line_segment& s)
    :   a(s.a),
        b(s.b)
    {}
};


inline bool is_degenerate(const RatPoint_line_segment& s)
{
    return s.a == s.b;
}




RatPoint::Rat triangle_area(
    const RatPoint_line_segment&,
    const RatPoint&
);


bool is_on(const RatPoint_line_segment&, const RatPoint&);


bool is_intersecting(
    const RatPoint_line_segment&,
    const RatPoint_line_segment&
);


inline
bool are_parallel(
    const RatPoint_line_segment& s,
    const RatPoint_line_segment& t
)
{
    // test if corresponding matrix is singular (zero determinant).
    return (s.b.x - s.a.x)*(t.a.y - t.b.y) == (s.b.y - s.a.y)*(t.a.x - t.b.x);
}


RatPoint line_intersection(
    const RatPoint_line_segment&,
    const RatPoint_line_segment&
);


inline bool segment_intersection(
    const RatPoint_line_segment& s,
    const RatPoint_line_segment& t,
    RatPoint_line_segment* intersection 
)
{
    NTX(intersection);
    if (!is_intersecting(s, t)) return false;

    if (are_parallel(s, t))
    {
        if (!are_sharing_a_continuum(s, t, intersection))
        {
            // not a continuum, just an endpoint
            if (s.a == t.a || s.a == t.b)
            {
                intersection -> a = intersection -> b = s.a;
            }
            else
            {
                KJB(ASSERT(s.b == t.a || s.b == t.b));
                intersection -> a = intersection -> b = s.b;
            }
        }
    }
    else
    {
        intersection -> a = intersection -> b = line_intersection(s, t);
    }
    return true;
}


#if 0 /* maybe too trivial to commit */

inline bool line_intersection(
    const RatPoint_line_segment& s,
    const RatPoint& p
)
{
    if (is_degenerate(s)) KJB_THROW(Illegal_argument);
    return 0 == triangle_area(s, p);
}
#endif



} // end ns qd
} // end ns kjb

#endif /* QD_CPP_RATPOINT_INCLUDED_IVILAB_UARIZONAVISION */