[algorithmie] 2D colorier l'intérieur d'un polygone (fermé)

Recherche :

Dernière réponse
Sujet : [algorithmie] 2D colorier l'intérieur d'un polygone (fermé)
farib	oui, DSL j'ai pas répondu, les explications sont claires, et le reste fourni avec est également tres intéressant ( j'aimerais bien air e le TP 3D dans mon école :D )

Votre réponse

Nom d'utilisateur

Pour poster, vous devez être inscrit sur ce forum .... si ce n'est pas le cas, cliquez ici !

Le ton de votre message

Votre réponse

Smilies

Liste des smilies perso
Wiki smilies
Chercher un smiley

Options

Activer votre signature
Désactiver les smilies
Activer la notification par email du sujet

Aperçu

Vous avez perdu votre mot de passe ?

Vue Rapide de la discussion

farib

oui, DSL j'ai pas répondu, les explications sont claires, et le reste fourni avec est également tres intéressant ( j'aimerais bien air e le TP 3D dans mon école :D )

Carbon_14

Le sommet de tout polygône est aussi le sommet d'un triangle qui a les deux segments/côtés communs.
Si le point considéré appartient à TOUS les triangles qui ont pour sommet les points du polygone, il est dans le polygone.
Si concave, plus facile car direct. Convexe, faut voir...

rufo

farib a écrit a écrit :

j'ai vu en effet déja des topics sur les triangles....

j'ai déja dnas mes cartons un algo qui dit si un pt est a l'intérieur d'un triangle, maintenant il faut que je triangurlarise un polygone....c cho :lol:

fo ke je réfléchisse a un algo

t'as reçu ce que je t'ai envoyé? Si oui, ça t'a aidé?

bjone

pour traçer un triangle en 2D, vo mieux pas passer par une routine qui teste si un point est dans un triangle :D

farib

j'ai vu en effet déja des topics sur les triangles....

j'ai déja dnas mes cartons un algo qui dit si un pt est a l'intérieur d'un triangle, maintenant il faut que je triangurlarise un polygone....c cho :lol:

fo ke je réfléchisse a un algo

Carbon_14

C'est ce que je sous-entendais :ange:.

Si le polygone est concave, ça complique le module d'appartenance, sauf qu'il suffit de prendre le rectangle qui le contient pour l'exploration.

Il vaut mieux faire comme avec un pinceau à la main que de chercher des ruses tarabiscotées.

tomlameche

carbon_14 a écrit a écrit :

Si on fait
for (y = 0 to YMax)
for (x = 0 to XMax)
if (PointDansPolygone(x,y) = TRUE) then
CouleurPoint(x,y) = CouleurDesirée
next x
next y

c'est pas bon ?

Il faut "juste" coder la fonction PointDansPolygone() en ne prenant pas les traits de bordure si y en a :).

Tu peux faire pareil en limittant la boucle : en prenant y à partir du YMax du polygone et x à partir du XMax. ca devrai pas être trop compliqué de connaitre le carré ou le rectangle dans lequel s'inscrit ton polygone, surout s'il est construit segment par segment ( tu récupère les Xmax et YMax à chaque fois qu'on ajoute un segement ).

bjone

Première chose: oublie la récursivité, pour ce genre de truc il vaux mieux une approche itérative, et ça évite de vautrer la pile....

bjone

bon:

1) Est-ce que ton polygone est connu ?
du style tu as une liste (x,y) de pt1,pt2,pt3,pt4....

2) Ou est que tu veux vraiment faire un floodfill, du style tu as un contour fermé qu'il soit en segments linéaires, en coube, ou sgui-sgui-sgui, tu tu veux colorer toute la surface contenue dans le contour... Ou plustôt colorier à la couleur B touts les pixels de la couleur A ou tu as cliqué avec la souris, qui sont aussi en "contact" le pixel ?

Pour la 1, il faut faire un traçage ligne par ligne (scanline),
tu tries tes points par le Y de haut en bas, et tu traçes tes lignes horizontales, de de haut en bas, en résolvant le X de début et de fin de ta ligne, en fonction des segments à "gauche" et à "droite" de ta ligne.

Pour la 2, à partir d'un clic à une position X,Y, pour refaire le floodfill fo partir du point au ta cliquer et se propager au niveau des lignes en haut en bas à partir de ce point...
Tu colories tous les pixels A en B, et tu regardes pour la propagation vers le haut, si la ligne plus haut que la courante à des pixels à la couleur A en contact avec des pixels à la couleur A de la ligne courante....
Symétrique pour la propgation vers le bas...

enfin c'est des idées...

Mais la première chose à faire c'est bien indentifier ce que tu dois faire....

Krueger

Tu vas parcourir toute ton image pour un polygone. S'il est très petit, il y a beaucoup plus efficace, même si ça marche.

Carbon_14

Si on fait
for (y = 0 to YMax)
for (x = 0 to XMax)
if (PointDansPolygone(x,y) = TRUE) then
CouleurPoint(x,y) = CouleurDesirée
next x
next y

c'est pas bon ?

Il faut "juste" coder la fonction PointDansPolygone() en ne prenant pas les traits de bordure si y en a :).

Krueger

Le remplissage par ligne, c'est pas celui avec l'histoire d'empilement de "germes"?

farib

pas con le remplissage par ligne...

sinon pour mon "récursif", la profondeur maximale d'appel serait la dimension maximale de l'image.... ca peut aller, 1000 appels d'un tout petit algo, ca va pas surcharger la pile....

rufo	j'avais fait ça pour un petit moteur 3D en VC++ (sans directX)

rufo	le mieux, c'est l'algo de remplissage par des lignes horizontales entre 2 côtés du polygone. J'avais trouvé ça sur un site très bien fait pour la 2D et 3D. Si tu veux, file moi ton e-mail, et je pourrais t'envoyer le source et l'algo... :)

farib

sinon le vrai algo c'est quoi ?
en fait, je souhaite réinventer la roue pour mon ego :D

zion

Benh quoi, que tu utilises un Canvas ou Windows ou l'équivalent sous QT tu as toujours un FloodFill, alors pourquoi te casser le cul à le refaire.

Enfin, sinon la solution récursive c'est ptre pas géant, ca risque de faire beaucoup... Enfin si tu veux un bon exemple, télécharge GD, y a les sources évidemment ;)

farib

ug ?

zion	Le FloodFill ca te dit rien? Pourquoi réinventer la roue? ;)

farib

voila je me demande comment colorier tous les points a l'intérieur d'un polygone fermé, comme avec le "pot de peinture" dans un logiciel de dessin

je pensais un un algo un peu récursif : je trouve un point a l'intérieur du polygone, et je colorie ses voisins de maniere récursive jusqu'a trouver un bord, et ainsi de suite

Voisin Voisin Voisin
Voisin Point Voisin
Voisin Voisin Voisin

est-ce une bonne idée ? sera-ce suffisemment rapide au aurais-je assez de mémoire ?

faut-il que j'emprunte un voir completement différente ?

bref, vos avis sont les bienvenus