This is a collection of different C++ implementations for calculating the discrete Fréchet distance between two polygonal curves:

1. vanilla: A recursion-free adaptation of the original algorithm as proposed in Computing Discrete Fréchet Distance by T. Eiter and H. Mannila (1994), used as a baseline.
2. linear: This formulation reduces the quadratic memory footprint to a linear one.
3. SIMD: Formulation using SIMD parallelization on a single CPU core.
4. CUDA: Formulation using CUDA.

Implementations of all these variants can be found under ffrechet-{vanilla,linear,simd,cuda}/source/ or by simply clicking on the listed names above.

This project has been primarily tested on Linux environments. Please note the following dependencies:

1. SIMD implementation: Requires at least GCC-11, as it relies on the experimental SIMD implementation of the Parallelism Technical Specification (TS) v2.
2. CUDA implementation: Requires a compiler version compatible with the NVCC installation.

You can customize the compiler versions by editing the respective toolchain files ffrechet-simd/ffrechet-simd_toolchain.cmake and ffrechet-simd/ffrechet-cuda_toolchain.cmake.

First, make sure that you have checked out the dependencies (google-benchmark and google-test) by running

$ git submodule init
$ git submodule update

Then, you can customize the build options in CMakeUserPresets.json or simply copy the default one from CMakeUserPresets.json.EXAMPLE:

$ cp CMakeUserPresets.json.EXAMPLE CMakeUserPresets.json

Finally, configure and build the entire project via

$ cmake --preset=release
$ cmake --build --preset=release

If you want to run the benchmark, type:

$ ./build/release/install/bin/ffrechet-benchmark \
--benchmark_out_format=json \
--benchmark_out=benchmark.json

this will run the benchmark and store the results in benchmark.json. Remember to enable the performance mode on your CPU before running the benchmark, e.g., via

$ sudo cpupower frequency-set --governor performance

Afterwards, you can reset the performance mode back to powersave via

$ sudo cpupower frequency-set --governor powersave

In case you are interested in contributing to this project, you might find our debug preset helpful:

$ cmake --preset=debug
$ cmake --build --preset=debug

You can test your changes by running

$ ./build/debug/install/bin/ffrechet-test

Please make sure to obey the formatting, for example by running

$ cmake --build --preset=debug -t format-check
$ cmake --build --preset=debug -t format-fix

We use Jupyter Notebooks to render the visualizations of the results of the benchmarks. You can find them here alongside others.

Python implementations of the discrete Fréchet Distance can be found here.