Fast Discrete Fréchet Distance

Find C++/SIMD/CUDA implementations of the algorithms here.

This is Python package that provides a collection of different implementations for calculating the discrete Fréchet distance between two polygonal curves.

As a baseline, referred to as vanilla, we implement the proposed algorithm by Eiter and Manilla (1994). Starting from here, we subsequently fix several of its shortcomings. More precisely,

1. vanilla: The baseline implementation as proposed in Computing Discrete Fréchet Distance by T. Eiter and H. Mannila (1994)
2. no_recursion: A formulation w/o recursion.
3. vectorized: A vectorized implementation that calculates the distance matrix within a single NumPy call.
4. branchless: A variant w/o branches.
5. linear_memory: This formulation reduces the quadratic memory footprint to a linear one.
6. accumulate: Formulation using a scan operation.
7. reduce_accumulate: Formulation using a fold operation.
8. compiled: Variant of reduce_accumulate using the Numba library for JIT compilation of the innermost loop.

Implementations of all these variants can be found under fast_frechet/ or by simply clicking on the listed names above.

Installation

# production installation
$ pip install -r requirements.txt
$ pip install fast_frechet

# development installation
$ pip install -e .[dev]
$ pre-commit install

Usage

The snippet below estimates the Fréchet distance between the polygonal curves p and q using the Euclidean distance as a metric to measure distances between points:

>>> from fast_frechet.linear_memory import frechet_distance

>>> p = np.array([[1, 2], [3, 4]])
>>> q = np.array([[2, 1], [3, 3], [5, 5]])

>>> frechet_distance(p, q, metric=lambda a, b: np.hypot(a[..., 0] - b[..., 0], a[..., 1] - b[..., 1]))
2.23606797749979

For invoking the benchmark script, run:

$ python fast_frechet
Length of trajectory = 1024

        no_recursion: 2303 ms
          vectorized:  553 ms
          branchless:  508 ms
       linear_memory:  348 ms
          accumulate:  286 ms
   reduce_accumulate:  282 ms
            compiled:   11 ms

(Note that we don't even try to benchmark the vanilla version here, as it already crashes for polygonal curves with a few hundred points due to its recursive nature.)