将一个矩形分成较小的、相等的、最大尺寸的整数 rectangles/tiles

Question

我需要创建分辨率非常高的屏幕截图。由于分辨率大于我的渲染器支持的分辨率，因此需要将它们拆分成更小的分辨率，然后再拼接在一起。

我已经弄清楚了矩形的 stitching/rendering 部分，但我正在努力寻找用于每个图块的最佳矩形分辨率。

我的渲染器有 4096x4096 的限制。

对于像 16384x16384 这样的分辨率，这很容易计算出来：4*4 个 4096x4096 的矩形。

我的输入分辨率并不总是 2 的幂，但是，一个这样的例子可能是 5005x5000，最佳矩形大小是 5*2 个 1001x2500 的矩形。

我正在寻找的是一个函数，当给定所需的分辨率和最大分辨率时，输出最大分辨率内的分辨率，该分辨率可以相乘以达到所需的分辨率。

像这样：

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

连续输出要求：

分辨率 x 和 y 必须是整数
分辨率 x 和 y 必须更低比给定的最大 x 和 y
分辨率 x 和 y 必须是整数 desiredResolution 的划分
分辨率x和y应该尽可能高，只要它们满足其他规则
纵横比不需要保留

我曾尝试在互联网上搜索解决方案，但这些似乎都是针对不同的、更常见的用例。

可能并不总能找到一个满足我所有规则的矩形，在这种情况下，我希望函数 return 一些可区分的东西，比如 -1x-1

Answer 1

我不是数学专家，但这可能会给你一个起点。这段代码是草图。它不是 production-ready。它不是测试版质量。这只是一个草图，您将需要做很多工作来清理它并使其可用。

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);
        }
    }
}

Answer 2

您的问题可以分解为两个相等的问题：找到整数 n 的等整数分区 p，其中 p < m。

使用扩展方法和一些助手，您可以生成 n 的质因数分解：

static IEnumerable<int> PotentialPrimes() { // fails once int.MaxValue exceeded
    yield return 2;
    yield return 3;
    var pp = 5;
    for (; ; ) {
        yield return pp;
        yield return pp + 2;
        pp += 6;
    }
}
public static IEnumerable<int> Primes() {
    return PotentialPrimes().Where(p => {
        var sqrt = (int)Math.Floor(Math.Sqrt(p));
        return !PotentialPrimes().TakeWhile(f => f <= sqrt)
                                 .Any(f => p % f == 0);
    });
}

public static IEnumerable<int> PrimeFactors(this int n) {
    var maxDivisor = (int)Math.Floor(Math.Sqrt(n));
    var testDivisors = Primes().TakeWhile(pp => pp < maxDivisor);

    foreach (var f in testDivisors)
        for (; n % f == 0; n /= f)
            yield return f;

    if (n != 1)
        yield return n;
}

现在，使用质因数分解，您可以找到小于 m 的最大 p（根据评论，如果 n > m，则返回 n）：

public static int LargestPartition(this int n, int maxPartitionSize) {
    var factors = n.PrimeFactors().Where(f => f <= maxPartitionSize);
    if (factors.Any()) {
        var flist = factors.OrderByDescending(f => f).ToList();
        var partition = flist.First();
        foreach (var f in flist.Skip(1)) {
            var tp = partition * f;
            if (tp <= maxPartitionSize)
                partition = tp;
        }

        return partition;
    }
    else
        return n;
}

最后，只需将 LargestPartition 应用到矩形的每一边：

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

注意：我更新了我的 PrimeFactors 函数，以便在更一般的情况下更快，以防有人遇到这个问题。以前我无法在一小时内从 2 计算到 int.MaxValue，现在需要 36 秒。如果性能仍然是一个问题，可以替换 Math.Sqrt，但我认为到那时其他开销将占主导地位。

将一个矩形分成较小的、相等的、最大尺寸的整数 rectangles/tiles

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

c#

math

tiling