Trim start and end points of straight line to where they enter/exit a rectangle?

Question

I'm doing some canvas painting, and for performance reasons I want to get the coordinate of where a straight line enters and/or exits the screen.

To put it more simply, I want to find out the coordinates A' and B' in the illustration below. A and B are the original start- and end coordinates. A' and B' are the coordinates where the straight line from A to B enters or exits the screen bounds.

This seems like something that would be a common scenario, but I can't really find a simple and efficient algorithm for it.

I'm using Flutter, but I guess this is a general problem with a similar solution no matter which language (A and B are points, the screen is a rect).

Answer 1

We are given the following parameters and equations:

• points A and B are given by their respective coordinates (xA, yA) and (xB, yB);
• the bounding box is given by the 4 inequations xMin <= x; x <= xMax; yMin <= y; y <= yMax;
• line (AB) is given by its equation (y-yA)*(xB-xA) = (yB-yA)*(x-A).

We can use them to solve for the intersection points:

• In the first two examples, you can find the coordinates (x,y) of A' by setting y=yMax and solving the line equation for x;
• In the first example, you can find the coordinates (x,y) of B' by setting x=xMax and solving the line equation for y;
• In the third example, you can find the coordinates (x,y) of B' by setting y=yMin and solving the line equation for x.

To find all intersection points with the bounding box in all possible case, you could solve the equations for all 4 possible types of intersections, then discard solutions which either:

• do not satisfy the bounding box inequations (those solutions are intersections with the "continuations" of the sides of the bounding box); or
• do not satisfy the inequations of the implicit bounding box around segment [AB] (those solutions are intersections of the line (AB) with the bounding box, and of no interest to you if you want only the intersections of the segment [AB] with the bounding box).