% Exact Euclidean Distance Transform 
% Uses MATLAB image processing toolbox function bwdist() with default
% transform type
% M J de Smith, 19/5/03
% Ref:  Heinz Breu, Joseph Gil, David Kirkpatrick, and Michael Werman, 
%      "Linear Time Euclidean Distance Transform Algorithms," 
%       IEEE Transactions on Pattern Analysis and Machine Intelligence, 
%       vol. 17, no. 5 May 1995, pp. 529-533.
% Variation: Multiple weighted Distance Transform example - Steiner problem

home;tic;
bw = zeros(101,101);
w1=1;w2=1;w3=1;
bw(41,81) = 1; 
D = bwdist(bw);
bw = zeros(101,101);
bw(21,11) = 1; 
E = bwdist(bw);
bw = zeros(101,101);
bw(71,31) = 1; 
F = bwdist(bw);
G = w1*D + w2*E + w3*F;
p = min(min(G))
[i,j]=find(G==p)

% shaded contour plot
whitebg([0 .4 .6]); rect = [100, 100, 650, 600];
figure(1); set(1,'Position',rect); str = datestr(now,0); 
contourf (G,15); colormap jet; alpha (.3); title([' Generated on: ',str]); xlabel('x-position'); ylabel ('y-position');
hold on;
plot(81,41,'--rs','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','k','MarkerSize',10);
hold on;
plot(11,21,'--rs','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','k','MarkerSize',10);
hold on;
plot(31,71,'--rs','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','k','MarkerSize',10);
plot(j,i,'--rs','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','w','MarkerSize',10);
toc