Etape 2 – Entités géométriques

Il existe plusieurs techniques pour calculer l'aire d'un triangle. La plus connue est probablement celle consistant à multiplier la base du triangle par sa hauteur puis à diviser le résultat par deux.

Toutefois, lorsqu'un triangle est représenté par ses trois sommets, ce qui est le cas des triangles considérés plus bas, une technique plus simple de calculer cette aire consiste à utiliser le produit vectoriel. Pour la comprendre, considérons le triangle \(\triangle V_0 V_1 V_2\) de la figure ci-dessous.

Les vecteurs \(\vec{v} = \overrightarrow{V_0V_1}\) et \(\vec{w} = \overrightarrow{V_0V_2}\) sont bidimensionnels, il n'est donc pas possible de calculer leur produit vectoriel, cette opération n'étant définie que pour les vecteurs tridimensionnels. On peut toutefois rendre ces vecteurs tridimensionnels en leur ajoutant une troisième composante nulle. On obtient alors les deux vecteurs \(\vec{v_3}\) et \(\vec{w_3}\) suivants, où \(x_i\) et \(y_i\) sont les coordonnées du sommet \(V_i\) :

\[\vec{v_3} = \left(\begin{array}{c} x_1 - x_0\\ y_1 - y_0\\ 0 \end{array} \right)\ \vec{w_3} = \left(\begin{array}{c} x_2 - x_0\\ y_2 - y_0\\ 0 \end{array} \right)\]

Le produit vectoriel de ces deux vecteurs, \(\vec{v_3}\times\vec{w_3}\), vaut :

\[\vec{v_3}\times\vec{w_3} = \left(\begin{array}{c} 0\\ 0\\ (x_1 - x_0)(y_2 - y_0) - (x_2 - x_0)(y_1 - y_0) \end{array}\right)\]

Une propriété du produit vectoriel de deux vecteurs est que sa norme est égale à l'aire du parallélogramme engendré par ces vecteurs. Dès lors, l'aire du triangle \(\triangle V_0 V_1 V_2\), notée \(A(\triangle V_0 V_1 V_2)\) peut s'obtenir en divisant la norme de ce produit vectoriel par deux :

\begin{align} A(\triangle V_0 V_1 V_2)&= \frac{1}{2}\|\vec{v_3}\times\vec{w_3}\|\\ &= \frac{1}{2}\left|(x_1 - x_0)(y_2 - y_0) - (x_2 - x_0)(y_1 - y_0)\right| \end{align}

En supprimant la valeur absolue de la formule ci-dessous, on obtient une autre notion d'aire, que nous nommerons l'aire signée et que nous noterons \(A^±\). Cette aire signée est donc définie ainsi :

\[ A^{±}(\triangle V_0 V_1 V_2) = \frac{1}{2}\left((x_1 - x_0)(y_2 - y_0) - (x_2 - x_0)(y_1 - y_0)\right) \]

Comme son nom le suggère, l'aire signée peut être positive ou négative. Mais que signifie le signe ? En examinant les propriétés du produit vectoriel, on constate que ce signe est positif si et seulement si les sommets du triangle sont organisés dans le sens antihoraire¹.

Ainsi, étant donnés les trois points de la figure 2, l'aire signée du triangle \(\triangle V_0 V_1 V_2\) est positive, tandis que l'aire signée du triangle \(\triangle V_0 V_2 V_1\) est négative. En valeur absolue, ces deux aires signées sont bien entendu égales. Elles sont donc liées par la relation suivante :

\[ A^{±}(\triangle V_0 V_1 V_2) = -A^±(\triangle V_0 V_2 V_1) \]

Bien entendu, toute rotation de la liste des sommets du triangle préserve le signe. On a donc également :

\[ A^{±}(\triangle V_0 V_1 V_2) = A^±(\triangle V_1 V_2 V_0) = A^±(\triangle V_2 V_0 V_1) > 0 \]

et :

\[ A^{±}(\triangle V_0 V_2 V_1) = A^±(\triangle V_2 V_1 V_0) = A^±(\triangle V_1 V_0 V_2) < 0 \]

L'utilité de cette notion d'aire signée n'est pas apparente au premier abord, mais deviendra évidente plus bas.

Une ligne passant par deux points distincts \(P_1\) et \(P_2\) partitionne le plan en trois parties :

