ReSCue - Retrieval System for Curves

---

         

---

covering_matcher.h

#ifndef COVERING_MATCHER_H
#define COVERING_MATCHER_H

#include "polygonal_curve.h"
#include "rescutil.h"
#include "rescuenumerics.h"
#include "rigid_motion_interval.h"
#include "point2.h"

namespace rescue
{

    

// ==========================================================================================
// ==========================================================================================
template<class arithmetic, class interval_container>
class covering_matcher
{

public:

    typedef unit_circle_angle<arithmetic> angle;
    typedef rigid_motion<arithmetic> motion;
    typedef rigid_motion_interval<arithmetic> motion_interval;
    typedef Point2<arithmetic> point;
    typedef polygonal_curve<point> curve;
    typedef curve::size_t index_t;
    typedef polygonal_curve<point>::vertex vertex;
    typedef polygonal_curve<point>::edge edge;

private:
    
    index_t m;
    index_t n;

    index_t m_prime;
    index_t n_prime;

    index_t* c;
    index_t* d;

    index_t* kappa;
    index_t* lambda;
    
    point* P;
    point* Q;
    point* P_prime;
    point* Q_prime;

    arithmetic eps;
    arithmetic delta;

    bool matched;
    bool match_found;

public:

    covering_matcher(curve&, curve&, const arithmetic&, const arithmetic&);

    covering_matcher();

    ~covering_matcher();

    bool match();

    bool dynamic_match();

    rigid_motion<arithmetic> get_match();

private:

    void construct_coverings();

    motion match_result;

    bool match(index_t i, index_t j, index_t i_prime, index_t j_prime);

    bool dynamic_match(index_t i, index_t j, index_t i_prime, index_t j_prime);

    bool approx_intersect(index_t);

    bool dynamic_intersect(index_t);

    void dynamic_delete(index_t);

    static inline arithmetic dist(const point&, const point&);

public:

    void clear();

private:
    
