Cover a Region with Rectangles Input

Your input in this challenge is a list of integer pairs. They represent the southwest corners of unit squares on the plane, and the list represents their union as a subset of the plane. For example, the list

[(0,0),(1,0),(0,1),(1,1),(2,1),(1,2),(2,2)]


represents the red-colored set in this picture:



Output

Yor output is a list of integer quadruples, representing rectangular subsets of the plane. More explicitly, a quadruple (x,y,w,h) reperents a rectangle of width w &gt; 0 and height h &gt; 0 whose southwest corner is at (x,y). The rectangles must form an exact covering of the input region, in the sense that each of the unit squares is a subset of some rectangle, each rectangle is a subset of the region, and two rectangles may overlap only at their borders. To forbid trivial solutions, the covering must not contain two rectangles that could be merged into a larger rectangle.

For example, the list

[(0,0,2,1),(0,1,3,1),(1,2,2,1)]


represents the legal covering



of the above region, whereas the covering given by

[(0,0,2,2),(2,1,1,1),(1,2,1,1),(2,2,1,1)]


is illegal, since the neighboring 1-by-1 squares could be merged:



Rules

You can give a full program or a function. The precise formatting of the input and output is not important, within reason. The shortest byte count wins, and standard loopholes are disallowed. You are encouraged to provide an explanation of your algorithm, and some example outputs.

Test Cases

A U-shaped region:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(2,0),(2,1),(3,0),(3,1),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(5,0),(5,1),(5,2),(5,3),(5,4),(5,5)]




A large triangle:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(0,9),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(2,0),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(3,0),(3,1),(3,2),(3,3),(3,4),(3,5),(3,6),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(5,0),(5,1),(5,2),(5,3),(5,4),(6,0),(6,1),(6,2),(6,3),(7,0),(7,1),(7,2),(8,0),(8,1),(9,0)]




A square with holes:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(1,0),(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),(2,0),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(3,0),(3,1),(3,2),(3,4),(3,5),(3,6),(3,7),(3,8),(3,9),(4,0),(4,1),(4,2),(4,3),(4,4),(4,5),(4,6),(4,7),(4,8),(4,9),(5,0),(5,1),(5,2),(5,3),(5,4),(5,5),(5,7),(5,8),(5,9),(6,1),(6,2),(6,3),(6,5),(6,6),(6,7),(6,8),(6,9),(7,0),(7,1),(7,2),(7,3),(7,4),(7,5),(7,6),(7,7),(7,8),(7,9),(8,0),(8,1),(8,2),(8,3),(8,4),(8,5),(8,6),(8,7),(8,8),(8,9),(9,0),(9,1),(9,2),(9,3),(9,4),(9,5),(9,6),(9,7),(9,8),(9,9)]




Disconnected regions:

[(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(1,0),(1,1),(1,2),(1,3),(1,4),(1,6),(1,7),(1,8),(1,9),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),(4,0),(4,1),(4,2),(4,4),(4,5),(4,6),(4,7),(4,8),(4,9),(5,0),(5,1),(5,2),(5,3),(5,4),(5,5),(5,6),(5,7),(5,8),(5,9),(6,0),(6,1),(6,2),(6,4),(6,5),(6,6),(6,7),(6,8),(6,9),(8,0),(8,1),(8,2),(8,3),(8,4),(8,5),(8,6),(8,7),(8,8),(8,9),(9,0),(9,1),(9,2),(9,3),(9,7),(9,8),(9,9),(10,0),(10,1),(10,2),(10,3),(10,4),(10,5),(10,6),(10,7),(10,8),(10,9)]




Verifier

Use this Python 2 program to verify your solution. It takes from STDIN a list of tuples (the input) and a list of quadruples (your output), separated by a comma.

I also wrote this Python 2 program to generate the pictures, and you can use it too. It takes from STDIN a list of either tuples or quadruples, and produces a file named out.png. It requires the PIL library. You can change the size of the grid cells and the width of the gird lines too, if you want.
Python - 272 261 258 251 224

I think I can golf this more. I'm pretty sure this works, but I haven't finished testing it on all of the test cases yet. I finished testing it. It works for all of the test cases.

a=sorted(input())
b=[]
r=range
for i in a:
 c=set(a)-set(b);w=h=1;x,y=i
 if i in b:continue
 while not{(x,y+h)}-c:h+=1
 while all((x+w,y+j)in c for j in r(h)):w+=1
 for j in r(w):
  for k in r(h):b+=(j+x,k+y),
 print x,y,w,h


I'm working on adding images of the results.
Edit: Here are the results from the example and the test cases:







I'm trying to write this in Perl, but I can't figure out how to get multidimensional arrays from stdin without a huge number of characters. Does anyone have any suggestions?