Data

Tools

Indexes

Applications

Experiments

Open Source Science

fast_frechet-python

Comparison of different (fast) discrete Fréchet distance implementations in Python.

https://github.com/avitase/fast_frechet-python

Science Score: 44.0%

This score indicates how likely this project is to be science-related based on various indicators:

  • ✓
    CITATION.cff file
    Found CITATION.cff file
  • ✓
    codemeta.json file
    Found codemeta.json file
  • ✓
    .zenodo.json file
    Found .zenodo.json file
  • ○
    DOI references
  • ○
    Academic publication links
  • ○
    Academic email domains
  • ○
    Institutional organization owner
  • ○
    JOSS paper metadata
  • ○
    Scientific vocabulary similarity
    Low similarity (11.4%) to scientific vocabulary

Keywords

benchmark frechet-distance python
Last synced: 6 months ago · JSON representation ·

Repository

Comparison of different (fast) discrete Fréchet distance implementations in Python.

Basic Info
Statistics
  • Stars: 3
  • Watchers: 1
  • Forks: 0
  • Open Issues: 0
  • Releases: 0
Topics
benchmark frechet-distance python
Created about 2 years ago · Last pushed 7 months ago
Metadata Files
Readme License Citation

README.md

Fast Discrete Fréchet Distance

Python 3.10 Test coverage Unit tests Code style: black

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

```bash

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:

```python

import numpy as np from fastfrechet.linearmemory 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:

```bash $ python fast_frechet Length of trajectory = 1024

    no_recursion: 1915 ms
      vectorized:  495 ms
      branchless:  466 ms
   linear_memory:  294 ms
      accumulate:  258 ms

reduceaccumulate: 249 ms reduceaccumulate2: 360 ms compiled: 9 ms `` (Note that we don't even try to benchmark the [vanilla`](fast_frechet/vanilla.py) version here, as it already crashes for polygonal curves with a few hundred points due to its recursive nature.)

Owner

  • Name: Nis Meinert
  • Login: avitase
  • Kind: user
  • Company: Pasteur Labs

Citation (CITATION.cff) 

cff-version: 1.2.0
message: "If you use this software, please cite it as below."
authors:
- family-names: "Meinert"
  given-names: "Nis"
  orcid: "https://orcid.org/0000-0002-4712-9579"
title: "Fast Discrete Fréchet Distance"
version: 1.1
date-released: 2025-07-13
url: "https://github.com/avitase/fast_frechet-python"

GitHub Events

Total
  • Issues event: 1
  • Watch event: 4
  • Issue comment event: 1
  • Push event: 3
  • Fork event: 1
Last Year
  • Issues event: 1
  • Watch event: 4
  • Issue comment event: 1
  • Push event: 3
  • Fork event: 1

Issues and Pull Requests

Last synced: 11 months ago

All Time
  • Total issues: 0
  • Total pull requests: 0
  • Average time to close issues: N/A
  • Average time to close pull requests: N/A
  • Total issue authors: 0
  • Total pull request authors: 0
  • Average comments per issue: 0
  • Average comments per pull request: 0
  • Merged pull requests: 0
  • Bot issues: 0
  • Bot pull requests: 0
Past Year
  • Issues: 0
  • Pull requests: 0
  • Average time to close issues: N/A
  • Average time to close pull requests: N/A
  • Issue authors: 0
  • Pull request authors: 0
  • Average comments per issue: 0
  • Average comments per pull request: 0
  • Merged pull requests: 0
  • Bot issues: 0
  • Bot pull requests: 0
View more stats
Top Authors
Issue Authors
  • neildhir (1)
Pull Request Authors
Top Labels
Issue Labels
Pull Request Labels

Dependencies

.github/workflows/get_coverage.yml actions
  • actions/checkout v3 composite
  • actions/setup-python v4 composite
  • codecov/codecov-action v3 composite
.github/workflows/pre_commit.yml actions
  • actions/checkout v3 composite
  • actions/setup-python v4 composite
  • pre-commit/action v3.0.0 composite
.github/workflows/run_tests.yml actions
  • actions/checkout v3 composite
  • actions/setup-python v4 composite
pyproject.toml pypi
requirements.txt pypi
  • numba *
  • numpy *
setup.py pypi
  • numba *
  • numpy *