Salut les gens,
 
Suis actuellement confronté à un chti problème avec un projet que je développe sous Visual C++ 6.0 : En fait l'idée est simple, je cherche à coder un outil genre "remplissage" comme dans paint, mais comme je débute, je ne connais pas toutes les possibilités offertes par le C++ (mais ca va venir...   )  
Pour l'instant, je m'entraîne avec une ellipse de contour noir. J'utilise la fonction CDC::GetPixel pour détecter les contours de l'ellipse et remplir un tableau avec des 1 et des 0 : 1 si présence d'un pixel noir, 0 sinon. Ensuite, et c'est là que ca coince   , j'aimerais remplacer par des 1 une chaîne de 0 placée entre deux chaînes de 1. Par exemple :
 
00000011111110000000000011111111110000000000 deviendrait
00000011111111111111111111111111110000000000
 
ou
 
00000000010000000000000010000000000000000000 deviendrait
00000000011111111111111110000000000000000000
 
Bref vous voyez le truc. Et ben c'est là que ca coince   .
Est-ce qu'il y aurait une âme charitable pour me donner des idées ou au moins pour me dire si ma manière de procéder peut être la bonne ou si elle est à revoir??
Ma vie est entre vos mains   Merci par avance.

parcourt ton tableau ligne par ligne en cherchant les 1
des que tu en trouves un, remplis les cases suivantes avec des 1 jusqu'au prochain un, et continue jusqu'a la fin de la ligne
itere sur toutes les lignes.

Oui, c'est l'idée que j'avais eue aussi mais pour le cas d'une ligne qui ressemblerait à :
0000000001100000000000000011111100000 Je détecte le premier 1 et je mets des 1 jusqu'au prochain 1, donc rien ne sera modifié...
Par contre j'arrive à détecter le dernier 1 d'une série de 1 :
if (tab[k] >= tab[k-1] && tab[k] > tab[k+1])
et le premier 1 d'une série de 1 :
if (tab[k] > tab[k-1] && tab[k] >= tab[k+1])
Mais rien n'y fait. Le problème c'est je peux dire que je mets des 1 à partir du dernier 1 de la série de 1 (fiou... compliqué...) et zou toute la fin de la ligne passera à 1...
J'ai essayé plein de trucs, genre utiliser des compteurs pour savoir combien de fois on est passé de 0 à 1 et de 1 à 0 et réagir en conséquence. Mais ca morch pô...
Merci pour ta réponse. Reste cool avec les castors.

Bah là faut faire une vulgaire machine à état avec un switch case parceque les if machin c'est vraiment pas adapté à ce genre de pb.
 
genre tu démarres en etat DETECTION, une fois le front descendant ( 1->0) détecté et bien tu passes à l'etat REMPLISSAGE jusqu'à la détection front montant ( 0-> ).
 

Oui je n'avais pas pensé à cette solution, mais quoi qu'il en soit je vais avoir un pb avec le deuxième front descendant. Après le deuxième front descendant, je vais repasser en mode REMPLISSAGE et c'est un comportement qui n'est pas souhaitable...
Bon j'essaie, merci pour ta réponse.

ok, il suffit de rajouter une étape je pense

 
je plussoie, en gros, tant que tu as des 1, tu ne fait rien (front montant), dès que tu as des 0 tu cherches le 1er 1 qui apparait et en attendant de le trouver tu remplaces par des 1.
 

 
si tu raisonne ligne par ligne ça doit le faire non ?

Ben suis pas sûr, sur une ligne il y a 2 fronts montant et 2 fronts descendant. Faudrait que je rajoute un compteur de fronts descendants, ouaip, allez je vais essayer ca...

Il suffit d'avoir une etape ATTENTE fin de ligne

imaginons qu'une ligne soit comme ca :
0000000000100000000000
donc a priori, il n'y a rien a remplir, j'ai l'impression que vos propositions ne marche pas

 
effectivement c'est gênant
 
