Orientation de courbe
En mathématiques, une courbe orientée positivement est une courbe fermée simple plane (c'est-à -dire une courbe dans le plan dont le point de départ est également le point final et qui n'a pas d'autres intersections propres) de telle sorte que lorsque l'on se déplace dessus, on a toujours la courbe intérieur à gauche (et par conséquent, la courbe extérieure à droite). Si dans la définition ci-dessus on échange gauche et droite, on obtient une courbe orientée négativement .
L'élément crucial de cette définition est le fait que chaque courbe fermée simple admet un intérieur bien défini qui découle du théorème de Jordan.
Toutes les courbes fermées simples peuvent être classées comme orientées négativement (dans le sens des aiguilles d'une montre), orientées positivement (dans le sens inverse des aiguilles d'une montre) ou non orientables. La boucle intérieure d'une route périphérique en France (ou dans d'autres pays où les gens conduisent du côté droit de la route) serait un exemple de courbe orientée négativement (dans le sens des aiguilles d'une montre). Un cercle orienté dans le sens antihoraire est un exemple de courbe orientée positivement. Le même cercle orienté dans le sens des aiguilles d'une montre serait une courbe orientée négativement.
Le concept d'orientation d'une courbe n'est qu'un cas particulier de la notion d'orientation d'une variété (c'est-à -dire qu'en plus de l'orientation d'une courbe on peut aussi parler d'orientation d'une surface, d'une hypersurface, etc.). Ici, l'intérieur et l'extérieur d'une courbe héritent tous deux de l'orientation habituelle du plan. L'orientation positive sur la courbe est alors l'orientation dont elle hérite comme frontière de son intérieur ; l'orientation négative est héritée de l'extérieur.
Orientation d'un polygone simple
En deux dimensions, étant donné un ensemble ordonné d'au moins trois sommets (points) connectés (comme dans relier les points) qui forme un polygone simple, l'orientation du polygone résultant est directement liée au signe de l'angle à tout sommet de l'enveloppe convexe du polygone, par exemple de l'angle ABC dans l'image. Dans les calculs, le signe du plus petit angle formé par une paire de vecteurs est généralement déterminé par le signe de la composante du produit vectoriel des vecteurs sur la normale au plan. Ce dernier peut être calculé comme le signe du déterminant de leur matrice d'orientation. Dans le cas particulier où les deux vecteurs sont définis par deux segments de ligne d'extrémité commune, tels que les côtés BA et BC de l'angle ABC dans notre exemple, la matrice d'orientation peut être définie comme suit:
Une formule pour son déterminant peut être obtenue, par exemple, en utilisant la formule de Laplace [méthode de développement suivant une ligne (ou colonne)] :
Si le déterminant est négatif, alors le polygone est orienté dans le sens des aiguilles d'une montre. Si le déterminant est positif, le polygone est orienté dans le sens antihoraire. Le déterminant est non nul si les points A, B et C ne sont pas colinéaires. Dans l'exemple ci-dessus, avec des points ordonnés A, B, C, etc., le déterminant est négatif et donc le polygone est dans le sens des aiguilles d'une montre.
Considérations pratiques
Dans les applications pratiques, les considérations suivantes sont généralement prises en compte.
Il n'est pas nécessaire de construire l'enveloppe convexe d'un polygone pour trouver un sommet approprié. Un choix courant est le sommet du polygone avec la plus petite coordonnée X. S'il y en a plusieurs, celui avec la plus petite coordonnée Y est choisi. Il est garanti qu'il s'agit d'un sommet de l'enveloppe convexe du polygone. Alternativement, le sommet avec la plus petite coordonnée Y parmi ceux avec les coordonnées X les plus grandes ou le sommet avec la plus petite coordonnée X parmi ceux avec les coordonnées Y les plus grandes (ou tout autre des 8 "plus petits, plus grands" X / Combinaisons Y) feront également l'affaire. Une fois qu'un sommet de l'enveloppe convexe est choisi, on peut alors appliquer la formule en utilisant les sommets précédent et suivant, même si ceux-ci ne sont pas sur l'enveloppe convexe, car il ne peut y avoir de non convexité locale sur ce sommet.
Si l'orientation d'un polygone convexe est recherchée, alors, bien sûr, n'importe quel sommet peut être sélectionné.
Pour des raisons numériques, la formule équivalente suivante pour le déterminant est couramment utilisée:
Cette dernière formule a quatre multiplications de moins. Ce qui est plus important dans les calculs informatiques impliqués dans la plupart des applications pratiques, telles que l'infographie ou la CAO, les valeurs absolues des multiplicateurs sont généralement plus petites (par exemple, lorsque A, B, C sont dans le même quadrant), donnant ainsi une valeur numérique d'erreur plus petite ou, dans les cas extrêmes, évitant le dépassement de capacité.
Lorsqu'on ne sait pas à l'avance que la séquence de points définit un polygone simple, les points suivants doivent être gardés à l'esprit.
Pour un polygone se recoupant lui-même (polygone non simple) (ou pour toute courbe se recoupant elle-même), il n'y a pas de notion naturelle de "l'intérieur", donc l'orientation n'est pas définie. En même temps, en géométrie et en infographie, il existe un certain nombre de concepts pour remplacer la notion d '« intérieur » pour les courbes fermées non simples ; voir, par exemple, " algorithme de remplissage par diffusion " et " indice (analyse complexe) ".
Dans les cas "modérés" de recoupement propre, avec des sommets dits "dégénérés" correspondant à trois points consécutifs autorisés sur la même ligne droite et formant un angle de zéro degré, le concept d'"intérieur" a toujours du sens, mais une attention particulière doit être apportée dans la sélection de l'angle testé. Dans l'exemple donné, imaginez que le point A se trouve sur le segment BC. Dans cette situation, l'angle ABC et son déterminant seront 0, donc inutiles. Une solution consiste à tester des coins consécutifs le long du polygone (BCD, DEF, ...) jusqu'à ce qu'un déterminant non nul soit trouvé (à moins que tous les points ne se trouvent sur la même ligne droite) (Notez que les points C, D, E sont sur la même ligne et forment un angle de 180 degrés avec un déterminant nul).
Convexité locale
Une fois que l'orientation d'un polygone formé à partir d'un ensemble ordonné de sommets est connue, la non convexité d'une région locale du polygone peut être déterminée en utilisant une seconde matrice d'orientation. Cette matrice est composée de trois sommets consécutifs dont la convexité est examinée. Par exemple, dans le polygone illustré ci-dessus, si nous voulions savoir si la séquence de points FGH est non convexe, convexe ou colinéaire (plate), nous construisons la matrice
Si le déterminant de cette matrice est 0, alors la séquence est colinéaire - ni non convexe ni convexe. Si le déterminant a le même signe que celui de la matrice d'orientation pour tout le polygone, alors la séquence est convexe. Si les signes diffèrent, la séquence est non convexe. Dans cet exemple, le polygone est orienté négativement, mais le déterminant pour les points FGH est positif, et donc la séquence FGH est non convexe.
Le tableau suivant illustre les règles permettant de déterminer si une séquence de points est convexe, non convexe ou plate:
| Polygone orienté négativement (sens horaire) | Polygone orienté positivement (sens antihoraire) | |
|---|---|---|
| le déterminant de la matrice d'orientation pour les points locaux est négatif | séquence convexe de points | séquence non convexe de points |
| le déterminant de la matrice d'orientation pour les points locaux est positif | séquence non convexe de points | séquence convexe de points |
| le déterminant de la matrice d'orientation pour les points locaux est 0 | séquence colinéaire de points | séquence colinéaire de points |