cl.geologyidea.com
Más

Calcule el color del objeto para que no se repitan los objetos adyacentes

Calcule el color del objeto para que no se repitan los objetos adyacentes


We are searching data for your request:

Forums and discussions:
Manuals and reference books:
Data from registers:
Wait the end of the search in all databases.
Upon completion, a link will appear to access the found materials.


Estoy intentando asignar uno de los 16 colores a los objetos del mapa (por ejemplo, condados, estados, códigos postales, etc.) para que no haya dos objetos adyacentes que compartan el mismo color.

Veo toneladas de artículos en línea sobre "coloración de bordes" y el "teorema de los cuatro colores", pero parece que no puedo encontrar una manera de aplicar estos teoremas como un algoritmo en PostgreSQL / PostGIS (o cualquier aplicación práctica, para el caso) .

Estoy 100% seguro de que este es un problema resuelto, pero dado que Google no está revelando una respuesta, supongo que soy demasiado ignorante sobre este tema como para hacer la pregunta correcta.

¿Alguien me puede apuntar en la dirección correcta?


Tuve buena suerte usando el algoritmo de 6 colores descrito en la introducción a Dos algoritmos de tiempo lineal para cinco colores de un gráfico plano. Aunque ciertamente es posible colorear un gráfico con menos colores, es posible que no se vea mejor que con 5 o 6.

ALGORITMO 6 COLORES.

Dado un norte-Gráfico plano de vértice GRAMO en forma de lista de adyacencia, este algoritmo determina una coloración 6 de GRAMO.

Paso 1. Establecer listas de títulos.

Para cada j donde 0 , forman una lista doblemente enlazada de todos los vértices de GRAMO de grado j.

Paso 2. Etiquete los vértices con el grado más pequeño al final.

Para i = n, n-1, n-2,…, 1, designa el primer vértice del no vacío j-Lista de grados de los más pequeños j como vértice vI.

Borrar vI de la lista de grados j.

Para cada vértice v ' que estaba adyacente a vI en GRAMO y permanece en alguna lista de grados, digamos j ', Eliminar v ' desde el j ' lista de grados e insertar v ' en el j '- 1 lista de grados.

Paso 3. Colorea los vértices.

Para i = 1,2,…, n, asignar vértice vI el valor de color más pequeño (que debe ser un número entero entre uno y seis) que no ocurre en los vértices adyacentes a vI que ya han sido coloreados.


Estoy seguro de que esta función es increíblemente ineficiente (sin mencionar que está codificada muy mal, fue escrita como una implementación rápida y sucia "única"), pero aquí hay una cuyos resultados funcionan bastante bien para mí:

