그리드 포장 알고리즘

Question

크기 w X h의 사각형을 감안할 때, 그리고 요구 사항은 더 큰 사각형, 최적의 원래의 사각형을 채워 그 작은 사각형의 크기 dx 및 dy을 선택하는 것이 내 n 동일한 크기의 사각형을 에 맞게.

모든 제약 번호는 이어야하며,이어야합니다.

function pack(n, w, h) { 

    var nx, ny; 
    var dx = w, dy = h; // initally try one rectangle that fills the box 

    while (true) { 
     nx = ~~(w/dx); // see how many times this fits in X 
     ny = ~~(h/dy); // and in Y 

     if (nx * ny >= n) break; // they all fit! 

     if (dx * h >= w * dy) { // look at the aspect ratio 
      dx = ~~(w/(nx + 1)); // try fitting more horizontally 
     } else { 
      dy = ~~(h/(ny + 1)); // or try more vertically 
     } 

     if (dx < 1 || dy < 1) { 
      return;    // they can't fit 
     } 
    }; 

    return [nx, ny, dx, dy]; 
}; 

더 나은 알고리즘이 있나요 :

나의 현재 (JS) 알고리즘이 무엇입니까?

[주의 사항 : 숙제가 아닙니다. 캔버스의 행렬에 "n"개 항목을 그리는 방법에 대한 문제를 해결하려고하지만 각 항목은 전체 픽셀 만 사용해야합니다.]

Answer 1

function pick(tiles, grid_width, grid_height) 
{ 
    var max_area = ~~(grid_width * grid_height/tiles); 

    for (var area = max_area; area > 0; area--) 
    { 
     var result = [grid_width * grid_height - area * tiles]; 

     divisors_do(area, 
      function (tile_width) 
      { 

       var tile_height = area/tile_width; 
       if (tile_width > grid_width) return true; 
       if (tile_height > grid_height) return true; 

       var count_horizontal = ~~(grid_width/tile_width); 
       var count_vertical = ~~(grid_height/tile_height); 
       if (count_horizontal * count_vertical < tiles) return true; 

       result.push([ 
        tile_width, tile_height, 
        count_horizontal, count_vertical 
       ]); 
      }); 
     if (result.length > 1) return result; 
    } 
    return null; 
} 

function divisors_do(x, f) 
{ 
    var history = [1]; 
    if (f(1) === false) return false; 

    // for each prime factor 
    return prime_factors_do(x, 
     function(prime, primePower) 
     { 
      var len = history.length; 

      for (var iHistory = 0; iHistory < len; iHistory++) 
      { 
       var divisor = history[iHistory]; 

       for (var power = 1; power <= primePower; power++) 
       { 
        divisor *= prime; 
        history.push(divisor); 

        if (f(divisor) === false) return false; 
       } 
      } 

      return true; 
     }); 
} 

function prime_factors_do(x, f) 
{ 
    for (var test = 2; test*test <= x; test++) 
    { 
     var power = 0; 
     while ((x % test) == 0) 
     { 
      power++; 
      x /= test; 
     } 

     // If we found a prime factor, report it, and 
     // abort if `f` returns false. 
     if (power > 0 && f(test, power) === false) 
      return false; 
    } 

    if (x > 1) return f(x,1); 
    return true; 
} 

예 :

> pack(5, 12, 8); 
[16, [2, 8, 6, 1], [4, 4, 3, 2]] 
> pack(47,1024,768); 
[16384, [64, 256, 16, 3], [128, 128, 8, 6], [256, 64, 4, 12], [512, 32, 2, 24]] 

첫번째 예는 두 개의 동등한 결과를 생성 3 두 행에 충전 6 개

의 4x4 타일의 한 행에 충전

• 2X8 타일

각각 하나의 슬롯이 사용되지 않은 상태로 남겨지며 총 16 개의 셀이 사용되지 않습니다.

### ### ### ### ### . . ####### ####### ####### 
### ### ### ### ###  ####### ####### ####### 
### ### ### ### ### . . ####### ####### ####### 
### ### ### ### ###  ####### ####### ####### 
### ### ### ### ### . . ####### ####### ####### 
### ### ### ### ###  ####### ####### ####### 
### ### ### ### ### . . ####### ####### ####### 
### ### ### ### ### 
### ### ### ### ### . . ####### ####### . . . 
### ### ### ### ###  ####### ####### 
### ### ### ### ### . . ####### ####### . . . 
### ### ### ### ###  ####### ####### 
### ### ### ### ### . . ####### ####### . . . 
### ### ### ### ###  ####### ####### 
### ### ### ### ### . . ####### ####### . . . 

Answer 2

그것은 당신이 기본적으로 당신이 Euclidean algorithm를 사용하여 효율적으로 할 수있는 GCD을 계산하려는 것 같습니다. 나는 다음 작품들이 - 그것을 시도해보십시오!

먼저 gwn = GCD (w, n) 및 ghn = GCD (h, n)을 계산합니다. 이들 중 하나가 n이면 완료됩니다. gwn = n이면 각 사각형이 h 픽셀만큼 w/n 일 수 있음을 의미합니다. 그렇지 않으면 h가 n/gwn으로 나눌 수 있거나 w가 n/ghn으로 나눌 수있는 경우에만 직사각형을 맞출 수 있습니다.