Similarity metric using Fréchet distance

simil_Frechet_metric() computes similarity metrics between two or more trajectories using the Fréchet distance. It allows for different superposition methods to align trajectories before calculating the Fréchet distance metrics. The function also supports testing with simulations to calculate p-values for the Fréchet distance metrics.

Usage

simil_Frechet_metric(data, test = FALSE, sim = NULL, superposition = "None")

Arguments

data

A track R object, which is a list consisting of two elements:

Trajectories: A list of interpolated trajectories, where each trajectory is a series of midpoints between consecutive footprints.
Footprints: A list of data frames containing footprint coordinates, metadata (e.g., image reference, ID), and a marker indicating whether the footprint is actual or inferred.

test

Logical; if TRUE, the function compares the observed Fréchet distances against simulated trajectories and calculates p-values. Default is FALSE.

sim

A track simulation R object consisting of a list of simulated trajectories to use for comparison when test = TRUE.

superposition

A character string indicating the method used to align trajectories. Options are "None", "Centroid", or "Origin". Default is "None".

Value

A track similarity R object consisting of a list containing the following elements:

Frechet_distance_metric: A numeric matrix of pairwise Fréchet distances between trajectories. Each entry represents the Fréchet distance between the corresponding pair of trajectories.
Frechet_distance_metric_p_values: (If test = TRUE) A numeric matrix of raw pairwise p-values, computed by Monte Carlo tail tests with the (+1) correction (Phipson & Smyth, 2010): $$p = (1 + \#\{\text{extreme}\}) / (nsim + 1)$$. Each entry reflects the probability of observing a Fréchet distance as extreme as the observed one, given the null hypothesis of no difference.
Frechet_distance_metric_p_values_BH: (If test = TRUE) A numeric matrix of Benjamini–Hochberg (BH) adjusted p-values controlling the false discovery rate (FDR), applied across the set of unique pairwise tests (Benjamini & Hochberg, 1995).
Frechet_metric_p_values_combined: (If test = TRUE) A single numeric value representing the combined p-value across all Fréchet distances (based on a global dominance criterion, evaluating in how many simulations the observed distances are smaller than the simulated ones across all trajectory pairs simultaneously). This indicates the overall significance of the observed Fréchet distances relative to simulations.
Frechet_distance_metric_simulations: (If test = TRUE) A list containing matrices of Fréchet distances for each simulation iteration, allowing for inspection of the distribution of Fréchet distances across randomized scenarios.

Details

The simil_Frechet_metric() function calculates the similarity between trajectories using the Frechet() function from the SimilarityMeasures package.

The Fréchet distance is a measure of similarity between two curves or continuous trajectories, which takes into account both the order and location of points within the trajectories (Besse et al. 2015). The distance can be described by the analogy of a person walking a dog on an extendable leash (Aronov et al. 2006). Both the person and the dog move along their respective trajectories, with each able to adjust their speed but not retrace their steps. The Fréchet distance is the minimum leash length required to keep the dog connected to the person throughout the walk (Cleasby et al., 2019).

Unlike other trajectory comparison techniques, such as Dynamic Time Warping, the Fréchet distance focuses on the overall shape of the trajectories rather than matching specific points. As a result, it is sensitive to noise because all points of the compared trajectories are considered in its calculation. However, it can still be a powerful tool for trajectory clustering and comparison, particularly when shape is the primary concern (Cleasby et al., 2019).

Note that when comparing real trajectories that are very disparate or those simulated under an unconstrained method, the resulting trajectories may not be suitable for Fréchet distance calculations. In such cases, the Fréchet distance is returned as -1 to indicate an invalid measurement.

The function offers three different superposition methods to align the trajectories before Frechet() is applied:

"None": No superposition is applied.
"Centroid": Trajectories are shifted to align based on their centroids.
"Origin": Trajectories are shifted to align based on their starting point.

If test = TRUE, the function can compute p-values by comparing the observed Fréchet distances with those generated from a set of simulated trajectories. The p-values are calculated for both individual trajectory pairs and for the entire set of trajectories. Pairwise p-values are computed with a Monte Carlo tail test using the (+1) correction to avoid zero-values (see Phipson & Smyth, 2010): $$p = (1 + \#\{\text{extreme}\}) / (nsim + 1)$$

These raw p-values are then adjusted for multiple comparisons across the set of unique pairwise tests using the Benjamini–Hochberg (BH) procedure for false discovery rate (FDR) control (Benjamini & Hochberg, 1995). Both the raw and the BH-adjusted p-value matrices are returned in the output object, allowing users to inspect either uncorrected or corrected results. In addition, a global combined p-value is provided, summarizing the overall deviation from the null across all pairs.

Logo

References

Benjamini, Y., & Hochberg, Y. (1995). Controlling the false discovery rate: a practical and powerful approach to multiple testing. Journal of the Royal statistical society: series B (Methodological), 57(1), 289-300.

Cleasby, I. R., Wakefield, E. D., Morrissey, B. J., Bodey, T. W., Votier, S. C., Bearhop, S., & Hamer, K. C. (2019). Using time-series similarity measures to compare animal movement trajectories in ecology. Behavioral Ecology and Sociobiology, 73, 1-19.

Phipson, B., & Smyth, G. K. (2010). Permutation P-values should never be zero: calculating exact P-values when permutations are randomly drawn. Statistical applications in genetics and molecular biology, 9(1).

Author

Humberto G. Ferrón

humberto.ferron@uv.es

Macroevolution and Functional Morphology Research Group (www.macrofun.es)

Cavanilles Institute of Biodiversity and Evolutionary Biology

Calle Catedrático José Beltrán Martínez, nº 2

46980 Paterna - Valencia - Spain

Phone: +34 (9635) 44477

Examples

# Example 1: Simulating tracks using the "Directed" model and comparing Frechet distance
# in the PaluxyRiver dataset
s1 <- simulate_track(PaluxyRiver, nsim = 3, model = "Directed")
simil_Frechet_metric(PaluxyRiver, test = TRUE, sim = s1, superposition = "None")
#> 2026-01-21 09:03:52.854846 Iteration 1
#>  
#> Frechet metric
#>           Track_1   Track_2
#> Track_1        NA 0.8858555
#> Track_2 0.8858555        NA
#> ------------------------------------
#> 2026-01-21 09:03:53.045258 Iteration 2
#>  
#> Frechet metric
#>          Track_1  Track_2
#> Track_1       NA 1.001106
#> Track_2 1.001106       NA
#> ------------------------------------
#> 2026-01-21 09:03:53.22593 Iteration 3
#>  
#> Frechet metric
#>           Track_1   Track_2
#> Track_1        NA 0.7908833
#> Track_2 0.7908833        NA
#> ------------------------------------
#> ANALYSIS COMPLETED
#> ------------------------------------
#>  
#> $Frechet_distance_metric
#>           Track_1   Track_2
#> Track_1        NA 0.7821257
#> Track_2 0.7821257        NA
#> 
#> $Frechet_distance_metric_p_values
#>         Track_1 Track_2
#> Track_1      NA    0.25
#> Track_2    0.25      NA
#> 
#> $Frechet_distance_metric_p_values_BH
#>         Track_1 Track_2
#> Track_1      NA    0.25
#> Track_2    0.25      NA
#> 
#> $Frechet_metric_p_values_combined
#> [1] 0
#> 
#> $Frechet_distance_metric_simulations
#> $Frechet_distance_metric_simulations[[1]]
#>           Track_1   Track_2
#> Track_1        NA 0.8858555
#> Track_2 0.8858555        NA
#> 
#> $Frechet_distance_metric_simulations[[2]]
#>          Track_1  Track_2
#> Track_1       NA 1.001106
#> Track_2 1.001106       NA
#> 
#> $Frechet_distance_metric_simulations[[3]]
#>           Track_1   Track_2
#> Track_1        NA 0.7908833
#> Track_2 0.7908833        NA
#> 
#> 

# Example 2: Simulating tracks using the "Constrained" model and comparing Frechet distance
# in the PaluxyRiver dataset  using the "Centroid" superposition method
s2 <- simulate_track(PaluxyRiver, nsim = 3, model = "Constrained")
simil_Frechet_metric(PaluxyRiver, test = TRUE, sim = s2, superposition = "Centroid")
#> 2026-01-21 09:03:53.60203 Iteration 1
#>  
#> Frechet metric
#>          Track_1  Track_2
#> Track_1       NA 1.916336
#> Track_2 1.916336       NA
#> ------------------------------------
#> 2026-01-21 09:03:53.748521 Iteration 2
#>  
#> Frechet metric
#>          Track_1  Track_2
#> Track_1       NA 6.404749
#> Track_2 6.404749       NA
#> ------------------------------------
#> 2026-01-21 09:03:53.932298 Iteration 3
#>  
#> Frechet metric
#>          Track_1  Track_2
#> Track_1       NA 1.386378
#> Track_2 1.386378       NA
#> ------------------------------------
#> ANALYSIS COMPLETED
#> ------------------------------------
#>  
#> $Frechet_distance_metric
#>           Track_1   Track_2
#> Track_1        NA 0.6589325
#> Track_2 0.6589325        NA
#> 
#> $Frechet_distance_metric_p_values
#>         Track_1 Track_2
#> Track_1      NA    0.25
#> Track_2    0.25      NA
#> 
#> $Frechet_distance_metric_p_values_BH
#>         Track_1 Track_2
#> Track_1      NA    0.25
#> Track_2    0.25      NA
#> 
#> $Frechet_metric_p_values_combined
#> [1] 0
#> 
#> $Frechet_distance_metric_simulations
#> $Frechet_distance_metric_simulations[[1]]
#>          Track_1  Track_2
#> Track_1       NA 1.916336
#> Track_2 1.916336       NA
#> 
#> $Frechet_distance_metric_simulations[[2]]
#>          Track_1  Track_2
#> Track_1       NA 6.404749
#> Track_2 6.404749       NA
#> 
#> $Frechet_distance_metric_simulations[[3]]
#>          Track_1  Track_2
#> Track_1       NA 1.386378
#> Track_2 1.386378       NA
#> 
#> 

# Example 3: Simulating tracks using the "Unconstrained" model and comparing Frechet distance
# in the PaluxyRiver dataset using the "Origin" superposition method
s3 <- simulate_track(PaluxyRiver, nsim = 3, model = "Unconstrained")
simil_Frechet_metric(PaluxyRiver, test = TRUE, sim = s3, superposition = "Origin")
#> 2026-01-21 09:03:54.319269 Iteration 1
#>  
#> Frechet metric
#>         Track_1 Track_2
#> Track_1      NA 2.04268
#> Track_2 2.04268      NA
#> ------------------------------------
#> 2026-01-21 09:03:54.349992 Iteration 2
#>  
#> Frechet metric
#>          Track_1  Track_2
#> Track_1       NA 26.59941
#> Track_2 26.59941       NA
#> ------------------------------------
#> 2026-01-21 09:03:54.389622 Iteration 3
#>  
#> Frechet metric
#>          Track_1  Track_2
#> Track_1       NA 16.82425
#> Track_2 16.82425       NA
#> ------------------------------------
#> ANALYSIS COMPLETED
#> ------------------------------------
#>  
#> $Frechet_distance_metric
#>          Track_1  Track_2
#> Track_1       NA 1.144628
#> Track_2 1.144628       NA
#> 
#> $Frechet_distance_metric_p_values
#>         Track_1 Track_2
#> Track_1      NA    0.25
#> Track_2    0.25      NA
#> 
#> $Frechet_distance_metric_p_values_BH
#>         Track_1 Track_2
#> Track_1      NA    0.25
#> Track_2    0.25      NA
#> 
#> $Frechet_metric_p_values_combined
#> [1] 0
#> 
#> $Frechet_distance_metric_simulations
#> $Frechet_distance_metric_simulations[[1]]
#>         Track_1 Track_2
#> Track_1      NA 2.04268
#> Track_2 2.04268      NA
#> 
#> $Frechet_distance_metric_simulations[[2]]
#>          Track_1  Track_2
#> Track_1       NA 26.59941
#> Track_2 26.59941       NA
#> 
#> $Frechet_distance_metric_simulations[[3]]
#>          Track_1  Track_2
#> Track_1       NA 16.82425
#> Track_2 16.82425       NA
#> 
#>