整理毛毡笔尖：使用JS根据相邻物品的相似性优化2D网格中物品的排列[更新版] [英] Organizing felt tip pens: optimizing the arrangement of items in a 2D grid by similarity of adjacent items, using JS [updated]

查看：115 发布时间：2022/5/17 14:05:45 javascript arrays algorithm matrix mathematical-optimization

本文介绍了整理毛毡笔尖：使用JS根据相邻物品的相似性优化2D网格中物品的排列[更新版]的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

更新：问题已更新，具体内容和代码如下。

警告：此问题与优化矩阵中项目的排列有关。这不是比较颜色的问题。最初，我决定提供有关我的问题的背景信息会有所帮助。我现在后悔这个决定，因为结果适得其反：太多无关的颜色讨论，而几乎没有关于实际算法的讨论。😔

我给我的孩子买了一盒80支毛毡钢笔，它们没有被分类，这让我很恼火。

我曾经在Android上玩过一款名为Blendoku的游戏，你需要做的就是这样做：排列颜色，使它们形成渐变，附近的颜色最相似：

像纵横字谜一样，在相交的线条中组织颜色很容易，也很有趣。但有了这些素描记号笔，我就得到了一个完整的2D网格。更糟糕的是，颜色不是从统一的渐变中提取的。

这使我无法根据直觉对毛毡笔尖进行分类。我需要通过算法来完成它！

这是我得到的信息：

扎实的JavaScript知识
所有笔的颜色值的平面数组
Afunctiondistance(color1, color2)这显示了颜色对的相似性。它返回一个介于0和100之间的浮点数，其中0表示颜色相同。

我所缺少的只是一个算法。

80的阶乘是一个118位的数字，这排除了暴力强制。

可能有办法使暴力逼迫变得可行：

固定几支笔的位置(例如，在角落中)，以减少可能的组合数量；
删除包含至少一对非常不同的邻居的分支；
找到第一个令人满意的安排后停止。

但我仍然缺乏一个实际的算法，更不用说非蛮力算法了。

PS作业：

Sorting a matrix by similarity--无应答。
Algorithm for optimal 2D color palette arrangement--非常相似的问题，没有答案。
How to sort colors in two dimensions?--超过50%的单元格已包含正确组织的颜色；不熟悉编程语言；未解释实际的排序解决方案。
Sort Colour / Color Values--单平面阵列。

更新

目标

在8x10网格中排列一组预定义的80种颜色，使颜色形成漂亮的渐变而不会撕裂。

由于下面所述的原因，这个问题没有确定的解决方案，可能的解决方案容易产生不完美的结果和主观性。这是意料之中的。

请注意，我已经有一个函数可以比较两种颜色并指出它们有多相似。

色彩空间为3D

人眼有三种类型的感受器来区分颜色。人类的色彩空间是三维的(三原色)。

描述颜色有不同的模型，它们都是三维的：RGB、HSL、HSV、XYZ、LAB、CMY(请注意，只有因为彩色油墨不是完全不透明和昂贵的，才需要使用CMYK中的&q；K&q；)。

例如，此调色板：

使用极坐标，在角度上使用色调，在半径上使用饱和度。没有了第三维度(亮度)，这个调色板缺少了所有亮和暗的颜色：白色、黑色、所有的灰色(除了中间50%的灰色)和有色的灰色。

此调色板只是HSL/HSV色彩空间的一小部分：

在不撕裂渐变的情况下，无法在2D网格上以渐变显示所有颜色。

例如，以下是lexicographic order中列举到2D网格中的所有32位RGB颜色。您可以看到渐变有很多撕裂：

因此，我的目标是找到一种任意的、足够好的安排，其中邻居或多或少相似。我宁愿牺牲一点相似之处，也不愿有几个非常相似的星团在它们之间撕裂。

此问题是关于在JavaScript中优化网格，而不是关于比较颜色！

我已经选择了一个函数来确定颜色的相似性：Delta E 2000。该函数是专门为反映人类对颜色相似性的主观感知而设计的。这里有一个whitepaper描述它是如何工作的。

此问题是关于优化2D网格中项目的排列，以使每对相邻项目(垂直和水平)的相似度尽可能低。

