Hausdorff and Modified Hausdorff distance implemented using KDTree

Hausdorff KDTree.ipynb

hausdorff_kdtree.m

n = 50;

theta = linspace(0,2*pi-2/n*pi,n);
noise = 0.025;
inner_scale = 0.75;

unit_circle = vertcat(cos(theta), sin(theta))';

A = unit_circle + randn(n,2) * noise;
B = unit_circle * inner_scale + randn(n,2) * noise;

scatter(A(:,1),A(:,2));
hold on
scatter(B(:,1),B(:,2));

% compute Hausdorff distance by brute force
D = pdist2(A,B);
fhd = max(min(D,[],1));
rhd = max(min(D,[],2));
hd = max(fhd,rhd);

% compute modified Hausdorff distance by brute force
fhd = mean(min(D,[],1));
rhd = mean(min(D,[],2));
mhd = max(fhd, rhd);

% use the mex function
% mhdm = ModHausdorffDistMex(A,B);

% assert(mhd == mhdm);

% now use KDTree
a_kdt = KDTreeSearcher(A);
b_kdt = KDTreeSearcher(B);

[~, fhd] = knnsearch(a_kdt,B,'K',1);
[~, rhd] = knnsearch(b_kdt,A,'K',1);
knn_hd = max(max(fhd), max(rhd));
knn_mhd = max(mean(fhd), mean(rhd));

assert(knn_hd == hd);
assert(knn_mhd == mhd);