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 scan and fold operations.
8. reduce_accumulate2: Alternative formulation using the scan with an associative operator that is slower in a single-threaded context but can take full advantage of parallel scan implementations.
9. 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 -e .

# 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:

>>> import numpy as np
>>> 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: 1915 ms
          vectorized:  495 ms
          branchless:  466 ms
       linear_memory:  294 ms
          accumulate:  258 ms
   reduce_accumulate:  249 ms
  reduce_accumulate2:  360 ms
            compiled:    9 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.)