Intersection line and quadrilateral

8 views (last 30 days)
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!

Accepted Answer

David Goodmanson
David Goodmanson on 20 Aug 2020
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

More Answers (0)

Categories

Find more on Bounding Regions in Help Center and File Exchange

Products


Release

R2019b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!