Dividing a rectangle into smaller, equal, integer rectangles/tiles of maximum size

Question

I need to create screenshots with an extremely large resolution. Because the resolution is larger than my renderer supports, they need to be split up into smaller resolutions and stitched together later.

I have figured out the stitching/rendering part of rectangles, but I am struggling trying to find the most optimal rectangle resolution to use for each tile.

My renderer has a limit of 4096x4096.

For resolutions like 16384x16384 this would be easy to figure out: 4*4 rectangles of 4096x4096.

My input resolutions aren't always a power of two however, one such example could be 5005x5000, for which the optimal rectangle size would be 5*2 rectangles of 1001x2500.

What I'm looking for is a function that, when given a desired resolution and a maximum resolution, outputs a resolution within the maximum resolution that can be multiplied to reach the desired resolution.

Something like this:

public IntRect FindOptimalTileSize(IntRect desiredResolution, IntRect maximumTileSize)
{
    //some magic
    return new IntRect(magic.X, magic.Y);
}

The output requirements in a row:

• Resolution x and y must be integer
• Resolution x and y must be lower than given maximum x and y
• Resolution x and y must be an integer division of desiredResolution
• Resolution x and y should be as high as possible, as long as they satisfy the other rules
• Aspect ratio doesn't need to be retained

I have tried searching the internet for a solution, but those all seem to be for a different, more common usecase.

It might not always be possible to find a rectangle that satisfies all my rules, in which case I'd like the function to return something distinguishable, like -1x-1

Answer 1

I'm no math expert, but this might get you a starting point. This code is a sketch. It is not production-ready. It is not of beta quality. It is only a sketch and you will have to do a lot of work to clean it up and make it usable.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1 {
    class Program {
        static void Main(string[] args) {

            int resultX = -1;
            int resultY = -1;
            int sourceX = 5005;
            int sourceY = 5000;
            int targetX = 4096;
            int targetY = 4096;

            if (sourceX <= targetX) { resultX = sourceX; }
            if (sourceY <= targetY) { resultY = sourceY; }
            if (IsValid(resultX, resultY)) {
                //  return the results
                Console.WriteLine($"x={resultX}, y={resultY}");
                return;
            }

            for (int index=targetX; 0 < index; index--) {
                double result = (double)sourceX / index;
                if (0 == result - (int)result) {
                    resultX = index;
                    break;
                }
            }

            for (int index = targetY; 0 < index; index--) {
                double result = (double)sourceY / index;
                if (0 == result - (int)result) {
                    resultY = index;
                    break;
                }
            }

            Console.WriteLine($"x={resultX}, y={resultY}");
            Console.ReadKey(true);
        }


        static bool IsValid(int x, int y) {
            return (-1 != x) && (-1 != y);
        }
    }
}