Split a rectangle into equal sized rectangles?

Question

I need to split a rectangle (A CGRect structure which is {{float x,float y},{float w,float h}}) into a number of smaller rectangles/structures, creating some sort of a grid. I'm writing a window layout manager and I want a window preview option.

I saw similar questions but none of the algorithms I saw (the ones involving ceil and floor) worked. I've also tried:

float widthOfNewRect = total.size.width / floor(sqrt(n));
float heightOfNewRect = total.size.height / ceil(sqrt(n));

Can someone provide an example of doing it with my structure in C?

Padua

Do you expect n to be a power of two? If not, what should the result look like for e.g. n = 3 or n = 11? – Chickadee

If n isn't a power of two, I'll just center the rects on the bottom row. I just need to work out the optimal size so all of them fit on the screen. – Padua

Answer 1

Based on your last comment, I assume that you want to split your rectangle into n subrectangles of equal size, and that they should be aligned in such a manner that the number of rows and number of columns are equal (with the last row possibly not being completely filled). If so, you can use ceil(sqrt(n)) to compute the number of columns (since this is, as you apparently have guessed, the smallest amount of columns you need in order to not have more rows than columns). Then, the number of rows you need in order to accommodate n elements distributed across numColumns columns will be given by ceil(n / (double)numColumns).

As for the code you showed: the reason it doesn't work is (as you probably discovered yourself) that floor(sqrt(n)) * ceil(sqrt(n)) may well be less than n; for instance, this is the case for n = 7. The calculation I propose is a safer way to (indirectly) discover whether the number of rows should be ceil(sqrt(n)) or floor(sqrt(n)).

Chickadee

Answer 2

Have a look at this. I know it's in C++ rather than C, but the algorithm should be understandable to you. This code is untested, but should give you the general idea.

std:vector<CGRect> arrange(CGRect &original, int numWindows)
{
  int columns = ceil(sqrt(numWindows));
  int fullRows = numWindows / columns;
  int orphans = numWindows % columns;   // how many 'odd-sized' ones on our bottom row.

  int width =  original.width/ columns;
  int height = original.height / (orphans == 0 ? fullRows : (fullRows+1)); // reduce height if there are orphans

  std:vector<CGRect> output;

  //Calculate rectangles
  for (int y = 0; y < fullRows; ++y)
    for (int x = 0; x < columns; ++x)
      output.push_back(CGRect(x * width, y * height, width, height));

  if (orphans > 0)
  {
    int orphanWidth = original.width / orphans);
    for (int x = 0; y < orphans; ++x)
      output.push_back(CGRect(x * orphanWidth , y * height, orphanWidth , height));
  }

  return output;
}

Cunning

Answer 3

You want to find the factors of n which are closest to sqrt(n).

factorMax = floor(sqrt(n));
factorY = 1;
for (x = factorMax; x > 0; x--) {
if ( (n % x) == 0 ) {
    factorY = x;
    break;
}

factorX = floor(n/factorX)

This should give you equal distribution of rows and columns. It'll fail if you pick a prime number since the highest factor < sqrt(n) will be 1.

Ultramontane

factorX = floor(n/factorX), shouldn't be n/factorY? – Reinwald

Answer 4

Try this:

CGRect rect = myView.bounds;
    CGRect slice;
    CGRect remainder;
    /*enum CGRectEdge {
     CGRectMinXEdge,
     CGRectMinYEdge,
     CGRectMaxXEdge,
     CGRectMaxYEdge
     };*/

    //CGRectDivide(<#CGRect rect#>, <#CGRect *slice#>, <#CGRect *remainder#>, <#CGFloat amount#>, <#CGRectEdge edge#>)
    CGRectDivide(rect, &slice, &remainder, rect.size.width/2, CGRectMinXEdge);

    LOG_DBUG(@"%@", NSStringFromCGRect(rect));
    LOG_DBUG(@"%@", NSStringFromCGRect(slice));
    LOG_DBUG(@"%@", NSStringFromCGRect(remainder));

Scaramouch