I have thought about doing it with a k-ary tree. So each node is a possible placement of a small rectangle. There are 4 combinations to add a rectangle (vertical/horizontal and how does it divide the regions).
Where the root node is the empty big rectangle and its children are the first level of possible combinations when adding one rectangle, the second level defines the possible combinations when a second rectangle is added, so on...
I have defined some objects:
BigRectangle: integer v1, v2, v3, v4 //the 4 vertices that define a BigRectangle. List<Region> regions //contains a list of Regions contained in BigRectangle. Region: integer v1, v2, v3, v4 //the 4 vertices that define a region. list<SmallRectangle> smallRectangles //contains a list of SmallRectangle contained in Region. SmallRectangle: integer v1, v2, v3, v4 //the 4 vertices that define a SmallRectangle. integer orientation //(0|1) 0-vertical, 1-horizontal.
I am trying to write the algorithm but it is being a mess. I cannot figure out how to write an algorithm to simulate this tree :(
(I am not interested on achieving the best performance)
1. Create and insert an empty BigRectangle as the root. 2. ... ...