ReSCue - Retrieval System for Curves

---

         

---

free_space_graph.h

#ifndef RESCUE__FREE_SPACE_GRAPH_H
#define RESCUE__FREE_SPACE_GRAPH_H

#include "rescutil.h"

namespace rescue
{


// ==========================================================================================
// ==========================================================================================
template<class transporter_edge>
class free_space_graph
{

friend class edge_iterator;

protected:

public:

    typedef transporter_edge transporter_edge_class;
    typedef transporter_edge::index_t index_t;
    typedef transporter_edge::arithmetic_t arithmetic;
    typedef transporter_edge::interval_border interval_border;
        typedef transporter_edge::border_iterator edge_border_iterator;
    typedef transporter_edge::point_t point;
    typedef transporter_edge::motion motion;

    typedef arithmetic arithmetic_t;

    typedef std::pair<point,point> point_pair;
    typedef transporter_edge::border_value border_value;
    typedef std::list<interval_border> border_list;
    typedef border_list::iterator border_iterator;

    typedef std::pair<index_t,index_t> discrete_free_space_point;

    typedef std::list<discrete_free_space_point> discrete_reparametrization_pair;


    free_space_graph();

    ~free_space_graph();

    void build(point* P,point* Q,index_t m_P,index_t n_Q, 
                const arithmetic& eps, const arithmetic& delta);

        bool update(const interval_border& e);

    motion get_match();

    bool get_reparametrizations(discrete_reparametrization_pair& kappa_lambda);

    void clear();

    index_t m;
        
    index_t n;
        
    transporter_edge*** edges; 

private:
    
    void save_borders(transporter_edge& e, index_t col, index_t row, graph_direction dir);

    border_list left_border_list;

    point_pair reference_points;

    border_value match_pos;

    bool match_found;


    // ==========================================================================================
    // ==========================================================================================
    class edge_iterator
    {

    protected:

            transporter_edge*** edges;
            index_t i;
            index_t j;
            index_t m;
            index_t n;
            graph_direction dir;


    public:

        // ==========================================================================================
            inline edge_iterator()
        // ==========================================================================================
            {
            }

        // ==========================================================================================
        inline edge_iterator(index_t it_i, index_t it_j, 
                    graph_direction it_dir, const free_space_graph<transporter_edge>& Gamma)
        // ==========================================================================================
        {
            i = it_i;
                    j = it_j;
                    dir = it_dir;
                    m = Gamma.m;
                    n = Gamma.n;
                    edges = Gamma.edges;
        }

        // ==========================================================================================
        inline edge_iterator& operator++()
        // ==========================================================================================
        {
                    
                    if (dir<vertical)
                    {
                            dir++;
                            return *this;
                    }
                    dir = horizontal;

                    if (i<m-1)
                    {
                            i++;
                            return *this;
                    }
                    i=0;

                    if (j<=n-1)
                    {
                            j++;
                            return *this;
                    }

                    return *this;

        }

        // ==========================================================================================
        inline edge_iterator& operator++(int)
        // ==========================================================================================
        {
                    
                    if (j==n)
                    {
                            if (i<m)
                            {
                                    i++;
                                    j=0;
                                    dir=horizontal;
                            }
                            return *this;
                    }

                    if (i==m)
                    {
                            if (j<n)
                            {
                                    j++;
                                    dir=vertical;
                            }
                            return *this;
                    }

                    if (dir==horizontal)
                    {
                            dir=diagonal;
                            return *this;
                    }
                    if (dir==diagonal)
                    {
                            dir=vertical;
                            return *this;
                    }
                    dir = horizontal;

                    if (j<n)
                    {
                            j++;
                            return *this;
                    }

                    if (i<m)
                    {
                            i++;
                            j=0;
                            if (i==m)
                                    dir=vertical;
                            return *this;
                    }

                    return *this;

        }

        // ==========================================================================================
        inline transporter_edge& operator*()
        // ==========================================================================================
        {
            return edges[i][j][dir];
        }

        // ==========================================================================================
        inline bool operator==(const edge_iterator& e_it)
        // ==========================================================================================
        {
            return dir==e_it.dir && i==e_it.i && j==e_it.j;
        }

