Algorithme de l'intersection.

Algorithme de l'intersection:

Description :

Chaque case est a l'intersection d'une ligne et d'une colone. Chaque case vide ne peut peut contenir qu'un chiffre non présent sur sa ligne et sa colone, cette technique doit être appliquée a chaque case vide.

Algorithme:

1-Choisir une ligne.

2-Vérifier s' il y a une case vide sur cette ligne.

3- Si un case est vide, alors comparer les chiffres de la ligne de la case vide aux chiffres de la colone de cette même case.

4- Si un seul chiffre est manquant alors il ne peut que correspondre qu'aux chiffre manquant.

Algorithme de la paire exclusive:

Description :

Pour chaque deux cases vides d'une même ligne, d'une colone ou d'un carré ne peut contenir que deux même chiffre. Alors les autres chiffres de cette colone, de cette ligne ou de ce carré ne peuvent pas contenir ces deux chiffres.

Algorithme:

1-Choisir une ligne.

2-Vérifier s' il y a des cases vide sur cette ligne.

3-Comparer les chiffres avec les autres du même carré et de la même colone.

4-Si seulment deux chiffres peuvent corresponde a une endroit précis dans la ligne, dans la colone ou dans le carré, alors les autres case vide doivent contenir les autres chiffres.

L’algorithme de Greiner-Hormann est utilisé en infographie pour découper des polygones1. Il est plus performant que l’algorithme de Vatti, mais ne peut pas gérer d’éventuels cas dégénérés2. Il peut cependant être utilisé avec des polygones s’auto-intersectant et n'étant pas convexes. Il peut facilement être généralisé afin d’effectuer d’autres opérations booléennes sur les polygones, telles que l’union et la différence.

L’algorithme est basé sur la définition d’« intérieur » d’un polygone, elle-même basée sur la notion d’indice. Il considère les régions d’indice pair comme étant à l’intérieur du polygone : ceci est également connu sous le nom de règle du pair-impair. L’algorithme prend deux listes de polygones en entrée, chaque polygone étant lui-même représenté comme une liste de sommets reliés.

Dans sa formulation initiale, l’algorithme est divisé en trois phases :

Dans la première phase, les intersections entre les côtés des polygones sont calculées. Des sommets sont rajoutés aux points d’intersection, et chacun est muni d’un pointeur vers son homologue situé dans l’autre polygone.

Dans la deuxième phase, chaque intersection est marquée comme étant soit une intersection d’entrée, soit une intersection de sortie. Cette décision est prise en appliquant la règle du pair-impair au premier sommet, puis en traversant le polygone en alternant le marquage (à une intersection d’entrée doit suivre

...