File Exchange

image thumbnail

Frechet Distance Calculator

version 2.0 (2.43 KB) by Tristan Ursell
Estimate the similarity between curves in space using the scalar Frechet Distance.

34 Downloads

Updated 03 Jun 2020

View License

Tristan Ursell
Frechet Distance between two curves
May 2013, updated June 2020

f = frechet(X1,Y1,X2,Y2)
f = frechet(X1,Y1,X2,Y2,res)

(X1,Y1) are the ordered x and y coordinates of the first curve.
(X2,Y2) are the ordered x and y coordinates of the second curve.

The number of points composing the two curves does not have to be the same.

'res' is an optional positive parameter setting the number of linearly spaced distances spanning the minimum pairwise distance between any two points and the maximum pairwise distance between any two points. In general, first try without setting 'res', as that is guaranteed to give the highest precision answer. If computations are taking too long, try setting 'res=1000' for starters. When not using 'res', the script examines thresholds for all unique values of pairwise distances (O(N^2)). This might be ok for curves made up of (eg) 1000 points, but not 100,000.

This function estimates the Frechet Distance, which is a measure of the dissimilarity between two curves in space (in this case in 2D). It is a scalar value that is symmetric with respect to the two curves (i.e. switching X1->X2 and Y1->Y2 does not change the value). Roughly speaking, this distance metric is the minimum length of a line 'f' that connects a point on each curve, and allows one to traverse both curves from start to finish with a line of length 'f' or shorter.
(wiki: Frechet Distance)

The function requires the function 'bwlabel' from the image processing toolbox.

EXAMPLE: compare three curves to find out which two are most similar

%curve 1
t1=0:1:50;
X1=(2*cos(t1/5)+3-t1.^2/200)/2;
Y1=2*sin(t1/5)+3;

%curve 2
t2=-2:1:50;
X2=flip((2*cos(t2/4)+2-t2.^2/200)/2);
Y2=flip(2*sin(t2/5)+3);

%curve 3
t3=2:1:55;
X3=(2*cos(t3/4)+2-t3.^2/200)/2;
Y3=2*sin(t3/4+2)+3;

f11=frechet(X1,Y1,X1,Y1);
f12=frechet(X1,Y1,X2,Y2);
f13=frechet(X1,Y1,X3,Y3);
f21=frechet(X2,Y2,X1,Y1);
f22=frechet(X2,Y2,X2,Y2);
f23=frechet(X2,Y2,X3,Y3);
f31=frechet(X3,Y3,X1,Y1);
f32=frechet(X3,Y3,X2,Y2);
f33=frechet(X3,Y3,X3,Y3);

figure;
subplot(2,1,1)
hold on
plot(X1,Y1,'r','linewidth',2)
plot(X2,Y2,'g','linewidth',2)
plot(X3,Y3,'b','linewidth',2)
legend('curve 1','curve 2','curve 3','location','eastoutside')
xlabel('X')
ylabel('Y')
axis equal tight
box on
title(['three space curves to compare'])
legend

subplot(2,1,2)
imagesc([[f11,f12,f13];[f21,f22,f23];[f31,f32,f33]])
xlabel('curve')
ylabel('curve')
cb1=colorbar('peer',gca);
set(get(cb1,'Ylabel'),'String','Frechet Distance')
axis equal tight

Cite As

Tristan Ursell (2020). Frechet Distance Calculator (https://www.mathworks.com/matlabcentral/fileexchange/41956-frechet-distance-calculator), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (5)

gang qin

Lisa Wang

Just what i need! Thank you so much!

yak1226

just what I want ,great!

Venkat R

Nice submission. Has great potential application.

you

Updates

2.0

fixed a symmetry bug that would cause identical curves to not give a zero frechet distance, also improved the resolution handling.

MATLAB Release Compatibility
Created with R2016b
Compatible with any release
Platform Compatibility
Windows macOS Linux