Discrete Fréchet distance

Description

The discrete Frechet distance dells with the easier variant, where the input is two sequence of points, and the distance is the minimum max-leash that is needed, if two "frogs" jumps in a synchronized fashion along the two sequences, starting at the start of the sequences, and end in the end of the sequences. At each point only one frog jumps, and it can jump only forward by one position in the sequence of points it is on.

The basic solution to this is dynamic programming, which is similar in nature to edit-distance.

We also present the retractable variant, which tries to use a leash that is as short as possible at any point in time.

Finally, we also present a variant for the "continuous" variant, where one samples points along two polygons, and then compute their discrete Frechet distance. This is the "standard" way of using the discrete Frechet distance for the continuous problem. It provides inferior results than the continuous variants, but it is simple enough to implement, and it is thus provided.

Functions documentation

FrechetDist.frechet_d_compute — Function
frechet_d_compute

Computes the discrete Fréchet distance between the two sequences of points. It interpresents the vertices of the polygons and the desired sequence of points.

FrechetDist.frechet_d_r_compute — Function
frechet_d_r_compute

Compute discrete frechet distance that is locally optimal Frechet. Essentially discrete frechet + Prim/Dijkstra algorithm For the discrete case, that is modified to be retractable – that is minimize the maximum bottleneck edge being computed.

Note, the function still allocates quadratic space for the lookup tables. Doesn't seem to matter, but this might be worth fixing in future versions.

FrechetDist.frechet_d_r_compute_sample — Function
frechet_d_compute_sample

Computes the discrete Frechet distance between the two curves.by sampling them

It first sapmles the two curves rougly uniformly. n is supposed to be the nubmer of vertices, by the optput might be a sample that is slightly bigger, as the code tries to ensure the vertices are being picked.

Arguments

  • n: number of vertices to add when "refining" the two curves. The number of vertices computed might be larger (but hopefully not much larger).

  • f_lopt true: Use the rectractable Frechet distance version false: Use the standard discrete Frechet version.

FrechetDist.DTW_d_compute — Function
DTW_d_compute

Compute the Dynamic Time Wrapping distance between two
polygons. Here the price is the of lengths of leashes throughtout
the discrete morphing.