% The use of this code should cite

% Khan,M., Mohamad,A.F.A., Isaacs,A. and Ray,T., A smart repair embedded
% memetic algorithm for 2D shape matching problems, Engineering
% Optimization, 2012. Fothcoming http://www.tandfonline.com/doi/abs/10.1080/0305215X.2011.634408#preview

% Khan,M., Mohamad,A.F.A, Isaacs,A. and Ray,T. ,A novel evolutionary 
% approach for 2D shape matching based on B-Spline modeling, in Proceedings 
% of the IEEE Congress on Evolutionary Computation, (New Orleans,USA),pp. 655 to 661 ,2011.

% The input x is a N times 2 matrix, where N are the points and x and y
% coordinates of them as columns. The output is the reordered set of
% points. 

function [x]=Repair(x)
    close all;clc;xold=x;
	K=convhull(x(:,1),x(:,2));K(end)=[];
	left_out=setdiff(1:size(x,1),K);

	E=form_edges(K);de_min=[];
	for i=1:length(left_out)
		id=left_out(i);
		de_min(i,:)=min_edge_dist(E,x,id);
	end

	% Insert points (starting from first node)
	new_K = K;
	for i = 1:size(E,1)
		n_id = K(i);
		id = find(de_min(:,2) == n_id);
		if ~isempty(id)
			p_id = left_out(id);
			if length(p_id) > 1
				diff = x(p_id,:) - repmat(x(n_id,:), length(p_id), 1);
				d = sum(diff .* diff, 2);
				[tmp, I] = sort(d);
				new_K = insert(new_K, p_id(I), n_id);
			else
				new_K = insert(new_K, p_id, n_id);
			end
		end
	end
	x=x(new_K,:);
	[xmin,id]=min(x(:,1));
	K=[id:size(x,1) 1:id-1];
	x=x(K,:);
    xold((size(xold,1)+1),:)=xold(1,:);
    x((size(x,1)+1),:)=x(1,:);
    figure(1);plot(xold(:,1),xold(:,2),'b.-');xlabel('X Coordinate');ylabel('Y Coordinate');title('Original Sequence');
    figure(2);plot(x(:,1),x(:,2),'r.-');xlabel('X Coordinate');ylabel('Y Coordinate');
    title('Repaired Sequence');
end

function [E]=form_edges(K)
	for i=1:length(K)
		E(i,1)=K(i);
		E(i,2)=K(mod(i,length(K))+1);
	end
end

function [de_min]=min_edge_dist(E,x,id)
	P=x(id,:);
	for i=1:size(E,1)
		Q1=x(E(i,1),:);
		Q2=x(E(i,2),:);
		d(i)=abs(det([Q2-Q1;P-Q1]))/norm(Q2-Q1);
	end
	[de_min(1) ind]=min(d);
	de_min(2:3)=E(ind);
end

function [set2] = insert(set1, point, location)
	id = find(set1 == location);
	set2 = [set1(1:id); point'; set1(id+1:end)];
end