I have a arbitrary rectangle of size I1 X I2 and I have to formulate an recursive/iterative algorithm to partition the rectangle into set of squares. The article that I am following have formulated some mathematical formula and I am having some trouble to formulate an algorithm out of it. Lets describe the mathematics behind it.
It is assumed in the paper that I1 < I2 and
long long int L1 = std::floor(I2/I1) x I1;
The rectangular region is first partitioned into
- One I1 x L1 sub-region , and
- One I1 x (I2 - L1) sub-region.
Then the I1 x L1 sub-region is partitioned into (L1/I1) smaller square sub-regions, each with size I1 x I1.
The remaining I1 x (I2 - L1) can be partition into
- One (I2 - L1) X L2 sub-region and
- (I2 - L1) X (I1 - L2) sub-region, where
long long int L2 = std::floor(I1/(I2 - L1)) x (I2 - L1);
Repeating the above rule to partition the remaining (I2 - L1) x (I1 - L2) sub-region until the remaining sub-region is of size Z1 x Z2 such that Z1 > Z2 and one is the factor of the other. At that time, the final remaining sub-image can be partitioned into Z1/Z2 or Z2/Z1 square regions.
Now lets try to put a number over those variables …
7(I1) X 17(I2) region I shall try to explain over here.
The 7 X 17 region is first partitioned into
- 7 X 14 sub-region.
- 7 X 3 sub-region.
Then 7 X 14 sub-region is partitioned into 14/7 = 2 smaller square sub-regions, each with size 7 X 7.
The remaining 7 x 3 sub-region is also partitioned into
- One (17-14) X 6 = 3 X 6 sub-region.
- One (17 - 14) X (7 - 6) = 3 X 1 sub-region.
At last 3 X 6 sub-region is partitioned into 2 3 X 3 square sub-regions and eventually we get the square sub-regions.
And 3 X 1 sub-region is partitioned into 3 1 X 1 square sub-regions.
I am specially looking forward to formulate a recursive algorithm of the above mathematical formulation. I am attaching the related image link regarding this issue.
I hope that I explained the issue and eagerly looking forward to some hints regarding the recursive algorithm formulation.
By the way once we have the set of squares I am processing it further with recursive algorithm to generate the hilbert path.
Let me know if you need further explanation over this issue.