Something like this?
So then it remains to get this set of zones (which can be done with some simple rectangle intersection tests) and to be able to find the intersection of two rectangles:
zones = set of zones this box intersects
if (size of 'zones' == 1)
exit //don't have to split this box
for each 'z' in 'zones':
create a box that covers the intersection of this box and 'z'
delete this box //the boxes we made cover the same area
You could probably combine these two steps, finding the set and finding the intersections (eg, find the "intersection" and create a box only if it is a valid area: width and height > 0).
box intersect; //will contain a intersect b
intersect.xmin = max(a.xmin, b.xmin);
intersect.ymin = max(a.ymin, b.ymin);
intersect.xmax = min(a.xmax, b.xmax);
intersect.ymax = min(a.ymax, b.ymax);