Division des polygones (problème d'Euler de la)

Prenez un hexagone convexe dont les sommets sont nommés A, B, C, D, E et F dans l'ordre. Depuis A, tracez les diagonales AC, AD et AE sans qu'elles se croisent. L'hexagone se partage alors en quatre triangles : ABC, ACD, ADE et AEF.

Ce découpage est une triangulation. D'autres choix de diagonales produisent d'autres triangulations, mais chacune contient toujours quatre triangles. La forme change ; le nombre de morceaux triangulaires ne change pas.

Une triangulation d'un polygone simple est un ensemble de diagonales intérieures qui ne se coupent pas, sauf à un sommet commun. Les triangles obtenus ont des intérieurs disjoints et recouvrent exactement le polygone. Si la lettre n désigne le nombre de sommets, avec n ≥ 3, toute triangulation contient n − 2 triangles et utilise n − 3 diagonales. Cette propriété vaut aussi pour un polygone simple non convexe, à condition de ne retenir que des diagonales situées à l'intérieur.

Le problème combinatoire consiste à compter les triangulations possibles. Pour un polygone convexe à n sommets, ce nombre est le nombre de Catalan d'indice n − 2, noté C_n−2 : $C_{n-2}=\frac{1}{n-1}\left(\genfrac{}{}{0px}{}{2n-4}{n-2}\right)C\_\{n-2\}=\backslash frac\{1\}\{n-1\}\backslash binom\{2n-4\}\{n-2\}$. Un hexagone convexe possède donc C₄ = 14 triangulations, chacune formée de quatre triangles.

Dans un polygone non convexe, certaines diagonales sortent de la figure et sont interdites : la formule de Catalan ne donne alors plus le nombre de triangulations. La triangulation reste toutefois un outil pour additionner les aires des triangles, organiser un rendu graphique et étudier les choix de diagonales.

Considérons l'hexagone convexe ABCDEF. Les données sont ses six sommets rangés dans cet ordre sur le contour et le sommet A choisi comme origine de l'éventail. Nous allons construire une triangulation, puis contrôler ses nombres.

1. Traçons depuis A les trois diagonales AC, AD et AE. Elles restent à l'intérieur de l'hexagone et ne se croisent qu'en A.

2. Lisons les quatre régions obtenues : ABC, ACD, ADE et AEF. La figure matérialise cette triangulation en éventail.

3. Avec n = 6 sommets, les formules donnent n − 3 = 3 diagonales et n − 2 = 4 triangles. Les valeurs observées concordent.

4. Comptons maintenant tous les découpages possibles de l'hexagone convexe : $C_4=\frac{1}{5}\left(\genfrac{}{}{0px}{}{8}{4}\right)=\frac{70}{5}=14C\_4=\backslash frac\{1\}\{5\}\backslash binom\{8\}\{4\}=\backslash frac\{70\}\{5\}=14$. La figure n'en montre qu'un. Pour un second contrôle de la triangulation dessinée, les quatre triangles totalisent 12 côtés comptés avec multiplicité : les 6 côtés du contour comptent une fois et les 3 diagonales deux fois, soit 6 + 2 × 3 = 12.

Calculer une aire. On choisit des diagonales intérieures, on calcule l'aire de chaque triangle, puis on additionne. Si le polygone est non convexe, une diagonale qui sort de la figure doit être remplacée par une diagonale admissible.

Préparer un rendu graphique. Un polygone complexe est décomposé en triangles, unités simples à traiter par les algorithmes de rendu. Si la surface est déjà triangulaire, aucune diagonale n'est nécessaire.

Compter des configurations. Pour un polygone convexe, les nombres de Catalan donnent directement le total des triangulations. Pour un polygone non convexe, il faut énumérer seulement les choix composés de diagonales intérieures compatibles.

Nombre de triangles et nombre de triangulations. Le premier est fixé par n − 2 ; le second compte les découpages distincts. Pour l'hexagone convexe, chaque triangulation a 4 triangles, mais il existe 14 triangulations.

Toutes les diagonales et diagonales d'une triangulation. Un polygone convexe à n sommets possède n(n − 3)/2 diagonales au total, mais une triangulation n'en retient que n − 3 sans croisement. L'hexagone a 9 diagonales au total ; l'éventail depuis A en utilise 3.

Triangulation et découpage quelconque. Une coupe qui produit un quadrilatère et deux triangles divise bien l'hexagone, mais ce n'est pas encore une triangulation. Le critère est que toutes les régions finales soient des triangles.

Le triangle est le cas charnière. Pour n = 3, les formules donnent un triangle et aucune diagonale. Il existe une seule triangulation, comptée par C₁ = 1 ; ajouter une diagonale serait impossible.

La convexité est indispensable au comptage par Catalan. Dans un polygone concave, une partie de certaines diagonales se trouve à l'extérieur. Le symptôme est visible dans la représentation : ces segments ne peuvent appartenir à une triangulation. Il faut compter seulement les diagonales intérieures compatibles.

Le polygone doit être simple. Si deux côtés non consécutifs se croisent, l'intérieur n'est plus celui d'un polygone simple et la règle des n − 2 triangles ne s'applique pas directement. Il faut d'abord traiter les intersections et définir les régions à décomposer.

Une diagonale admissible ne suffit pas à elle seule. Deux diagonales intérieures peuvent se croiser. Si un croisement apparaît ailleurs qu'à un sommet commun, il faut changer l'un des choix : une triangulation exige un ensemble entier de diagonales compatibles.

Le nombre de Catalan replace le comptage des triangulations convexes dans une famille qui apparaît dans plusieurs problèmes combinatoires.

La fiche Diagonale précise la nature des segments joignant deux sommets non consécutifs, qui servent à construire une triangulation.