Your 3rd example indicates you permit the user to enter a polygon $P$ that overlaps with
previous polygons $R$, with the expectation that $P$ should "wrap around" $R$.
If you want this level of generality, then you need to implement Boolean subtraction
on [orthogonal polygons](https://en.wikipedia.org/wiki/Rectilinear_polygon). See the 
[Wikipedia article on Boolean polygon operations](https://en.wikipedia.org/wiki/Boolean_operations_on_polygons), or
see [my answer](http://mathoverflow.net/a/111323/6094) to the earlier question, 
"Subtract Rectangle from Polygon."

In graphics, these are called *clipping algorithms*; there are many algorithms
available. Your task is easier because you are only considering orthogonal polygons.
Likely sweeping over your polygons with a vertical line would lead to the simplest
algorithm.

Alternatively, you could restrict the level of input generality to avoid the need
for Boolean subtraction.