Comment savoir si un point se trouve à l'intérieur d'un polygone en utilisant JavaScript

Dans le développement front-end, nous rencontrons souvent des situations où nous devons déterminer si un point se trouve dans un polygone. Par exemple, lorsque nous ajoutons un événement de clic à la carte, nous devons déterminer si le point cliqué par l'utilisateur se trouve dans une certaine zone pour déterminer l'opération correspondante. Cet article explique comment utiliser JavaScript pour déterminer si un point se trouve dans un polygone.

1. Algorithme de polygone

Il existe de nombreux algorithmes pour déterminer si un point se trouve dans un polygone, parmi lesquels la méthode des rayons et la méthode du produit scalaire sont plus couramment utilisées. Cet article présentera la méthode du produit scalaire à titre d'exemple.

L'idée principale de la méthode du produit scalaire est d'utiliser les propriétés des vecteurs pour considérer le point P à chaque sommet du polygone comme un vecteur, puis de calculer si le point P est à l'intérieur du polygone à travers le produit scalaire entre les vecteurs. Plus précisément, le fait que le point P soit à l'intérieur du polygone dépend du signe de la somme des produits scalaires de P et des vecteurs latéraux du polygone.

2. Formule de calcul du produit scalaire

La formule de calcul du produit scalaire est la suivante :

a · b = hache bx + ay #🎜 🎜# by

où a(x, y) et b(x, y) sont deux vecteurs, a·b représente leur produit scalaire. Le résultat du produit scalaire est un scalaire représentant le cosinus de l’angle entre les deux vecteurs.

Il est à noter que si le résultat du produit scalaire est supérieur à 0, cela signifie que l'angle du vecteur est inférieur à 90 degrés ; si le résultat du produit scalaire est inférieur à 0, cela signifie que le vecteur ; l'angle est supérieur à 90 degrés ; si le résultat du produit scalaire est égal à 0, cela signifie que le vecteur est vertical, c'est-à-dire 90 degrés.

3. Déterminez si le point se trouve dans le polygone

Ensuite, nous présenterons comment utiliser la méthode du produit scalaire pour déterminer si le point P se trouve dans le polygone.

Construction de vecteurs

Considérez le point P de chaque sommet du polygone comme un vecteur, et vous pouvez construire un vecteur en calculant la différence de coordonnées du vecteur. Plus précisément, si les coordonnées du point P sont (xp, yp) et les coordonnées du i-ème sommet du polygone sont (xi, yi), alors les coordonnées du vecteur P->i sont (vx, vy), et sa formule de calcul est :

vx = xi - xp;

vy = yi - yp;

Grâce à ce calcul, on peut obtenir les vecteurs de chacun côté du polygone, vous pouvez également obtenir les vecteurs du point P à chaque sommet du polygone.

Calculer le produit scalaire

Ensuite, nous devons calculer la somme des produits scalaires du point P et des vecteurs de chaque côté de le polygone. Si la somme des produits scalaires est positive, alors le point P est à l'extérieur du polygone ; si la somme des produits scalaires est négative, alors le point P est à l'intérieur du polygone.

Il convient de noter que le vecteur dans la formule du produit scalaire doit d'abord être normalisé, c'est-à-dire que la longueur du vecteur est mise à l'échelle à 1. Cela garantit que le résultat du produit scalaire est uniquement lié à l'angle entre les vecteurs et n'est pas affecté par les effets de l'angle du vecteur.

Le code pour calculer le produit scalaire est le suivant :

function isPointInsidePolygon(point, polygon) {

var angle = 0,

i,
vertex1,
vertex2;

# 🎜🎜#var n = polygon.length;

for (i = 0; i < n; i++) {

vertex1 = polygon[i];
vertex2 = polygon[(i + 1) % n];

angle += polarAngle(
  point[0],
  point[1],
  vertex1[0],
  vertex1[1],
  vertex2[0],
  vertex2[1]
);

}

return Math.abs (angle) >= Math.PI;

}

function polarAngle(x, y, x1, y1, x2, y2) {

var angle1 = Math.atan2( y - y1, x - x1);

var angle2 = Math.atan2(y - y2, x - x2);

var diff = angle2 - angle1;#🎜 🎜# while ( diff > Math.PI) {

diff -= 2 * Math.PI;

}
while (diff < -Math.PI) {

diff += 2 * Math.PI;

}#🎜🎜 ##🎜🎜 #return diff;
}

Parmi eux, la fonction isPointInsidePolygon est utilisée pour déterminer si le point est à l'intérieur du polygone, et la fonction polarAngle est utilisée pour calculer le produit scalaire .

4. Résumé

Cet article explique comment utiliser Javascript pour déterminer si un point se trouve à l'intérieur d'un polygone. Il convient de noter que la méthode du produit scalaire n’est applicable qu’aux polygones convexes. Pour les polygones concaves, d’autres algorithmes doivent être utilisés pour le jugement. Dans les applications pratiques, certaines situations particulières doivent être prises en compte, telles que les polygones avec des arêtes ou des sommets qui se chevauchent, des sommets sur des arêtes de polygone, etc., qui nécessitent un jugement et un traitement supplémentaires.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!