I suggest you investigate the CGAL manual, Chapter 19:
"2D Regularized Boolean Set-Operations".
Here is an example of polygon difference:
This is well-understood & explored algorithmically, but nevertheless a very delicate computation, as the term regularized indicates. You are subtracting a rectangle, but there is nothing special about a rectangle—"degenerate" situations may occur.
You really need to consider the general situation. So I recommend you look at general resources,
such as
"Boolean operations on general planar polygons." M. Riveroa, F.R. Feitob. Computers & Graphics. Volume 24, Issue 6, December 2000, Pages 881–896 (Elsevier link)
or
"A General Polygon Clipping Library." Version 2.32. Alan Murta. (link)
The upperleft corner of his Murta's Fig.2 illustrates a complicated polygon difference (and the
remaining images illustrate other Boolean operations).
