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$.