kmlShape (version 0.9.5)

pathFrechet: ~ Function: Frechet distance ~

Description

Compute Frechet distance and Frechet path between two trajectories.

Usage

pathFrechet(Px,Py,Qx,Qy,timeScale=0.1,FrechetSumOrMax = "sum")

Arguments

Px

[vector(numeric)] Times (abscisse) of the first trajectories.

Py

[vector(numeric)] Values of the first trajectories.

Qx

[vector(numeric)] Times of the second trajectories.

Qy

[vector(numeric)] Values of the second trajectories.

timeScale

[numeric]: allow to modify the time scale, increasing or decreasing the cost of the horizontal shift. If timeScale is very big, then the Frechet path is only a set of vertical segment. If timeScale is very small, then it is equal to the path find by Dynamic Time Warping.

FrechetSumOrMax

[character]: Like Frechet's distance, the Frechet's path can be define using the 'sum' function or the 'max' function. This option let the user to chose one or the other.

Value

A numeric value and the Frechet path in a matrix.

Author

Christophe Genolini \& Elie Guichard 1. UMR U1027, INSERM, Universit Paul Sabatier / Toulouse III / France 2. CeRSME, EA 2931, UFR STAPS, Universit de Paris Ouest-Nanterre-La Dfense / Nanterre / France

Details

Given two curve P and Q, Frechet distance between P and Q is define as distFrechet(P,Q)=inf_{a,b} max_{t} d(P(a(t)),Q(b(t))).

The Frechet path is the couple of function (a(t),b(t)) that realize the previous equality : distFrechet(P,Q)=max_{t} d(P(a(t)),Q(b(t)))

It's computation is a NP-complex problem. When P and Q are trajectories (discrete curve), the problem is polynomial.

The Frechet path can also be define using a sum instead of a max: inf_{a,b} sum_{t} d(P(a(t)),Q(b(t)))

The function pathFrechet is C compiled whereas the function pathFrechetR is in R.

References

Thomas Eiter & Heikki Mannila: "Computing Discrete Frechet Distance"

[1] C. Genolini and B. Falissard "KmL: k-means for longitudinal data" Computational Statistics, vol 25(2), pp 317-328, 2010

[2] C. Genolini and B. Falissard "KmL: A package to cluster longitudinal data" Computer Methods and Programs in Biomedicine, 104, pp e112-121, 2011

See Also

distFrechet

Examples

   Px <- 1:20
   Py <- dnorm(1:20,12,2)
   Qx <- 1:20
   Qy <- dnorm(1:20,8,2)

   ### Function from Eiter and Mannila compiled in C
   system.time(pathFrechet(Px,Py,Qx,Qy))

   ### Same thing in R
   system.time(pathFrechet(Px,Py,Qx,Qy))

   ### Frechet using sum instead of max.
   pathFrechet(Px,Py,Qx,Qy,FrechetSumOrMax="sum")