Sagen wir, du machst A minus B. Und es existiert mindestens ein Punkt von B
innerhalb A (Alles andere vorher abfangen)
Dieser Punkt wird in der Form eine konkave Ecke bilden. (Also eine Ecke "nach innen") und muss ein neues Rechteck erzeugen. Hierzu kannst du einfach eine der beiden Richtungen nach innen wählen, und entlang dieser Richtung das Rechteck teilen.
Nun bleibt zu prüfen, ob eines der verbleibenden Rechtecke einen (anderen) Punkt von A enthält. Da sich der vorige Punkt auf dem Ranf befindet, darf er nicht nochmals gefunden werden.
Sobald es komplexer wird, würde ich dir diese ausgezeichnete Stack-Overflow Antwort ans Herz legen:
http://stackoverflow.com/a/6634668/1974021
Dort wir eine Form in möglichst viele Rechtecke zerteilt, wenn du deine Differenz als Polygon definierst, würde das direkt zutreffen.