ReSCue - Retrieval System for Curves

---

         

---

extended_fs_graph.h

#ifndef RESCUE__EXTENDED_FS_GRAPH_H
#define RESCUE__EXTENDED_FS_GRAPH_H

#include <vector>
#include <list>
#include <algorithm>
#include "rescutil.h"
#include "compact_interval_border.h"


namespace rescue
{


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

public:

    typedef transporter_edge transporter_edge_class;
    typedef transporter_edge::angle_t angle_t;
    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::pair<index_t,index_t> discrete_free_space_point;

    typedef std::list<discrete_free_space_point> discrete_reparametrization_pair;

    
    typedef std::vector<interval_border> border_array;
    typedef std::list<interval_border> border_list;
    typedef border_array::iterator border_iterator;

    extended_fs_graph();

    ~extended_fs_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& update_borders);

        bool find_path();

    motion get_match();

    bool get_reparametrizations(discrete_reparametrization_pair& kappa_lambda);

    void clear();

private:

    index_t* columns;

    index_t* rows;
    
    index_t active_columns;
    
    index_t active_rows;

    border_type prev_border_type;

    index_t m;
        
    index_t n;
        
    transporter_edge*** edges; 
    
    bool*** edge_activated;
    
    index_t*** activation_step;

    bool** reachable;

    index_t update_step;

    point_pair reference_points;

    border_value match_pos;

    bool match_found;

    border_list interval_borders_list;

    border_array interval_borders;

    void extract_borders(transporter_edge& E, const index_t& i, const index_t& j,
        graph_direction dir);

    void sort_borders();

public:

    border_iterator border_begin();

        border_iterator border_end();

};

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




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

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

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

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

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

    if (rows!=NULL)
        delete[] rows;
    if (columns!=NULL)
        delete[] columns;
    rows = NULL;
    columns = NULL;

    if (edges!=NULL)
    {
            for (index_t i=0; i<=m; i++)
            {
                    for (index_t j=0; j<=n; j++)
                    {
                            delete[] edges[i][j];
                            delete[] edge_activated[i][j];
                            delete[] activation_step[i][j];
                    }
                    delete[] edges[i];
                        delete[] edge_activated[i];
                        delete[] activation_step[i];
                        delete[] reachable[i];
            }
            delete[] edges;
                delete[] edge_activated;
                delete[] activation_step;
                delete[] reachable;

            edges = NULL;
                edge_activated = NULL;
                activation_step = NULL;
                reachable = NULL;
    }

    m = 0;
    n = 0;
    match_found = false;

}

// ==========================================================================================
template<class transporter_edge>
void extended_fs_graph<transporter_edge>::
        extract_borders(transporter_edge& E,
    const index_t& i, const index_t& j, graph_direction dir)
// ==========================================================================================
{

    edge_border_iterator r_it, r_end, l_it, l_end;

    r_it = E.right_borders_begin();
    r_end = E.right_borders_end();
    l_it = E.left_borders_begin();
    l_end = E.left_borders_end();

    for (; l_it!=l_end; l_it++)
    {
        transporter_edge::angle_t a = *l_it;
        if (a.type!=transporter_edge::angle_t::regular && a.type!=transporter_edge::angle_t::two_pi)
            return;
        interval_borders_list.push_back(interval_border(a,LEFT_BORDER,i,j,dir));
    }

    for (; r_it!=r_end; r_it++)
    {
        transporter_edge::angle_t a = *r_it;
        if (a.type!=transporter_edge::angle_t::regular && a.type!=transporter_edge::angle_t::two_pi)
            return;
        interval_borders_list.push_back(interval_border(a,RIGHT_BORDER,i,j,dir));
    }

}

// ==========================================================================================
template<class transporter_edge>
void extended_fs_graph<transporter_edge>::
        sort_borders()