1. les points se trouvant sur la ligne,
2. les points se trouvant (strictement) à gauche de la ligne, lorsque celle-ci est parcourue de \(P_1\) à \(P_2\),
3. les points se trouvant (strictement) à droite de la ligne, lorsque celle-ci est parcourue de \(P_1\) à \(P_2\).

Cette partition est illustrée sur l'extrait du plan ci-dessous, qui montre l'ensemble des points se trouvant à gauche de (en rouge), à droite de (en vert) et sur (en noir) la ligne passant par \(P_1\) et \(P_2\), lorsqu'elle est parcourue dans ce sens. Par exemple, le point \(P\) se trouve à gauche de cette ligne.

Pour déterminer la position d'un point \(P\) par rapport à une ligne orientée passant par \(P_1\) puis \(P_2\), on peut utiliser l'aire signée du triangle \(\triangle P P_1 P_2\). Comme cela a été dit plus haut, celle-ci est positive si et seulement si les points \(P\), \(P_1\) et \(P_2\) sont orientés dans le sens antihoraire, c-à-d si \(P\) est à gauche de la ligne \(P_1\), \(P_2\).

Donc, si \(P=(x, y)\) et \(P_i=(x_i, y_i)\), alors le point \(P\) est à gauche de la ligne \(P_1\), \(P_2\) si et seulement si :

\begin{align} & A^±(\triangle P P_1 P_2) > 0\\ \Leftrightarrow & \tfrac{1}{2}\left((x_1 - x)(y_2 - y) - (x_2 - x)(y_1 - y)\right) > 0\\ \Leftrightarrow & (x_1 - x)(y_2 - y) - (x_2 - x)(y_1 - y) > 0\\ \Leftrightarrow & (x_1 - x)(y_2 - y) > (x_2 - x)(y_1 - y) \end{align}

Une manière simple et élégante de déterminer l'aire (signée) d'une polyligne fermée consiste à choisir un point \(P\) quelconque du plan puis à additionner les aires signées de tous les triangles formés par ce point et les deux extrémités de chaque segment de la polyligne. Pour illustrer cette procédure, considérons la polyligne fermée à 7 sommets — \(V_0\) à \(V_6\) — de la figure ci-dessous.

On peut maintenant choisir un point \(P\) quelconque du plan, par exemple situé en-dessous de la polyligne pour faciliter le dessin. Cela fait, il est possible de dessiner les 7 triangles composés du point \(P\) et des extrémités des segments de la polyligne, à savoir \(\triangle P V_0 V_1, \triangle P V_1 V_2, \ldots, \triangle P V_6 V_0\). Les quatre premiers d'entre-eux ont une aire signée négative, tandis que les trois derniers ont une aire signée positive. Cela est illustré dans les deux images de la figure ci-dessous, où les triangles à aire négative apparaissent en rouge, tandis que ceux à aire positive apparaissent en vert. Pour faciliter la lecture, ces deux types de triangles sont représentés sur des images séparées.

Il est clair qu'en additionnant les aires (signées) de tous ces triangles on obtient l'aire de la polyligne. Notez qu'elle est ici positive, car ses sommets sont orientés dans le sens antihoraire. Si ceux-ci étaient orientés dans le sens horaire, l'aire obtenue serait négative.

Etant donné que le point \(P\) est arbitraire, on peut choisir d'utiliser l'origine du plan \(O = (0, 0)\) afin de simplifier les formules. L'aire signée de la polyligne fermée \(L=(V_0, V_1, \ldots, V_n)\) où \(V_i = (x_i, y_i)\) s'obtient alors simplement en sommant l'aire des triangles décrits plus haut :

\begin{align} A^±(L) &= \sum_{i=0}^{n} A^±(\triangle O V_i V_{i+1})\\ &= \sum_{i=0}^{n} \frac{1}{2}\left((x_i - 0)(y_{i+1} - 0) - (x_{i+1} - 0)(y_i - 0)\right)\\ &= \sum_{i=0}^{n} \frac{1}{2}\left(x_i y_{i+1} - x_{i+1} y_i\right)\\ &= \frac{1}{2} \sum_{i=0}^{n}\left(x_i y_{i+1} - x_{i+1} y_i\right) \end{align}

