decouper un polygon en rectangles

Salut,
Je veux faire une fonction qui decoupe un polygon en rectangles et j'ai aucune idee .
on a juste le coordones (x,y) des coins du polygon dans un vecteur . qui sont trie par rapport a x .

structure qui contiens deux int x et y chaque couple (x et y ) represente un coin du poligon . le tous est trie du plus proche a 0 au loin dans un vecteur (on travail juste sur le cadran positif x>=0 et y>=0 ).
Il ce rectangle sera identifie par un vecteur de coins (x,y)
Merci

Citation:

---

Je veux faire une fonction qui decoupe un polygon en rectangles et j'ai aucune idee

---

C'est possible de faire ça avec un nombre fini de rectangles ? Si on prend comme polygone un triangle, comment fait-on ?

j'ai oublie de preciser ca
Je crois que l'image explique tous :D

http://i41.tinypic.com/fxh36c.jpg

Il s'agit donc bien de coordonnées entières, et de polygones qui sont forcément concaténation d'un nombre fini de rectangles? Et y a-t-il des règles spécifiques pour le découpage, comme "par coupes verticales uniquement", ou quelque chose dans le genre?

Oui, que des coupes verticales

Alors voilà un algo, supposant que tu partes du coin le plus à gauche et le plus haut (donc min des x, puis si plusieurs x min, max de y).

Code:

---

1 2 3 4 5 6 7 8 9 10 11

y = y1; //y1 = coordonnée y du premier coin x = x1; //x1 = coordonnée x du premier coin do { x = x + 1; }while (x != de l'abscisse d'un des autres coins)   do { y = y - 1; }while (y != de l'ordonnée d'un des autres coins && il existe des y plus petits avec l'abscisse x1)

---

A ce stade, (x, y1) et (x1, y) sont les coordonnées de deux coins opposés du premier rectangle, qui le définissent donc complètement.
Il suffit donc d'enregistrer ou afficher le résultat, puis passer au rectangle suivant, en cherchant les coordonnées du coin de la figure restante le plus à gauche puis le plus en haut (x min, et y max pour cette valeur de x).

A priori, ça marche pour faire ton découpage vertical à condition que ta figure initiale ne soit pas concave (donc pas en forme de U, par exemple). Si ça peut être le cas, il faut ajouter un ou deux tests supplémentaires.

Y a il pas de solution pour commnencer juste d'agauche sans la condition de haut ?

Je crois que dans le polygone B du dessin il y a un petit probleme pour passer au deuxieme rectangle

A priori, pas de problème... Enfin, je ne vois pas lequel, du moins.

Pour ce qui est de commencer ailleurs que le plus à gauche et le plus en haut, il n'y a pas de problèmes, il faut juste que tu décides une fois pour toutes d'où tu pars. Et ensuite, si tu pars par exemple dans le coin en bas à gauche, il faudra juste changer la décrémentation de y par une incrémentation (y = y + 1 au lieu de y = y - 1).

Pour passer au rectangle suivant, tu prends la dernière valeur de x retournée (qui marque donc l'endroit où l'on va couper le premier rectangle), et tu cherches les valeurs de y correspondantes à celle-ci. Tu prends la plus petite si tu veux commencer en bas, la plus grande si tu veux commencer en haut, et c'est reparti =)

merci beaucoup je vais essayer ce que tu m'a dit .
Si vous avez d'autres solutions n'hesitez pas a me dire