// ==========================================================================================
{
    
    // assign sufficient space to border_intervals
    index_t ii = interval_borders_list.size();
    interval_borders = border_array(interval_borders_list.size());

    // copy from border_interval_list to border_intervals
    //std::copy(
    //    interval_borders_list.begin(),interval_borders_list.end(),
    //    interval_borders.begin());

    border_list::iterator b_it = interval_borders_list.begin();
    border_list::iterator b_end = interval_borders_list.end();

    for (; b_it!=b_end; b_it++)
    {
        interval_border border = *b_it;
        if (!(border.m_value.s<-1. || border.m_value.s>1.))
            interval_borders.push_back(border);
    }

    // sort border_intervals
    std::sort(interval_borders.begin(),interval_borders.end());

    // the unsorted list is needed no mo'.
    interval_borders_list.clear();

}

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

        index_t i = ib.col();
    index_t j = ib.row();
    match_pos = ib.val();

    // update suitability-data of currently active intervals
    if (ib.type()==LEFT_BORDER)
    {
        columns[ib.col()]++;
        rows[ib.row()]++;
        if (rows[ib.row()]==1)
            active_rows++;
        if (columns[ib.col()]==1)
            active_columns++;
            // toggle edge activation
            edge_activated[i][j][ib.dir()] = true;
    } 


    // determine whether the active configuration of active edges is suitable
    // using the suitability information that has just been updated
    bool suitable;
    if (active_columns>=m && active_rows>=n && 
        ib.type()==RIGHT_BORDER && prev_border_type==LEFT_BORDER)
        suitable = true;
    else
        suitable = false;

    border_type prev_border_type = ib.type();

    if (suitable)
    {            
                if (find_path())
        {
                        return true;
        }
    }

    // The suitability-information for left interval broders
    // is updated after the path-update, because the border itself is still contained
    // in the intersection.
    if (ib.type()==RIGHT_BORDER)
    {
        columns[ib.col()]--;
        rows[ib.row()]--;
        if (rows[ib.row()]==0)
            active_rows--;
        if (columns[ib.col()]==0)
            active_columns--;
        // toggle edge activation
                edge_activated[i][j][ib.dir()] = false;
    }
        
        return false;

}


// ==========================================================================================
template<class transporter_edge>
void extended_fs_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;

    update_step = 0;

    // initialize the counters that help to determine the suitability
    // of the currently active intervals.
    prev_border_type = LEFT_BORDER;
    index_t i;
    columns = new index_t[m+1];
    rows = new index_t[n+1];
    for (i=0; i<=m; i++)
        columns[i] = 0;
    for (i=0; i<=n; i++)
        rows[i] = 0;
    active_columns = 0;
    active_rows = 0;

        edges = new transporter_edge**[m+1];
        edge_activated = new bool**[m+1];
        activation_step = new index_t**[m+1];
    reachable = new bool*[m+1];

        reference_points = point_pair(P[0],Q[0]);
        
        for (i=0; i<m; i++)
        {
                edges[i] = new transporter_edge*[n+1];
                edge_activated[i] = new bool*[n+1];
                activation_step[i] = new index_t*[n+1];
        reachable[i] = new bool[n+1];

        for (index_t j=0; j<n; j++)
                {
                        edges[i][j] = new transporter_edge[3];
                        edge_activated[i][j] = new bool[3];
                        activation_step[i][j] = new index_t[3];

                        edges[i][j][horizontal].assign_transporter
                                (point_pair(P[i],P[i+1]),point_pair(Q[j],Q[j]),reference_points,eps,delta);
                        edges[i][j][diagonal].assign_transporter
                                (point_pair(P[i],P[i+1]),point_pair(Q[j],Q[j+1]),reference_points,eps,delta);
                        edges[i][j][vertical].assign_transporter
                                (point_pair(P[i],P[i]),point_pair(Q[j],Q[j+1]),reference_points,eps,delta);
            
            // extract interval borders from the three edges just created            
            extract_borders(edges[i][j][horizontal],i,j,horizontal);
            extract_borders(edges[i][j][diagonal],i,j,diagonal);
            extract_borders(edges[i][j][vertical],i,j,vertical);

            // initially, each edge is inactive (until it is activated in an update()-step)
            edge_activated[i][j][horizontal] = false;
            edge_activated[i][j][diagonal] = false;
            edge_activated[i][j][vertical] = false;

            // activation_step 0 means that the edge has never been activated.
            activation_step[i][j][horizontal] = 0;
            activation_step[i][j][diagonal] = 0;
            activation_step[i][j][vertical] = 0;

            // since all edges are inactive, no vertex is reachable
            // (except for the source (0,0), but we'll take care of that later...).
            reachable[i][j] = false;

                }

        reachable[i][n] = false;
                edges[i][n] = new transporter_edge[3];
                edge_activated[i][n] = new bool[3];
                activation_step[i][n] = new index_t[3];

                edges[i][n][horizontal].assign_transporter
                                (point_pair(P[i],P[i+1]),point_pair(Q[n],Q[n]),reference_points,eps,delta);
        extract_borders(edges[i][n][horizontal],i,n,horizontal);
        edge_activated[i][n][horizontal] = false;
        activation_step[i][n][horizontal] = 0;

        }

        edges[m] = new transporter_edge*[n+1];
        edge_activated[m] = new bool*[n+1];
        activation_step[m] = new index_t*[n+1];
    reachable[m] = new bool[n+1];

        for (index_t j=0; j<n; j++)
        {
        reachable[m][j] = false;

                edges[m][j] = new transporter_edge[3];
                edge_activated[m][j] = new bool[3];
                activation_step[m][j] = new index_t[3];

        edges[m][j][vertical].assign_transporter
                        (point_pair(P[m],P[m]),point_pair(Q[j],Q[j+1]),reference_points,eps,delta);
        extract_borders(edges[m][j][vertical],m,j,vertical);

        // initially, each edge is inactive (until it is activated in an update()-step)
        edge_activated[m][j][vertical] = false;
        // activation_step 0 means that the edge has never been activated.
        activation_step[m][j][vertical] = 0;

        }

    reachable[m][n] = false;
        edges[m][n] = new transporter_edge[3];
        edge_activated[m][n] = new bool[3];
        activation_step[m][n] = new index_t[3];


    // Before we forget: the graph's source (0,0) is always reachable!
    reachable[0][0] = true;

    // sort the extracted interval borders
    sort_borders();
                
}

