UPD: la pregunta se ha actualizado con detalles y código, ver más abajo.

Advertencia: esta pregunta se trata de optimizar una disposición de elementos en una matriz. No se trata de comparar colores. Inicialmente, he decidido que proporcionar contexto sobre mi problema ayudaría. Ahora lamento esta decisión porque el resultado fue el contrario: demasiada charla irrelevante sobre colores y casi nada sobre algoritmos reales. 😔

Tengo una caja de 80 rotuladores para mi hijo y me molesta mucho que no estén clasificados.

Solía jugar un juego llamado Blendoku en Android donde necesitas hacer exactamente eso: organizar los colores de tal manera que formen degradados, siendo los colores cercanos los más similares:

Es fácil y divertido organizar los colores en líneas que se cruzan como un crucigrama. Pero con estos marcadores de boceto, tengo una cuadrícula 2D completa. Lo que lo empeora aún más es que los colores no se extraen de un degradado uniforme.

Esto me hace incapaz de clasificar los rotuladores por intuición. ¡Necesito hacerlo algorítmicamente!

Esto es lo que tengo:

• Sólidos conocimientos de JavaScript
• Una matriz plana de valores de color de todos los bolígrafos
• Una función de distance(color1, color2) que muestra qué tan similar es un par de colores. Devuelve un flotante entre 0 y 100 donde 0 significa que los colores son idénticos.

Todo lo que me falta es un algoritmo.

Un factorial de 80 es un número con 118 dígitos, lo que descarta la fuerza bruta.

Puede haber formas de hacer factible la fuerza bruta:

• fijar la posición de algunos bolígrafos (por ejemplo, en las esquinas) para reducir el número de combinaciones posibles;
• soltar ramas que contengan al menos un par de vecinos muy diferentes;
• parada después de encontrar el primer arreglo satisfactorio.

Pero todavía me falta un algoritmo real incluso para eso, sin mencionar uno que no sea de fuerza bruta.

PD tarea:

• Ordenar una matriz por similitud : no hay respuestas.
• Algoritmo para la disposición óptima de la paleta de colores en 2D : pregunta muy similar, sin respuestas.
• ¿Cómo ordenar los colores en dos dimensiones? -- más del 50% de las celdas ya contienen colores correctamente organizados; lenguaje de programación desconocido; la solución de clasificación real no se explica.
• Ordenar color/valores de color: matriz plana única.

Actualizar

Meta

Organice un conjunto predefinido de 80 colores en una cuadrícula de 8 × 10 de tal manera que los colores formen degradados agradables sin rasgarse.

Por las razones que se describen a continuación, no existe una solución definitiva a esta pregunta, las posibles soluciones tienden a resultados imperfectos y subjetivos. Esto se espera.

Tenga en cuenta que ya tengo una función que compara dos colores y dice qué tan similares son.

El espacio de color es 3D

El ojo humano tiene tres tipos de receptores para distinguir los colores. El espacio de color humano es tridimensional (tricromático).

Existen diferentes modelos para describir los colores y todos son tridimensionales: RGB, HSL, HSV, XYZ, LAB, CMY (tenga en cuenta que "K" en CMYK solo se requiere porque la tinta de color no es completamente opaca y costosa).

Por ejemplo, esta paleta:

...utiliza coordenadas polares con matiz en el ángulo y saturación en el radio. Sin la tercera dimensión (luminosidad), a esta paleta le faltan todos los colores claros y oscuros: blanco, negro, todos los grises (excepto el 50% de gris en el centro) y grises tintados.

Esta paleta es solo una pequeña porción del espacio de color HSL/HSV:

Es imposible colocar todos los colores en una cuadrícula 2D en un degradado sin rasgar el degradado .

Por ejemplo, aquí están todos los colores RGB de 32 bits, enumerados en orden lexicográfico en una cuadrícula 2D. Puedes ver que el degradado tiene mucho desgarro:

Por lo tanto, mi objetivo es encontrar un arreglo arbitrario "suficientemente bueno" donde los vecinos sean más o menos similares. Prefiero sacrificar un poco de similitud que tener algunos grupos muy similares con desgarros entre ellos.

¡Esta pregunta se trata de optimizar la cuadrícula en JavaScript, no de comparar colores!

Ya elegí una función para determinar la similitud de los colores: Delta E 2000 . Esta función está específicamente diseñada para reflejar la percepción humana subjetiva de la similitud del color. Aquí hay un documento técnico que describe cómo funciona.

Esta pregunta se trata de optimizar la disposición de los elementos en una cuadrícula 2D de tal manera que la similitud de cada par de elementos adyacentes (vertical y horizontal) sea mínima.

