MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 added 43 characters in body

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).

1

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. 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).