ReSCue - Retrieval System for Curves

---

         

---

circular_arc_edge.h

#ifndef RESCUE__CIRCULAR_ARC_EDGE
#define RESCUE__CIRCULAR_ARC_EDGE

#include <list>
#include <utility>
#include "rigid_motion.h"
#include "compact_interval_border.h"
#include "angle.h"

// ==========================================================================================
// ==========================================================================================

namespace rescue
{

//template<class value_type>
//class compact_interval_bound;
    
template <class index_class, class point>
class circular_arc_edge
{

public:

    typedef point::arithmetic_t arithmetic_t;
    typedef arithmetic_t arithmetic;
    typedef index_class index_t;
    typedef unit_circle_angle<arithmetic> angle_t;
    typedef angle_t border_value;
    typedef unit_circle_angle<arithmetic> border_type;
    typedef point point_t;
    typedef std::pair<angle_t, angle_t > circular_arc;
    typedef std::pair<point,point> point_pair;
    typedef rigid_motion<arithmetic> motion;
    typedef compact_interval_border<angle_t,index_t> interval_border;
        typedef std::list<angle_t> interval_bounds;
        typedef std::list<angle_t>::iterator border_iterator;
    
        circular_arc_edge();
    
    ~circular_arc_edge();
    
        inline border_iterator left_borders_begin();// const;
    
    inline border_iterator left_borders_end();// const;
    
        inline border_iterator right_borders_begin();// const;
    
    inline border_iterator right_borders_end();// const;

        inline bool contains(const angle_t& phi);
    
        circular_arc_edge
                (const point_pair& P, const point_pair& Q, const point_pair& ref_points,
                 const arithmetic& eps, const arithmetic& delta);
    
        void assign_transporter
                (const point_pair& P, const point_pair& Q, const point_pair& ref_points,
                 const arithmetic& eps, const arithmetic& delta);
    
    static motion compute_match(const angle_t& phi, const point_pair& ref_points);
    
    static bool empty(const circular_arc&);
    
    static bool full(const circular_arc&);

private:
    
        interval_bounds left_borders;
    