La palabra "optimizar" no se usa en el sentido de hacer que un algoritmo se ejecute más rápido. Es en un sentido de optimización matemática :

En el caso más simple, un problema de optimización consiste en maximizar o minimizar una función real eligiendo sistemáticamente valores de entrada dentro de un conjunto permitido y calculando el valor de la función.

En mi caso:

• "La función" aquí significa ejecutar la DeltaE.getDeltaE00(color1, color2) para todos los elementos adyacentes, el resultado es un montón de números (142 de ellos... creo) que reflejan cuán diferentes son todos los pares adyacentes.
• "Maximizar o minimizar": el objetivo es minimizar la salida de "la función".
• "Un valor de entrada": es una disposición específica de 80 elementos predefinidos en la cuadrícula de 8×10. ¡Hay un total de 80! valores de entrada, lo que hace que la tarea sea imposible de realizar por fuerza bruta en una computadora doméstica.

Tenga en cuenta que no tengo una definición clara para los criterios de minimización de "la función". Si simplemente usamos la suma más pequeña de todos los números, entonces el resultado ganador podría ser un caso en el que la suma sea la más baja, pero algunos pares de elementos adyacentes sean muy diferentes.

Por lo tanto, "la función" tal vez debería tener en cuenta no solo la suma de todas las comparaciones, sino también garantizar que ninguna comparación esté fuera de lugar.

Posibles caminos para resolver el problema.

De mi anterior intento de recompensa en esta pregunta, he aprendido los siguientes caminos:

• algoritmo genético
• biblioteca de optimizador/solucionador
• clasificación manual con algo de ayuda algorítmica
• ¿algo más?

La solución de la biblioteca del optimizador/solucionador es lo que inicialmente esperaba. Pero las bibliotecas maduras como CPLEX y Gurobi no están en JS. Hay algunas bibliotecas JS, pero no están bien documentadas y no tienen tutoriales para principiantes.

El enfoque del algoritmo genético es muy emocionante. Pero requiere concebir algoritmos de especímenes mutantes y de apareamiento (arreglos de cuadrícula). Mutar parece trivial: simplemente intercambie elementos adyacentes. Pero no tengo ni idea sobre el apareamiento. Y tengo poca comprensión de todo el asunto en general.

Las sugerencias de clasificación manual parecen prometedoras a primera vista, pero se quedan cortas cuando se analizan en profundidad. También asumen el uso de algoritmos para resolver ciertos pasos sin proporcionar algoritmos reales.

Código repetitivo y muestras de color

He preparado un modelo de código en JS: https://codepen.io/lolmaus/pen/oNxGmqz?editors=0010

Nota: el código tarda un poco en ejecutarse. Para facilitar el trabajo con él, haga lo siguiente:

• Inicie sesión/regístrese en CodePen para poder bifurcar el repetitivo.
• Bifurcar el repetitivo.
• Vaya a Configuración/Comportamiento y asegúrese de que la actualización automática esté deshabilitada.
• Cambie el tamaño de los paneles para maximizar el panel JS y minimizar otros paneles.
• Vaya a Cambiar vista/Modo de depuración para abrir el resultado en una pestaña separada. Esto habilita console.log() . Además, si la ejecución del código se congela, puede eliminar la pestaña de procesamiento sin perder el acceso a la pestaña de codificación.
• Después de realizar cambios en el código, presione guardar en la pestaña de código, luego actualice la pestaña de procesamiento y espere.
• Para incluir bibliotecas JS, vaya a Configuración/JS. Uso este CDN para vincular el código de GitHub: https://www.jsdelivr.com/?docs=gh

Datos fuente:

 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"}, // ... ];

El índice es una numeración de colores basada en uno, en el orden en que aparecen en el cuadro, cuando se ordenan por id. No se usa en el código.

Id es el número del color del fabricante de la pluma. Dado que algunos números tienen la forma de WG3 , los identificadores son cadenas.

Clase de color.

Esta clase proporciona algunas abstracciones para trabajar con colores individuales. Facilita la comparación de un color dado con otro color.

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

Colección: una clase para almacenar todos los colores y ordenarlos.

 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}\n${color.rgbStr}" > <span class="color-name"> ${color.id} </span> </div> `; }) .join("\n\n"); document.querySelector('#box').innerHTML = html; document.querySelector('#title').innerHTML = propertyName; } }

Uso:

 const collection = new Collection(data); console.log(collection); collection.render("colorsLinear"); // Implement your own getter on Collection and use its name here

Salida de muestra: