FrechetDist.cg.LineType
Line in N dimensions.

`p` is a point on the line and `u` is the direction vector (not
necessarily normalized). Parametrised as $p + ut$
FrechetDist.cg.PointType
Point

Point in N dimensions. Implemented currently as a struct with
StaticArray for values. It is templated, with `N` for dimension,
and `T` for underlying type.
FrechetDist.cg.Segment_get_bisection_pointMethod
Segment_get_bisection_point -> Bool, Real, Point

Computes the intersection point of the segment `seg` with the

bisector plane between p and q.

Returns

The first argument returns whether the segment intersects the bisector, the pramaterized location (tm), and the intersection piont itself.

FrechetDist.cg.dist_seg_nn_pointMethod
dist_seg_nn_point

Returns the distance to the closest point lying on the segment induced by the first two points, to the query point. By avoiding creating the segment iself, it is hopeflly more efficient.

FrechetDist.cg.induced_seg_nn_pointMethod
induced_seg_nn_point

Returns the closest point to the segment induced by the first two points, to the query point. By avoiding creating the segment iself, it is hopeflly more efficient.

FrechetDist.cg.pointMethod
point( args... )

A flexible constructor for a point specified by the arguments. Thus point( 2.0, 3.0, 4.0 ) defined the 3d point (2.0, 3.0, 4.0).

FrechetDist.MorphingType
Morphing

Encoding of a moprhing (i.e., matching) between two polygonal cuves.

FrechetDist.EIDFunction
EID

A function that encodes a matching "edge" betwee two polygons.

FrechetDist.Morphing_as_polygonsMethod
Morphing_as_polygons

Turns the morphing matching into a "true" matching, by creating two polygons that their edges are directly matched. The output polygons P and Q will definitely have reapeated points.

FrechetDist.Morphing_combineMethod
Morphing_combine

Gets two morphings u, v (i.e., two parameterizations) and combine them into a single morphing u(v(.)).

For example, if u: γ → δ and v: δ → ξ, then the returned morphing is u(v(⋅)): γ → ξ.

FrechetDist.Morphing_extract_prmMethod
Morphing_extract_prm

A parameterization is a polygonal curve that starts at (0,0) and
end at (m,n).  The polygonal curve ither have positive slope edge,
or vertical or horizontla edges. It can be thought of as a
piecewise linear function from [0,m] to [0,n]. Here m and n are the
lengths of the two given polygons of P and Q, respectively.
FrechetDist.Morphing_extract_vertex_radiiMethod
Morphing_extract_vertex_radii

Computes for each polygon vertex, the length of the longest edge
in the matching attached ot it. It is a cheap upper bound on the
local Frechet distance for each vertex (and implicitly the
attached edge).
FrechetDist.Morphing_monotonizeMethod
Morphing_monotonize

Turns a morphing into a monotone morphing, by simply not going back, staying in place if necessary.

FrechetDist.Morphing_verify_validMethod
Morphing_verify_valid

Does some minimal checks that the morphing is valid. Speciifcally, check the times stemps of the events are valid.

FrechetDist.add_points_along_segMethod
add_points_along_seg

Arguments

seg: t[1], t[2], .... , t[end]

 t[...]: Time stamps for points on the segment (all between 0 and 1)

Details

Add points along seg at time stamps specified by t, and add points in the middle between them (i.e., refining segment). These new points are added the output polygon pout.

Note, that one can set nmidpoints to be larger than 1, but it does not seem to be necessary/benefitial from the experimentation we did.

Output: Sorted( t[1]/2, t[1], (t[1]+t[2])/2, t[2],...)

FrechetDist.extract_param_innerMethod
extract_param_inner

Takes the sequence of events (i.e., sequence of points along the curve), and outputs a corresponding sequence of real numbers, where the ith nubmer if the distance of the ith point in sequence from the beginning of the curve. Here, distance means the total distance of the subcurve from the start point, to the current point.

FrechetDist.extract_refined_polygonMethod
extract_refined_polygon( P, pes, num_points_to_add )

Refine edges along which pes (the sequence of matching points
along P is not monotone, so that the returned polygon has
vertices, which hopefully force the Frechet morphing computed in
the next iteration to be monotone.

Arguments

P : the polygo pes: Sequence of events long the polygon P num_points_to_add: how many points to add between points of non-monotonicity. The default is 1. Having a larger value speeds up the process of getting rid of non-monotonicity, but the polygons grow faster.

FrechetDist.frechet_c_approxMethod
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 really rough approximation.

FrechetDist.frechet_c_computeMethod
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_mono_approx_subcurveMethod
frechet_c_mono_approx_subcurve

Approximates the Frechet distance between a curve (P) and subcurbe (Q). Here, Q vertices are the vertices of P specifieid by pindices. That is Q[ i ] =P[ pindices[ i ].

FrechetDist.frechet_d_computeMethod
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_computeMethod
frechet_dr__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.

FrechetDist.frechet_d_r_compute_sampleMethod
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 standard discrete Frechet or the retractable version.

FrechetDist.frechet_dist_upper_boundMethod
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_mono_via_refinementMethod
frechet_mono_via_refinement( P, Q, approx )

Computes the "true" monotone Frechet distance between P and Q,
using the ve_r algorithm. It does refinement, to add vertices if
needed to get monotonicity. Note, that there is an eps parameter -
for real inputs you can set it quite small. In any case, in the
worst case it only approximates the Frechet (monotone)
distance. It returns a morphing, and a boolean that is true if the
result is the true Frechet distance.

Observe, that this function might be too slow if the two curves
are huge, since it does not simplify them before computing the
distance.

Returns

Returns a 4-tuple ( m, f, P, Q ): m: Morphing realizing result. f: Is distance returned is the exact continuous Frechet distance. P: Refined first input polygon Q: Refined second input polygon

FrechetDist.frechet_ve_r_mono_computeMethod
frechet_ve_r_mono_compute

Computing the ver frechet distance, and then monotonize it. No guarentee as far as the quality of the distance this realizes...