CREAR O REEMPLAZAR LA FUNCIÓN public.calc_colors (tbl text, unique_field text, neighbour_style text, search_distance real DEFAULT 0) REGRESA CONFIGURAR registro AS $ BODY $ DECLARE first_vertex text; r GRABAR; next_color INTEGER; max_used_color INTEGER; colores_disponibles INTEGER; texto next_vertex; create_contig TEXT; color_string TEXT; BEGIN --encontrar vecinos IF neighbour_style = 'no_corners' ENTONCES create_contig = 'CREAR TABLA DE TEMPERATURA contig_temp ON COMMIT DROP AS SELECT p1.' || quote_ident (campo_unico) || ':: texto AS c1, p1.geom como geom, p2.' || quote_ident (campo_único) || ':: texto AS c2 FROM' || tbl || 'p1 CROSS JOIN' || tbl || 'p2 WHERE (ST_Relate (p1.geom, p2.geom, "2 ********") O ST_Relate (p1.geom, p2.geom, "**** 1 ****")) Y p1. ' || quote_ident (campo_unico) || '! = p2.' || quote_ident (campo_unico); ELSIF neighbour_style = 'dentro de' ENTONCES create_contig = 'CREAR TABLA DE TEMPERATURA contig_temp ON COMMIT DROP AS SELECT p1.' || quote_ident (campo_único) || ':: texto AS c1, p1.geom como geom, p2.' || quote_ident (campo_único) || ':: texto AS c2 FROM' || tbl || 'p1 CROSS JOIN' || tbl || 'p2 WHERE (ST_Intersects (p1.geom, p2.geom) O ST_DWithin (st_envelope (p1.geom), st_envelope (p2.geom),' || search_distance || ')) AND p1.' || quote_ident (campo_unico) || '! = p2.' || quote_ident (campo_unico); ELSE create_contig = 'CREAR TABLA DE TEMPERATURA contig_temp ON COMMIT DROP AS SELECT p1.' || quote_ident (campo_unico) || ':: texto AS c1, p1.geom como geom, p2.' || quote_ident (campo_unico) || ':: texto AS c2 FROM' || tbl || 'p1 CROSS JOIN' || tbl || 'p2 DONDE ST_Intersects (p1.geom, p2.geom) Y p1.' || quote_ident (campo_único) || '! = p2.' || quote_ident (campo_unico); TERMINARA SI; EJECUTAR create_contig; CREAR ÍNDICE sidx_contig_temp ON contig_temp USANDO gist (geom); CREAR TABLA DE TEMPERATURA vertex_degree_temp ON COMMIT DROP AS SELECT c1, count (*) as neighbour_count FROM contig_temp GROUP BY c1 ORDER BY count (*) DESC, c1; CREAR ÍNDICE dv_tmp_idx ON vertex_degree_temp (c1); --color primer vértice, que es el vértice con el mayor número de vecinos SELECT c1 INTO first_vertex FROM vertex_degree_temp LIMIT 1; CREAR TABLA DE TEMPERATURA vertex_colors_temp ON COMMIT DROP AS SELECT first_vertex c1, 1 :: int color_idx; CREAR ÍNDICE vc_tmp_idx ON vertex_degree_temp (c1); max_used_color = 1; LOOP: encuentra el siguiente vértice, que es el vértice con el mayor número de colores distintos en los vecinos: para los vínculos, elige el vértice con el mayor número de vecinos SELECT d.c1 INTO next_vertex FROM (SELECT DISTINCT d.c1, d.neighbour_count, c. color_idx FROM vertex_degree_temp d, contig_temp n LEFT JOIN vertex_colors_temp c ON (c.c1 = n.c2) WHERE d.c1 NOT IN (SELECT c1 FROM vertex_colors_temp) Y d.c1 = n.c1) d GROUP BY d.c1, d .neighbour_count ORDER BY count (d.color_idx) DESC, neighbour_count DESC LIMIT 1; SALIR CUANDO next_vertex ES NULL; - encontrar el color disponible menos utilizado para el vértice DROP TABLE IF EXISTS used_colors_temp; CREAR TABLA DE TEMPERATURA used_colors_temp AS SELECT * FROM (SELECT generate_series (1, max_used_color) a) seq WHERE a NOT IN (SELECT c.color_idx FROM contig_temp n, vertex_colors_temp c WHERE (c.c1 = n.c2) AND n.c1 = next_vertex ORDEN POR color_idx); SELECT count (*) FROM used_colors_temp INTO available_colors; SI available_colors = 0 ENTONCES next_color = max_used_color + 1; max_used_color = next_color; ELSE: elija el color con el recuento más pequeño, pero la distancia más alejada de la geometría actual SELECT d.color_idx FROM (SELECT disponible.color_idx, ST_Distance (st_envelope (c.geom), st_envelope (disponible en geom)) dist FROM contig_temp c, (SELECT u .c1, u.color_idx, c.geom FROM vertex_colors_temp u LEFT JOIN contig_temp c ON u.c1 = c.c1 WHERE color_idx IN (SELECT a FROM used_colors_temp)) disponible DONDE c.c1 = next_vertex) d AGRUPAR POR d.color_idx ORDER POR min (dist) DESC LIMIT 1 INTO next_color; TERMINARA SI; --insert INSERT INTO vertex_colors_temp (c1, color_idx) VALUES (next_vertex, next_color); max_used_color = MEJOR (max_used_color, siguiente_color); END LOOP; VOLVER CONSULTA SELECCIONAR * FROM vertex_colors_temp; FIN; $ BODY $ IDIOMA plpgsql COSTO VOLÁTIL 100 FILAS 1000;

Se usa uniéndolo a la tabla existente, por ejemplo:

SELECCIONE l.id, colors.color_idx, l.geom FROM public.localities l LEFT JOIN public.calc_colors ('public.localities' :: text, 'id' :: text, 'within' :: text, 2000 :: real ) colores (id texto, color_idx entero) ON colors.id::bigint = l.id

(Nuevamente, disculpas por la horrible sintaxis ... ¡fue una implementación desechable!)

