Find the center of n squares which together build a rectangle

Question

I have a rectangle with size w and height h. Now I want to split this rectangle into n new rectangles that are as similar as possible to a square. Afterwards I'd like to calculated the center of each square.

public static List<Point> getCenters(int number, double width, double height) { List<Point> points = new List<Point>(); int originalNumberOfSquares = number; int numberOfSquares = number; if (numberOfSquares % 2 == 1) { numberOfSquares++; } int rectangleWidth = Convert.ToInt32(width); int rectangleHeight = Convert.ToInt32(height); double minDistance = Double.MaxValue; int nSquaresInRow = -1; int nSquaresInColumn = -1; for (int i = 0; i <= numberOfSquares; i++) { for (int j = 0; j <= numberOfSquares; j++) { if (i * j == numberOfSquares) { if (Math.Abs(i - j) < minDistance) { minDistance = Math.Abs(i - j); nSquaresInRow = i; nSquaresInColumn = j; } } } } int squareWidth = rectangleWidth / nSquaresInColumn; int squareHeight = rectangleHeight / nSquaresInRow; for (int r = 0; r < originalNumberOfSquares; r++) { int xSquareCenter = (((r + 1) * 2) - 1) * (squareWidth / 2); while (xSquareCenter > rectangleWidth) { xSquareCenter = xSquareCenter - rectangleWidth; } int row = (r / nSquaresInColumn) + 1; int ySquareCenter = ((2 * row) - 1) * (squareHeight / 2); points.Add(new Point(Convert.ToDouble(xSquareCenter), Convert.ToDouble(ySquareCenter))); } return points; }

Now the code works, but I think it's a little bit ugly. Any hints on how I can improve it?

Are you sure your code does what you say it does? The best way to place 4 rectangles in a 2x8 rectangle would be if each one was 2x2 and thus square. However your algorithm would prefer 1x4 rectangles, since it looks for the size where the number of rectangles in a row and in a column are most similar, not where they are most square. — sepp2k
– sepp2k, Commented Feb 9, 2011 at 2:53
@sepp2k: I'm not really sure what you're referring to. But for example if I call the method with (4, 20, 80), I get as results (20/5) (60/5) (20/15) (60/15). So I think the ordering is 2x2? — RoflcoptrException
– RoflcoptrException, Commented Feb 9, 2011 at 9:34
@Rofcloptr: The ordering is 2x2, but the size of each of the rectangles is 40x10. But according to your description, you want the rectangles to be as close to a square as possible, so the ordering should be 4x1, which would make the size of each rectangle 20x20. So either your problem description or your code is wrong. — sepp2k
– sepp2k, Commented Feb 9, 2011 at 14:50

sepp2k · Accepted Answer · 2011-02-09 02:43:06Z

A couple of notes:

The width, height and number of sub-rectangles should be parameters, not local variables. If you should, for example, want to print out the centres for differing values of w, h and n, calling the method in a loop with different arguments is more convenient than changing the code and rerunning it multiple times.
Determining the size of the sub-rectangles and collecting their centres could be done in two separate methods because a) they can easily be separated as they're not intertwined b) it makes it immediately obvious which part is done by which code and c) they might be useful on their own.
Rather than outputting the centres, you should return them in an array or list. This way you can also easily use the method in a context where you don't want to print the centres or want to do something to them before printing. Also it's generally a good practice to separate IO code from logic code.
Since both i and j are ints and thus minDistance will only ever hold integer values, it should have type int, not double. Otherwise it leaves the impression that it could possibly have a non-integer value.
On a similar note you should probably make the type of width and height int as well since the first thing you do is to truncate them to ints. Having their type be double might make the user of your method think the results will be more accurate than they really are.

Anthony Pegram · Accepted Answer · 2011-02-09 02:11:04Z

Your first step should be to use meaningful variable names, even for your looping variables. I've never looked at this code before. I have no idea what it's doing. When other members of your team (if you have one) look at this code, they'll have no idea what's happening. If you come back to this code in a few days, weeks, months, etc., you will be in the same boat as the rest of us. Once you've given variables good names, it will be easier to reason about the code for both yourself and anyone else who comes after you. In turn, it will be easier to give additional refactoring advice, if appropriate.

