Une colle pour Baruch (et tt ceux qui voudront participer) - Page 1

J'avais envie de vous faire une petite colle, mais sans indices, je suis pas sur que tout le monde réussisse. =D

Bon, voilà l'intitulé du problème:

Faire un programme pot de peinture, cad un prog auquel on spécifie point sur le graphe, et qui remplit la zone qui l'entoure avec des pixels noirs. Genre remplir uyn cercle qui a été dessine plus tôt...
Vous suivez jusque là?? Parce que maintenant ça se corse: le but n'est pas de faire un programme rapide, mais un programme qui marche bien pour remplir des zones de grandes tailles: par exemple, remplir tout le graphe... (faut se munir d'un émulateur par contre, sinon c'est trop lent)

Tout le problème réside dans la gestion de la mémoire, mais j'en dis pas plus!!
A vous de trouver des solutions... Vous avez bien sur le droit de découper le problème en plusieurs sous-programmes...

(en théorie, je m'en sors avec 250 blocs mémoire contigus pour l'ensemble du graphe, et ceux qui ont fait autre chose que du Basic ont déjà des éléments de réponse...)

Tiens tiens, j'y avais déja réflèchi, sans trouver de solution ^^. Je ne vois pas trop ce que tu appelles un programme "qui marche bien", mais bon je verrai bien.

Le "marche bien", ça veut dire que ton programme doit pas devenir super lent quand tu augmentes l'aire de la surface à remplir (par exemple, si il fait du 5 pxl à la seconde au début, il fait à peu près la même chose à la fin); et surtout qu'il doit pas planter à cause d 'un manque de mémoire...

Je pense avoir trouvé un algo : un peu comme le A*...

Oué ! Ca marche ! Reste à optimiser quelques trucs.

Zut il ralentit quand même au bout d'un certain temps.

Allez, je le montre quand même : Download

