Regarde par ici (c'est une page sur mon serveur personnel): http://t0wer.ddns.net/files/superdrawstat.html

En haut, tu as mon image de test. Ce que je fais pour l'instant c'est que je la découpe en petits morceaux avec pour objectif de dessiner les morceaux indépendamment. Comme a priori les morceaux sont petits, on peut bruteforcer un peu pour obtenir un Super DrawStat intéressant.

J'ai utilisé un algorithme assez simple. Je créer des paquets (chunks) jusqu'à ce que j'ai recouvert toute l'image. Pour créer un chunk, je pars d'un pixel pas encore recouvert et j'ajoute des voisins dedans jusqu'à atteindre une taille convenable.

Au moment de choisir un voisin, je choisis toujours le pixel libre qui est le « plus connecté » au chunk. Intuitivement, ça veut dire que parmi ses 8 voisins à lui il y en aura un grand nombre qui auront déjà été pris dans le chunk. Et ça rejoint les principes algorithmiques derrière l'histoire de la coupe minimale dont je parlais avant.

Je répète cette procédure jusqu'à atteindre ma taille minimale, que ici configurée à 16. Sauf si bien sûr le pixel que j'avais choisi était isolé, auquel cas il n'a pas de voisins et je ne peux rien y faire.

Une fois que j'ai atteint la taille minimale de 16, si le chunk n'est pas trop dense, je continue de rajouter des pixels jusqu'à ce que j'atteigne le maximum de (ici) 32 ou une densité maximum, ic 0.6. (La densité étant le nombre de pixels du chunk divisée par la surface du plus petit rectangle qui contient entièrement le chunk.)

En bas, tu peux voir la même image (affichée depuis mon terminal) où chaque chunk a une couleur. Tu peux considérer que chaque surface de couleur différente sera calculée et affichée indépendamment.

Il me paraît acceptable, pour un utilisateur confirmé, de jouer avec ces paramètres jusqu'à obtenir quelque chose de satisfaisant. Les bons paramètres peuvent dépendre de la taille ou la forme de l'image ; c'est difficile de savoir à l'avance si l'algorithme va bien se comporter. Par exemple ici, en bas de l'image, c'est pas impressionnant : il y a plein de chunks qui se baladent, parfois de taille 1 ou 2.

La prochaine étape sera de trouver une méthode bourrine pour calculer une liste Super DrawStat pour un chunk individuel. Une fois que ce sera fait, tout sera terminé parce qu'afficher l'image quand on sait afficher les chunks c'est une trivialité.

La difficulté principale c'est qu'il faut tenir compte de deux phénomènes :
- Lever le crayon a un coût
- On a le droit de passer deux fois sur le même pixel

Je sais plus exactement où j'en étais la dernière fois... en gros, là j'ai mon algorithme. Essentiellement, ça consiste à appliquer plusieurs fois l'algorithme de la coupe minimale d'un graphe puis à bourriner sur les morceaux qui restent.

L'algorithme de la coupe min te dit en gros à quel endroit il faut couper ton image en deux pour la séparer en parties « en coupant le moins de traits possibles ». L'idée c'est qu'on va faire du DrawStat sur les parties individuelles, donc à chaque endroit où on va couper, on ne pourra pas mettre de ligne, ce qui dégrade un peu la solution. Donc on veut couper le moins de choses possibles.

Ensuite, une fois que les morceaux sont « assez petits » (la taille reste à déterminer par expérimentation), on bourrine, c'est-à-dire qu'on tente le maximum de solutions pour prendre la meilleure. Remiweb a déjà tenté une approche exhaustive et de mémoire c'était une catastrophe, donc faudra être malin.

Pour ça, on peut démarrer par une approximation avec le problème de Set Cover. Ce problème consiste à prendre un ensemble (tous les pixels noirs) et des parties de cet ensemble (toutes les lignes qu'on a le droit de tracer) et cherche quel est le nombre minimal de parties (de lignes) qu'il faut pour recouvrir l'ensemble (tracer l'image). L'approximation qu'on peut obtenir en temps raisonnable est assez grossière et ne tient pas compte du fait que le Super DrawStat est meilleur quand on ne « lève pas le crayon ».

Une fois qu'on a une première approximation, on peut bourriner et backtracker. L'idée c'est qu'on ajoute des traits jusqu'à ce qu'on arrive à dessiner toute l'image, et si avant d'arriver au bout on dépasse le nombre de traits donné par l'approximation de set cover, on laisser tomber parce qu'on sait qu'on peut faire mieux. Ce procédé s'appelle branch-and-bound parce qu'on prend toutes les routes possibles (branch) mais on borne le nombre de traits qu'on prend (bound).

Je ne sais pas à quel point l'approximation par Set Cover peut être pertinente ni quelle taille d'image est bourrinable en temps raisonnable ; j'ai une idée pour bourriner à l'aide d'un graphe un peu intelligent mais ça demande plus réflexion. Il existe aussi une coupe min probabiliste qui va plus vite, mais je crois pas qu'on en aura besoin.