Authors: André Nusser, Marvin Künnemann, and Karl Bringmann

This package provides functions for computing the Fréchet distance of polylines in any dimension under the Euclidean metric.

Introdution

The Fréchet distance is a classical dissimilarity measure between polylines. Its advantages over other measures is that it both considers the polylines as continuous objects and takes into account the ordering of the points. Intuitively, the Fréchet distance is commonly explained as follows: Imagine a human walking on one polyline while a dog walks on the other polyline, they are connected by a leash, and they are only allowed to walk forward. The Fréchet distance is the shortest leash length that allows the human and the dog to jointly walk from start to end on their respective trajectories.

The Fréchet distance is a metric. This implies that two polylines have distance zero if and only if they are equal (after removing redundant vertices).

API

The package provides one function to approximate the Fréchet distance and one function to decide whether the Fréchet distance is at most a given value.

The function approximate_Frechet_distance() computes an approximation of the Fréchet distance between two polylines, up to a given approximation error. It returns an interval that contains the true distance. The function is_Frechet_distance_larger() decides if the Fréchet distance between two polylines is larger than a given bound.

Both functions have as template parameter a traits class defining the dimension and the point type. The traits classes have as template parameter a kernel. This may be a kernel such as Simple_cartesian with a floating point number type, or a filtered kernel such as Exact_predicates_inexact_constructions_kernel. In both cases the result is guaranteed to be correct.

Implementation

Internally all computations are done using interval arithmetic. In case of filter failures the algorithm switches to the usage of square root extensions.

The algorithms in this package are an adaption of the implementation of a SoCG/JoCG paper. In particular, the implementation can decide non-difficult cases very fast while for difficult cases it still has the quadratic running time guarantee of the classical Fréchet distance algorithm by Alt and Godau. This is achieved by using fast filtering methods and a divide and conquer algorithm with pruning rules on the free-space diagram.

Examples

In the examples we use different kernels to illustrate that the functions work as well for inexact or exact kernels.

Decision for 2D Polylines

The following example shows how we can use is_Frechet_distance_larger() to decide whether the Fréchet distance between two polylines in the Euclidean plane is at most a given value.

File Frechet_distance/Frechet_distance_2.cpp

#include <CGAL/Frechet_distance.h>
#include <CGAL/Frechet_distance_traits_2.h>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
 
#include <ostream>
 
using Kernel = CGAL::Exact_predicates_inexact_constructions_kernel;
using Traits = CGAL::Frechet_distance_traits_2<Kernel>;
using Point = Traits::Point;
 
int main(int argc, char* argv[])
{
    std::vector<Point> A, B;
    bool res = CGAL::is_Frechet_distance_larger<Traits>(A, B, 0.001);
    std::cout << std::boolalpha << res << std::endl;
    return 0;
}

Distance Computation for 3D Polylines

The following example shows how we can compute the Fréchet distance up to a given precision on two polylines in 3-dimensional Euclidean space using approximate_Frechet_distance().

File Frechet_distance/Frechet_distance_3.cpp

#include <CGAL/Frechet_distance.h>
#include <CGAL/Frechet_distance_traits_3.h>
#include <CGAL/Simple_cartesian.h>
 
#include <ostream>
 
using Kernel = CGAL::Simple_cartesian<double>;
using Traits = CGAL::Frechet_distance_traits_3<Kernel>;
using Point = Traits::Point;
 
int main(int argc, char* argv[])
{
    std::vector<Point> A, B;
    std::pair<double, double> res = CGAL::approximate_Frechet_distance<Traits>(A, B, 0.000001);
    std::cout << "The Frechet distance between the polylines is between " <<  res.first << " and " << res.second << std::endl;
    return 0;
}

Image Credits

The teaser image is a visualization of two data points from the Character Trajectories data set.

Implementation History

An initial version using floating point arithmetic was developed by the authors while working at the Max Planck Institute for Informatics in Saarbrücken, Germany. André Nusser, together with Sebastien Loriot and Andreas Fabri, introduced the usage of interval arithmetic and square root extensions to alleviate issues stemming from rounding errors and hence ensuring correctness of the computation.