rescue::sampling_matcher Template Class Reference

A sampling_matcher allows to approximately match two polygonal curves with respect to the Frechet distance by approximately solving the emptyness problem for the set of all Frechet matches. More...

#include <sampling_matcher.h>

List of all members.

Public Types

typedef fs_graph::transporter_edge_class transporter_edge

typedef fs_graph::motion motion

typedef fs_graph::arithmetic_t arithmetic

typedef arithmetic arithmetic_t

typedef fs_graph::index_t index_t

typedef fs_graph::point point

typedef fs_graph::discrete_reparametrization_pair discrete_reparametrization_pair

typedef polygonal_curve<point> curve

typedef curve::vertex vertex

typedef curve::edge edge

Public Methods

bool get_reparametrizations (discrete_reparametrization_pair&)

Returns a pair (kappa, lambda) containing the curves P and gQ reparemtrized by kappa and lambda, where g is a group element found by find_path() (if such g is available).

sampling_matcher (curve& P, curve& Q, const arithmetic& ee)

Initializes an object that computes a solution to the emptyness-problem of discrete Frechet-Matches. More...

sampling_matcher (curve& cP, curve& cQ, const arithmetic& ee, const arithmetic& dd)

Initializes an object that computes a solution to the emptyness-problem of Frechet-Matches. More...

sampling_matcher ()

Default constructor.

~sampling_matcher ()

Default destructor.

bool match ()

Runs the matching algorithm, taking O(m^2n^2) time if both P and Q are delta - sampled.

motion get_match ()

Returns a transformation computed by match(). More...

bool get_reparametrized_curves (curve& P_kappa, curve& Q_lambda)

Returns a pair (P_kappa, P_lambda) containing the curves P and gQ reparemtrized by kappa and lambda, where g is a group element found by find_path() (if such g is available).

void clear ()

Deallocates all memory used by the sampling_matcher object.

Protected Attributes

index_t m

Length of the delta - sampled polygonal curve P.

index_t n

Length of delta - sampled the polygonal curve Q.

index_t* kappa

Reparemtrization of P indicating a match. More...

index_t* lambda

Reparemtrization of Q indicating a match. More...

point* P

delta - sampled Polygonal curve of length m. More...

point* Q

delta - sampled Polygonal curve of length n. More...

arithmetic eps

Fault tolerance for matching.

arithmetic delta

Sampling density for matching; controls the aulity of approximation.

bool matched

Determines whether match() has been called since initialization or since the last call of clear().

bool match_found

Indicates whether the last call of match() yielded a match for P and Q. More...

bool parametrizations_available

Indicates whether parametrizations computed during the last call of match() can be specified.

fs_graph Gamma

The free space graph used for matching.

motion match_motion

A match found by match(). More...

discrete_reparametrization_pair match_kappa_lambda

A reparametrization found by match(). More...

Static Protected Methods

arithmetic dist (const point& x, const point& y)

Computes the Euclidean distance between x and y.

Detailed Description

template<class fs_graph> template class rescue::sampling_matcher

A sampling_matcher allows to approximately match two polygonal curves with respect to the Frechet distance by approximately solving the emptyness problem for the set of all Frechet matches.

The algorithm used is based on delta - samplings of polygonal curves.

The template parameters have the following meaning:

Parameters:

arithmetic determines the data type that is used for all arithmetic. All computations only use multiplication, division, addition, subtraction and computation of roots. Thus, the Leda-type real can be used as well as float and double.

transporter_edge determines the objects that are assigned to edges of the free space graph, and thus the group under which the matching problem is solved. Each edge is assigned a (projected) transporter subset of the transformation group, and the class transporter_edge needs to supply the neccessary operations for these transporter subsets. Currently, circular_arc_edge can be used for matching under rigid motions. The implementation of interval_edge for matching under homthetic motions is planned.

Constructor & Destructor Documentation

template<classfs_graph>

rescue::sampling_matcher< fs_graph >::sampling_matcher<fs_graph> ( curve & cP,

curve & cQ,

const arithmetic & ee )

Initializes an object that computes a solution to the emptyness-problem of discrete Frechet-Matches.
ee specifes the fault tolerance used for the matching task.

template<classfs_graph>

rescue::sampling_matcher< fs_graph >::sampling_matcher<fs_graph> ( curve & cP,

curve & cQ,

const arithmetic & ee,

const arithmetic & dd )

Initializes an object that computes a solution to the emptyness-problem of Frechet-Matches.
ee specifes the fault tolerance and dd the sampling density (and thus the quality of approximation) used for the matching task.

Member Function Documentation

template<classfs_graph>

