36

Con una lista/array de colores en formato hexadecimal como ésta:

[ "#fff000", "#238923", "#aaaaa0", "#ff2300", "#2ff014", "#010203" ]

La idea es ordenarla/organizarla para que queden los rojos primeros, los verdes después, y los azules al final. Pero con eso no es suficiente porque hay tonos y tonos de colores, la idea sería que estuvieran organizados de forma "cromática":

  1. Rojos azulados (rojo es el principal color, luego azul)
  2. Rojos (rojo es el principal color, azul y verde tienen el mismo valor)
  3. Rojos verdosos (rojo es el principal color, luego verde)
  4. Verdes rojizos
  5. Verdes
  6. Verdes azulados
  7. Azules verdosos
  8. Azules
  9. Azules rojizos

Como se puede ver, sería como un "círculo de color" donde los extremos se tocan: pongo el azul antes que el verde para el rojo, y el verde antes que el rojo para el azul. Entonces, por ejemplo: #331122 (rojo azulado) iría antes que #330000 (rojo-rojo) que iría antes que #331100 (rojo verdoso). El esquema de ordenación sería algo como esto:

   R        G        B
-------- -------- --------
RB RR RG GR GG GB BG BB BR

Entonces la lista anterior quedaría así:

[ "#ff2300", "#fff000", "#aaaaa0", "#2ff014", "#238923", "#010203" ]

No puedo utilizar un método de ordenación existente en el lenguaje de programación porque realmente no es una ordenación al uso y no va a ir de forma alfabética. Por eso hay que tener en cuenta los valores para los tres colores de forma independiente. Tendría que hacer algo propio.

Entonces busco una respuesta que:

  • Proponga una solución teórica para un gran número de colores.
  • Funcione también con un número limitado de colores (25-50 que se podrían usar para ordenar una tabla paginada).
  • Sea eficiente (orden algorítmico): ¿debería plantear hashing/buckets?
5
  • ¿ En JavaScript ?
    – Trauma
    Commented el 9 ene. 2019 a las 17:02
  • 2
    JavaScript valdría (y sería conveniente porque se podría poner un ejemplo en la respuesta), pero también valdría una solución en pseudo-código o una explicación teórica.
    – Alvaro Montoro
    Commented el 9 ene. 2019 a las 17:03
  • Otra cosita ... ¿ tiene obligatoriamente que ordenar el array que le pasas ? ¿ O puede generar una copia ? En ambos casos, es O( n ), pero el segundo caso, ordenar el propio array, será bastante mas lento.
    – Trauma
    Commented el 9 ene. 2019 a las 17:16
  • No, nada. No he dicho nada. Ordenar el propio array :-)
    – Trauma
    Commented el 9 ene. 2019 a las 17:17
  • No acabo de entender eso. Es muy tecnico para mi gusto hay alguna manera mas facil de hacer? Si les paso el codigo de los colores, podrian hacer-lo por mi?
    – james
    Commented el 10 ago. 2020 a las 1:26

2 respuestas 2

34

Nota el código que presento en esta respuesta no pretende ser una solución, sino sólo servir para explorar algunas ideas.

Idea inicial

Lo primero que se me ocurrió fue convertir cada color RGB a la representación HSV (Hue, Saturation, Value). En esta representación, el componente "Hue" te dice qué color es (ese valor es un número real entre 0 y 360 que representa un ángulo, que es la orientación de un vector imaginario en el espacio de colores). El componente "S" es la "Saturación" que te dice cuánto blanco tiene añadido ese color. Es un entero entre 0 y 1, siendo 0 saturación mínima (blanco) y 1 la máxima (nada de blanco, color puro). Finalmente la V es el "valor" de luminosidad que viene a decir cuánto negro se mezcla con el color (0 es todo negro, 1 es nada de negro, color "puro").

Pensé que transformando cada color de esta forma y ordenando simplemente los trios resultantes, ya quedarían agrupados por "similitud cromática", ya que estaríamos ordenando primero por Hue (color) y en el caso del mismo color, por saturación y luego por brillo.

Por desgracia los resultados no son lo que esperaba. El siguiente código python sirve para generar un montón de valores hexadecimales RGB al azar:

import random

def color_aleatorio():
  r, g, b = random.randint(0,255), random.randint(0,255), random.randint(0,255)
  return "#{:02x}{:02x}{:02x}".format(r,g,b)

