Минимальный размер, соответствующий соотношению сторон

Question

Мне нужно найти размер минимум , который имеет соотношение сторон точно (или в пределах 0,001) некоторого значения. Для этого есть какие-нибудь быстрые математические трюки или трюки с фреймворком?

Вот псевдокод для текущей плохой идеи, которую я использовал в 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;

Answer 1

Необычный.Вам нужно найти наибольший общий делитель и разделить на него ширину и высоту.Алгоритм Евклида и ему две тысячи триста лет.Подробности здесь .

Answer 2

Вместо тестирования всех возможных комбинаций, просто увеличьте сторону, которая приближает вас к соотношению сторон:

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

Answer 3

Вы можете записать aspectRatio в виде дроби (если вы хотите, чтобы это было до 0,001, чем вы можете использовать round (aspectRatio, 3) / 1000)

Тогда упростит эту дробь . Полученная дробь - это искомый х / у.

Answer 4

Более быстрый способ, но все же не формальный, состоит в том, чтобы смотреть только на возможные значения 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;
    }

Answer 5

Соотношение сторон - это соотношение между x и y. Вы можете определить соотношение сторон как x / y или y / x.

Минимальное соотношение сторон 0 / 0.

Необходимо определить какой-то другой минимум, либо минимальный x, либо минимальный y.

мин х = (мин у * х) / у

min y = (min x * y) / x