Esta función devolverá un número de color para cada característica en la tabla especificada como el primer argumento pasado a la función. El segundo argumento es una columna que identifica de forma única cada característica (utilizada para unir los colores a la tabla original). La magia está en los argumentos tercero y cuarto: estos controlan cómo se asignan los colores. El tercer argumento "neighbour_style" puede ser:

  • en blanco, lo que significa que los colores se asignarán de manera que no intersección las características comparten el mismo número de color
  • o 'no_corners', lo que significa que no intersección o conmovedor las características compartirán el mismo color
  • o 'dentro', en cuyo caso el cuarto parámetro se utiliza para especificar una tolerancia de distancia. Sin características dentro de esta distancia unos de otros compartirán el mismo color (puede ser útil si las características casi se tocan entre sí y no desea que compartan el mismo color).

El algoritmo intentará asignar colores para que el número total de características con un número de color dado sea aproximadamente igual y para que los colores se distribuyan de manera uniforme en los límites geográficos de la tabla de entrada.

¡Cualquier sugerencia para mejorar este script será muy apreciada!


Respondiendo a mi propia pregunta aquí con la esperanza de que esto ayude a los demás (oa mi yo futuro). En las semanas transcurridas desde que publiqué la pregunta, no pude encontrar una solución elegante a este problema que pudiera hacerse algorítmicamente en PostgreSQL. En cambio, dividí la tarea en partes constituyentes y la forcé más o menos brutalmente.

Para los propósitos de este tutorial, usaré códigos postales como ejemplo, pero este enfoque funcionó igual de bien para condados, ciudades, estados y países. Y en lugar de publicar un código muy específico del sistema que no sería reutilizable, solo explicaré mi enfoque.

1) Creé una tabla relacional provisional que contenía los ID de cada ZIP vecino. (por ejemplo, 12345 es adyacente a 12346, 12347 y 12348). Para determinar la adyacencia, utilicé ST_Intersects (). (Consulte las notas a continuación sobre las ciudades). Para acelerar las cosas, podría haber filtrado previamente la consulta para limitar la búsqueda de ZIP adyacentes dentro de una cierta distancia, pero descubrí que podía procesar todo dentro de una pausa para el café tolerable para esta ejecución única.

2) Luego creé un script PHP que procesaba cada ZIP a) eligiendo un color aleatorio de un grupo, yb) buscando para ver si alguno de los ZIP adyacentes a través del n. ° 1 anterior ya había usado ese color. Si se había usado el color, entonces recorrí colores aleatorios de la piscina hasta que encontré un color nuevo y sin usar.

Notas:

  • Para mis valores de color, simplemente utilicé un rango int de 0-15 en el primer lote y 0-7 en un segundo intento refinado. Esto hace que sea mucho más fácil elegir un valor aleatorio (por ejemplo, rand (0,7)), y proporciona más flexibilidad en el diseño de la línea. En mi caso, utilizo ese valor int con reglas condicionales en CartoCSS para diseñar los valores de color reales sobre la marcha.
  • Encontré solo un código postal y tres condados que tenían más de 7 vecinos (agotando así el grupo de colores disponible en mi conjunto de 8 colores (estas eran formas extraordinariamente altas con muchos vecinos a lo largo de cada lado largo si se pregunta cómo es posible) ). Para evitar que el script en el n. ° 2 se repita infinitamente, simplemente cerré de golpe el último valor aleatorio elegido y viví con el color duplicado. Este problema no ocurrió en el grupo de 16 colores, obviamente. He leído que los 50 estados de EE. UU. se puede hacer con tan solo 4 colores, aunque no lo intenté.
  • Las ciudades son un poco más complicadas, ya que la mayoría no se enfrentan a otras. Por lo tanto, ST_Intersects () no funcionará. En cambio, definí la adyacencia como estar dentro de una cierta distancia corta (demasiado larga y obtendrá demasiados vecinos). Si bien este enfoque no creará una solución matemáticamente pura, funciona en la práctica lo suficientemente bien como para engañar al ojo al dibujar el mapa.
  • Los tiempos de ejecución para procesar los ZIP y las ciudades, respectivamente, con el script en el n. ° 2 anterior fueron de aproximadamente una hora en mi plataforma. Asegúrese de que su valor max_execution_time en su php.ini esté configurado para permitir un trabajo realmente largo.

Espero que esto te ayude. No dude en enviarme un ping con cualquier pregunta o aclaración.



Comentarios:

  1. Shaktigar

    Esta notable frase es la correcta

  2. Voodookasa

    Pero, ¿qué es el ridículo aquí?



Escribe un mensaje