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 > 0
and height h > 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.