Skip to content

Compute the Fréchet distance between two polygonal curves in Euclidean space.

License

Notifications You must be signed in to change notification settings

spiros/discrete_frechet

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

30 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Build Status

DOI

Discrete Fréchet distance

Computes the discrete Fréchet distance between two curves. The Fréchet distance between two curves in a metric space is a measure of the similarity between the curves. The discrete Fréchet distance may be used for approximately computing the Fréchet distance between two arbitrary curves, as an alternative to using the exact Fréchet distance between a polygonal approximation of the curves or an approximation of this value.

This is a Python 3.* implementation of the algorithm produced in Eiter, T. and Mannila, H., 1994. Computing discrete Fréchet distance. Tech. Report CD-TR 94/64, Information Systems Department, Technical University of Vienna.

Function dF(P, Q): real;
    input: polygonal curves P = (u1, . . . , up) and Q = (v1, . . . , vq).
    return: δdF (P, Q)
    ca : array [1..p, 1..q] of real;
    function c(i, j): real;
        begin
            if ca(i, j) > −1 then return ca(i, j)
            elsif i = 1 and j = 1 then ca(i, j) := d(u1, v1)
            elsif i > 1 and j = 1 then ca(i, j) := max{ c(i − 1, 1), d(ui, v1) }
            elsif i = 1 and j > 1 then ca(i, j) := max{ c(1, j − 1), d(u1, vj ) }
            elsif i > 1 and j > 1 then ca(i, j) :=
            max{ min(c(i − 1, j), c(i − 1, j − 1), c(i, j − 1)), d(ui, vj ) }
            else ca(i, j) = ∞
            return ca(i, j);
        end; /* function c */

    begin
        for i = 1 to p do for j = 1 to q do ca(i, j) := −1.0;
        return c(p, q);
    end.

Parameters

P : Input curve - two dimensional array of points
Q : Input curve - two dimensional array of points

Returns

dist: float64
The discrete Frechet distance between curves `P` and `Q`.

Examples

>>> from frechetdist import frdist
>>> P=[[1,1], [2,1], [2,2]]
>>> Q=[[2,2], [0,1], [2,4]]
>>> frdist(P,Q)
>>> 2.0
>>> P=[[1,1], [2,1], [2,2]]
>>> Q=[[1,1], [2,1], [2,2]]
>>> frdist(P,Q)
>>> 0