How to detect if a line intersects with itself?

Given a coordinate matrix:

A = [1 1; 1 2; 2 2; 2 1; 3 1];

And a tour order:

tour_order = [2; 1; 4; 3; 5; 2];

Which, when plotted, produces the following:

How do you detect that the line produced intersects with itself, and return where it does (i.e in this case it occurs by the lines 4-3 and 5-2)?

Answer 1

[George Papazafeiropoulos]

% initial data
A = [1 1; 1 2; 2 2; 2 1; 3 1];
tour_order = [2; 1; 4; 3; 5; 2];
% engine
sizeA=size(A,1);
meanA=mean(A); % point inbetween the others
vecs=A-meanA(ones(sizeA,1),:); % vectors connecting points with point inbetween
vec1=vecs(1,:);
vec1=vec1(ones(sizeA,1),:);
cosines1=sum(vecs.*vec1,2)./(hypot(vecs(:,1),vecs(:,2)).*hypot(vec1(:,1),vec1(:,2)));
vec2=vecs(1,:);
vec2=[vec2(2),-vec2(1)];
vec2=vec2(ones(sizeA,1),:);
cosines2=sum(vecs.*vec2,2)./(hypot(vecs(:,1),vecs(:,2)).*hypot(vec2(:,1),vec2(:,2)));
ind1=find(cosines2>0);
ind2=find(cosines2<0);
[~,order1]=sort(cosines1(ind1),'descend');
[~,order2]=sort(cosines1(ind2));
full_order=[1;ind1(order1);ind2(order2)];
dmax=polyarea(A(full_order,1),A(full_order,2));
d=polyarea(A(:,1),A(:,2));
% result
if d<dmax
    disp('lines intersect')
end