Parfois, il est intéressant de savoir si un point est sur une droite, avant ou après. Dans mon moteur Build-like pour mon musée virtuel, par exemple, détecter cela entre dans le système de décision du sens du dessin. Si un polygone est dessiné dans un sens, il sera considéré à l’endroit (normales dirigées vers l’intérieur) ou dessiné dans l’autre sens, il sera considéré comme à l’envers (normales dirigées vers l’extérieur). J’expliquerais ce système de décision dans un autre article qui marie la technique pour trouver le sens d’un segment et celle présenté ici 🙂

Dans le dessin ici présent, on peut voir une droite et trois points. Le point A et avant la droite, soit négatif. Le point B est sur la droite, soit à zéro. Le point C est après la droite, soit positif. Pour calculer le signe du rapport entre le point et la droite, il faut d’abord calculer l’équation cartésienne de la droite à partir d’un vecteur de cette droite. Prenons un segment et calculons son vecteur directeur. J’explique cela dans l’article Calculer la norme, la normale et le milieu d’un segment. Voici comment déterminer l’équation cartésienne de ce vecteur directeur non horizontale, ni verticale. Ces deux cas particuliers seront déterminés ensuite.

Voilà, une fois cette équation obtenue il s’utilise simplement en plaçant des coordonnées du point à détecter sur ou autour de la droite à la place y et x et déplacer y dans l’équation de sorte à obtenir un nombre inférieur, égal ou supérieur à zéro.

Avant d’expliquer avec un schéma où se situe la positif et le négatif pour les différentes droites possibles, voici comment traiter les droites horizontale et verticale.

Pour l’utilisation de ces équations, il n’y a pas de difficulté pour la droite verticale, par contre pour la droite horizontale, il y a un sens à respecter pour obtenir un résultat signé correctement comme vous le verrez sur le schéma qui suivra.

La logique de ces équations ressort dans le schéma suivant. Dans un repère avec X allant de gauche à droite, et Y allant de haut en bas, cela se passe comme suit. Pour la droite horizontale, le signe positif se trouve à droite et le négatif à gauche. Pour la droite horizontale, le signe positif se trouve en haut et le négatif en bas. Le sens est inversé par rapport au repère pour cette droite. Enfin, les autres droites, en les imaginant tourner de la droite verticale en partant d’en haut (au-dessus de zéro), et tournant vers la gauche, le positif est donc à droite de la droite, parties bleue et rouge confondus. Une fois que le haut (bleu) de la droite dépasse la droite horizontale, toujours en tournant vers la gauche, donc se trouve en dessous, le positif est au-dessus de la droite et le négatif en dessous, et tend vers la droite du repère. La rotation s’arrête peu avant de revenir à une droite verticale, autrement le positif à gauche pour la partie bleue de la droite en bas change de côté. C’est visible pour la partie rouge de la droite verticale qui suit le sens de sa partie bleue.

Ce principe rappelle mon schéma pour le Calcul du sens d’un segment, à la différence que l’axe des changements de sens n’est pas l’axe des X, mais celui des Y. En adaptant ce schéma du sens d’un segment à celui-ci, j’ai pu marier les deux techniques et concevoir mon système de prise de décision du sens du dessin et de où se trouve l’intérieur et l’extérieur d’un secteur dessinés sans  que nous utilisateurices n’ayons à nous soucier du sens du dessin. Ce sera expliqué au prochaine article 🙂

Dans cet article on va parler de comment calculer simplement la norme, la normale et le milieu d’un segment en 2 dimensions. L’intérêt est multiple, mais en ce moment, ces trois calculs me servent à afficher les normales des murs des secteurs dans l’éditeur de mon moteur de musée virtuel. Je m’en suis servit en partie dans Demiurge, en 3D, sauf pour la normale qui nécessite l’utilisation d’un produit en croix pour les surfaces (cross product en anglais).

Le milieu d’un segment

