Find out whether a 2D line (y = a*x + b) intersects with a square without using "solve" (I need something faster)

I want to find whether a line (defined by an equation of the type y = a*x + b) intersects with a square defined by 4 vertices (x_min, x_max, y_min, y_max). This needs to be evaluated thousands of times for many lines and squares using while loops, so I need something faster than my implementation using solve.

My code right now:

% example line parameters:
    a = 1.61; 
    b = -3.1;


% example square parameters:
    x_min = 7.5;
    x_max = 8.5;
    y_min = 9.5;
    y_max = 10.5;

%% Finding wheter the line interects with the square (excerpt from a while loop)

    do_they_intersect = false;

    syms x y

    tic;
    solution = solve([y == a*x + b, x>x_min, x<x_max, y>y_min, y<y_max],[x,y]);

    if rank(solution.x) > 0
        do_they_intersect = true;
    end
    toc

Elapsed time is 0.294136 seconds.

Whether choosing < / > or <= / >= is not important.

I've seen I could define the square as a polygon and then use something like inpolygon(), but it seems it only works with numeric points, bot with symbolic values.

Any ideas?

Thanks

Answer 1

[Matt J]

Sort of like William's, but faster for some reason:

% example line parameters:
a = 1.61; 
b = -3.1;
% example square parameters:
x_min = 7.5;    x_max = 8.5;
y_min = 9.5;    y_max = 10.5;

tic  
    q=[-a 1]';
    
    V=[x_min y_min; ...
       x_min y_max; ...
       x_max y_min; ...
       x_max y_max];
    
  
    tmp=V*q;
    
    do_they_intersect = any(tmp>b,1)&any(tmp<b) ;
toc

Elapsed time is 0.003675 seconds.

do_they_intersect

do_they_intersect = logical
   1

[Perico Nasdemico]

Amazing, thanks!

[Matt J]

You're welcome, but curiious that you Accepted this answer. Bruno's is shorter and faster.

Answer 2

[Bruno Luong]

This shoudl do:

% example line parameters:
a = 1.61; 
b = -3.1;
% example square parameters:
x_min = 7.5;    x_max = 8.5;
y_min = 9.5;    y_max = 10.5;

tic
y = a.*[x_min x_max] + b;
isintersected = any(y >= y_min) && any(y <= y_max);
toc

Elapsed time is 0.002860 seconds.

Answer 3

[Matt J]

Using linexlines2D,

https://www.mathworks.com/matlabcentral/fileexchange/93470-intersections-of-multiple-2d-lines-or-line-segments?s_tid=srchtitle

is about 3 times faster. If the squares in question form a regular grid, though, there are ways to apply it much faster than that.

% example line parameters:
    a = 1.61; 
    b = -3.1;


% example square parameters:
    x_min = 7.5;    x_max = 8.5;
    y_min = 9.5;    y_max = 10.5;


%% Finding wheter the line interects with the square (excerpt from a while loop)

    do_they_intersect = false;

   warning off
    
    tic;

    p=polyshape([x_min y_min; ...
                 x_min y_max; ...
                 x_max y_min; ...
                 x_max y_max]);
    
     out=linexlines2D(p,[a,-1,b]);
     
     do_they_intersect =any(~isnan(out),'all');
    toc

Elapsed time is 0.109479 seconds.

Answer 4

[William Rose]

@Perico Nasdemico,

If the slope, a, is positive, then, if there is an intersection, the line passes below or through the upper left corner, and the line passes above or through the lower right corner.

If the slope, a, is negative, then, if there is an intersection, the line passes above or thorugh the lower left corner, and the line passes below or through the upper right corner.

% example line parameters:
a = 1.61; 
b = -3.1;
% example square parameters:
x_min = 7.5;    x_max = 8.5;
y_min = 9.5;    y_max = 10.5;
%% Finding wheter the line interects with the square (excerpt from a while loop)
tic;
if a>0
        if a*x_min+b<=y_max && a*x_max+b>=y_min
            fprintf('Intersects\n');
        else
            frpintf('Does not intersect\n');
        end
else
        if a*x_min+b>=y_min && a*x_max+b>=y_max
            fprintf('Intersects\n');
        else
            frpintf('Does not intersect\n');
        end
end

Intersects

toc

Elapsed time is 0.016870 seconds.

This is a lot faster.

Good luck.

[Perico Nasdemico]

Nice, thanks!