Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

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

share|improve this answer
    
Is it possible for you to add a picture illustrating this? –  daniel.jackson Apr 17 '12 at 20:34
add comment

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

share|improve this answer
    
Looking at the example above, if there's a rectangle E that is above R and to the left of it then it will never intersect with R but you are still taking it in account when finding M. –  daniel.jackson Apr 17 '12 at 20:29
    
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^2 –  Adam Rubinson Apr 17 '12 at 20:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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