FrechetDist.jl

Compute the Fréchet distance between curves.

Package Features

• Provides algorithm for computing the discrete, VE, regular Frechet distance between polygonal curves. Supports also the retractable version.

Function Documentation

FrechetDist.frechet_c_computeFunction
frechet_c_compute

Compute the exact continuous (monotone) Frechet distance between the two polygons. It should be reasonably fast.

This function is somewhat slower than the approximate versions. Use it only if you really want the exact answer. Consider using frechetcontinousapprox instead.

Details

This works by first computing a very rough approximation, followed by distance senstiave simplification of the curves. It then compute the monotone frver distance between the simplified curves, and it combine it to get a distance between the two original cuves. It makre sure the answers are the same, otherwise, it repeates with a finer simplification/approximation till they are equal.

Finally, the algorithm uses the frverwithoffests distance between the two simplified curves to comptue a lower bound, and make sure this is equal to the Frechet distance computed. If they are equal, then the upper/lower bounds on the Frechet distance of the two curves are the same, which implies that the computed distance is indeed the desired Frechet distance.

More details

To really ensure converges, the monotone distance computed between the simplification is computed using refinement, so tha the ve_r distance

FrechetDist.frechet_c_approxFunction
frechet_c_approx

Approximates the continuous Frechet distance between the two input curves. Returns a monotone morphing realizing it.

Arguments

• approx : The output morhing has Frechet distance <= approx*optimal.

Importantly, approx can be larger than 2, if you want a rough approximation.

The quality of approximation is available at ret.ratio. Thus, ret.leash/ret.ratio is a lower bound on the Frechet distance, while ret.leash is an upper bound.

FrechetDist.frechet_dist_upper_boundFunction
frechet_dist_upper_bound

Returns a rough upper bound on the Frechet distance between the two curves. This upper bound is on the continuous distance. No guarenteee on how bad the approximation is. This is used as a starting point for real approximation of the Frechet distance, and should not be used otherwise.

FrechetDist.frechet_width_approxFunction
frechet_width_approx

2-approximation to the Frechet distance between seg = P[first(rng)]-P[last(rng)] and he polygon P[rng] Here, rng is a range i:j

This function implements a greedy matching alnog the segment - you move to the cloest point on seg to the current point, making sure never moving back.