`FrechetDist.cg.Line`

— Type```
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.Point`

— Type```
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`

— Type`Segment`

Specifies a *directed* segment by two endpoints.

`FrechetDist.cg.Polygon_read_plt_file`

— Method```
Polygon_read_plt_file
Reads a .plt file into a polygon (2d floating point).
```

`FrechetDist.cg.Segment_get_bisection_point`

— Method```
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.Segment_nn_point`

— Method`Segment_nn_point`

Returns the closest point on the segment `s`

to the query point `qr`

.

`FrechetDist.cg.dist_seg_nn_point`

— Method`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_point`

— Method`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.point`

— Method`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.Morphing`

— Type`Morphing`

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

`FrechetDist.EID`

— Function`EID`

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

`FrechetDist.Morphing_as_polygons`

— Method`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_combine`

— Method`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_empty`

— Method`Morphing_empty`

Returns an empty morhping (i.e., a constructor).

`FrechetDist.Morphing_extract_offsets`

— Method`Morphing_extract_offsets`

`FrechetDist.Morphing_extract_prm`

— Method```
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_radii`

— Method```
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_from_prm`

— Method```
Morphing_from_prm( prm, P, Q )
Construct a morphing from a parameterization of the two polygons P
and Q.
```

`FrechetDist.Morphing_monotonize`

— Method`Morphing_monotonize`

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

`FrechetDist.Morphing_verify_valid`

— Method`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_seg`

— Method`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 n*mid*points 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_inner`

— Method`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_polygon`

— Method```
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_approx`

— Method`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_compute`

— Method`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 frechet*continous*approx instead.

**Details**

This works by first computing a very rough approximation, followed by distance senstiave simplification of the curves. It then compute the monotone fr*ve*r 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 fr*ve*r*with*offests 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_subcurve`

— Method`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 p*indices. That is Q[ i ] =P[ p*indices[ i ].

`FrechetDist.frechet_d_compute`

— Method`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`

— Method`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_sample`

— Method`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_bound`

— Method`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_refinement`

— Method```
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_compute`

— Method`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...