# divide an arbitrary rectangle into set of squares

Hello forum,

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

1. One I1 x L1 sub-region , and
2. 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

1. One (I2 - L1) X L2 sub-region and
2. (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

1. 7 X 14 sub-region.
2. 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

1. One (17-14) X 6 = 3 X 6 sub-region.
2. 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.

http://i.imgur.com/EiJmVtG.png

http://i.imgur.com/so47k0A.png

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.

Thanks