2
$\begingroup$

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:

$\endgroup$
  • $\begingroup$ One necessary but not sufficient condition is that every rect (short for iso-oriented rectangle) must overlap the convex hull of "opposite" rects. For each dimension, one such pair is one rect with minimum and one with maximum coordinate value. $\endgroup$ – greybeard Mar 5 '18 at 8:47
  • $\begingroup$ If only I understood the paragraph Stabbing line segments in $ℝ^2$ in Hohmeyer, M.E.; Teller, S.J.: Stabbing isothetic boxes and rectangles in O(n log n) time in Computational Geometry: Theory and Applications 2 (1992) pp. 201-207. $\endgroup$ – greybeard Mar 6 '18 at 19:17
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ There is a line through the four rectangles if and only if you can pick one edge from each rectangle such that the line goes through those four edges the rectangles' sides are perpendicular or parallel to the axes, I can't see a similar condition for the line. $\endgroup$ – greybeard Mar 5 '18 at 6:16
  • $\begingroup$ @greybeard, thanks for the comment. In retrospect, my writing was unclear. I didn't mean that the line has to be horizontal or vertical. Rather, I meant that the line intersects each of those four edges somewhere. I've edited the question to try to improve the wording. I hope it makes sense now. Thanks again for the feedback! $\endgroup$ – D.W. Mar 5 '18 at 7:28
  • $\begingroup$ (I read more into line goes through[…] edges than warranted. You seem to have posted in a hurry: straightforward (but not necessarily) algorithm?) $\endgroup$ – greybeard Mar 5 '18 at 8:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.