André Nusser°, Marvin Künnemann†, and Karl Bringmann*
° CNRS / Inria Center at Université Côte d’Azur,
† Karlsruhe Institute of Technology,
* Saarland University and Max Planck Institute for Informatics
The Fréchet distance is a classical dissimilarity measure between polylines. 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 where they can each vary their speed arbitrarily. The Fréchet distance has significant advantages over other measures because it considers the polylines as continuous objects and takes into account the ordering of the points.
The applications of this distance measure are plenty, for example:
- Comparing the GPS traces of migrating animals to find the different routes that are being used;
- Measuring the similarity between movement patterns recorded via motion capture;
- Perform map matching to match a GPS trace to a transportation network.
Frechet distance is a powerful tool to compute clusters of given polylines [1, Fig. 1]
New Package: dD Fréchet Distance
This new package provides the means to compute an approximation of the Fréchet distance between two polylines that is guaranteed to be within an arbitrarily small, user-provided bound. In addition, a near neighbor data structure for polylines under the Fréchet distance is offered. These functionalities are provided for polylines in any dimension.
The following code snippet demonstrates how to compute the Fréchet distance between two polylines, with a maximal additive error of 0.000001 to the exact distance:
std::vector<Point> pA, pB;
CGAL::IO::read_linestring_WKT("wkt/moebius.wkt", pA);
CGAL::IO::read_linestring_WKT("wkt/moebius2.wkt", pB);
std::pair<double, double> res = CGAL::bounded_error_Frechet_distance(pA, pB, 0.000001);
std::cout << "The Frechet distance between the polylines is between " << res.first << " and " << res.second << std::endl;
The two polylines (blue and red), and the a visualization of the distance (green).
Fast and Correct
Following the usual Exact Computation Paradigm,
this package guarantees the correctness of the result, provided functions are called using a kernel offering
filtered predicates or exact predicates, such as provided by the kernel CGAL::Exact_predicates_and_inexact_constructions_kernel.
The implementation is based on state-of-the-art papers by Bringmann et al. [2, 3], which significantly improved on previous research. Furthermore, the algorithm is not affected by the curse of dimensionality; we refer to the papers themselves for a very detailed practical analysis.
Status
The package Fréchet Distance has been available since CGAL 6.1, released in the fall of 2025.
Documentation of the “dD Fréchet Distance” package
CGAL “main” branch on GitHub
Bibliography
[1] M. Brankovic, K. Buchin, K. Klaren, A. Nusser, A. Popov,and S. Wong, (k, l)-medians clustering of trajectories using continuous dynamic time warping. In Proceedings of the 28th International Conference on Advances in Geographic Information Systems 2020 Nov 3 (pp. 99-110).
[2] Karl Bringmann, Marvin Künnemann, and André Nusser. Walking the dog fast in practice: Algorithm engineering of the fréchet distance. In Gill Barequet and Yusu Wang, editors, 35th International Symposium on Computational Geometry, SoCG 2019, June 18-21, 2019, Portland, Oregon, USA, volume 129 of LIPIcs, pages 17:1–17:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
[3] Karl Bringmann, Marvin Künnemann, and André Nusser. Walking the dog fast in practice: Algorithm engineering of the fréchet distance. J. Comput. Geom., 12(1):70–108, 2021.