sampling_matcher< fs_graph >::motion rescue::sampling_matcher< fs_graph >::get_match ( )

Returns a transformation computed by match().
Only specified if match() has been called before and returned true.

Member Data Documentation

template<classfs_graph>

point * rescue::sampling_matcher<fs_graph>::P [protected]

delta - sampled Polygonal curve of length m.
P[0], P[1], ..., \c P[m] are the vertices of P.

template<classfs_graph>

point * rescue::sampling_matcher<fs_graph>::Q [protected]

delta - sampled Polygonal curve of length n.
Q[0], Q[1], ..., \c Q[n] are the vertices of Q.

template<classfs_graph>

index_t * rescue::sampling_matcher<fs_graph>::kappa [protected]

Reparemtrization of P indicating a match.
Currently unused.

template<classfs_graph>

index_t * rescue::sampling_matcher<fs_graph>::lambda [protected]

Reparemtrization of Q indicating a match.
Currently unused.

template<classfs_graph>

bool rescue::sampling_matcher<fs_graph>::match_found [protected]

Indicates whether the last call of match() yielded a match for P and Q.
Only specified if matched is true.

template<classfs_graph>

discrete_reparametrization_pair rescue::sampling_matcher<fs_graph>::match_kappa_lambda [protected]

A reparametrization found by match().
Only specified if both matched and match_found are true.

template<classfs_graph>

motion rescue::sampling_matcher<fs_graph>::match_motion [protected]

A match found by match().
Only specified if both matched and match_found are true.

The documentation for this class was generated from the following file:

sampling_matcher.h

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

Public Types
typedef fs_graph::transporter_edge_class	transporter_edge
typedef fs_graph::motion	motion
typedef fs_graph::arithmetic_t	arithmetic
typedef arithmetic	arithmetic_t
typedef fs_graph::index_t	index_t
typedef fs_graph::point	point
typedef fs_graph::discrete_reparametrization_pair	discrete_reparametrization_pair
typedef polygonal_curve<point>	curve
typedef curve::vertex	vertex
typedef curve::edge	edge
Public Methods
bool	get_reparametrizations (discrete_reparametrization_pair&)
	Returns a pair (`kappa`, `lambda)` containing the curves `P` and `gQ` reparemtrized by `kappa` and `lambda`, where `g` is a group element found by `find_path()` (if such `g` is available).
	sampling_matcher (curve& P, curve& Q, const arithmetic& ee)
	Initializes an object that computes a solution to the emptyness-problem of discrete Frechet-Matches. More...
	sampling_matcher (curve& cP, curve& cQ, const arithmetic& ee, const arithmetic& dd)
	Initializes an object that computes a solution to the emptyness-problem of Frechet-Matches. More...
	sampling_matcher ()
	Default constructor.
	~sampling_matcher ()
	Default destructor.
bool	match ()
	Runs the matching algorithm, taking O(m^2n^2) time if both `P` and `Q` are `delta` - sampled.
motion	get_match ()
	Returns a transformation computed by `match()`. More...
bool	get_reparametrized_curves (curve& P_kappa, curve& Q_lambda)
	Returns a pair (`P_kappa`, `P_lambda)` containing the curves `P` and `gQ` reparemtrized by `kappa` and `lambda`, where `g` is a group element found by `find_path()` (if such `g` is available).
void	clear ()
	Deallocates all memory used by the `sampling_matcher` object.
Protected Attributes
index_t	m
	Length of the `delta` - sampled polygonal curve `P`.
index_t	n
	Length of `delta` - sampled the polygonal curve `Q`.
index_t*	kappa
	Reparemtrization of `P` indicating a match. More...
index_t*	lambda
	Reparemtrization of `Q` indicating a match. More...
point*	P
	`delta` - sampled Polygonal curve of length `m`. More...
point*	Q
	`delta` - sampled Polygonal curve of length `n`. More...
arithmetic	eps
	Fault tolerance for matching.
arithmetic	delta
	Sampling density for matching; controls the aulity of approximation.
bool	matched
	Determines whether `match()` has been called since initialization or since the last call of `clear()`.
bool	match_found
	Indicates whether the last call of `match()` yielded a match for `P` and `Q`. More...
bool	parametrizations_available
	Indicates whether parametrizations computed during the last call of `match()` can be specified.
fs_graph	Gamma
	The free space graph used for matching.
motion	match_motion
	A match found by `match()`. More...
discrete_reparametrization_pair	match_kappa_lambda
	A reparametrization found by `match()`. More...
Static Protected Methods
arithmetic	dist (const point& x, const point& y)
	Computes the Euclidean distance between `x` and `y`.