优化一词的用法并不是让算法运行得更快。在某种意义上Mathematical optimization：

在最简单的情况下，optimization problem包括通过系统地从允许的集合中选择输入值并计算函数的值来最大化或最小化实数函数。

在我的案例中：

&这里的函数"；表示对所有相邻项目运行DeltaE.getDeltaE00(color1, color2)函数，输出是一串数字(其中142个...我认为)反映出所有相邻的配对是多么的不同。
最大化或最小化"；-目标是最小化函数"；的输出。
&q；-是8x10网格中80个预定义项目的特定排列。总共有80!个输入值，这使得该任务无法在家庭计算机上强制执行。

请注意，我没有明确定义函数"；的最小化标准。如果我们简单地使用所有数字中最小的和，那么获胜的结果可能是和最小的情况，但几个相邻的项目对非常不相似。

因此，"；函数可能不仅应该考虑所有比较的总和，还应该确保没有任何比较是错误的。

解决该问题的可能途径

从我之前对这个问题的赏金尝试中，我了解到了以下几条途径：

遗传算法
优化器/求解器库
在一些算法帮助下进行手动排序
其他事情？

优化器/解算器库解决方案正是我最初所希望的。但成熟的库如CPLEX和Gurobi不在JS中。有一些JS库，但它们没有很好的文档记录，也没有新手教程。

遗传算法的方法非常令人兴奋。但它需要突变和交配样本(网格排列)的处理算法。变异似乎微不足道：只需交换相邻的物品即可。但我对交配一无所知。总的来说，我对整件事知之甚少。

手动排序建议乍一看似乎很有前途，但当深入研究它们时，它们就会显得力不从心。他们还假设使用算法来解决某些步骤，而不提供实际的算法。

代码样板和颜色样本

我已经在JS中准备了一个代码样板：https://codepen.io/lolmaus/pen/oNxGmqz?editors=0010

注意：代码需要一段时间才能运行。要更轻松地使用它，请执行以下操作：

登录/注册CodePen以便能够派生样板。
分叉样板。
转到"设置/行为"，并确保已禁用自动更新。
调整窗格大小以最大化JS窗格并最小化其他窗格。
转到更改视图/调试模式以在单独的选项卡中打开结果。这将启用console.log()。此外，如果代码执行冻结，您可以终止"呈现"选项卡，而不会失去对"编码"选项卡的访问。
更改代码后，点击"代码"选项卡中的"保存"，然后刷新"呈现"选项卡并等待。
要包含JS库，请转到设置/JS。我使用此CDN链接到GitHub的代码：https://www.jsdelivr.com/?docs=gh

源数据：

const data = [
  {index: 1, id: "1", name: "Wine Red", rgb: "#A35A6E"},
  {index: 2, id: "3", name: "Rose Red", rgb: "#F3595F"},
  {index: 3, id: "4", name: "Vivid Red", rgb: "#F4565F"},
  // ...
];

索引是按ID排序时颜色在框中的显示顺序，从一开始的编号。它未在代码中使用。

ID是钢笔制造商的颜色编号。由于某些数字的形式为WG3，因此ID是字符串。

颜色类。

这个类提供了一些抽象概念来处理各种颜色。它使您可以轻松地将给定颜色与另一种颜色进行比较。

  index;
  id;
  name;
  rgbStr;
  collection;
  
  constructor({index, id, name, rgb}, collection) {
    this.index = index;
    this.id = id;
    this.name = name;
    this.rgbStr = rgb;
    this.collection = collection;
  }
  
  // Representation of RGB color stirng in a format consumable by the `rgb2lab` function
  @memoized
  get rgbArr() {
    return [
      parseInt(this.rgbStr.slice(1,3), 16),
      parseInt(this.rgbStr.slice(3,5), 16),
      parseInt(this.rgbStr.slice(5,7), 16)
    ];
  }
  
  // LAB value of the color in a format consumable by the DeltaE function
  @memoized
  get labObj() {
    const [L, A, B] = rgb2lab(this.rgbArr);
    return {L, A, B};
  }

  // object where distances from current color to all other colors are calculated
  // {id: {distance, color}}
  @memoized
  get distancesObj() {
    return this.collection.colors.reduce((result, color) => {
      if (color !== this) {      
        result[color.id] = {
          distance: this.compare(color),
          color,
        };
      }
      
      return result;
    }, {});
  }
    
  // array of distances from current color to all other colors
  // [{distance, color}]
  @memoized
  get distancesArr() {
    return Object.values(this.distancesObj);
  }
  
  // Number reprtesenting sum of distances from this color to all other colors
  @memoized
  get totalDistance() {
    return this.distancesArr.reduce((result, {distance}) => {      
      return result + distance;
    }, 0); 
  }

  // Accepts another color instance. Returns a number indicating distance between two numbers.
  // Lower number means more similarity.
  compare(color) {
    return DeltaE.getDeltaE00(this.labObj, color.labObj);
  }
}

