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

rescue::extended_fs_graph Template Class Reference

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

#include <extended_fs_graph.h>

List of all members.

Public Types

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
 Type by which the interval borders are described.

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.

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

Public Methods

 extended_fs_graph ()
 Default constructor. More...

 ~extended_fs_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& update_borders)
 Updates reachability etc. More...

bool find_path ()
 Determines whether there is a path from (0,0) to (m,n) (i.e., a flow) along the currently active edges through the graph. 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)
 Returns a pair (kappa, lambda) containing the discretized reparametrizations that deschribe a monotonic curve in the 2(eps + delta)-free space.

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

border_iterator border_begin ()
 This iterator allows to iterate over all interval borders of the edges assigned to the graph. More...

border_iterator border_end ()
 See border_begin().

Detailed Description

template<class transporter_edge> template class rescue::extended_fs_graph

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

The class extended_fs_graph supplies all neccessary operations for such a graph, in particular finding certain maximal paths and dynamically extending the active configuration of edges.

Member Typedef Documentation

template<classtransporter_edge>
typedef std::pair<index_t,index_t> rescue::extended_fs_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).

Constructor & Destructor Documentation

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

Default constructor.

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

Member Function Documentation

template<classtransporter_edge>
extended_fs_graph< transporter_edge >::border_iterator rescue::extended_fs_graph< transporter_edge >::border_begin ( )
 

This iterator allows to iterate over all interval borders of the edges assigned to the graph.

The iteration is performed in ascending order.

template<classtransporter_edge>
void rescue::extended_fs_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>
bool rescue::extended_fs_graph< transporter_edge >::find_path ( )
 

Determines whether there is a path from (0,0) to (m,n) (i.e., a flow) along the currently active edges through the graph.

Each instance of the flow problem takes O(mn) time (using dynamic programming).

template<classtransporter_edge>
extended_fs_graph< transporter_edge >::motion rescue::extended_fs_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::extended_fs_graph< transporter_edge >::update ( const interval_border & ib )
 

Updates reachability etc.

by changing all properties affected by (de-)activating the edge indicated by ib.

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