        // ==========================================================================================
        inline bool operator!=(const edge_iterator& e_it)
        // ==========================================================================================
        {
            return !(dir==e_it.dir && i==e_it.i && j==e_it.j);
        }

    };


public:

        edge_iterator edge_begin();
        edge_iterator edge_end();

        border_iterator border_begin();
        border_iterator border_end();

};

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



// ==========================================================================================
template<class transporter_edge>
free_space_graph<transporter_edge>::
        free_space_graph()
// ==========================================================================================
{
        m=0;
        n=0;
        edges = NULL;
    match_found = false;
}

// ==========================================================================================
template<class transporter_edge>
free_space_graph<transporter_edge>::
        ~free_space_graph()
// ==========================================================================================
{
        clear();
}

// ==========================================================================================
template<class transporter_edge>
free_space_graph<transporter_edge>::edge_iterator
free_space_graph<transporter_edge>::edge_begin()
// ==========================================================================================
{
    if (m>0)
            return edge_iterator(0,0,horizontal,*this);
    else
        // If m=0, all edges are vertical ones.
        // Thus, we have to start with a vertical edge
        // in the begin() iterator.
            return edge_iterator(0,0,vertical,*this);
}

// ==========================================================================================
template<class transporter_edge>
free_space_graph<transporter_edge>::edge_iterator
free_space_graph<transporter_edge>::edge_end()
// ==========================================================================================
{
    if (n>0)
        return edge_iterator(m,n,vertical,*this);
    else
        // If n=0, all edges are horizontal ones.
        // Thus, treating the end() edge as a horizontal
        // one makes life more convenient in this case.
        return edge_iterator(m,n,horizontal,*this);
}


// ==========================================================================================
template<class transporter_edge>
free_space_graph<transporter_edge>::border_iterator
free_space_graph<transporter_edge>::border_begin()
// ==========================================================================================
{
    return left_border_list.begin();
}

// ==========================================================================================
template<class transporter_edge>
free_space_graph<transporter_edge>::border_iterator
free_space_graph<transporter_edge>::border_end()
// ==========================================================================================
{
    return left_border_list.end();
}

// ==========================================================================================
template<class transporter_edge>
void free_space_graph<transporter_edge>::
        clear()
// ==========================================================================================
{

        if (edges!=NULL)
    {
            for (index_t i=0; i<=m; i++)
            {
                    for (index_t j=0; j<=n; j++)
                    {
                            delete[] edges[i][j];
                    }
                    delete[] edges[i];
            }
            delete[] edges;
            edges = NULL;
    }
    //left_border_list.clear();
    m = 0;
    n = 0;
    match_found = false;

}

// ==========================================================================================
template<class transporter_edge>
void free_space_graph<transporter_edge>::
        build(point* P,point* Q,index_t m_P,index_t n_Q, 
        const arithmetic& eps, const arithmetic& delta)
// ==========================================================================================
{

        clear();

        m = m_P;
        n = n_Q;

        edges = new transporter_edge**[m+1];

        reference_points = point_pair(P[0],Q[0]);
        
        for (index_t i=0; i<m; i++)
        {
                edges[i] = new transporter_edge*[n+1];
                for (index_t j=0; j<n; j++)
                {
                        edges[i][j] = new transporter_edge[3];
                        edges[i][j][horizontal].assign_transporter
                                (point_pair(P[i],P[i+1]),point_pair(Q[j],Q[j]),reference_points,eps,delta);
            save_borders(edges[i][j][horizontal],i,j,horizontal);
                        
            edges[i][j][diagonal].assign_transporter
                                (point_pair(P[i],P[i+1]),point_pair(Q[j],Q[j+1]),reference_points,eps,delta);
            save_borders(edges[i][j][diagonal],i,j,diagonal);

            edges[i][j][vertical].assign_transporter
                                (point_pair(P[i],P[i]),point_pair(Q[j],Q[j+1]),reference_points,eps,delta);
            save_borders(edges[i][j][vertical],i,j,vertical);
                }
                edges[i][n] = new transporter_edge[3];
                edges[i][n][horizontal].assign_transporter
                                (point_pair(P[i],P[i+1]),point_pair(Q[n],Q[n]),reference_points,eps,delta);
        save_borders(edges[i][n][horizontal],i,n,horizontal);
        }

        edges[m] = new transporter_edge*[n+1];
        for (index_t j=0; j<n; j++)
        {
                edges[m][j] = new transporter_edge[3];
                edges[m][j][vertical].assign_transporter
                        (point_pair(P[m],P[m]),point_pair(Q[j],Q[j+1]),reference_points,eps,delta);
        save_borders(edges[m][j][vertical],m,j,vertical);

        }
        edges[m][n] = new transporter_edge[3];

}

// ==========================================================================================
template<class transporter_edge>
void free_space_graph<transporter_edge>::
        save_borders(transporter_edge& e, index_t col, index_t row, graph_direction dir)
// ==========================================================================================
{
    transporter_edge::border_iterator b_it = e.left_borders_begin();
    transporter_edge::border_iterator b_end = e.left_borders_end();

    for (; b_it!=b_end; b_it++)
    {
        left_border_list.push_back(interval_border(*b_it,LEFT_BORDER,col,row,dir));
    }
}

// ==========================================================================================
template<class transporter_edge>
bool free_space_graph<transporter_edge>::
    update(const free_space_graph<transporter_edge>::interval_border& ib)
// ==========================================================================================
{

        bool* last_column = new bool[n+1];
        bool* curr_column = new bool[n+1];

        bool path_found;
    match_found = false;

    bool b_v, b_h, b_d;

        // initialize last_row
        last_column[0] = true;
        curr_column[0] = true;
        for (index_t j=1; j<=n; j++)
        {
        b_v = edges[0][j-1][vertical].contains(ib.val());
                last_column[j] = last_column[j-1] && b_v;
        }
    // curr_column[n] needs to be initialized for the case m=0
    curr_column[n] = last_column[n];

        // dynamic programming
    path_found = true;
    index_t i;
        for (i=1; i<=m && path_found; i++)
        {
                path_found = false;
                curr_column[0] = false;
        b_h = edges[i-1][0][horizontal].contains(ib.val());
                if (last_column[0] && b_h)
                {
                        curr_column[0] = true;
                        path_found = true;
                }
                for (index_t j=1; j<=n; j++)
                {
                        curr_column[j] = false;

            // if-clause slightly optimized "by hand"
            b_d = edges[i-1][j-1][diagonal].contains(ib.val());                    
            if (last_column[j-1] && b_d)
                        {
                                curr_column[j] = true;
                                path_found = true;
            } else {
                b_v = edges[i][j-1][vertical].contains(ib.val());
                if (curr_column[j-1] && b_v)
                                {
                                        curr_column[j] = true;
                                        path_found = true;
                } else {
                    b_h = edges[i-1][j][horizontal].contains(ib.val());
                                if (last_column[j] && b_h)
                                    {
                                            curr_column[j] = true;
                                            path_found = true;
                    }
                }
            }
                        last_column[j-1] = curr_column[j-1];
                }
                last_column[n-1] = curr_column[n-1];
                last_column[n] = curr_column[n];

        }

        if (curr_column[n])
        {
                delete[] curr_column;
                delete[] last_column;
        match_found = true;
        match_pos = ib.val();
                return true;
        }

        delete[] curr_column;
        delete[] last_column;
        return false;
}


// ==========================================================================================
template<class transporter_edge>
free_space_graph<transporter_edge>::motion 
    free_space_graph<transporter_edge>::get_match()
// ==========================================================================================
{

    if (m==0 && n==0)
    {
        transporter_edge te;
        te.assign_transporter
            (point_pair(reference_points.first,reference_points.first),
             point_pair(reference_points.second,reference_points.second),
             reference_points,1.0,1.0);
        return transporter_edge::compute_match(*(te.left_borders_begin()),reference_points);

    }

    if (match_found)
    {
        return transporter_edge::compute_match(match_pos,reference_points);
    }
    motion match_motion;
    return match_motion;

}

// ==========================================================================================
template<class transporter_edge>
bool free_space_graph<transporter_edge>::get_reparametrizations
    (free_space_graph<transporter_edge>::discrete_reparametrization_pair& kappa_lambda)
// ==========================================================================================
{

    kappa_lambda.clear();    
    return false;

}




}

#endif

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