# How to detect if a line intersects with itself?

5 views (last 30 days)
John on 29 May 2014
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)?

George Papazafeiropoulos on 29 May 2014
% 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