I'm looking for a simple algorithm that, given a rectangle with width w and height h, splits the rectangle into n more or less equal sized and shape rectangles and calculates the center of these rectangles.
EDIT: Forgot to mention that the shapes should be as similar as possible to a square.
Any hints how to start?
A simple algorithm is to split vertically into n equal sized strips of height h and width w/n.
If you assume that the initial rectangle has corners (0,0) and (w,h) then using this algorithm the ith rectangle would have center (w / n * (i + ½), h/2), for 0 <= i < n.
Update: try finding all the factorizations of the number n into factor pairs (i, j) such that i * j = n, and find the factor pair such that the ratio of the factors is closest to the ratio of the sides of the rectangle. Then use the two factors to create a regular grid of smaller rectangles.
For example when n is 10, you can choose between (1, 10), (2, 5), (5, 2) and (10, 1). Here is an example grid using the factors (5, 2):
------------------------------------ | | | | | | | | | | | | ------------------------------------ | | | | | | | | | | | | ------------------------------------
If your initial rectangle has width 60 and height 20 then using the factor pair (5, 2) will give ten rectangles of size (60/5, 20/2) = (12, 10) which is close to square.