Notez que les indices des sommets sont à prendre modulo \(n + 1\). Par exemple, le dernier terme de la somme ci-dessus est \(x_n y_{n+1} - x_{n+1} y_n\). Toutefois, le dernier sommet portant l'indice \(n\), \(x_{n+1}\) désigne en réalité \(x_0\). Il en va de même pour \(y_{n+1}\).

En réorganisant les termes de la formule ci-dessus, on obtient la version ci-dessous, plus rapide à calculer car comportant moins de multiplications :

\[ A^±(L) = \frac{1}{2}\sum_{i=0}^{n} x_i(y_{i+1} - y_{i-1}) \]

L'aire conventionnelle, c-à-d positive, s'obtient simplement en prenant la valeur absolue de l'aire signée :

\begin{align} A(L) &= \left|A^±(L)\right|\\ &= \frac{1}{2}\left|\sum_{i=0}^{n} x_i(y_{i+1} - y_{i-1})\right| \end{align}

Il existe plusieurs algorithmes permettant de tester si un point se trouve ou non à l'intérieur d'une polyligne fermée. Celui décrit ci-dessous utilise la notion d'indice d'une courbe par rapport à un point.

L'indice (winding number en anglais) d'une courbe fermée par rapport à un point est le nombre de tours, dans le sens antihoraire, que la courbe fait autour de ce point. L'animation ci-dessous illustre ce concept dans le cas d'une courbe (rouge) dont l'indice par rapport au point sur lequel se trouve l'observateur vaut 2. En effet, comme le montre l'animation, l'observateur tourne deux fois sur lui-même dans le sens antihoraire lorsqu'il suit des yeux un point parcourant la courbe.

L'indice permet de déterminer si un point se trouve à l'intérieur ou à l'extérieur de la surface délimitée par une courbe fermée. En effet, un point se trouve à l'extérieur d'une courbe si et seulement si l'indice de la courbe par rapport à ce point vaut 0.

Pour calculer l'indice d'une courbe fermée par rapport à un point \(P\), on peut faire l'observation suivante : si on trace un rayon infini à partir de \(P\) dans une direction quelconque, l'indice est donné par la somme des intersections signées entre la courbe et ce rayon. Cette somme se calcule en additionant 1 chaque fois que la courbe intersecte le rayon dans le sens antihoraire, et en soustrayant 1 chaque fois que la courbe intersecte le rayon dans le sens horaire.

La figure 7 ci-dessous illustre ce calcul pour la courbe et le point de la figure 6 plus haut. Le rayon \(R\) choisi est ici horizontal et il intersecte la courbe en quatre points nommés \(I_1\) à \(I_4\). Etant donné qu'en les points \(I_1\), \(I_3\) et \(I_4\) la courbe intersecte \(R\) dans le sens antihoraire, tandis qu'en \(I_2\) elle l'intersecte dans le sens horaire, l'indice vaut 3 – 1 = 2.

Cette technique du calcul de l'indice est particulièrement simple à mettre en œuvre dans le cas où la courbe est une polyligne fermée, cas qui nous intéresse ici. En effet, il suffit alors de trouver tous les segments de la polyligne qui intersectent le rayon horizontal partant du point, puis de déterminer pour chacun d'eux le sens de l'intersection afin de calculer la somme des intersections signées et d'obtenir ainsi l'indice recherché.

En pratique, il est en fait plus simple de trouver tous les segments qui intersectent la ligne (et pas le rayon) horizontale passant par le point \(P\), puis de déterminer le sens de chaque intersection. Ensuite, on ajoute 1 à l'indice si et seulement si l'intersection est à la montée et \(P\) se trouve à gauche du segment. De même, on soustrait 1 à l'indice si et seulement si l'intersection est à la descente et \(P\) se trouve à droite du segment, c-à-d à gauche du segment inversé.

L'algorithme ci-dessous utilise cette technique pour déterminer si un point \(P\) se trouve ou non à l'intérieur d'une polyligne fermée \(L\), en calculant d'abord l'indice de \(L\) par rapport à \(P\) avant de le comparer avec 0.

 1: est_intérieur(P, L) :
 2:   indice = 0
 3:   pour chaque segment S = (P1, P2) de L :
 4:     si P1.y <= P.y :
 5:       si P2.y > P.y et P à gauche de (P1, P2) :
 6:         indice = indice + 1
 7:     sinon :
 8:       si P2.y <= P.y et P à gauche de (P2, P1) :
 9:         indice = indice - 1
10:   retourne (indice != 0)