Je sais pas comment il lit son image mais si il peut, il a qu'a le faire en 2 passes. 1 pour la lecture et une pour l'écriture si nécessaire non

Bon, j'ai trouvé une autre méthode, peut-être un peu moins contraignante, à voir...
Pour chaque pixel, je teste dans la ligne correspondante s'il existe un pixel noir à sa gauche et un pixel noir à sa droite. Test idem pour la colonne. Si les 4 tests sont positifs, le pixel est à l'intérieur de mon ellipse et zou je le colore.
Pb : Pour chaque pixel, j'effectue 4 tests, j'ai peur que ca mouline un peu longtemps.
Bon je code et je vous dis si ca marche ou si ca ne marche pas.
En attendant les bonnes idées sont tjs les bienvenues...

et un truc comme ça?
 

plus generalement, est ce qu'une ligne peut suffir pour savoir comment la remplir ?
je m'explique
imaginons que l'ont tombe sur une ligne comme cela :
000000100000100001000
je rempli quoi ? du 1er au 2eme ? du 2eme au 3eme ?
ben ca depend de se que la ligne represente (le 1er 1 peut etre un sommet du polygone ou un point d'un coté)
a mon avis decouper par ligne ne permet par de resoudre ce pb.

ha ben si, des infos ici
http://www.iiens.net/themes/autre3 [...] y_main.htm

 
tu risque aps de colorer trop de pixels par hasard ???
 
Je sais pas si tu lis ton image de gauche à droite ou de bas en haut mais 2 test suffisent pour savoir si tu est dans ta zone.
 
Exemple. Tu parcours ton image comme tu lis un livre --> gauche>droite et haut>bas.
Teste si ton pixel courant est blanc à chaque fois. Si oui c'est bon, sinon il faut passer en mode Remplissage/Arret Remplissage selon ce que tu faisait avant de rencontrer ce pixel noir
Il suffit de tester si le pixel précédent gauche était noir et si le pixel précédent haut était noir. Si c'est le cas tu colore le pixel courant et tu reteste avec celui de droite, dans ce cas comme tu viens de colorer celui de gauche, il ne te reste plus qu'à tester le pixel du haut.
 
Et ainsi de suite.
 
Pour chaque ligne, si tu doit économiser le temps de calcul,tu teste gauche et haut. Lorsque tu rempli les 2 conditions, tu rempli le pixel courant et tu passe en mode test haut uniquement tant que test haut est vrai. Si test haut passe a faux, tu repasse en mode test gauche et test haut et ainsi de suite.
 
J'espère que je me suis fait comprendre sinon je tenterai un dessin .

Bon c'est la super honte!! Je n'arrive pas à créer un tableau de deux dimensions (400 * 250) avec new. Si si je vous assure... Bon je vais me cacher sous le bureau en attendant vos moqueries...

Vas expier ta faute http://forum.hardware.fr/hardwaref [...] 64.htm#bas

Ok Joeff, merci, ca a l'air pas mal. Je teste ca dès que je m'en suis orti avec mes tableaux 2D... (ho c'te honte)

Ok les gens,
J'ai finalement trouvé une solution à mon problème de remplissage de polygônes . Aux oubliettes les tableaux deux dimensions et les 1 et les 0 . Le programme suivant analyse pour chaque pixel de la figure s'il existe un pixel noir à la gauche du pixel en question, en bas, à sa droite et en haut. Si tel est le cas, le pixel est coloré en rouge, sinon on passe au pixel suivant.
Ca fonctionne plutôt bien sauf pour les formes un peu exotiques, mais pour tout ce qui est carré, rectangle, triangle, trapèze, cercle, ellipse, ... pas de problème.

Par contre le gros inconvénient, c'est la vitesse d'exécution   . J'ai le temps d'aller boire trois café pendant le traitement d'une figure de la taille de mon écran. Y aurait-il une solution plus rapide??

Tu bosses directement à l'écran là non? (je connais pas grand-chose aux api microsoft de ce coté...).
Si c'est le cas le mieux c'est de récupérer ton image en ram, la traiter, puis la rebalancer vers l'écran.

skeye> +1
 
sinon... un algo comme le floodfill ça serait pas mieux? ils sont gros tes polygones?

Floodfill?? Sais pas trop ce que c'est...    
En fait, à terme, ce ne seront plus des polygônes mais des patates mi-ellipses mi-n'importe quoi, et concentriques. Ce sont des figures qui prennent la taille de mon écran à peu près... Un fort bel écran ma foi.
Plus sérieusement, je pense que l'idée du traitement en Ram puis de l'affichage du résultat est une voie que je vais explorer de ce pas   .
Merci pour vos tips   .

Pourquoi tu fais pas ca pseudo-récursivement?
Tu prends ton point a l'intérieur, et tu vérifies ses voisins, et pour chacun d'eux tu réiteres?

 
le floodfill c'est tout con, mais gourmand
un exemple d'algo:
 

 
et là je n'ai fais que la version la moins gourmande (sur les 4 voisins).
tu peux faire ta recursivité sur les 8 voisins, c'est plus rapide mais encore plus gourmand.
pourquoi gourmand? car récursif...

Qu'est-ce que tu entends par gourmand?
Je vais essayer d'implémenter ca, ca m'a l'air pas mal est pas trop dur... Comme je suis carrément chaud, je vais direct m'attaquer aux huit voisins .
Au boulot... Je vous tiens au courant.

en mémoire.

 

j'ai jamais réussi à le faire tourner sur des formes de plus de 600x400 de boîte englobante  

ah oué quand même...

le problème vient surtout de la pile d'appel qui viens vite à saturation
j'ai eu beau jongler avec les tailles de pile et de tas, à chaque fois je me suis retrouvé coincé...
par contre, sur des petites formes ça roxxe méchamment

faut le faire en lisp!

bah tiens, fais nous un bench C/lisp, toi qui a tout plein de temps

ah ouais, quand même...    
Bon, pas grave, je tente... On verra bien ce ca donne   .

J'ai pas touché au lisp depuis la maitrise (ou licence même p-e...) et j'ai pas l'intention de changer quoi que ce soit à cet état de fait!

 
méfies toi des résultats au fait
ce n'est pas parceque ça ne plante pas que ça marche

'tention à la connexité des contours, je suppose!

 
oui entre autres
sinon j'ai pu voir des choses bizarres justement à cause de la perte de la pile d'appels (récursivité infinie alors que le test d'arrêt est forcément vrai, appel de fonctions non désirées etc.)

Bon ben voilà, c'est la fête   , merci beaucoup pour le coup de pouce   . J'ai implémenté ce fameux floodfill, en effectuant une récurrence sur les 4 voisins les plus proches, et je dois avouer que le résultat est stupéfiant   . Même avec des figures complexes c'est nickel.
Si j'effectue une récurrence sur les 8 voisins les plus proches, je me retrouve avec des effets de bord indésirables...   Mais bon, la vitesse atteinte avec 4 voisins est déjà largement satisfaisante   . J'ai rajouté une ch'tite boucle pour localiser le premier pixel à partir duquel lancer le floodfill, c'est le premier pixel qui a un pixel noir à sa gauche et un pixel noir juste au-dessus. Il se trouve alors dans la figure à colorier.
Voici le prog final, qui tient en qques lignes, et qui fonctionne effectivement (testé avec MS Visual C++ 6.0) :

 
Par contre, dès que je veux traiter des figures un peu plus grandes, ca coince... Y aurait-il une manip à effectuer sur windows qui pourrait m'aider, genre augmenter la taille de la mémoire virtuelle??
Ou sinon j'ai toujours la possibilité de faire le traitement en mémoire et d'afficher le résultat une fois le traitement terminé.
Quoi qu'il en soit, un grand MERCI pour vos conseils, ca fait plaisir, je reviendrai tiens!!  

 
C'est le pb de la récursivité...pasgrand chose à faire!
 

De toute manière c'est conseillé quelle que soit ta méthode ensuite.