代码之家 › 专栏 › 技术社区 › ManIkWeet

将矩形划分为最大大小的较小、相等、整数矩形/分幅

tiling math c#

ManIkWeet · 技术社区 · 7 年前

我需要创建分辨率极高的屏幕截图。由于分辨率大于渲染器支持的分辨率,因此需要将它们拆分为更小的分辨率,然后再缝合在一起。

我已经找到了矩形的拼接/渲染部分,但我正在努力找到每个平铺使用的最佳矩形分辨率。

我的渲染器限制为4096x4096。

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

我的输入分辨率并不总是二的幂,但是,其中一个示例可能是5005x5000,对于该示例,最佳矩形大小为1001x2500的5×2矩形。

我要寻找的是一个函数,当给定所需的分辨率和最大分辨率时,它会在最大分辨率范围内输出一个分辨率,可以将该分辨率乘以以达到所需的分辨率。

类似这样:

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

一行中的输出要求:

分辨率x和y必须为整数
分辨率x和y必须更低大于给定的最大x和y
分辨率x和y必须是整数理想解决方案分部
分辨率x和y应尽可能高,只要它们满足其他规则
无需保留纵横比

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

可能并不总是能够找到一个满足所有规则的矩形,在这种情况下,我希望函数返回一些可区分的内容,如-1x-1

2 回复 | 直到 7 年前

Sam Axe 7 年前

我不是数学专家,但这可能会给你一个起点。此代码是一个草图。它还没有准备好生产。它不是beta质量。这只是一个草图,你需要做很多工作来清理它并使其可用。

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

NetMage 7 年前

您的问题可以分解为两个相等的问题:找到整数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 如果性能仍然是一个问题,则可以替换,但我认为到那时,其他开销将占主导地位。