Suite

Calculer la couleur de l'objet afin qu'aucun objet adjacent ne se répète


J'essaie d'attribuer l'une des 16 couleurs aux objets de la carte (par exemple, les comtés, les États, les codes postaux, etc.) afin qu'aucun deux objets adjacents ne partagent la même couleur.

Je vois des tonnes d'articles en ligne sur la "coloration des bords" et le "théorème des quatre couleurs", mais je n'arrive pas à trouver un moyen d'appliquer ces théorèmes en tant qu'algorithme dans PostgreSQL/PostGIS (ou toute application pratique, d'ailleurs) .

Je suis sûr à 100% que c'est un problème résolu, mais comme Google ne révèle pas de réponse, je suppose que je suis trop ignorant sur ce sujet pour poser la bonne question.

Quelqu'un peut me diriger dans la bonne direction?


J'ai eu de la chance en utilisant l'algorithme à 6 couleurs décrit dans l'introduction de Deux algorithmes en temps linéaire pour la cinq-coloration d'un graphique planaire. Bien qu'il soit certainement possible de colorer un graphique en utilisant moins de couleurs, cela peut ne pas paraître mieux que d'utiliser 5 ou 6.

ALGORITHME 6 COULEURS.

Étant donné un m-graphique planaire des sommets g sous forme de liste d'adjacence, cet algorithme détermine une 6-coloration de g.

Étape 1. Établir des listes de diplômes.

Pour chaque j0 < j < n-1, forment une liste doublement chaînée de tous les sommets de g de diplôme j.

Étape 2. Étiquetez les sommets au plus petit degré en dernier.

Pour i=n, n-1, n-2,… , 1, désignent le premier sommet du non-vide j-liste des degrés des plus petits j comme sommet vje.

Supprimer vje de la liste des j degrés.

Pour chaque sommet v' qui était adjacent à vje dans g et reste dans une liste de degrés, disons j'ai, effacer v' du j'ai liste des diplômes et insérer v' dans le j' - 1 liste des diplômes.

Étape 3. Colorez les sommets.

Pour i =1,2,… ,n, affecter un sommet vje la plus petite valeur de couleur (qui doit être un nombre entier compris entre un et six) n'apparaissant pas sur les sommets adjacents à vje qui ont déjà été colorées.


Je suis sûr que cette fonction est incroyablement inefficace (sans parler du fait qu'elle est très mal codée - elle a été écrite comme une implémentation rapide et sale "unique), mais en voici une dont les résultats fonctionnent assez bien pour moi :

CRÉER OU REMPLACER LA FONCTION public.calc_colors( tbl text, unique_field text, around_style text, search_distance real DEFAULT 0) RETOURNE SETOF record AS $BODY$ DECLARE first_vertex text; r ENREGISTREMENT ; next_color INTEGER; max_used_color ENTIER ; couleurs_disponibles ENTIER ; texte suivant_sommet ; créer_contig TEXTE ; color_string TEXTE; COMMENCER --trouver les voisins IF style_voisin = 'no_corners' ALORS create_contig = 'CREATE TEMP TABLE contig_temp ON COMMIT DROP AS SELECT p1'.' || quote_ident(unique_field) || '::text AS c1, p1.geom as geom, p2.' || quote_ident(unique_field) || '::texte AS c2 FROM ' || tbl || 'p1 CROSS JOIN' || tbl || ' p2 WHERE ( ST_Relate( p1.geom, p2.geom,"2********") OU ST_Relate( p1.geom, p2.geom,"****1****")) ET p1.' || quote_ident(unique_field) || ' != p2.' || quote_ident(unique_field); ELSIF voisin_style = 'within' THEN create_contig = 'CREATE TEMP TABLE contig_temp ON COMMIT DROP AS SELECT p1.' || quote_ident(unique_field) || '::text AS c1, p1.geom as geom, p2.' || quote_ident(unique_field) || '::texte AS c2 FROM ' || tbl || 'p1 CROSS JOIN' || tbl || ' p2 WHERE (ST_Intersects( p1.geom, p2.geom) Ou ST_DWithin( st_envelope(p1.geom), st_envelope(p2.geom), ' || search_distance || ')) ET p1.' || quote_ident(unique_field) || ' != p2.' || quote_ident(unique_field); ELSE create_contig = 'CREATE TEMP TABLE contig_temp ON COMMIT DROP AS SELECT p1.' || quote_ident(unique_field) || '::text AS c1, p1.geom as geom, p2.' || quote_ident(unique_field) || '::texte AS c2 FROM ' || tbl || 'p1 CROSS JOIN' || tbl || ' p2 O ST_Intersects( p1.geom, p2.geom) ET p1.' || quote_ident(unique_field) || ' != p2.' || quote_ident(unique_field); FIN SI; EXÉCUTER create_contig; CREATE INDEX sidx_contig_temp ON contig_temp USING gist (geom); CREATE TEMP TABLE vertex_degree_temp ON COMMIT DROP AS SELECT c1, count(*) as around_count FROM contig_temp GROUP BY c1 ORDER BY count(*) DESC, c1; CRÉER UN INDEX dv_tmp_idx ON vertex_degree_temp (c1) ; --color first vertex, qui est le sommet avec le plus grand nombre de voisins SELECT c1 INTO first_vertex FROM vertex_degree_temp LIMIT 1; CREATE TEMP TABLE vertex_colors_temp ON COMMIT DROP AS SELECT first_vertex c1, 1::int color_idx; CRÉER UN INDEX vc_tmp_idx ON vertex_degree_temp (c1) ; max_used_color = 1 ; LOOP --trouver le sommet suivant, qui est le sommet avec le plus grand nombre de couleurs distinctes dans les voisins --pour les liens, choisissez le sommet avec le plus grand nombre de voisins SELECT d.c1 INTO next_vertex FROM ( SELECT DISTINCT d.c1, d.related_count, c. color_idx FROM vertex_degree_temp d, contig_temp n LEFT JOIN vertex_colors_temp c ON (c.c1 = n.c2) O d.c1 NOT IN (SELECT c1 FROM vertex_colors_temp) ET d.c1 = n.c1 ) d GROUP BY d.c1, d .neighbor_count ORDER BY count(d.color_idx) DESC, around_count DESC LIMIT 1; EXIT LORSQUE next_vertex EST NULL ; --trouver la couleur disponible la moins utilisée pour le sommet DROP TABLE IF EXISTS used_colors_temp; CREATE TEMP TABLE 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 ORDRE PAR color_idx); SELECT count(*) FROM used_colors_temp DANS available_colors ; SI couleurs_disponibles = 0 ALORS couleur_suivante = couleur_max_utilisée + 1 ; max_used_color = next_color; ELSE --choisir la couleur avec le plus petit nombre, mais la distance la plus éloignée de la géométrie actuelle .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) ) available WHERE c.c1 = next_vertex) d GROUP BY d.color_idx ORDER BY min(dist) DESC LIMIT 1 INTO next_color; FIN SI; --insert INSERT INTO vertex_colors_temp (c1, color_idx) VALUES (next_vertex, next_color); max_used_color = LE PLUS GRAND(max_used_color, next_color); FIN DE BOUCLE ; RETURN QUERY SELECT * FROM vertex_colors_temp; FINIR; $BODY$ LANGUE plpgsql COT VOLATIL 100 LIGNES 1000 ;

Il est utilisé en le joignant à la table existante, par exemple :

SELECT l.id, colours.color_idx, l.geom FROM public.localities l LEFT JOIN public.calc_colors('public.localities'::text, 'id'::text, 'within'::text, 2000::real ) colours(id text, color_idx integer) ON colours.id::bigint = l.id

(Encore une fois, excuses pour la syntaxe horrible… c'était une implémentation jetable !)

Cette fonction renverra un numéro de couleur pour chaque caractéristique de la table spécifiée comme premier argument passé à la fonction. Le deuxième argument est une colonne qui identifie de manière unique chaque caractéristique (utilisée pour joindre les couleurs à la table d'origine). La magie réside dans les 3e et 4e arguments - ceux-ci contrôlent la façon dont les couleurs sont attribuées. Le 3ème argument "voisin_style" peut être soit :

  • vide, ce qui signifie que les couleurs seront attribuées de manière à ce qu'aucun sécante les fonctionnalités partagent le même numéro de couleur
  • ou 'no_corners', ce qui signifie que non sécante ou alors émouvant les fonctionnalités partageront la même couleur
  • ou 'à l'intérieur', auquel cas le 4ème paramètre est utilisé pour spécifier une tolérance de distance. Aucune fonctionnalité dans cette distance les uns des autres partageront la même couleur (cela peut être utile si les éléments se touchent presque et que vous ne voulez pas qu'ils partagent la même couleur).

L'algorithme tentera d'attribuer des couleurs de sorte que le nombre total d'entités avec un numéro de couleur donné soit à peu près égal et que les couleurs soient à peu près uniformément réparties sur les limites géographiques de la table d'entrée.

Toute suggestion d'amélioration de ce script serait grandement appréciée !


Répondre à ma propre question ici dans l'espoir que cela aide les autres (ou mon futur moi). Dans les semaines qui se sont écoulées depuis que j'ai posté la question, je n'ai pas réussi à trouver une solution élégante à ce problème qui pourrait être faite de manière algorithmique dans PostgreSQL. Au lieu de cela, j'ai divisé la tâche en parties constitutives et je l'ai plus ou moins brutalement forcée.

Pour les besoins de cette procédure pas à pas, j'utiliserai les codes postaux comme exemple, mais cette approche a tout aussi bien fonctionné pour les comtés, les villes, les États et les pays. Et plutôt que de publier du code très spécifique au système qui ne serait pas réutilisable, je vais juste expliquer mon approche.

1) J'ai créé une table relationnelle provisoire qui contenait les identifiants de chaque ZIP voisin. (par exemple, 12345 est adjacent à 12346, 12347 et 12348). Pour déterminer la contiguïté, j'ai utilisé ST_Intersects(). (Voir les notes ci-dessous sur les villes). Pour accélérer les choses, j'aurais pu pré-filtrer la requête pour limiter la recherche de ZIP adjacents à une certaine distance, mais j'ai découvert que je pouvais tout traiter pendant une pause-café tolérable pour cette exécution unique.

2) J'ai ensuite créé un script PHP qui traitait chaque ZIP en a) choisissant une couleur aléatoire dans un pool et b) en cherchant si l'un des ZIP adjacents via #1 ci-dessus avait déjà utilisé cette couleur. Si la couleur avait été utilisée, j'ai parcouru des couleurs aléatoires de la piscine jusqu'à ce que je trouve une couleur fraîche et inutilisée.

Remarques:

  • Pour mes valeurs de couleur, j'ai simplement utilisé une plage int de 0 à 15 dans le premier lot et de 0 à 7 dans une deuxième tentative raffinée. Cela facilite beaucoup la sélection d'une valeur aléatoire (par exemple, rand(0,7)), et offre plus de flexibilité dans le style sur toute la ligne. Dans mon cas, j'utilise cette valeur int avec des règles conditionnelles dans CartoCSS pour styliser les valeurs de couleur réelles à la volée.
  • Je n'ai trouvé qu'un seul code postal et trois comtés qui avaient plus de 7 voisins (épuisant ainsi le pool de couleurs disponible dans mon ensemble de 8 couleurs (c'étaient des formes extraordinairement hautes avec beaucoup de voisins le long de chaque côté si vous vous demandez comment c'est possible ). Pour empêcher le script dans #2 de boucler à l'infini, j'ai simplement claqué la dernière valeur aléatoire choisie et j'ai vécu avec la couleur dupliquée. Ce problème ne s'est évidemment pas produit dans le pool de 16 couleurs. J'ai lu que les 50 États américains peut être fait avec aussi peu que 4 couleurs, même si je n'ai pas essayé.
  • Les villes sont un peu plus délicates car la plupart ne se heurtent pas à une autre. Ainsi, ST_Intersects() ne fonctionnera pas. Au lieu de cela, j'ai défini la contiguïté comme étant à une certaine distance courte (trop longue et vous aurez trop de voisins). Bien que cette approche ne crée pas une solution mathématiquement pure, elle fonctionne suffisamment bien dans la pratique pour tromper l'œil lors du dessin de la carte.
  • Les temps d'exécution pour traiter les ZIP et les villes, respectivement, avec le script n ° 2 ci-dessus étaient d'environ une heure sur ma plate-forme. Assurez-vous que votre valeur max_execution_time dans votre php.ini est définie pour permettre un travail très long.

J'espère que ceci vous aide. N'hésitez pas à me contacter pour toute question ou clarification.