Commençons par le milieu d’un segment qui ne nécessite pas les deux autres pour être calculé. En 2D, pour calculer simplement le milieu d’un segment, il suffit tout d’abord de ramener le segment à son vecteur directeur, ici non normalisé, comme on la vue dans l’article sur le calcul du sens d’un segment. L’équation est simple, je le rappelle ici :

Ce vecteur, contrairement, au segment (sauf cas particulier) a sa position aux coordonnées (0, 0) et donc les coordonnées de la pointe du vecteur correspondent logiquement à la soustraction du deuxième point du segment par le premier point. Il s’agit d’une simplification du segment qui permet de lui faire toutes sortes de choses et notamment trouver le milieu, mais aussi sa normale. Mais, on verra après pour la normale 🙂

Pour trouver le milieu du segment, il reste deux étapes toutes simple. La première consiste à diviser par 2 les coordonnées du vecteur non normalisé. Ainsi, on obtient la moitié du vecteur. Puis, la deuxième et dernière étape consiste à ramener le vecteur à sa place en l’additionnant avec le premier point du segment.

La norme du segment

La norme d’un segment est la distance entre le premier et le deuxième point qui le constitue. C’est à dire, pour faire simple, sa longueur. Peu importe que votre segment se trouve sur une grille de pixels, et donc soumis à un repère, il s’agit là de la longueur que vous obtiendriez si vous aviez une règle est mesureriez le segment 🙂

La formule de la norme est un peu plus compliqué et gourmand en ressources pour un ordinateur que ce qu’on a fait précédemment. Heureusement pour nous, elle a au moins le mérite de tenir sur une seule ligne :p

Je le réécris différemment pour plus de lisibilité et de compréhension.

J’ai utilisé ici le vecteur de tout à l’heure. En effet, on ne calcule pas directement la norme d’un segment, mais celui de son vecteur non normalisé. Et si depuis tout à l’heure je n’ai pas normalisé mon vecteur, c’est précisément parce que normaliser signifie qu’on le ramène à une norme de 1, hors nous voulons mesurer notre segment, ce serait donc absurde 🙂

Avec une norme on peut faire le calcul du milieu du segment d’une façon différente que la méthode précédente, mais aussi faire d’autres choses comme calculer la trajectoire d’un projectile par exemple. Cependant, pour y arriver, il va normaliser le vecteur. Je vais vous expliquer comment en même temps que le calcul de la normale d’un segment ou d’une droite 🙂

Normaliser un segment et calculer sa normale

Comme je l’ai dit tout à l’heure, normaliser un vecteur, c’est mettre sa norme à 1. Et pour faire cela, rien de plus simple 🙂

Voilà, c’est fait 😀 Il suffisait tout simplement de diviser les coordonnées du vecteur précédemment obtenu. C’est assez logique, puisque la norme est la longueur du vecteur de départ. Et c’est pour cette raison qu’un vecteur normalisé est très utile pour une trajectoire de projectile par exemple, puisque entre le moment où un personnage fait feu et un instant T, le projectile aura parcouru une certaine distance. Ainsi, connaître son vecteur directeur permet de simplement le multiplier par la distance parcouru pour trouver les coordonnées du projectile :p Si vous voulez par exemple, afficher un objet se déplaçant suivant un vecteur, vous pouvez associer une distance pour chaque quantum de temps (fraction du temps) et additionner ces distances à chaque instant pour ensuite le multiplier par le vecteur. A chaque quantum de temps, votre ordinateur affichera votre objet aux bonnes coordonnées et vous le verrez se déplacer sur votre trajectoire. Ajoutez à ceci, un vecteur de gravité, qui irait toujours vers le bas, soit ceci (0, y), et vous aurez la base d’un jeu de missile, sniper ou d’archer, et une part non négligeable d’un Worms x)

Bon, je vous raconte tout ça, mais il me reste un truc à vous expliquer. C’est le calcul de la normale au segment, ou plus tôt au vecteur. La normale d’un vecteur est un vecteur perpendiculaire au premier. Là encore, en 2 dimensions, trouver la normale d’un vecteur est simplicime. Voici la formule :

