Line in N dimensions.

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

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.
Segment_get_bisection_point -> Bool, Real, Point

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

bisector plane between p and q.


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

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.

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.
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).


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


A function that encodes a matching "edge" betwee two 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.


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(⋅)): γ → ξ.


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.

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).

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


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



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

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


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],...)


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.

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.


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.


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


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

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


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.


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


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 ].


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.


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.


Computes the discrete Frechet distance between the two 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.


  • 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.


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.

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


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


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