mil_colores = [color_aleatorio() for _ in range(1000)]

Algunos elementos de la lista resultante:

['#6264c0',
 '#b37f4d',
 '#116dcc',
 '#a8ce4b',
 '#7ea6f8',
 '#a94f89',
 '#83be23',
 '#6c8052',
 '#d87e04',
 '#d107f2'
 ...]

La representación gráfica de esta "paleta" de colores, en el mismo orden aleatorio en que fueron generados sería la siguiente:

Colores

Esta representación la obtuve con este código, por si alguien quiere replicarlo:

import matplotlib.pyplot as plt
import numpy as np
import matplotlib.colors

def mostrar_colores(colores):
  data = matplotlib.colors.to_rgba_array(colores)
  plt.imshow(np.array(data).reshape((20,50,4)))
  plt.grid(False)

mostrar_colores(mil_colores)

La siguiente función implementa la conversión de uno de esos valores a la forma HSV:

import matplotlib

def rgb2hsv(hex_rgb):
    r, g, b, a = matplotlib.colors.to_rgba(hex_rgb)
    r, g, b = r/255.0, g/255.0, b/255.0
    mx = max(r, g, b)
    mn = min(r, g, b)
    df = mx-mn
    if mx == mn:
        h = 0
    elif mx == r:
        h = (60 * ((g-b)/df) + 360) % 360
    elif mx == g:
        h = (60 * ((b-r)/df) + 120) % 360
    elif mx == b:
        h = (60 * ((r-g)/df) + 240) % 360
    if mx == 0:
        s = 0
    else:
        s = df/mx
    v = mx
    return h, s, v

Ahora podemos pedir a Python que ordene la secuencia mil_colores usando como clave de ordenación la función anterior:

colores_ordenados = sorted(mil_colores, key=rgb2hsv)

Los primeros diez elementos ya ordenados serían estos:

