%This software implements the point matching algorithm described in the paper:
%"Rotation Invariant Nonrigid Point Set Matching in Cluttered Scenes", IEEE transaction on Image Processing, 2012

%Author: Wei Lian (Changzhi University, Changzhi, 046011, Shanxi Province, P.R. China, Email: lianwei3 at gmail.com)

%If you use this software for research purposes, you should cite the aforementioned paper in any resulting publications.


function X=TSP_2opt_improvement(X)
%%X: N x 2
N=size(X,1);
%%2-opt improvement
% for iter=1:100
while 1    
    flag=0;
    %%loop
    for ii=1:N-2
        if ii==1
            jend=N-1;
        else
            jend=N;
        end        
        for jj=ii+2:jend
            jnex=mod(jj,N)+1;
            leniin=sqrt(sumsqr(X(ii+1,:)-X(ii,:)));%dist(ii+1,ii);%
            lenjjn=sqrt(sumsqr(X(jnex,:)-X(jj,:)));%dist(jnex,jj);%
            lenij=sqrt(sumsqr(X(ii,:)-X(jj,:)));%dist(ii,jj);%
            leninjn=sqrt(sumsqr(X(ii+1,:)-X(jnex,:)));%dist(ii+1,jnex);
            
            cost=leniin+lenjjn-lenij-leninjn;
            if cost>1e-5
                X=[X(1:ii,:); flipud(X(ii+1:jj,:)); X(jj+1:N,:)];
                flag=1;
            end
        end
    end
    if flag==0
        break;
    end    
end

%%general fomula: mod(x-1,N)+1
