How to subtract two rectangles? I am wondering how to get the Set Subtraction between two rectangles from the programming point of view. I would really appreciate if anyone could help!
We know that in $\mathbb R^2$ each rectangle can be encoded by two points at the left-bottom and right-top corner, respectively. Now, assume that we have 2 rectangles encoded by 4 points. We observe that the set subtraction of the two rectangles is a union of some other rectangles. How can we encoded these resulting rectangles?
Of course, I can do it by considering all the possible positions of the two rectangles (there are 10 cases), but I have to do it manually and without any formula.
Are there any more efficient ways to do it?
 A: As a programming point of view is mentioned, I assume that we are only interested in lattice points (e.g., "pixels") in $\Bbb Z^2$ and need not worry about the distinction between open and closed rectangles, not to mention those containing only part of their boundary.
Suppose you have rectangles $R_1=[x_1,x_2)\times[y_1,y_2)$ and $R_2=[x_3,x_4)\times[y_3,y_4)$, where $x_1<x_2$ etc.
To simplify, replace
$$x_3\leftarrow\max\{x_1,x_3\},\quad y_3\leftarrow\max\{y_1,y_3\},\quad
x_4\leftarrow\min\{x_2,x_4\},\quad y_4\leftarrow\min\{y_2,y_4\}.$$
This way, we make sure that $R_2$ does not extend outside $R_1$ and the following formulations become simpler insofar as we now have
$$ x_1\le x_3<x_4\le x_2,\quad y_1\le y_3<y_4\le y_2,$$
except that the above may make  $x_3\ge x_4$ or $y_3\ge y_4$, but then we are already done because $R_1\setminus R_2=R_1$.
Now $R_1\setminus R_2$ can be covered by four pairwise disjoint rectangle:
$$\tag1[x_1,x_3)\times[y_3,y_2)\;\cup  \;
[x_3,x_2)\times[y_4,y_2) \;\cup  \;
[x_4,x_2)\times[y_1,y_4) \;\cup  \;
[x_1,x_4)\times[y_1,y_3).$$
The only unusual thing that may happen is that one or more (in fact, perhaps all!) of these degenerate to a line (e.g., the first when $x_1=x_3$) and can thus be removed from the list.
If after removing degenerate rects, we are left with two rectangles
$$\tag2[u_1,u_2)\times [v_1,v_2)\;\cup \;[u_3,u_4)\times [v_3,v_4),$$ it may happen that we can simplify further if we want (but the two-rectangle partition is valid), namely

*

*If the horizontal intervals are the same (i.e., $u_1=u_3$ and $u_2=u_4$) and the vertical ones are juxtaposed (i.e., $v_2=v_3$ or $v_1=v_4$), thenh $(2)$ can be simplified to
$$ [u_1,u_3)\times [\min\{v_1,v_3\},\max\{v_2,v_4\}).$$

*If the vertical intervals are the same (i.e., $v_1=v_3$ and $v_2=v_4$) and the horizontal ones are juxtaposed (i.e., $u_2=u_3$ or $u_1=u_4$), thenh $(2)$ can be simplified to
$$ [\min\{u_1,u_3\},\max\{u_2,u_4\})\times [v_1,v_2).$$
