2
$\begingroup$

I have a list $W$, of (non intersecting) rectangles where $W \ni w = (x, y, \text{width}, \text{height})$. The list is increasingly sorted by $y$-coordinates.

Given an input rectangle $R$, I would like to know how much $R$ can grow (maintaining aspect ratio) without intersecting with any of the other rectangles.

An example:

enter image description here

Here $W=\{D, B, C\}$ where $D=(10, 2, 2, 8)$, .. and $R=(1, 1, 1, 1)$, so its aspect ratio is $\frac{w}{h}=1$. R can grow its width to 8, because at 9 it intersects with D, but the height is maximized at 6. Therefore R can grow up to 6 times before it intersects with any of the other rectangles.

I'd like this function (or algorithm) to return 6 as the result.

Right now I'm doing the brute force approach, that is grow R once, check for each $w\in W$ if $w \cap R = \emptyset$ and repeat until the intersection is non-empty.

2 Answers 2

2

Because $R$ maintains its aspect ratio, you know the line $L$ along which $R$'s upper-right corner tracks as it grows. Identify all those rectangles that either lie above $L$, with some portion right of the leftmost coordinate of $R$, or are intersected (from below) by $L$. Sort their bottom edges vertically. The lowest bottom edge is the rectangle you'll hit above as $R$ grows.

Repeat the same calculation for the rectangles right of $L$, sorting left edges to find the one first hit as $R$ grows.

Then take the smaller of the two growths.

In your example, $L$ has slope 1, $B$ is hit first above, $D$ is hit first to the right, but $B$ is hit before $D$.


As requested, here is an illustration, with the slope of $L$ $\frac{1}{2}$:
Rectangles

  • 0
    Is it possible for you to add a picture illustrating this?2012-04-17
0

Your final sentence is basically knocking on the door...

You could write: Given n rectangles $A_1$ = $(a_{1},b_{1},c_{1},d_{1})$ , $A_2$ = $(a_{2},b_{2},c_{2},d_{2})$ , ... , $A_n$ = $(a_{n},b_{n},c_{n},d_{n})$ , then the largest possible square which doesn't intersect any of the squares $A_i$ ($1\leq$ i $\leq$ n) is $(1,1,M,M)$, where M = min{$a_{1}$, $a_{2}$, ..., $a_{n}$, $b_{1}$, $b_{2}$, ..., $b_{n}$} - 2.

This is the same thing as finding the minimum of the $a_{i}$, then finding the minimum of the $b_{i}$ and then you have M = (minimum of these two values) - 2

  • 0
    that is trivial... My example obviously assumed we are only drawing rectangles in the first quartile of the graph... you can easily extend my method to all four quartiles and hence to R^22012-04-17