Discussion :

[matt22]

Bonjour à tous.

Le sujet à déjà été abordé il y a quelques temps, mais je n'ai pas trouvé ma réponse.
J'explique ma problèmatique.
J'ai un programme qui a pour objectif de remplir des zones de couleur.
J'ai une détermination de contour qui me permet des séparer mon image en zone.

Aujourd'hui, pour remplir mes zone mon algorithme de remplissage permet de coloré pixel par pixel chaque point de la zone.
Mais la méthode (application android) permettant le remplissage d'un pixel est longue à executé.
Pour optimiser ce remplissage (trop long à mon gout) j'ai la possibilité de remplir une zone rectangulaire d'un coup (bcp plus rapide).

Mon objectif est donc :
Sur un tableau à deux dimensions (boolean tab[w][h])
qui a true pour dire "à colorier" et false pour les autres pixels.
je voudrais pouvoir découper cette zones (les pixel "true") en rectangles pour optimiser le remplissage, mais je n'arrive pas à trouver un algorithme permettant cela.

Quelqu'un peut il m'aider ?

Désolé, ce n'est peut être pas très clair, mais quand on est dedans c'est pas facile d'expliquer....

Merci à tous,
Matt

[Nebulix]

As-tu essayé de colorier des rectangles de 1 pixel de haut ?

[matt22]

Salut,

Oui en effet j'ai modiifé mon algo pour colorier des ligne (rectangle d'1 de haut) ce qui optimise déjà, mais peut on pas faire mieux ???

[pseudocode]

Je pense que tu cherches a faire du "rectangle covering", c'est à dire découper ta forme en gros rectangles, dans le but d'accélérer le tracé.

(google : Rectangle Covers Revisited Computationally)

Trouver le découpage optimal est un problème NP Hard. Aussi vaut-il mieux trouver une autre stratégie, par exemple un simple quadtree.

[bertry]

Salut,

Dans ce cas précis, pourquoi ne pas contourner le problème en recherchant une fonction qui permette de colorier une zone délimitée de ton image, au lieu de vouloir faire toi même un algo à base de rectangles? ( D'après ton post c'est un résultat rapide qui compte et non la méthode utilisée )

Si tu tiens à le faire toi même, sais-tu si la zone à colorier a des propriétés particulières? Y-a-t-il une seule zone ou plusieurs séparées?

Et enfin, si tu colorie ton dessin lignes par lignes ( rectangles de hauteur 1 ), tu peut optimiser un peut en vérifiant si la ligne au dessus est identique ( largeur et position ) à la ligne courante et si oui grouper ces deux lignes en un seul rectangle.