Snowbear · Accepted Answer · 2011-03-06 11:55:35Z

1) Your code doesn't handle number=0 properly anyway (it will throw on int squareWidth = rectangleWidth / nSquaresInColumn;) so I would start your first loops (i,j iterators) from 1 since 0 rows/columns won't fit anyway.

2) You do not actually need j loop. Instead of:

 for (int i = 0; i <= numberOfSquares; i++) { for (int j = 0; j <= numberOfSquares; j++) { if (i * j == numberOfSquares) { ... } } }

It can simplified to (and taking into account my #1):

 for (int i = 1; i <= numberOfSquares; i++) { int j = numberOfSquares / i; if (i * j == numberOfSquares) { ... } }

3) You don't need to iterate up to numberOfSquares here: for (int i = 1; i <= numberOfSquares; i++). Since i=2,j=6 is the same as i=6,j=2 and you're looking only for first one you can iterate up to root square of numberOfSquares:

int maxI = (int)Math.Sqrt(numberOfSquares); for (int i = 1; i <= maxI; i++)

4) Since you're looking for minimal i-j difference you should start iterating from closest one and stop iterating as soon as you will find matching pair. Original:

 int maxI = (int)Math.Sqrt(numberOfSquares); for (int i = 1; i <= maxI; i++) { int j = numberOfSquares / i; if (i * j == numberOfSquares) { if (Math.Abs(i - j) < minDistance) { minDistance = Math.Abs(i - j); nSquaresInRow = i; nSquaresInColumn = j; } } }

Modified:

 int maxI = (int)Math.Sqrt(numberOfSquares); for (int i = maxI; i >= 1; i--) // looping in reverse order { int j = numberOfSquares / i; if (i * j == numberOfSquares) { // if (Math.Abs(i - j) < minDistance) we do not need this check anymore { minDistance = Math.Abs(i - j); nSquaresInRow = i; nSquaresInColumn = j; break; } } }

5) With my #3 change you do not need Math.Abs anymore since i is always less or equal than j:

minDistance = j - i;

Now let's go to second loop:

6) int xSquareCenter = (((r + 1) * 2) - 1) * (squareWidth / 2); here double maths should be used otherwise you're loosing precision here.

7) Also this line is a little bit difficult to understand. I would introduce row and column variables to make it more clear:

int column = r % nSquaresInRow; double xSquareCenter = (column + 0.5) * squareWidth; int row = r / nSquaresInRow; double ySquareCenter = (row + 0.5) * squareHeight;

8) Last thing, I would replace both loops with Linq. Final result:

public static List<Point> getCenters(int number, double width, double height) { List<Point> points = new List<Point>(); int originalNumberOfSquares = number; int numberOfSquares = number; if (numberOfSquares % 2 == 1) { numberOfSquares++; } int rectangleWidth = Convert.ToInt32(width); int rectangleHeight = Convert.ToInt32(height); int nSquaresInRow = -1; int nSquaresInColumn = -1; int maxI = (int)Math.Sqrt(numberOfSquares); int nSquaresInRow = Enumerable.Range(1, maxI) .Reverse() .First(i => numberOfSquares % i == 0); int nSquaresInColumn = numberOfSquares / nSquaresInRow; int squareWidth = rectangleWidth / nSquaresInColumn; int squareHeight = rectangleHeight / nSquaresInRow; return Enumerable.Range(0, originalNumberOfSquares) .Select(r => new { Column = r % nSquaresInRow, Row = r / nSquaresInRow}) .Select(p => new { xSquareCenter = (p.Column + 0.5) * squareWidth, ySquareCenter = (p.Row + 0.5) * squareHeight}) .Select(p => new Point(p.xSquareCenter, p.ySquareCenter)) .ToList(); }

Stack Exchange Network

Find the center of n squares which together build a rectangle

3 Answers 3

You must log in to answer this question.

Hot Network Questions

Find the center of n squares which together build a rectangle

3 Answers 3

You must log in to answer this question.

Related

Hot Network Questions