javascript - 查找三个不同数字的倍数的连续最小和，javascript

Question

关于this post我找到了一种确定 RGB 颜色亮度的算法:

Luminance (standard for certain colour spaces): (0.2126*R + 0.7152*G + 0.0722*B)

我想使用这个等式，从 rgb(0,0,0) 开始，按亮度从最低到最高的顺序生成所有 RGB 颜色，然后将它们绘制到 4096x4096 Canvas 上。

我的问题是，对于 1670 万种不同的组合，我无法生成所有这些组合，然后对它们进行排序，而不会导致浏览器崩溃或需要几天时间才能完成渲染。所以我想找到一种方法来找到每个数字的倍数，这些倍数将与下一个最小数字相加。

例如，从 0,0,0 的 rgb 开始，亮度将为 0 (0.2126*0 + 0.7152*0 + 0.0722*0 = 0 )，下一个最不发光的 rgb 值将是 0,0,1，因为 0.2126*0 + 0.7152*0 + 0.0722*1 = .0722，并且没有一组的倍数相加后会得到一个较小的数字。

前 19 个连续亮度值如下(我可能错过了一两个，因为我手动计算了它们，但希望它有助于说明问题):

RGB       =>     Luminence

0,0,0     =>     0
0,0,1     =>     .0722
0,0,2     =>     .1444
1,0,0     =>     .2126
0,0,3     =>     .2166
1,0,1     =>     .2848
0,0,4     =>     .2888
1,0,2     =>     .357
0,0,5     =>     .361
2,0,0     =>     .4252
1,0,3     =>     .4292
0,0,6     =>     .4332
2,0,1     =>     .4974
1,0,4     =>     .5014
0,0,7     =>     .5054
2,0,2     =>     .5696
1,0,5     =>     .5736
0,0,8     =>     .5776
3,0,0     =>     .6378

我似乎找不到任何模式，所以我希望也许有一个方程式或编码技巧可以让我找到三个数字的倍数的最小总和，大于先前的总和，无需暴力破解并检查每个可能的值。

编辑:我做了一些额外的研究，看起来解决方案可能在于使用线性丢番图方程。如果我将每个小数乘以 1000，则得到 2126、7152 和 722。然后逐一数到 2,550,000 (2126*255 + 7152*255 + 722*255)，我可以检查每个数字，看看它是否是方程 2126r + 7152g + 722b = n，其中 n 是当前计数的数字，r、g 和 b 是未知数。如果我能做到这一点，我就可以计算出下一个连续亮度值处的所有可能的 rgb 值，甚至不必将重复亮度值的任何值加倍，而且我只需要进行 255 万次计算，而不是 1677+ 万次(每种颜色一个)。如果有人知道如何编写这个方程，或者有人有更好的解决方案，我将非常感激。谢谢!

Answer 1

这是解决您的问题的算法(忘记了它的名字): 该算法可以列出按某种顺序排序的所有颜色元组 {R,G,B}。在您的情况下，它是按亮度升序: color1 < color2 <==> f(color1) < f(color2)，其中 f(color) = 0.2126*R + 0.7152*G + 0.0722*B

• 初始化:arr = [{r:0, g:0, b:0}](最小颜色)
• 重复:
  • 对于每个 i，选择 min(iR):a[iR] = {rR < 255, gR, bR}，且 cR = {rR + 1, gR, bR} > arr[i]。 (选择 arr 中的第一个颜色，如果我们将其 r 分量加 1，我们会得到一个比 arr 中当前所有颜色都大的新颜色)
  • 与 iG 和 iB 类似 => 也可得到 cG = {rG, gG + 1, bG} 和 cB = {rB, gB, bB + 1}
  • 在cR、cG和cB中选择最小颜色c
  • 将 c 附加到数组 arr

当找不到这样的 iR、iG 或 iB 时，算法停止。

注释:

• arr 始终按升序排列，因为每次将新颜色附加到 arr 时，它总是大于 中当前的每个元素到达。
• 因为arr是升序排列的，所以我们只需将cR/cG/cB与arr的最后一个元素进行比较，以检查它是否大于<的每个元素强>arr
• iR、iG 和 iB 在整个算法中不断增加
• 复杂度为 O(N)，颜色数量为 N (2^24) ~ 16M。使用基于堆的算法，复杂度约为 O(NlogN)。

这是我的实现(在nodejs 6中测试)

//  use integer to avoid floating point inaccuracy
const lumixOf = {r: 2126, g: 7152, b: 722};

const maxValue = 256;
const components = ['r', 'g', 'b'];

class Color {
  constructor(r, g, b, lum) { 
    this.r = r;
    this.g = g;
    this.b = b;
    this.lum = lum;
  }

  add(component) { 
    const ans = new Color(this.r, this.g, this.b, this.lum);
    if (++ans[component] >= maxValue) return null; // exceed 255
    ans.lum += lumixOf[component];
    return ans;
  }

  greater(color2) {
    // return this.lum > color2.lum;
    if (this.lum !== color2.lum) return this.lum > color2.lum;
    if (this.r !== color2.r) return this.r > color2.r;
    if (this.g !== color2.g) return this.g > color2.g;
    return this.b > color2.b;        
  }
}

let a = [new Color(0, 0, 0, 0)];  //  R, G, B, lumix
let index = {r: 0, g: 0, b: 0};

console.log('#0:', a[0]);
// Test: print the first 100 colors
for (let count = 1; count < 100; ++count) {
  let nextColor = null;
  const len = a.length;
  const currentColor = a[len - 1];
  components.forEach(component => {
    let cIndex = index[component];
    for (; cIndex < len; ++cIndex) {
      const newColor = a[cIndex].add(component);
      if (!newColor || !newColor.greater(currentColor)) continue;

      //  find the minimum next color
      if (nextColor == null || nextColor.greater(newColor)) {
        nextColor = newColor;
      }
      break;
    }
    index[component] = cIndex;
  });

  if (!nextColor) break;  //  done. No more color
  a.push(nextColor);
  console.log('#' + count + ':', nextColor);
}
console.log(a.length);

此实现列出了所有 2^24 = 16777216 种颜色(一旦您删除主循环中的 count < 100 条件，但您不想打印出这么多行)。如果某些颜色具有相同的亮度值，则按 R 值、G 值、B 值对它们进行排序。如果每个亮度值只需要一种颜色，请取消注释 greater() 中的第一行函数 - 那么你会得到 1207615 种具有不同亮度的颜色