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?
- 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: