종횡비와 일치하는 최소 크기

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

비정상적인를. 가장 큰 공약수를 찾아 폭과 높이로 나누어야합니다. 알고리즘은 유클리드 (Euclid)를 기반으로하며 2 천 3 백년 된 것입니다. 세부 사항 are here.

Answer 2

화면 비율은 x와 y 사이의 비율이다. 종횡비를 x ​​/ y 또는 y/x로 정의 할 수 있습니다.

최소 종횡비 0/0

몇몇 다른 최소 정의 할 수 있으며, 최소의 X 또는 Y 중 최소이다.

분 X = (최소의 Y *의 X)/Y

분 Y = (분 X의 * y를)/X

Answer 3

당신은 당신이 그것을 원하는 경우에 (A 부분로 aspectRatio을 쓸 수 있습니다 (aspectRatio, 3)/1000)

다음에 simplify this fraction을 사용할 수있는 것보다 0.001의 프리젠 테이션. 결과 분수는 찾고있는 x/y입니다.

Answer 4

더 빠른 방법이지만 여전히 공식은 MAX_Y까지 반복하는 대신 가능한 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

대신 가능한 모든 조합을 테스트, 단지 가까이 가로 세로 비율을 얻는 측의 증가 :

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