['#d4d4d4',
 '#efc7c7',
 '#df2b2a',
 '#c1201f',
 '#a30907',
 '#f09b99',
 '#9a2623',
 '#efcecd',
 '#753836',
 '#e30b01',
 ...

Que gráficamente da este resultado, un poco decepcionante:

Ordenado

Podemos ver que, sí... más o menos se han agrupado por colorido, pudiendo apreciarse la "franja arcoiris" con el anaranjado arriba, el violeta abajo...pero dentro de cada franja el orden parece un poco aleatorio y se debe a que valores con un HUE muy próximo, pero diferentes valores o saturaciones acaban muy próximos.

Segunda idea

Entonces me di cuenta que lo que queremos es que colores próximos terminen juntos. Lo que nos obliga a definir el concepto de distancia entre colores.

Un color al final no es más que un punto en un espacio de tres coordenadas: R, G, B. Por tanto podemos usar la distancia euclídea entre ellos (raiz de la suma de cuadrados de distancias entre cada coordenada).

Aunque la distancia queda ahora bien definida, lograr una ordenación en la que los colores cercanos acaben juntos, es en el fondo otra forma del problema del viajante. Es decir, hay que encontrar un recorrido de todos los puntos que minimice la distancia viajada. Ese recorrido sería la ordenación de colores buscada.

Ya que ese problema es NP-duro, he renunciado a implementarlo

Actualización. Reflexiones y heurísticos

Tras pensar un rato más, llego a la conclusión de que la ordenación "por distancias" en realidad sólo es una forma más de ordenarlos, y no necesariamente la mejor, puesto que el concepto de "mejor" no está bien definido aquí. En la ordenación por "proximidad" pueden aparecer separados colores que en otra ordenación se consideraría que deberían ir juntos, por ejemplo, un rojo muy oscuro podría aparecer "con los negros" en lugar de "con los rojos". ¿Cuál es mejor?

Creo que el problema en el fondo no se puede resolver porque no está bien definido. El conjunto de colores de entrada en realidad puede entenderse matemáticamente como un conjunto de puntos en un espacio de 3 dimensiones (que serían sus componentes, ya sea RGB o HSV). Al pedir una ordenación, en el fondo queremos pasar eso a una sola dimensión. Por tanto es un problema de proyección.

Es equivalente en cierta forma al problema de cartografiar en un plano la superficie de la esfera terrestre. No hay solución única, y por tanto existen diferentes proyecciones cartográficas, según a qué aspecto demos prioridad. Unas proyecciones son útiles porque hacen más fácil la navegación, al mantener constante los ángúlos. Otras mantienen constante las superficies de los países y son más útiles para hacerse una idea de su tamaño relativo, etc.

Con las ordenaciones de colores pasa algo similar. Si todos los colores fuesen "puros" (en HSV tendrían S=1 y V=1) su ordenación sería sencilla, basándose sólo en su "Hue", y sería así:

Hue

Pero si además tenemos colores "pastel" (en los que la saturación baja y por tanto se acercan al blanco), o colores "oscuros" (en los que el brillo baja y por tanto se acercan al negro), ya no hay dónde colorarlos en la impecable ordenación por hue recién vista.

Esta caja de pinturas muestra cómo ha resuelto el problema el fabricante:

Pinturas

Ha hecho dos cajones. El de arriba para los colores saturados (ordenados por hue) y el de abajo para los tonos pastel (ordenados también por hue). Los colores "oscuros" los ha intercalado según su hue. Por ejemplo un azul oscuro al final de los azules. Eso "rompe" el bonito arcoiris pues tras ese azul oscuro viene un verde-azul más clarito. Además, sólo ha considerado dos niveles de saturación (los dos cajones). Podría haber muchos más...

¿Es esta ordenación mejor o peor que otra? De nuevo depende de lo que se pretenda. El artista posiblemente quiera tener juntas las pinturas con un mismo hue y le importe poco si la "distancia rgb" entre los colores coincide o no con la distancia entre pinturas en su caja.

En definitiva no hay criterio definido para preferir una ordenación sobre otra.

Dicho todo lo cual, presento otro heurístico para ordenar los mil colores aleatorios que se basa en:

  1. Separar los colores muy oscuros y dejarlos para el final
  2. Separar los restantes colores por su saturación, poniendo al principio los más saturados y después los "tonos pastel".
  3. Ordenar cada secuencia por su hue, pero reduciendo el numero de posibles hues, de infinito (pues el hue es un real que varía de forma continua entre 0 y 360) a sólo 15 categorías (un valor arbitrario basado un poco en los hues fácilmente discernibles), y a igualdad de hue, por su brillo.

Este es el algoritmo (python):

def ordenacion(hex_rgb):
  h,s,v = rgb2hsv(hex_rgb)
  return  v<0.002, s<0.7, int(h/360*15), v

colores_ordenados = sorted(mil_colores, key=ordenacion)

Y este el resultado:

Resultado

Si en lugar de mil colores uso diezmil, el resultado es más impresionante, al pasar de esto:

Entrada

a esto:

Salida

Para que se vea que el algoritmo escala también para pocos colores, estos los propuestos por Alvaro:

c = [ "#fff000", "#238923", "#aaaaa0", "#ff2300", "#2ff014", "#010203" ]

Colores alvaro

Y esta es la ordenación que resulta:

['#ff2300', '#fff000', '#2ff014', '#238923', '#aaaaa0', '#010203']

Colores Alvaro ordenados

24

Tu problema es más simple de resolver de lo que parece a simple vista si entiendes un par de cosas primero.

  1. Ordenar colores es una tarea imposible pero tu no estás intentando ordenar todos los colores, solo una pequeña colección.
  2. La parte difícil de ordenar cualquier colección es determinar cual de entre dos elementos tiene mas precedencia que el otro. Precedencia significa que va primero, no necesariamente que su valor sea menor pues en una lista ordenada descendente los mayores valores van primero.

Los algoritmos de ordenamiento para esto son ampliamente conocidos y puedes escoger entre un gran número de ellos con ventajas y desventajas entre ellos. En todos los casos es necesario poder determinar cuando un elemento tiene más precedencia que otro. En esa parte es en la que debes concentrarte.

Para comparar debes saber una cosa primero y es que los colores no se pueden representar usando un "círculo de color" como pretendes pues dependiendo del formato a usar (en tu caso RGB) siempre son una figura geométrica tridimensional. En el caso de RGB se usa un cubo como este:

color cube

By SharkD - Own work. 
Download source code., CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=70991647

Es posible usar un cilindro para representarlo teniendo en cuenta un par de cosas:

Que tan rojo azul o verde es un color depende del empuje del componente o los componentes de color más fuerte hacia su base (el más puro), o sea un vector que parte del eje transversal del cilindro hacia su borde.

Por ejemplo el rojo puro FF0000 es exactamente igual a este otro rojo más oscuro #BE0000. Esto es difícil de digerir a simple vista pero si lo representas con una imagen te darás cuenta que la única diferencia es que uno es más brillante que otro, o sea que el rojo puro se encuentra más arriba en el eje vertical del cilindro de colores.

rojo puro

Rojo puro

rojo oscuro

Rojo oscuro

Si te fijas bien te darás cuenta que esta representación coincide más menos con el modelo HSL donde el color se expresa con grados formando un círculo. En realidad ni HSL ni HSV son cilindros tampoco sino figuras formadas por conos pero el hecho que puedan representarse de forma circular es suficiente para tus propósitos.

cono color

En ambos modelos se puede deducir un par de cosas:

  1. El blanco #FFFFFF, el negro #000000 y los puros grises (igual valor de R, G y B) son el mismo color variando por el brillo pero que no tienen afinidad por ningún componente en particular lo que cambia es su posición en el eje vertical de acuerdo al modelo escogido.

  2. Que existen colores que a simple vista parecen negros pero en realidad son rojos, verdes, etc, pero que son muy oscuros o claros para decirlo de una manera muy sobre-simplificada.

  3. Que no puedes decidir por un sólo parámetro, el color, sino que debes tener en cuenta otros como luminosidad, chroma o valor de acuerdo al modelo escogido. El resultado final será diferente de acuerdo a tus preferencias.

Las prioridad de colores impuesta por tu problema requiere que el violeta puro (#ff00ff) se encuentre el primero en la lista y este se encuentra exactamente a los 300o grados de la circunferencia de color así que lo único que debes hacer para obtener los valores que deseas es rotar 60 grados la circunferencia en sentido contrario a las manecillas del reloj.

Aquí te dejo el algoritmo:

// girar 60 grados el valor de hue
function offsetHgrad(color) {
  const offset = 60;
  const start = 360 - offset;
  const h = color.h >= start ? color.h - start : color.h + offset;

  return {
    h,
    s: color.s,
    l: color.l,
  }
}

// convertir rgb en hsl, algoritmo genérico
function rgbToHsl(color) {
  const rbgReg = /#([0-9a-f]{2})([0-9a-f]{2})([0-9a-f]{2})/;
  const [, red, green, blue] = rbgReg.exec(color);
  const r = parseInt(red, 16) / 255,
    g = parseInt(green, 16) / 255,
    b = parseInt(blue, 16) / 255;
  let max = Math.max(r, g, b),
    min = Math.min(r, g, b);
  let h, s, l = (max + min) / 2;

  if (max === min) {
    h = s = 0; // achromatic
  } else {
    let d = max - min;
    s = l > 0.5 ? d / (2 - max - min) : d / (max + min);
    switch (max) {
      case r:
        h = (g - b) / d + (g < b ? 6 : 0);
        break;
      case g:
        h = (b - r) / d + 2;
        break;
      case b:
        h = (r - g) / d + 4;
        break;
    }
    h /= 6;
  }

  return {
    h: Math.floor(h * 360),
    s: Math.floor(s * 100),
    l: Math.floor(l * 100)
  };
}

// función de comparación para algoritmo del mismo tipo
function compare(color1, color2) {
  const values1 = offsetHgrad(rgbToHsl(color1));
  const values2 = offsetHgrad(rgbToHsl(color2));

  if (values1.h !== values2.h) {
    return values1.h - values2.h;
  }
  if (values1.s !== values2.s) {
    return values1.s - values2.s;
  }
  return values1.l - values2.l;
}

document.addEventListener('DOMContentLoaded', () => {
  const sample = document.getElementById('sample');
  const expected = document.getElementById('expected');
  const result = document.getElementById('result');

  function addToDoc(container, color) {
    const box = document.createElement('div');
    box.className = 'box';
    box.style.backgroundColor = color;
    box.innerText = color;
    container.appendChild(box);
  }

  const input = ["#fff000", "#238923", "#aaaaa0", "#ff2300", "#2ff014", "#010203"];
  const intended = ["#ff2300", "#fff000", "#aaaaa0", "#2ff014", "#238923", "#010203"];
  input.forEach((i) => addToDoc(sample, i));
  intended.forEach((i) => addToDoc(expected, i));
  input.sort(compare).forEach((i) => addToDoc(result, i))
});
#sample,
#result,
#expected {
  display: flex;
  flex-wrap: nowrap;
}

.box {
  border: solid 1px black;
  margin: 5px;
  padding: 5px;
  color: white;
}
<div>Muestra</div>
<div id="sample">

</div>
<div>Resultado esperado</div>
<div id="expected">

</div>
<div>Resultado obtenido</div>
<div id="result">

</div>

Como ves la solución es bastante simple una vez que cambias el modelo mental y comparas usando los grados de una circunferencia en lugar de usar valores de color.

Si lo pruebas con los datos de @abulafia te das cuenta que hay violetas en ambos extremos pero que los menores son los violetas que tienen un mayor componente azul que es exactamente lo que pides.

function offsetHgrad(color) {
  const offset = 60;
  const start = 360 - offset;
  const h = color.h >= start ? color.h - start : color.h + offset;

  return {
    h,
    s: color.s,
    l: color.l,
  }
}

function rgbToHsl(color) {
  const rbgReg = /#([0-9a-f]{2})([0-9a-f]{2})([0-9a-f]{2})/;
  const [, red, green, blue] = rbgReg.exec(color);
  const r = parseInt(red, 16) / 255,
    g = parseInt(green, 16) / 255,
    b = parseInt(blue, 16) / 255;
  let max = Math.max(r, g, b),
    min = Math.min(r, g, b);
  let h, s, l = (max + min) / 2;

  if (max === min) {
    h = s = 0; // achromatic
  } else {
    let d = max - min;
    s = l > 0.5 ? d / (2 - max - min) : d / (max + min);
    switch (max) {
      case r:
        h = (g - b) / d + (g < b ? 6 : 0);
        break;
      case g:
        h = (b - r) / d + 2;
        break;
      case b:
        h = (r - g) / d + 4;
        break;
    }
    h /= 6;
  }

  return {
    h: Math.floor(h * 360),
    s: Math.floor(s * 100),
    l: Math.floor(l * 100)
  };
}

function compare(color1, color2) {
  const values1 = offsetHgrad(rgbToHsl(color1));
  const values2 = offsetHgrad(rgbToHsl(color2));

  if (values1.h !== values2.h) {
    return values1.h - values2.h;
  }
  if (values1.s !== values2.s) {
    return values1.s - values2.s;
  }
  return values1.l - values2.l;
}


document.addEventListener('DOMContentLoaded', () => {
  const sample = document.getElementById('sample');
  const expected = document.getElementById('expected');
  const result = document.getElementById('result');

  function addToDoc(container, color) {
    const box = document.createElement('div');
    box.className = 'box';
    box.style.backgroundColor = color;
    box.innerText = color;
    container.appendChild(box);
  }

  const input = ['#6264c0',
    '#b37f4d',
    '#116dcc',
    '#a8ce4b',
    '#7ea6f8',
    '#a94f89',
    '#83be23',
    '#6c8052',
    '#d87e04',
    '#d107f2'
  ];
  input.forEach((i) => addToDoc(sample, i));
  input.sort(compare).forEach((i) => addToDoc(result, i))
});
#sample,
#result {
  display: flex;
  flex-wrap: nowrap;
}

.box {
  border: solid 1px black;
  margin: 5px;
  padding: 5px;
  color: white;
}
<div>Muestra</div>
<div id="sample">

</div>
<div>Resultado obtenido</div>
<div id="result">

</div>

Puedes mejorar los algoritmos, el punto que me ocupa es que entiendas cuales son las partes importantes. Yo use el sort de javascript que no tiene un algoritmo definido pero al menos en Chrome usará una variante de Merge Sort llamada TimSort. En otros navegadores puede que usen Insertion sort, el resultado es realmente variable.

Lo ideal sería poder convertir los tres valores HSL a un sólo entero o cadena de caracteres y usar un algoritmo de enteros como el radix sort que puede llegar a ser más rápido que uno de comparación. Ten en cuenta que esto exige un paso de conversión adicional para cada valor HSL por lo que debes evaluar si en realidad hay beneficios en usarlo. Para colecciones muy grandes el beneficio será evidente. La realidad es que el conjunto de datos (mejor, medio, peor caso, su tamaño, etc) afecta el rendimiento de cada algoritmo de comparación así que debes decidir cual es el que desear usar. No hay una respuesta infalible sino ventajas y desventajas como rapidez, complejidad y consumo de memoria.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.