Collection：用于存储所有颜色并对其进行排序的类。

class Collection {
  // Source data goes here. Do not mutate after setting in the constructor!
  data;
  
  constructor(data) {
    this.data = data;
  }
  
  // Instantiates all colors
  @memoized
  get colors() {
    const colors = [];

    data.forEach((datum) => {
      const color = new Color(datum, this);
      colors.push(color);
    });
  
    return colors;    
  }

  // Copy of the colors array, sorted by total distance
  @memoized
  get colorsSortedByTotalDistance() {
    return this.colors.slice().sort((a, b) => a.totalDistance - b.totalDistance);
  }

  // Copy of the colors array, arranged by similarity of adjacent items
  @memoized
  get colorsLinear() {
    // Create copy of colors array to manipualte with
    const colors = this.colors.slice();
    
    // Pick starting color
    const startingColor = colors.find((color) => color.id === "138");
    
    // Remove starting color
    const startingColorIndex = colors.indexOf(startingColor);
    colors.splice(startingColorIndex, 1);
    
    // Start populating ordered array
    const result = [startingColor];
    
    let i = 0;
    
    while (colors.length) {
      
      if (i >= 81) throw new Error('Too many iterations');

      const color = result[result.length - 1];
      colors.sort((a, b) => a.distancesObj[color.id].distance - b.distancesObj[color.id].distance);
      
      const nextColor = colors.shift();
      result.push(nextColor);
    }
    
    return result;
  }

  // Accepts name of a property containing a flat array of colors.
  // Renders those colors into HTML. CSS makes color wrap into 8 rows, with 10 colors in every row.
  render(propertyName) {
    const html =
      this[propertyName]
        .map((color) => {
          return `
          <div
            class="color"
            style="--color: ${color.rgbStr};"
            title="${color.name}
${color.rgbStr}"
          >
            <span class="color-name">
              ${color.id}
            </span>
          </div>
          `;
        })
        .join("

");
    
    document.querySelector('#box').innerHTML = html;
    document.querySelector('#title').innerHTML = propertyName;
  }
}

用法：

const collection = new Collection(data);

console.log(collection);

collection.render("colorsLinear"); // Implement your own getter on Collection and use its name here

示例输出：

整理毛毡笔尖：使用JS根据相邻物品的相似性优化2D网格中物品的排列[更新版] [英] Organizing felt tip pens: optimizing the arrangement of items in a 2D grid by similarity of adjacent items, using JS [updated]

问题描述

更新

目标

色彩空间为3D

此问题是关于在JavaScript中优化网格，而不是关于比较颜色！

解决该问题的可能途径

代码样板和颜色样本

推荐答案

相关文章

前端开发最新文章

热门教程

热门工具

登录关闭

整理毛毡笔尖：使用JS根据相邻物品的相似性优化2D网格中物品的排列[更新版] [英] Organizing felt tip pens: optimizing the arrangement of items in a 2D grid by similarity of adjacent items, using JS [updated]

问题描述

更新

目标

色彩空间为3D

此问题是关于在JavaScript中优化网格，而不是关于比较颜色！

解决该问题的可能途径

代码样板和颜色样本

推荐答案

相关文章

前端开发最新文章

热门教程

热门工具

登录 关闭

登录关闭