I suggest you investigate the CGAL manual, Chapter 19: "2D Regularized Boolean Set-Operations". Here is an example of polygon difference:
            PolygonSubtraction http://cs.smith.edu/%7Eorourke/MathOverflow/TriangleSubtraction.jpg
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 Murta's Fig.2 illustrates a complicated polygon difference (and the remaining images illustrate other Boolean operations).
      Boolean Ops http://cs.smith.edu/%7Eorourke/MathOverflow/BooleanOps.jpg

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 Murta's Fig.2 illustrates a complicated polygon difference (and the remaining images illustrate other Boolean operations).
      

I suggest you investigate the CGAL manual, Chapter 19: "2D Regularized Boolean Set-Operations". Here is an example of polygon difference:
            PolygonSubtraction http://cs.smith.edu/%7Eorourke/MathOverflow/TriangleSubtraction.jpg
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. 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 Fig.2 illustrates a complicated polygon difference (and the remaining images illustrate other Boolean operations).
      Boolean Ops http://cs.smith.edu/%7Eorourke/MathOverflow/BooleanOps.jpg

I suggest you investigate the CGAL manual, Chapter 19: "2D Regularized Boolean Set-Operations". Here is an example of polygon difference:
            PolygonSubtraction http://cs.smith.edu/%7Eorourke/MathOverflow/TriangleSubtraction.jpg
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 Murta's Fig.2 illustrates a complicated polygon difference (and the remaining images illustrate other Boolean operations).
      Boolean Ops http://cs.smith.edu/%7Eorourke/MathOverflow/BooleanOps.jpg