ReSCue - Retrieval System for Curves
Main Page   Class Hierarchy   Compound List   File List   Compound Members  

rescue::free_space_graph Template Class Reference

The free space graph is an essential part of the matching-algorithm used by the class sampling_matcher. More...

#include <free_space_graph.h>

List of all members.

Public Types

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
 The matching task only yields discretized curves through the approximate free space. More...

typedef std::list<discrete_free_space_point> discrete_reparametrization_pair
 A discrete_reparametrization_pair is a sequence of (discrete) points contained in the (approxiamte) free space. More...


Public Methods

 free_space_graph ()
 Default constructor. More...

 ~free_space_graph ()
 Default destructor; calls clear() in order to deallocate all reserved memory.

void build (point* P,point* Q,index_t m_P,index_t n_Q, const arithmetic& eps, const arithmetic& delta)
 Constructs the free space graph of the polygonal curves P and Q of lengths m and n , respectively. More...

bool update (const interval_border& e)
 Determines whether there is a path through the graph having the property that one of the (left) bounds assigned to e is contained in all projected transporters assigned to the edges along the path. More...

motion get_match ()
 Returns an element g of the transformation group with the property that d_F(P,gQ)<=2(eps+delta), if such g exists. More...

bool get_reparametrizations (discrete_reparametrization_pair& kappa_lambda)
 In this class, this method is provided only for reasons of upward-compatibility.

void clear ()
 Deallocates all memory reserved by the free_space_graph object.

edge_iterator edge_begin ()
edge_iterator edge_end ()
border_iterator border_begin ()
border_iterator border_end ()

Public Attributes

index_t m
 The width of the graph, i.e. More...

index_t n
 The height of the graph, i.e. More...

transporter_edge*** edges
 The set of all edges of the graph. More...


Friends

class  edge_iterator

Detailed Description

template<class transporter_edge> template class rescue::free_space_graph

The free space graph is an essential part of the matching-algorithm used by the class sampling_matcher.

The class free_space_graph supplies all neccessary operations for such a graph, in particular finding certain maximal paths.

Member Typedef Documentation

template<classtransporter_edge>
typedef std::pair<index_t,index_t> rescue::free_space_graph<transporter_edge>::discrete_free_space_point
 

The matching task only yields discretized curves through the approximate free space.

Thus, the points in free space can be described by integers (represented by the type index_t). In this class, this type is provided only for reasons of upward-compatibility.

template<classtransporter_edge>
typedef std::list<discrete_free_space_point> rescue::free_space_graph<transporter_edge>::discrete_reparametrization_pair
 

A discrete_reparametrization_pair is a sequence of (discrete) points contained in the (approxiamte) free space.

In this class, this type is provided only for reasons of upward-compatibility.

Constructor & Destructor Documentation

template<classtransporter_edge>
rescue::free_space_graph< transporter_edge >::free_space_graph<transporter_edge> ( )
 

Default constructor.

Initializes an empty graph; for initialization, use build() .

Member Function Documentation

template<classtransporter_edge>
void rescue::free_space_graph< transporter_edge >::build ( point * P,
point * Q,
index_t m_P,
index_t n_Q,
const arithmetic & eps,
const arithmetic & delta )
 

Constructs the free space graph of the polygonal curves P and Q of lengths m and n , respectively.

eps specifies the fault tolerance and delta specifies the sampling density and thus the quality of approximation.

template<classtransporter_edge>
free_space_graph< transporter_edge >::motion rescue::free_space_graph< transporter_edge >::get_match ( )
 

Returns an element g of the transformation group with the property that d_F(P,gQ)<=2(eps+delta), if such g exists.

The output refers to the last call of match() . If no such g exists or if match() has not yet been called, the output is not specified.

template<classtransporter_edge>
bool rescue::free_space_graph< transporter_edge >::update ( const interval_border & e )
 

Determines whether there is a path through the graph having the property that one of the (left) bounds assigned to e is contained in all projected transporters assigned to the edges along the path.

For each (left) bound assigned to e, one instance of a flow-problem is computed, where each instance of the flow problem takes O(mn) time.

The set of all (left) bounds of the interval is determined using the border_iterator of e .

Member Data Documentation

template<classtransporter_edge>
transporter_edge *** rescue::free_space_graph<transporter_edge>::edges
 

The set of all edges of the graph.

Needs to be public for internal reasons; other classes should not access edges anyway. (I know this needs to be fixed...)

template<classtransporter_edge>
index_t rescue::free_space_graph<transporter_edge>::m
 

The width of the graph, i.e.

the length of the polygonal curve P specified in build() . Needs to be public for internal reasons; other classes should not access m anyway. (I know this needs to be fixed...)

template<classtransporter_edge>
index_t rescue::free_space_graph<transporter_edge>::n
 

The height of the graph, i.e.

the length of the polygonal curve Q specified in build() . Needs to be public for internal reasons; other classes should not access n anyway. (I know this needs to be fixed...)

The documentation for this class was generated from the following file:
ReSCue - Retrieval System for Curves
Universität Bonn, Institut für Informatik III, 2001