I'm trying to create a jigsaw puzzle game in JavaScript and am struggling with this particular part of the code.
The answer posted on this question by Neptilo is almost perfect for my needs, but it assumes that $n$ can be adjusted to the closest ideal value. In my case, $n$ must remain at the exact value given, but some pieces can be smaller/bigger than others to compensate for the extra/missing space.
To make this question a little more self-contained, here's Neptilo's proposed solution to the problem:
// Compute number of rows and columns, and cell size
var ratio = x / y;
var ncols_float = Math.sqrt(n * ratio);
var nrows_float = n / ncols_float;
// Find best option filling the whole height
var nrows1 = Math.ceil(nrows_float);
var ncols1 = Math.ceil(n / nrows1);
while (nrows1 * ratio < ncols1) {
nrows1++;
ncols1 = Math.ceil(n / nrows1);
}
var cell_size1 = y / nrows1;
// Find best option filling the whole width
var ncols2 = Math.ceil(ncols_float);
var nrows2 = Math.ceil(n / ncols2);
while (ncols2 < nrows2 * ratio) {
ncols2++;
nrows2 = Math.ceil(n / ncols2);
}
var cell_size2 = x / ncols2;
// Find the best values
var nrows, ncols, cell_size;
if (cell_size1 < cell_size2) {
nrows = nrows2;
ncols = ncols2;
cell_size = cell_size2;
} else {
nrows = nrows1;
ncols = ncols1;
cell_size = cell_size1;
}
where $x$ = the image width, $y$ = the image height and $n$ = the number of pieces.
So let's suppose that a user comes to my site and chooses an image that is 1024x682 pixels. He also specifies that he wants to play a 50 piece puzzle. The question is: how do I split the image into exactly 50 pieces but maintain the original size (or at least the aspect ratio) of the image?
Incorporating Neptilo's code above into my own gives me 54 pieces, spread over a 9x6 grid with each piece being 113px square. So how could I remove 4 of those pieces and resize some of the others to compensate (preferably without changing the grid or AR parameters)? MTIA! :D
P.S. If it helps at all, a great example of what I'm trying to acheive is this website. However, I'd like the user to be able to specify their own image to use (whether they input a URL or upload one from their PC), hence why I'm creating my own site.
Cutting rectangles into rectangles can be a surprisingly difficult problem. (See for example this related, more general question here: What rectangles can a set of rectangles tile?)
I am not sure in your specific case a solution is always possible. Even if an exact solution is possible, an algorithm to find it may need to run for a long time. And even then the solution may not be satisfactory. (For example, it may give you a bunch of $1 \times 1$ squares which don't make for good puzzle pieces.)
So the best solution will involve some compromise; you already have a solution that compromises the number of pieces and the image size.
A different compromise would be to allow non-square pieces, and change the number of pieces so that you can keep the image size. In this case, you can modify the code you have to calculate the excess image (in your example, its 7 pixels by 4 pixels). You can then enlarge some rectangles (in your example, 7 columns and 4 rows) by one pixel along the width and / or height. It will usually not be possible to tell the difference, especially if you use "classic cuts" which destroys the exact shape in any case.
Here is how big the pieces will be in your example (the image is conceptual, it does not match the actual pixel sizes):