Determine if a line going through n rectangles exists

Question

I guess this is kinda like asking if 3 (or more) rectangles are collinear.

The question is, given n rectangles on the 2D plane (given as the rectangle's top-left corner coordinates and it's width/height), does there exist a line that goes through all of them?

Notes:

• The rectangles' sides are perpendicular or parallel to the axes. So basically, none of the rectangle sides are slanted.
• Rectangles themselves can intersect
• Does not actually need to produce the line equation

I've been thinking through this for a good portion of today, and can't figure out (or find online) an answer. I keep finding edge cases and can't figure out a guaranteed method. The line of best fit for the mid-point or the corners of all n rectangles seem like a good heuristic for a line, should one exist, but I don't think it always works.

The corners of the rectangles seem like good starting points to determine the extreme slopes of a potential line, but it's still unclear to me how i'd use them to determine if a line exists for all n rectangles. I also know how I'd do this intuitively IRL, but not sure how to turn it into an algorithm.

Visual Example for 4 rectangles:

Answer 1

There is a line through the four rectangles if and only if you can pick one edge from each rectangle such that the line intersects each of those four edges -- or equivalently, if there is a point on each of those edges such that the resulting four points are colinear. So a plausible algorithm is to enumerate all $4^4$ ways to choose one edge from each rectangle; then check whether there exists a line that goes through those four edges.

How do we do the latter test? Let's suppose the endpoints of the first edge are the two points $P',P''$ (i.e., these are two adjacent corners of the first rectangle). Then any point $P$ on that edge can be expressed as $P = (1-\alpha) P' + \alpha P''$ for some $0 \le \alpha \le 1$. Similarly, we can express any point $Q$ on the second edge as $Q = (1-\beta) Q' + \beta Q''$ where $Q',Q''$ are the endpoints of the second edge, and similarly for the two remaining points $R,S$ on the two remaining edges.

We can express algebraically the condition that $P,Q,R$ are colinear (on the same line). Let $P_x$ be the x-coordinate of the point $P$, and $P_y$ be its y-coordinate. Then $P,Q,R$ are colinear iff

$$(Q_x-P_x)(R_y-P_y) = (Q_y-P_y)(R_x-P_x).$$

We can plug in $Q_x = (1-\beta)Q'_x + \beta Q''_x$, and so on, to get an equation in terms of the three $\alpha,\beta,\gamma$ unknowns. Similarly, the condition that $P,Q,S$ are colinear can be expressed as an equation in terms of $\alpha,\beta,\delta$. Now there exists a linear through these four edges iff there exists a common solution to these two equations such that $0 \le \alpha,\beta,\gamma,\delta \le 1$. This reduces the problem to solving two quadratic equations over four real unknowns. Now you can apply standard methods for solving such equations to determine whether a simultaneous solution exists.