    interval_container dynamic_intervals;

};
// ==========================================================================================
// ==========================================================================================



// ==========================================================================================
template<class arithmetic, class interval_container>
covering_matcher<arithmetic,interval_container>::covering_matcher()
// ==========================================================================================
{

    m = 0;
    n = 0;

    m_prime = 0;
    n_prime = 0;

    c = NULL;
    d = NULL;

    kappa = NULL;
    lambda = NULL;
    
    P = NULL;
    Q = NULL;
    P_prime = NULL;
    Q_prime = NULL;

    eps = 0.0;
    delta = 0.0;

}

// ==========================================================================================
template<class arithmetic, class interval_container>
covering_matcher<arithmetic,interval_container>::covering_matcher(curve& cP, curve& cQ, const arithmetic& ee, const arithmetic& dd)
// ==========================================================================================
{

    eps = ee;
    delta = dd;

    m = cP.length();
    n = cQ.length();
    P = new point[m+1];
    Q = new point[n+1];
    
    curve::vertex_iterator v_it, v_end;
    v_it = cP.vertex_begin();
    v_end = cP.vertex_end();
    index_t i=0;
    for (; v_it!=v_end; v_it++)
    {
        P[i] = (*v_it).pos;
        i++;
    }

    v_it = cQ.vertex_begin();
    v_end = cQ.vertex_end();
    index_t j=0;
    for (; v_it!=v_end; v_it++)
    {
        Q[j] = (*v_it).pos;
        j++;
    }
    
    c = new index_t[m+1];
    d = new index_t[n+1];

    kappa = new index_t[m+n+2];
    lambda = new index_t[m+n+2];
    
    construct_coverings();

}

// ==========================================================================================
template<class arithmetic, class interval_container>
void covering_matcher<arithmetic,interval_container>::construct_coverings()
// ==========================================================================================
{

    std::list<point> P_cp;
    P_cp.push_back(P[0]);
    c[0] = 0;
    
    for (index_t i=0; i<m; i++)
    {

        // construct covering vertices of <p_i,p_{i+1}>
        Point P0 = P[i];
        Point P1 = P[i+1];

        arithmetic length = sqrt((P0.x-P1.x)*(P0.x-P1.x)+(P0.y-P1.y)*(P0.y-P1.y));
        arithmetic Dx = 2.0*delta*(P1.x-P0.x)/length;
        arithmetic Dy = 2.0*delta*(P1.y-P0.y)/length;

        arithmetic covered = 2.0*delta;

        while (covered<=length)
        {
            P0.x += Dx;
            P0.y += Dy;
            P_cp.push_back(P0);
            covered += 2.0*delta;
        }

        P_cp.push_back(P1);        
        c[i+1] = P_cp.size()-1;

    }

    m_prime = P_cp.size()-1;
    P_prime = new point[P_cp.size()];
    std::list<point>::iterator p_it = P_cp.begin();
    i=0;

    for (; p_it!=P_cp.end(); p_it++)
    {
        P_prime[i]=*p_it;
        i++;
    }

    std::list<point> Q_cp;
    Q_cp.push_back(Q[0]);
    d[0] = 0;

    for (index_t j=0; j<n; j++)
    {

        // construct covering vertices of <p_i,p_{i+1}>
        Point Q0 = Q[j];
        Point Q1 = Q[j+1];

        arithmetic length = sqrt((Q0.x-Q1.x)*(Q0.x-Q1.x)+(Q0.y-Q1.y)*(Q0.y-Q1.y));
        arithmetic Dx = 2.0*delta*(Q1.x-Q0.x)/length;
        arithmetic Dy = 2.0*delta*(Q1.y-Q0.y)/length;

        arithmetic covered = 2.0*delta;

        while (covered<=length)
        {
            Q0.x += Dx;
            Q0.y += Dy;
            Q_cp.push_back(Q0);
            covered += 2.0*delta;
        }

        Q_cp.push_back(Q1);        
        d[j+1] = Q_cp.size()-1;

    }

    n_prime = Q_cp.size()-1;
    Q_prime = new point[Q_cp.size()];
    std::list<point>::iterator q_it = Q_cp.begin();
    j=0;

    for (; q_it!=Q_cp.end(); q_it++)
    {
        Q_prime[j]=*q_it;
        j++;
    }

}

// ==========================================================================================
template<class arithmetic, class interval_container>
bool covering_matcher<arithmetic,interval_container>::match()
// ==========================================================================================
{
    return match(0,0,0,0);
}

// ==========================================================================================
template<class arithmetic, class interval_container>
bool covering_matcher<arithmetic,interval_container>::match(index_t i, index_t j, index_t i_prime, index_t j_prime)
// ==========================================================================================
{
    
    if (i==m && j==n)
    {
        kappa[i+j] = c[m];
        lambda[i+j] = d[n];
        return approx_intersect(i+j);
    }

    if (i==m)
    {
        kappa[i+j] = c[m];
        lambda[i+j] = j_prime;
        return match(m,j+1,c[m],d[j+1]);
    }

    if (j==n)
    {
        kappa[i+j] = i_prime;
        lambda[i+j] = d[n];
        return match(i+1,n,c[i+1],d[n]);
    }

    std::list<index_t> A;
    std::list<index_t> B;

    for (index_t a=i_prime; a<=c[i+1] ; a++)
        if (dist(P_prime[i_prime],P_prime[a]) - dist(Q_prime[j_prime],Q_prime[d[j+1]])
                <=2.0*(eps+delta))
            A.push_back(a);
    for (index_t b=j_prime; b<=d[j+1]; b++)
        if (dist(P_prime[i_prime],P_prime[c[i+1]]) - dist(Q_prime[j_prime],Q_prime[b])
                <=2.0*(eps+delta))
            B.push_back(b);

    kappa[i+j] = i_prime;
    lambda[i+j] = j_prime;

    std::list<index_t>::iterator k;
    for (k = A.begin(); k!=A.end(); k++)
        if (match(i,j+1,*k,d[j+1])) return true;

    std::list<index_t>::iterator l;
    for (l = B.begin(); l!=B.end(); l++)
        if (match(i+1,j,c[i+1],*l)) return true;

    return false;

}


// ==========================================================================================
template<class arithmetic, class interval_container>
bool covering_matcher<arithmetic,interval_container>::approx_intersect(index_t N)
// ==========================================================================================
{

    interval_container I;

    for (int i=0; i<=N; i++)
    {
        std::cerr   <<"("<<P_prime[kappa[i]].x<<","<<P_prime[kappa[i]].y<<")::("
                    <<Q_prime[lambda[i]].x<<","<<Q_prime[lambda[i]].y<<")\n";
        I.push_back(std::pair<point,point>(P_prime[kappa[i]],Q_prime[lambda[i]]),eps+delta);
    }

    bool res =  I.is_empty();
    if (res)
        std::cerr<<"true\n";
    else
        std::cerr<<"false\n";
    std::cerr.flush();

    match_result = I.where();

    return res;

}

// ==========================================================================================
template<class arithmetic, class interval_container>
covering_matcher<arithmetic,interval_container>::motion covering_matcher<arithmetic,interval_container>::get_match()
// ==========================================================================================
{
    return match_result;
}

// ==========================================================================================
template<class arithmetic, class interval_container>
void covering_matcher<arithmetic,interval_container>::clear()
// ==========================================================================================
{
    delete[] P;
    delete[] Q;
    delete[] P_prime;
    delete[] Q_prime;
    delete[] c;
    delete[] d;
    delete[] kappa;
    delete[] lambda;
}
    
// ==========================================================================================
template<class arithmetic, class interval_container>
covering_matcher<arithmetic,interval_container>::~covering_matcher()
// ==========================================================================================
{
    clear();
}
    
// ==========================================================================================
template<class arithmetic, class interval_container>
inline arithmetic covering_matcher<arithmetic,interval_container>::dist(const point& P, const point& Q)
// ==========================================================================================
{
    return sqrt((P.x-Q.x)*(P.x-Q.x)+(P.y-Q.y)*(P.y-Q.y));
}

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

}

#endif

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