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

与纵横比匹配的最小大小

algorithm .net c#

4

TheCloudlessSky · 技术社区 · 15 年前

我需要找到 最低限度

下面是当前坏的我有个主意 O(n^2) :

epsilon = 0.001;

from x = 1 to MAX_X
{
  from y = 1 to MAX_Y
  {
    if(Abs(x / y - aspectRatio) <= epsilon)
    {
      return new Size(x, y);
    }
  }
}
return Size.Empty;

5 回复 | 直到 15 年前

1

6

Hans Passant 15 年前

不寻常。你需要找到最大公约数,用它来除宽度和高度。算法是由欧几里德和两千三百年的历史。细节 are here

2

1

Community Mohan Dere 9 年前

你可以把aspectRatio写成分数 (如果您希望它的预测值达到0.001,那么可以使用round(aspectRatio,3)/1000)

simplify this fraction . 得到的分数就是你要找的x/y。

3

1

Mike 15 年前

一个更快的方法,但仍然不是公式化的方法是只查看可能的y值,而不是迭代到MAX_y。例如。:

    static Size FindMinSize(double requiredRatio, double epsilon)
    {
        int x = 1;
        do
        {
            int y = (int)(x * requiredRatio);
            if (Test(x, y, requiredRatio, epsilon))
            {
                return new Size(x, y);
            }

            y = (int)((x + 1) * requiredRatio);
            if (Test(x, y, requiredRatio, epsilon))
            {
                return new Size(x, y);
            }
            x++;
        } while (x != int.MaxValue);

        return new Size(0, 0);
    }

    static bool Test(int x, int y, double requiredRatio, double epsilon)
    {
        double aspectRatio = ((double)y)/x;
        return Math.Abs(aspectRatio - requiredRatio) < epsilon;
    }

4

1

Guffa 15 年前

public static Size GetSizeFromAspectRatio(double aspectRatio) {
  double epsilon = 0.001;
  int x = 1;
  int y = 1;
  while (true) {
    double a = (double)x / (double)y;
    if (Math.Abs(aspectRatio - a) < epsilon) break;
    if (a < aspectRatio) {
      x++;
    } else {
      y++;
    }
  }
  return new Size(x, y);
}

5

0

Gilbert Le Blanc 15 年前

纵横比是x和y之间的比值。您可以将纵横比定义为x/y或y/x。

最小纵横比为0/0。

最小x=(最小y*x)/y

最小y=(最小x*y)/x