Et voilà, hihihihi 😀 Tout simplement, la coordonnées X de la normale est égale à la coordonnées Y en négatif du vecteur directeur, et la coordonnées Y de la normale est égale à la coordonnées X du vecteur directeur. Ni plus, ni moins 🙂 Il n’y a donc pas réellement de calcules à faire, mais juste des assignations de valeurs.

C’est lorsqu’on fait des tests sur un papier ou à l’écran, qu’on comprend l’utilité de calculer le sens d’un segment comme je l’ai proposé en premier article de la série sur l’algorithmie. En effet, si vous placez les points de votre segment dans un ordre ou dans un autre, vous changerez nécessairement l’ordre de ces derniers dans les opérations précédemment expliqué ici. Ainsi, votre normale ne sera pas dans le même sens non plus. Pour un ligne horizontale par exemple, la normale sera soit vers le haut, soit vers le bas, selon l’ordre dans lequel vous avez entré vos deux points du segment. Cette propriété peut provoquer des erreurs d’affichages, de physique dans un moteur physique, mais aussi, bien exploitée, permettre de déterminer l’intérieur et l’extérieur d’un monde comme dans mon moteur de musée 🙂

Bonus : Dessiner une normale au milieu d’un segment

Je vous mets un petit algorithme qui utilise tout ce qui est au-dessus pour dessiner la normale d’un segment.

Si les unités de votre dessin sont les pixels, la normale ne fera qu’un seule pixel et dans certains cas, il ne pourra pas s’afficher. Vous pouvez donc multiplier ses coordonnées par un nombre raisonnable pour bien voir la ligne s’afficher et apprécier la perpendiculaire a votre segment 🙂

Dans ma reproduction du moteur Build de Ken Silverman pour mon musée virtuel, j’ai eu besoin de déterminer le sens d’un segment. Je définis le sens du segment par est-ce que le segment va du point A au point B, ou du point B au point A. L’intérêt de savoir cela permet, dans mon moteur, de décider où se trouve l’intérieur et l’extérieur d’un polygone qui définit un secteur du musée. Lorsqu’on dessine un secteur, on ne fait pas toujours attention à l’ordre dans lequel on place les points qui le compose. Pour donner un exemple de l’intérêt de respecter l’ordre des points, dans OpenGL, placer les points dans un sens détermine la recto ou le verso d’un polygone, ce qui permet entre autres d’afficher l’un ou l’autre ou les deux. Dans mon moteur, en dessinant un secteur, si on se trompe dans l’ordre des points, l’intérieur ou l’extérieur seront inversés.

Comment faire simplement une détermination automatique du sens d’un segment pour ne pas avoir à le faire nous-même lors du dessin ? J’ai choisis d’utiliser les signes des coordonnées. D’abord, le moteur calcul un vecteur à partir des deux points du segment dans l’ordre dans lesquelles elles ont été dessinés. Ce dernier se calcule par l’équation suivante.

Une fois le vecteur correspondant au sens du segment, il suffit donc de regarder le signe des coordonnées. J’ai choisis d’indiquer le sens par négatif ou positif. Et je mets un dessin pour comprendre ce que ça donne pour toutes sortes de vecteurs sur 360°. Les sens sont déterminés de sorte à correspondre au cercle trigonométrique inversé dans l’axe Y en raison du fait que la plus part des repères graphiques sur ordinateur part du haut vers le bas et de gauche à droite. Ainsi le négatif est en haut pour les Y et le positif en bas.

Dans un autre article j’utiliserais ce petit système et vous expliquerais comment le moteur décide de l’ordre pour lire les points du dessin fraîchement réalisés par vous ou moi dans l’éditeur 🙂 Grâce à ça, et à l’aide d’une autre donnée, les secteurs et les ajouts aux secteurs sont créés de manière cohérentes.