    interval_bounds right_borders;

public:    
        static circular_arc get_angle_interval(const point_pair& pp1, const point_pair& pp2, const arithmetic& eps);

};

// ==========================================================================================
// ==========================================================================================



// ==========================================================================================
template <class index_class, class point>
circular_arc_edge<index_class,point>::circular_arc_edge()
// ==========================================================================================
{
        //left_borders.clear();
        //right_borders.clear();
}

// ==========================================================================================
template <class index_class, class point>
circular_arc_edge<index_class,point>::~circular_arc_edge()
// ==========================================================================================
{
        left_borders.clear();
        right_borders.clear();
}

// ==========================================================================================
template <class index_class, class point>
circular_arc_edge<index_class,point>::circular_arc_edge
        (const point_pair& P, const point_pair& Q, const point_pair& ref_points,
         const arithmetic& eps, const arithmetic& delta)
// ==========================================================================================
{
        assign_transporter(P,Q,ref_points,eps,delta);
}

// ==========================================================================================
template <class index_class, class point>
void circular_arc_edge<index_class,point>::assign_transporter
        (const point_pair& P, const point_pair& Q, const point_pair& ref_points,
         const arithmetic& eps, const arithmetic& delta)
// ==========================================================================================
{

        arithmetic eps_prime = eps+delta;

        left_borders.clear();
        right_borders.clear();
        
    angle_t angle_zero(false);
    angle_t angle_2pi(true);

    point_pair pq(P.second,Q.second);
        point_pair pq_pred(P.first,Q.first);

    // compute angle intervals for new point pair.
    // we need two intervals on S^1, i.e. up to four intervals on the real line.
    circular_arc I1 = get_angle_interval(ref_points,pq,eps_prime);
    circular_arc I2 = get_angle_interval(pq_pred,pq,eps_prime);

    if (empty(I1) || empty(I2))
        return;
    
    if (full(I1) && full(I2))
    {
        left_borders.push_back(angle_zero);
                right_borders.push_back(angle_2pi);
        return;
    }

    // convert I1 and I2 to (one to three) intervals on the real line
    if (I1.first<=I1.second)
    {
        if (I2.first<=I2.second)    
        {
            if (I2.second<I1.first || I1.second<I2.first)
                return;
            if (I1.first<=I2.first)
                left_borders.push_back(I2.first);
            else
                left_borders.push_back(I1.first);
            if (I1.second<=I2.second)
                right_borders.push_back(I1.second);
            else
                right_borders.push_back(I2.second);
        } else { //(I2.first > I2.second)    
            if (I2.first<=I1.second)
            {
                left_borders.push_back(I2.first);
                right_borders.push_back(I1.second);
            }
            if (I1.first<=I2.second)
            {
                left_borders.push_back(I1.first);
                right_borders.push_back(I2.second);
            }
        }
    } else { // (I1.first > I1.second)
        if (I2.first<=I2.second)    
        {
            if (I1.first<=I2.second)
            {
                left_borders.push_back(I1.first);
                right_borders.push_back(I2.second);
            }
            if (I2.first<=I1.second)
            {
                left_borders.push_back(I2.first);
                right_borders.push_back(I1.second);
            }
        } else { // (I1.first > I1.second) UND (I2.first > I2.second)
            if (I1.first<=I2.second)
            {
                left_borders.push_back(I1.first);
                right_borders.push_back(I2.second);
            } else if (I2.first<=I1.second)
            {
                left_borders.push_back(I2.first);
                right_borders.push_back(I1.second);
            }
            if (I1.first<=I2.first)
            {
                left_borders.push_back(I2.first);
                right_borders.push_back(angle_2pi);
            } else {
                left_borders.push_back(I1.first);
                right_borders.push_back(angle_2pi);
            }
            if (I1.second<=I2.second)
            {
                left_borders.push_back(angle_zero);
                right_borders.push_back(I1.second);
            } else {
                left_borders.push_back(angle_zero);
                right_borders.push_back(I2.second);
            }
        }
        }
        
}


// ==========================================================================================
template <class index_class, class point>
circular_arc_edge<index_class,point>::circular_arc  circular_arc_edge<index_class,point>::
        get_angle_interval(const point_pair& pp1, const point_pair& pp2, const arithmetic& eps)
// ==========================================================================================
{

    point p, q, S0, S1;

    arithmetic tp_x = (pp1.first.x+pp2.first.x) / 2.0;
    arithmetic tp_y = (pp1.first.y+pp2.first.y) / 2.0;
    arithmetic tq_x = (pp1.second.x+pp2.second.x) / 2.0;
    arithmetic tq_y = (pp1.second.y+pp2.second.y) / 2.0;

    p.x = pp2.first.x-tp_x;
    p.y = pp2.first.y-tp_y;
    q.x = pp2.second.x-tq_x;
    q.y = pp2.second.y-tq_y;

    arithmetic l_p_sq = p.x*p.x+p.y*p.y;
    arithmetic l_q_sq = q.x*q.x+q.y*q.y;
    arithmetic l_p = sqrt(l_p_sq);
    arithmetic l_q = sqrt(l_q_sq);

    if (eps>l_p+l_q)
        // Intervall [0,2pi]
        return circular_arc(angle_t(false),angle_t(true));
    if (l_p==0.0)
        if (l_q<=eps)
            // Intervall [0,2pi]
            return circular_arc(angle_t(false),angle_t(true));
        else
            // leeres Intervall
            return circular_arc(angle_t(true),angle_t(false));
    if (l_q==0.0)
        if (l_p<=eps)
            // Intervall [0,2pi]
            return circular_arc(angle_t(false),angle_t(true));
        else
            // return leeres Intervall
            return circular_arc(angle_t(true),angle_t(false));
    arithmetic diff = (l_p-l_q);
    if (diff>eps || (-diff)>eps)
        // leeres Intervall
        return circular_arc(angle_t(true),angle_t(false));

    arithmetic cos_phi = (l_p_sq+l_q_sq-eps*eps)/(2.0*l_p*l_q);
    arithmetic sin_phi = sqrt(1-cos_phi*cos_phi);

    angle_t phi_0(sin_phi,cos_phi);
    angle_t phi_1((-1.0)*sin_phi,cos_phi);

    angle_t alpha(p.y/l_p,p.x/l_p);
    angle_t minus_beta((-1.0)*q.y/l_q,q.x/l_q);

    angle_t theta_0, theta_1;

    theta_0 = alpha;
    theta_0 += minus_beta;
    theta_0 += phi_0;

    theta_1 = alpha;
    theta_1 += minus_beta;
    theta_1 += phi_1;

    return circular_arc(theta_1,theta_0);

}

// ==========================================================================================
template <class index_class, class point>
circular_arc_edge<index_class,point>::border_iterator  circular_arc_edge<index_class,point>::left_borders_begin()// const
// ==========================================================================================
{
        return left_borders.begin();
}

// ==========================================================================================
template <class index_class, class point>
circular_arc_edge<index_class,point>::border_iterator  circular_arc_edge<index_class,point>::left_borders_end()// const
// ==========================================================================================
{
        return left_borders.end();
}

// ==========================================================================================
template <class index_class, class point>
circular_arc_edge<index_class,point>::border_iterator  circular_arc_edge<index_class,point>::right_borders_begin()// const
// ==========================================================================================
{
        return right_borders.begin();
}

// ==========================================================================================
template <class index_class, class point>
circular_arc_edge<index_class,point>::border_iterator  circular_arc_edge<index_class,point>::right_borders_end()// const
// ==========================================================================================
{
        return right_borders.end();
}

// ==========================================================================================
template <class index_class, class point>
inline bool circular_arc_edge<index_class,point>::contains(const angle_t& phi)
// ==========================================================================================
{

        border_iterator l_it = left_borders.begin();
        border_iterator l_end = left_borders.end();
        border_iterator r_it = right_borders.begin();
        border_iterator r_end = right_borders.end();

        for (; l_it!=l_end; l_it++, r_it++)
        {
                if (*l_it<=phi && phi<=*r_it)
        {
                        return true;
        }
        }
        return false;

}

// ==========================================================================================
template <class index_class, class point>
    bool circular_arc_edge<index_class,point>::full(const circular_arc_edge<index_class,point>::circular_arc& I)
// ==========================================================================================
{
    if (I.first==angle_t(false) && I.second==angle_t(true))
        return true;
    return false;
}

// ==========================================================================================
template <class index_class, class point>
    bool circular_arc_edge<index_class,point>::empty(const circular_arc_edge<index_class,point>::circular_arc& I)
// ==========================================================================================
{
    if (I.first==angle_t(true) && I.second==angle_t(false))
        return true;
    return false;
}

// ==========================================================================================
template <class index_class, class point>
circular_arc_edge<index_class,point>::motion circular_arc_edge<index_class,point>::compute_match
    (const circular_arc_edge<index_class,point>::angle_t& phi, const circular_arc_edge<index_class,point>::point_pair& ref_points)
// ==========================================================================================
{

    motion rho_phi = motion(phi);

    point pp = ref_points.first;    
    point qq = ref_points.second;
    qq *= rho_phi;

    arithmetic t_x = pp.x-qq.x;
    arithmetic t_y = pp.y-qq.y;

    motion there(t_x,t_y);
    there *= rho_phi;

    return there;
}




}

#endif

ReSCue - Retrieval System for Curves
Universität Bonn, Institut für Informatik III, 2001