{0,0->L2:Ans->L1 // L1 et L2 contiennent les abscisses et ordonnées des points à partir desquels il faut explorer
2->I // la taille de L1 (et L2), utile pour éviter des dim(L1) répétés

31->B:47->A // ce qui suit est la routine de déplacement du curseur
Repeat K=105
Pxl-Change(B,Ans
Repeat Ans
getKey->K
End
Pxl-Change(B,A
B+(Ans=34)-(Ans=25->B
A+(K=26)-(K=24->A
End

Pxl-On(B,Ans // Ans vaut A
Repeat I=1 // jusqu'à ce qu'il n'y ait plus de branches non explorées (eh oui, les listes vides n'existent pas)
{Ans,Ans+1,Ans,Ans-1->L3 // abscisse des points autour de la branche courante
{B-1,B,B+1,B->L4 // ordonnée
I-1->I // le point courant a été exploré, donc on l'enlève des listes
Ans->dim(L1
Ans->dim(L2
For(Z,1,4
If not(pxl-Test(L4(Z),L3(Z // s'il n'y a rien à côté, on déclare un nouveau point à explorer
Then
Pxl-On(L4(Z),L3(Z
augment(L2,{L4(Z->L2
augment(L1,{L3(Z->L1
I+1->I
End
End
L2(dim(L2->B // on choisit arbitrairement le point suivant à explorer
L1(dim(L1 // comme ça, Ans vaut A
End


Bon d'accord, il y a des défauts :

- on teste le point par lequel on est arrivé, mais bon le tester sans se poser de questions était plus rapide
- vers la fin du coloriage, on explore des points dont les points autour sont déja coloriés

On pourrait éviter les tests inutiles avec un système de balises :

(1) A chaque exploration : pour chaque point autour, s'il est balisé, on ne le teste pas ; pour le reste des points alentours non balisés et non coloriés, on en choisit un qu'on colorie, et on balise les autres.
Et ainsi de suite jusquà être "cerné" par des points balisés ou coloriés.
Là, on choisit un point balisé, on le teste et on recommence (1)
On recommence tout ça jusqu'à ce qu'il n'y ait plus de points balisés.

C'est cool en théorie, mais nul en pratique, puisque qu'il faudrait pouvoir rechercher un élément dans une liste (donc long), et en plus le pxl-Test est assez rapide pour pouvoir en gâcher quelques uns.

Bon, si on cherche à améliorer mon algo (très certainement améliorable) :

Ce qui ralentit le prog, c'est le nombre de points à explorer qu'on retient (càd la taille de L1 et L2), puisque je fais des dim(), des augment() (et ceux-ci sont lents) et des L1(). Donc si on veut minimiser la taille de ces listes, il faudrait "viser les collisions" avec les murs. Par exemple : je sais qu'il y a un mur à ma droite, j'avance, je commence par regarder s'il y a toujours un mur à ma droite, et même, s'il n'y en a pas, j'avance vers la droite pour essayer de le trouver (puisqu'on peut supposer que l'utilisation du prog est plus fréquente pour des dessins avec des lignes continues plutôt que des points épars).

Voilà ! Bon je vais voir si je peux appliquer quelques unes de mes idées.


Bon enfait j'ai trouvé beaucoup mieux ^^.

Baruch (./4) :
Je pense avoir trouvé un algo : un peu comme le A*...

C'est quoi le A*???

Bon, va falloir que je regarde ce que donne ton programme sur calto... Dans la théorie, ça marche assez bien! Mais dans la pratique, normalement c'est moins bien.
En fait, t'as implémenté une Pile; c'est à dire un conteneur de type LIFO (Last In, First Out). C'est une structure valable pour ce programme, mais il y en a une qui permet d'éviter plus les collisions (je te laisse encore chercher un peu^^). D'ailleur, je pense que ça va planter pour des zones très grandes (sur le mien, ça utilisait à peu près trois fois moins de mémoire que le nombre de points à colorier, mais ça plantait quand même).

Baruch (./4) :
Ce qui ralentit le prog, c'est le nombre de points à explorer qu'on retient (càd la taille de L1 et L2), puisque je fais des dim(), des augment() (et ceux-ci sont lents) et des L1(). Donc si on veut minimiser la taille de ces listes, il faudrait "viser les collisions" avec les murs. Par exemple : je sais qu'il y a un mur à ma droite, j'avance, je commence par regarder s'il y a toujours un mur à ma droite, et même, s'il n'y en a pas, j'avance vers la droite pour essayer de le trouver (puisqu'on peut supposer que l'utilisation du prog est plus fréquente pour des dessins avec des lignes continues plutôt que des points épars).

En fait le système d'ajout à la liste ralentit ton programme:

Quand tu fais augment(...), tu copies la première liste en mémoire; puis la deuxième; et ensuite le token s'exécute, donc le temps d'exécution est à peu près proportionnel à la somme des tailles de listes. Enfin bref, plus ta liste grossit et plus l'exécution est lente.

En fait, ce que tu veux faire, c'est mettre une seule valeur au bout de ta liste; donc tu peux faire : L4(Z) -> L2(Dim(L2)+1
Ou beaucoup mieux, tu stockes la taille des listes dans une variable que tu incrémente de temps en temps... (comme pour I)
Je pense pas que ce soit utile de réduire la taille de ta liste quand tu as examiné un point; en fait, si tu ne fais que décrémenter l'indice, ça suffit (sinon, quand tu la réincrémente, le programme doit de nouveau chercher et allouer des zones mémoires à utiliser, et ça peut être lent).

Baruch (./4) :
(1) A chaque exploration : pour chaque point autour, s'il est balisé, on ne le teste pas ; pour le reste des points alentours non balisés et non coloriés, on en choisit un qu'on colorie, et on balise les autres.
Et ainsi de suite jusquà être "cerné" par des points balisés ou coloriés.
Là, on choisit un point balisé, on le teste et on recommence (1)
On recommence tout ça jusqu'à ce qu'il n'y ait plus de points balisés.
C'est cool en théorie, mais nul en pratique, puisque qu'il faudrait pouvoir rechercher un élément dans une liste (donc long), et en plus le pxl-Test est assez rapide pour pouvoir en gâcher quelques uns.

En théorie ça marche bien en fait! Il suffit de faire ça dans une matrice; et de stocker en plus la liste des points balisés dans une autre structure de données (une pile par exemple). Donc tu dois gérer deux structures de données, mais tu as un accès rapide aux infos... Sauf que tu peux pas faire ça sur Ti, parce que ça te prend trop de place une matrice...

Le A* c'est un algo de recherche d'un chemin (va voir sur SDZ). Enfait je suis sur la piste d'un autre algo bien mieux (enfin je crois), mais je dis rien pour l'instant ^^.

L'ennui sur Ti, c'est que les bons algos on peut pas les coder, il manque de la mémoire, de la puissance et un langage adapté...

Tout à fait d'accord.

Le vrai post est en-dessous (double post ^^).

Bon, j'arrive pas à trouver mon algo. Pourtant je crois avoir une bonne idée :

L'idée, c'est de faire ça de façon naïve. Faîtes une courbe fermée, avec des îles.

Moi ce que je fais, c'est :

Je pars d'un bout de la courbe.
Je fais une série de lignes dans la même direction (donc par exemple des lignes verticales) pour colorier.
Bon après il y a des complications. J'en vois de 2 types :

Les îles : par exemple un cercle au mileu de la courbe, qu'il ne faut donc pas colorier. Déja pour repérer les cercles il est nécessaire avant chaque tracé de ligne de repérer s'il y a quelque chose (ou pas). Quand on a repéré un truc, que fait-on ? Il faut choisir si on veut continuer à colorier au-dessus ou en-dessous de l'île. Puis à un moment ultérieur, on recommence à colorier à partir de l'autre chemin. Bon déja ça c'est pas si simple.

A noter quelques cas délicats :
- s'il y a juste un point à l'intérieur de la courbe, il ne faudrait pas que ça pose des problèmes (on ne sait jamais).
- si plusieurs îles apparaissent sur la même ligne, il faut retenir chacun des endroits d'où il faudra repartir.

Les virages : j'ai la flemme de vous faire un dessin, donc imaginez une courbe fermée de la forme d'un C. Supposons qu'on parte d'en haut à droite, on va donc vers la gauche, et on trace des lignes verticales. On voit qu'à un moment il faudra retenir qu'à droite il y a un trou qui est apparu. Voilà, faut faire aussi attention à ça.

Bon maintenant, comment implémenter ça ?

On part avec la donnée d'un point blanc à l'intérieur de la courbe (celui sur lequel l'utilisateur a cliqué) (et on supposera donc que celui-ci ne clique pas sur un bord, ce qui pourrait nous poser quelques problèmes).
Je suppose qu'on ne tracera que des lignes verticales.

J'ai mon point blanc, et je cherche les bords en haut et en bas, donc je fais des pxl-Test successifs jusqu'à les trouver.

Entre ces 2 points noirs, je sais qu'il n'y a pas d'îles, donc je peux tracer une ligne verticales entre eux. Oué on est content !

Je choisis une direction arbitraire dans laquelle poursuivre mon coloriage, en sachant que plus tard je devrai recommencer dans l'autre direction.

Alors là, qu'est-ce que je fais ? Comme données, j'ai juste 2 points qui sont les bords pour la colonne d'à côté. Ce qu'il va falloir que je fasse, c'est trouver les nouveaux bords.
S'il y a des points noirs juste à côté des anciens (càd leur ordonnée est égale à celle de l'ancien bord +1, -1, ou la même, et je parlerai de points connexes par la suite), c'est cool. Mais ça ne veut pas dire que ce sont eux les bords : l'ordonnée des bords peut varier de plusieurs pixels entre chaque colonne. Il faut donc que je cherche les vrais bords, car si je ne fais pas ça, à la colonne suivante je pourrais me retrouver à l'extérieur de la courbe ! Donc pour le bord supérieur, je descends jusqu'à trouver un point blanc, et inversement pour l'autre bord.
Sinon (s'il n'y a pas de points noirs connexes aux anciens bords), il faut que je cherche jusqu'à en trouver un (puisque la courbe est fermée, j'en trouverai nécessairement un). Quand je parle de chercher, c'est vers le haut pour le bord supérieur, et vers le bas pour l'autre.
Voilà j'ai mes 2 bords. Si j'ai dû aller les chercher plus loin qu'expecté, je sais qu'un trou est apparu, qu'il faudra explorer un jour.

Maintenant je m'occupe des îles : je parcours les pixels entre les 2 bords pour voir s'il y a des "parasites" (à noter qu'il peut y avoir déja pas mal de points qui ont été testés, donc il suffit d'explorer pour les ordonnées comprises entre celles des anciens bords). Donc d'abord je pars d'en haut, et je descends jusqu'à trouver un point noir.
Si je ne trouve personne (càd si le point noir que je trouve est mon bord inférieur), il n'y a pas d'îles.
Sinon, ça se complique. Il va falloir que je retienne des bords secondaires. Le point noir que j'ai trouvé en descendant, ce sera mon bord inférieur pour la colonne suivante (si je choisis arbitrairement de me "coller" au bord supérieur lors du changement de colonne). De là, je descends jusqu'à trouver un point blanc, j'aurais donc un bord supérieur secondaire (qui est donc juste au-dessus du point blanc). Et je continue : je descends jusqu'à trouver un point noir, et s'il n'est pas mon bord inférieur, je cherche un bord supérieur secondaire, etc. A noter que si je n'ai qu'un point parasite dans la colonne, ça ne posera pas de problème, j'aurai juste un bord inférieur et un bord supérieur qui seront confondus.
Voilà, j'ai noté s'il y avait des chemins que je devrai explorer ultérieurement, et où ils sont.

Bon je choisis le chemin que je vais prendre (moi je choisis celui qui colle au bord supérieur, mais peu importe), et je trace la ligne entre les 2 bords

Je me décale d'une colonne, et je recommence tous les tests écrits au-dessus.

J'arrête mon coloriage d'un chemin lorsque les bords supérieur et inférieur sont confondus.
Et là je reprends l'exploration d'un chemin que j'ai signalé auparavant.

Et ce jusqu'à ce qu'il n'y ait plus de chemins à explorer.


Ouf !

Bien que rien ne soit encore réalisé, j'ai pensé à améliorer l'algo comme ça : on ne fait le test des îles qu'une fois sur deux. Pourquoi ? Parce-qu'un île, càd une zone à ne pas colorier, s'étend au minimum sur 3 colonnes (testez), et qu'on à l'avantage de n'avoir que 2 couleurs sur TI (^^), donc les bords sont de même couleur que la couleur du coloriage, et donc colorier en noir un bord noir, peu importe.

Bon allez je vais essayer de coder ça.

PS : je vous avouerai qu'écrire ici a transformé mon "idée" en un algo un peu plus sérieux ^^.

hum...
comment tu compte t'y prendre avec les pixel noir isolés au milieu d'une ile ? ou d'une ile dans une ile ?
Si j'ai bien compris l'explication de ton futur code je pense que ça devrait poser problème :s

Euh tu peux développer plus le problème ? ^^

et bien imaginons, tu "cliques" en dehors d'une grande île dans laquelle il y a une autre île plus petite (voir juste un pixel)
étant donné (à ce que j'ai compris) que tu parcours les pixel jusqu'à trouver un pixel allumé symbolisant le bord d'une île, et que tu continue à parcourir jusqu'au pixel suivant allumé qui sera alors l'autre bord de l'île, et là tu te remet à dessiner. Hors si ce second pixel de bord est en fait le bord de la seconde île dans la première ? tu vas colorer une zone qui ne devrait logiquement pas l'être...
Et dans le cas où le bord inférieur des deux îles serait confondu, on aurait un problème beaucoup plus problématique :s
je te fait un dessin :

Non c'est bon, puisque j'arrête ma recherche des îles lorsque j'atteins l'ordonnée de mon bord inférieur.

C'est pas mal, mais si tu dois colorer une zone contenant un nuage de points, tu y gagnes pas du tout ... Dans le pire des cas, tu peux tester plein de fois le même point. Par contre, sur Ti, c'est plus rapide parce que Line() est plus performant qu'une boucle for et des PxlOn...

En fait, en complexité, c'est équivalent à l'autre méthode (implémentée par file) à cause du problème du "C"...

OK, je vais quand même essayer de réaliser le programme. Je veux bien ton algo.

C'est à peu près le même que le tien (le premier), sauf que je l'implémente avec une file au lieu d'une pile, et donc ça marche mieux. En fait c'est super lent parce que je l'ai fait de façon modulaire, mais en fait, c'est ça qui est vraiment implémenté dans la plupart des programmes sur PC... On peut à la limite faire quatre files, pour éviter de tester trop de fois chaque pixel.

Si tu modifies un peu ton second algo - en fait si il gère tous les "fronts" en même temps et pas l'un jusqu'à ce qu'il n'ait plus rien à faire, puis le second - je pense que y'a moyen de le rendre assez efficace en mémoire et en temps.

Sinon je peux te renvoyer sur un poly d'amphi qui parlait de ça (en fait on fait surtout du remplissage de polygones en cours).

Fichier joint : AAAFILE.8xp -> Ca c'est une structure de file un peu adaptée au problème.
Fichier joint : AAAPOTF.8xp -> Pot de peinture client de File.
Fichier joint : PAINTPOT.8xp -> Pour utiliser facilement les autres programmes.
Fichier joint : AAAPOT.8xp ->Version rapide sans gestion de mémoire