Frechet Distance Calculator

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