javascript - 如何找到大图像的有损尺寸

Question

我需要一个函数，它接受两个参数 width 和 height 并返回一个新的宽度和一个新的高度，它们是减少到 100 以下的值。

例子:

1. w: 1920 h:1080 => 返回 w: 16 h: 9
2. w: 1921 h:1080 => 返回 w: 16 h: 9
3. w: 800 h:600 => 返回 w: 4 h: 3
4. w: 100 h:831 => 返回 w: 1 h: 8
5. w: 10 h:2000 => 返回 w: 1 h: 200
6. w: 2047 h:663 => 返回 w: 102 h: 33

对于标准化的屏幕分辨率，GCD 是找到最大公约数的一个很好的算法，但是当我有像 #2 示例这样的非标准值时，它对我来说不是最优的。

有什么算法可以解决我的算法问题吗？ (算法应该是有损的，我知道没有损失是不可能的)。

这是我的 GCD 算法，适用于标准值:

function gcd($a, $b) {
    return ($a % $b) ? gcd($b, $a % $b) : $b;
}

function reduce(w, h) {
    var _gcd = gcd(w, h);
    return [w / _gcd, h / _gcd]
}

console.log(reduce(800, 600));

Answer 1

这是一个基于@KarolyHorvath 和@spektre 的可能解决方案

分数是存储相关维度的对象键。还将分数添加到数组中，然后对该数组进行排序和二进制搜索找到最接近 reduce 方法的分数的值。然后它返回压缩后的维度。

 function binaryIndexOf(searchElement) {
     'use strict';

     var minIndex = 0;
     var maxIndex = this.length - 1;
     var currentIndex;
     var currentElement;
     var resultIndex;

     while (minIndex <= maxIndex) {
         resultIndex = currentIndex = (minIndex + maxIndex) / 2 | 0;
         currentElement = this[currentIndex];

         if (currentElement < searchElement) {
             minIndex = currentIndex + 1;
         } else if (currentElement > searchElement) {
             maxIndex = currentIndex - 1;
         } else {
             return currentIndex;
         }
     }

     return~maxIndex;
 }

 Array.prototype.binaryIndexOf = binaryIndexOf;

 var helper = [],
     data = {};

 for (var i = 1; i < 100; i++) {
     for (var j = 1; j < 100; j++) {
         var d = i / j;
         if (typeof data[d] == 'undefined') {
             data[d] = [i, j];
             helper.push(d);
         }
     }
 }

helper.sort(function (a, b) {
     return a - b
 });

 function reduce(w, h) {
     return data[helper[Math.abs(helper.binaryIndexOf(w / h))]];
 }

 console.log(reduce(1921, 1079));