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. See the Wikipedia article on Boolean polygon operations, or see my answer 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.