Intersection line and quadrilateral

Hi everyone, I found something about this, but nothing as simplified as I'm looking for.

I have a line expressed with a series of x and y coordinates

x_l = [0 1 5 4 8];
y_l = [1 4 2 2 3];

and a quadrilateral area identified with the coordinates of its 4 angular nodes in counterclockwise order (it should be a generical quadrilateral, but I can assume it's a square if it's too articulated):

% ex: square
A_x = [3 4 4 3]; 
A_y = [2 2 3 3];

I need to verify if the line intersect the area... Just to verify, not to find the intersection.

I've found some methods online, but all of them are exaggerated and heavy for my purposes ("polyxpoly" for example); I have many squares and many lines to be processed and i just need a true or false flag in the fastest way possible. Maybe it's super simple, or maybe not, but nothing comes to my mind!

Thanks to anyone who wants to help me!

Answer 1

[David Goodmanson]

Hi Francesco

Here is one way. The function linecross determines whether two line segments intersect. The function yesno just runs through all possible pairs of segments, one from the line and one from the quadralateral. Points are represented by complex numbers, and you have to append the first point in the quadrilateral to the end in order to close the figure.

% sample data (doesn't necessarily make a convex polygon)
xydata = 10*rand(2,10);
Adata = 4*rand(2,4);

% complexify
xy = xydata(1,:) + i*xydata(2,:);
A = Adata(1,:) + i*Adata(2,:);
A = [A A(1)];   % close the figure

y = yesno(xy,A)

figure(1)
plot(xy,'ob-')
hold on
plot(A,'or-')
hold off

function y = yesno(xy,A)
% run through pairs of line segments
y = 0;
for j = 1:size(xy,2)-1
  for k = 1:size(A,2)-1
    y = linecross(xy(j),xy(j+1),A(k),A(k+1));
    if y==1
     return
    end
  end
end
end

function x = linecross(a,b,c,d)
% output is 1 if two line segments intersect, 0 otherwise
% end points a--b  and c--d are complex numbers  
ba = b-a;
ca = c-a;
dc = d-c;
if sign(imag((ca)/ba))~=sign(imag((d-a)/ba)) ... 
   & sign(imag(ca/dc))==sign(imag((b-c)/dc))
  x= 1;
else
  x = 0;
end
end