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 ofa list containing the following elements:

Frechet_distance_metric: A matrix containing the pairwise Frechet distances between trajectories.
Frechet_distance_metric_p_values: (If test is TRUE) A matrix containing the p-values for the pairwise Frechet distances.
Frechet_metric_p_values_combined: (If test is TRUE) The overall p-value for the combined Frechet distances.
Frechet_distance_metric_simulations: (If test is TRUE) A list of Frechet distance matrices from each simulated dataset.

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.

Logo

References

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.

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")
#> 2025-05-19 14:34:15.938598 Iteration 1
#>  
#> Frechet metric
#> ------------------------------------
#> 2025-05-19 14:34:16.13071 Iteration 2
#>  
#> Frechet metric
#> ------------------------------------
#> 2025-05-19 14:34:16.321743 Iteration 3
#>  
#> Frechet metric
#> ------------------------------------
#> ANALYSIS COMPLETED
#> ------------------------------------
#>  
#> $Frechet_distance_metric
#>         Track_1   Track_2
#> Track_1      NA 0.7821257
#> Track_2      NA        NA
#> 
#> $Frechet_distance_metric_p_values
#>         Track_1   Track_2
#> Track_1      NA 0.6666667
#> Track_2      NA        NA
#> 
#> $Frechet_metric_p_values_combined
#> [1] 0.6666667
#> 
#> $Frechet_distance_metric_simulations
#> $Frechet_distance_metric_simulations[[1]]
#>         Track_1   Track_2
#> Track_1      NA 0.7846134
#> Track_2      NA        NA
#> 
#> $Frechet_distance_metric_simulations[[2]]
#>         Track_1   Track_2
#> Track_1      NA 0.7735046
#> Track_2      NA        NA
#> 
#> $Frechet_distance_metric_simulations[[3]]
#>         Track_1   Track_2
#> Track_1      NA 0.7785932
#> Track_2      NA        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")
#> 2025-05-19 14:34:16.678824 Iteration 1
#>  
#> Frechet metric
#> ------------------------------------
#> 2025-05-19 14:34:16.858844 Iteration 2
#>  
#> Frechet metric
#> ------------------------------------
#> 2025-05-19 14:34:17.03952 Iteration 3
#>  
#> Frechet metric
#> ------------------------------------
#> ANALYSIS COMPLETED
#> ------------------------------------
#>  
#> $Frechet_distance_metric
#>         Track_1   Track_2
#> Track_1      NA 0.6589325
#> Track_2      NA        NA
#> 
#> $Frechet_distance_metric_p_values
#>         Track_1 Track_2
#> Track_1      NA       0
#> Track_2      NA      NA
#> 
#> $Frechet_metric_p_values_combined
#> [1] 0
#> 
#> $Frechet_distance_metric_simulations
#> $Frechet_distance_metric_simulations[[1]]
#>         Track_1  Track_2
#> Track_1      NA 6.940444
#> Track_2      NA       NA
#> 
#> $Frechet_distance_metric_simulations[[2]]
#>         Track_1  Track_2
#> Track_1      NA 4.896626
#> Track_2      NA       NA
#> 
#> $Frechet_distance_metric_simulations[[3]]
#>         Track_1  Track_2
#> Track_1      NA 5.205566
#> Track_2      NA       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")
#> 2025-05-19 14:34:17.279378 Iteration 1
#>  
#> Frechet metric
#> ------------------------------------
#> 2025-05-19 14:34:17.336036 Iteration 2
#>  
#> Frechet metric
#> ------------------------------------
#> 2025-05-19 14:34:17.361053 Iteration 3
#>  
#> Frechet metric
#> ------------------------------------
#> ANALYSIS COMPLETED
#> ------------------------------------
#>  
#> $Frechet_distance_metric
#>         Track_1  Track_2
#> Track_1      NA 1.144628
#> Track_2      NA       NA
#> 
#> $Frechet_distance_metric_p_values
#>         Track_1   Track_2
#> Track_1      NA 0.3333333
#> Track_2      NA        NA
#> 
#> $Frechet_metric_p_values_combined
#> [1] 0.3333333
#> 
#> $Frechet_distance_metric_simulations
#> $Frechet_distance_metric_simulations[[1]]
#>         Track_1  Track_2
#> Track_1      NA 30.34401
#> Track_2      NA       NA
#> 
#> $Frechet_distance_metric_simulations[[2]]
#>         Track_1  Track_2
#> Track_1      NA 18.57202
#> Track_2      NA       NA
#> 
#> $Frechet_distance_metric_simulations[[3]]
#>         Track_1 Track_2
#> Track_1      NA      -1
#> Track_2      NA      NA
#> 
#>