// ==========================================================================================
template<class transporter_edge>
bool extended_fs_graph<transporter_edge>::
        find_path()
// ==========================================================================================
{
        bool* last_column;
        bool* curr_column;

    // use dynamic programming for updating the graph.  

        bool path_found;
    match_found = false;

    bool b_v, b_h, b_d;

        // initialize last_row
        last_column = reachable[0];

        last_column[0] = true;
        for (index_t j=1; j<=n; j++)
        {
        b_v = edge_activated[0][j-1][vertical];
                last_column[j] = last_column[j-1] && b_v;
        }

    // in case m==0, curr_column[m][n] needs to specified...
        curr_column = last_column;
        index_t i=1;

        // dynamic programming
    path_found = true;
        for (; i<=m && path_found; i++)
        {
                last_column = reachable[i-1];
                curr_column = reachable[i];

                path_found = false;
                curr_column[0] = false;
        b_h = edge_activated[i-1][0][horizontal];
                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 = edge_activated[i-1][j-1][diagonal];                    
            if (last_column[j-1] && b_d)
                        {
                                curr_column[j] = true;
                                path_found = true;
            } else {
                b_v = edge_activated[i][j-1][vertical];
                if (curr_column[j-1] && b_v)
                                {
                                        curr_column[j] = true;
                                        path_found = true;
                } else {
                    b_h = edge_activated[i-1][j][horizontal];
                                if (last_column[j] && b_h)
                                    {
                                            curr_column[j] = true;
                                            path_found = true;
                    }
                }
            }
                }

        }

        if (curr_column[n])
        {
        match_found = true;
                return true;
        }

        return false;

}


// ==========================================================================================
template<class transporter_edge>
extended_fs_graph<transporter_edge>::motion 
    extended_fs_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 extended_fs_graph<transporter_edge>::get_reparametrizations
    (extended_fs_graph<transporter_edge>::discrete_reparametrization_pair& kappa_lambda)
// ==========================================================================================
{

    kappa_lambda.clear();
    int i = m;
    int j = n;
    kappa_lambda.push_front(discrete_free_space_point(i,j));

    while (i>0 || j>0)
    {
        if (i>0 && j>0 && reachable[i-1][j-1] && edge_activated[i-1][j-1][diagonal]) {
            // activating the following lines inserts a loop for the diagonal edge...
                        // discrete_free_space_point x(i,j);
            //kappa_lambda.push_front(x);
            i--;
            j--;
                        discrete_free_space_point y(i,j);
            kappa_lambda.push_front(y);
        } else if (i>0 && reachable[i-1][j] && edge_activated[i-1][j][horizontal]) {
            i--;
                        discrete_free_space_point x(i,j);
            kappa_lambda.push_front(x);
        } else if (j>0 && reachable[i][j-1] && edge_activated[i][j-1][vertical]) {
            j--;
                        discrete_free_space_point x(i,j);
            kappa_lambda.push_front(x);
        } else {
                        return false;
                }
    }
    
    return true;

}


// end of namespace rescue
}


#endif

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