# What's the minimum number of points I need to measure to find out how much two rectangles are overlapping?

This is for a web app, but I think it's a general geometric problem, and almost certainly a solved one:

I have a rectangle $(A)$ and I know its size. I'm trying to figure out if there's another rectangle $(B)$ overlapping mine, and by how much to $25\%$ accuracy. (That is, I want to know if $B$ is covering $0\%$, $0-25\%$, $25-50\%$, $50-75\%$ or $100\%$ of $A$.)

• There may or may not be a second rectangle.
• There may be more than one other rectangle.
• The rectangles are all oriented parallel to each other (no rotation).
• I can only test by checking for an overlap at a particular point on my rectangle's surface.

I'm trying to figure out the most efficient possible arrangement of detection points. Ideally, I'd simply be able to count up the number of hits to know the $\%$ in some kind of simple linear way. Something like the image in this overlap detection drawing.

$\hskip{2.8in}$

-
The answer might depend on whether the sides of the other rectangles are always perpendicular/parallel to the sides of the first rectangle. – Seamus Feb 29 '12 at 17:38
They are parallel. Well... in theory, there could be rotation, but it's extremely rare, so let's assume "no" for now. It doesn't have to be a perfect approximation. – Muka Sprugman Feb 29 '12 at 17:42
So for an overlap of >25%, the centre of the rectangle will be covered. And I have a feeling that there will be points along the line from the centre to each vertex that suffice to show more overlap? I'm not sure. – Seamus Feb 29 '12 at 17:46
>50%, I agree, but couldn't you have an overlap like that in the drawing that was just shy of 50% without the centre being covered? – Muka Sprugman Feb 29 '12 at 17:49
Oh yeah. I was just imagining congruent rectangles sliding over each other. And even there I was being silly. So this is true: it is a necessary condition on >50% being covered, that the centre is covered. But it is not sufficient. A sufficient condition for >25% coverage is one vertex and the centre covered. But this is not necessary. – Seamus Feb 29 '12 at 17:53

There are a few domains that treat this kind of thing.

Just to try to give your problem a concrete formulation, here are some very simple observations and fundamental questions.

I imagine your problem is that you have a collection of rectangles $\{A_k\}_{k=1}^n$ in $\mathbb{N}^2$ (i.e. with nonnegative integral coordinates), each centered at $(x_k,y_k)$ and having half-lengths $(a_k,b_k)$, so that $A_k=\{(x,y)\in\mathbb{N}^2 \mid |x-x_k| \le a_k \wedge |y-y_k| \le b_k \}$. Such representations are unique as long as $\forall k: a_k \le x_k,~b_k \le y_k$.

Fundamental questions (the first being, are you working in $\mathbb{R}$ or ${Z}$, continuous or discrete coordinates):

• Are you working with continuous or discrete rectangles (i.e. over $\mathbb{R}$ or $\mathbb{Z}$), and are the coordinates signed or unsigned?
• Do all the edges of a rectangle contain points (which can cover those of another rectangle)?
• Do you know $k$?
• Do you know all rectangles?
• Do you know their centers $(x_k,y_k)$ and "radii" $(a_i,b_i)$?

One subtlety with the above definition is that, in the discrete case, the $x$ or $y$ coordinates of the center and "radii" will be half-integers, in $(\frac12\mathbb{N})^2$, precisely when the full length in that dimension is even. This amounts to an additional constraint, namely, that $2x_k\equiv2a_k\pmod2$ and $2y_k\equiv2b_k\pmod2$. But the interval endpoints are always integers.

Let us abbreviate this by saying $A_k=\text{Rect}(x_k,y_k,a_k,b_k)$, $C(A_k)=(x_k,y_k)$ for the center and $R(A_k)=(a_k,b_k)$ for the "radii". We could then say that an arbitrary point $P$ is inside $R$ if $|P-C| \le R$, where this is interpreted as a joint statement or simultaneous inequality in each dimension (so that $|P-C| \not\le R$ and $|P-C| \gt R$ have different meanings).

This definition is equivalent to defining rectangles on $[0,\infty)^2$ by identifying points $(x,y)\in\mathbb{N}^2$ with cells $[x,x+1)\times[y,y+1)\in\mathbb{R_{\ge0}}^2$. With this identification of $\mathbb{N}^2$ with $\mathbb{R}_{\ge0}^2$, we can say that $A_k=[x_k-a_k,x_k+a_k ]\times[y_k-b_k,y_k+b_k ]$ in the former space, but that $A_k=[x_k-a_k,x_k+a_k+1)\times[y_k-b_k,y_k+b_k+1)$ in the latter space.

Let $m$ be your area function on rectangles, i.e. $m(A)=\#(A\cap\mathbb{N}^2)$ is the number of integer points in the rectangle (this formula works also in $\mathbb{R_{\ge0}}^2$ if the rectangles have integral side lengths and are left-closed, righ-open). The intersection of two rectangles $A$ and $B$ is also a rectangle, $AB=A\cap B$, since they are parallel. The overlap is just $m(AB)$.

Given $A_j$ and $A_k$ as above, their intersection is (non)empty iff their centers are (not) too far apart in either dimension:

$$A_j \cap A_k = \emptyset \qquad \iff \qquad |x_j-x_k|>a_j+a_k \quad \vee \quad |y_j-y_k|>b_j+b_k$$

$$A_j \cap A_k \ne \emptyset \qquad \iff \qquad |x_j-x_k| \le a_j+a_k \quad \wedge \quad |y_j-y_k| \le b_j+b_k$$

In the case that it is nonempty, the intersection will be given by

\eqalign{ A_j \cap A_k &= % why are the parenthesis pair sizes different when using \left & \right? % \left( [x_j-a_j,x_j+a_j] \cap [x_k-a_k,x_k+a_k] \right) % \times % \left( [y_j-b_j,y_j+b_j] \cap [y_j-b_j,y_j+b_j] \right) \bigg( [x_j-a_j,x_j+a_j] \cap [x_k-a_k,x_k+a_k] \bigg) \times \bigg( [y_j-b_j,y_j+b_j] \cap [y_j-b_j,y_j+b_j] \bigg) \\ &= [\max(x_j-a_j,x_k-a_k),\min(x_j+a_j,x_k+a_k)] \\ & \times~[\max(y_j-b_j,y_k-b_k),\min(y_j+b_j,y_k+b_k)] \\ } where, since we are treating endpoints, they are all integral in the discrete case.

Assuming parallel rectangles and in the discrete case that edges contain points and can therefore cover points from other objects, it will be true that for two rectangles $A$ & $B$, $A$ covers half or more of $B$ iff $A$ (as an object in $\mathbb{R}^2$) contains the center of $B$: $$m(AB)\ge\frac12m(B) \iff C(B)\in A.$$ Note, in the discrete case, that we must on the RHS treat half-integer coordinates of $C(B)$ as being in $A$ as long as they satisfy (both) the distance inequalities above, i.e. if the point's four nearest integral neighbors lie in $A$.

Actually, the diagram you linked is very illuminating. If you think about integer-valued vertices as the sample points each being assigned or identified with a $1\times1$ cell (say, by a left endpoint rule to use terminology from Riemann sums), I think you will see that it is a limiting case. Therefore, the interplay between discrete rasterization and the more familiar continuous geometry of $\mathbb{R}^2$ comes into play, and you need $25$ sample points to detect quarter-area overlaps of a $4\times4$ rectangle of area $16$.

-