How to tell if a point is inside a polygon using JavaScript

In front-end development, we often encounter situations where we need to determine whether a point is within a polygon. For example, when we add a click event to the map, we need to determine whether the point clicked by the user is within a certain area to determine the corresponding operation. This article will introduce how to use JavaScript to determine whether a point is within a polygon.

1. Polygon Algorithm

There are many algorithms for determining whether a point is within a polygon, among which the ray method and the dot product method are more commonly used. This article will introduce the dot product method as an example.

The core idea of ​​the dot product method is to use the properties of vectors to regard point P to each vertex of the polygon as a vector, and then calculate whether point P is inside the polygon through the dot product between the vectors. Specifically, whether point P is inside the polygon depends on the sign of the sum of the dot products of P and the side vectors of the polygon.

2. Dot product calculation formula

The dot product calculation formula is as follows:

a · b = ax bx ay by

where a(x, y) and b(x, y) are two vectors, and a·b represents their dot product. The result of the dot product is a scalar representing the cosine of the angle between the two vectors.

It is worth noting that if the dot product result is greater than 0, it means that the vector angle is less than 90 degrees; if the dot product result is less than 0, it means that the vector angle is greater than 90 degrees; if the dot product result is equal to 0, It means the vector is vertical, that is, 90 degrees.

3. Determine whether the point is within the polygon

Next, we will introduce how to use the dot product method to determine whether the point P is within the polygon.

1. Constructing vectors

Consider point P to each vertex of the polygon as a vector. You can construct a vector by calculating the coordinate difference of the vector. Specifically, if the coordinates of point P are (xp, yp) and the coordinates of the i-th vertex of the polygon are (xi, yi), then the coordinates of vector P->i are (vx, vy), and its calculation formula is is:

vx = xi - xp;
vy = yi - yp;

Through this calculation, we can get the vectors of each side of the polygon, and we can also get the point P Vectors to the vertices of the polygon.

2. Calculate the dot product

Next, we need to calculate the sum of the dot products of point P and the vectors of each side of the polygon. If the sum of the dot products is positive, then point P is outside the polygon; if the sum of the dot products is negative, then point P is inside the polygon.

It is worth noting that the vector in the dot product formula needs to be normalized first, that is, the vector length is scaled to 1. This ensures that the result of the dot product is only related to the angle between the vectors and is not affected by the vector length. Influence.

The code for calculating dot product is as follows:

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;
}

Among them, the isPointInsidePolygon function is used to determine whether the point is inside the polygon, polarAngle Function is used to calculate the dot product.

4. Summary

This article introduces how to use Javascript to determine whether a point is inside a polygon. It should be noted that the dot product method is only applicable to convex polygons. For concave polygons, other algorithms need to be used for judgment. In practical applications, some special situations need to be considered, such as polygons with overlapping edges or vertices, vertices on polygon edges, etc., which require additional judgment and processing.

The above is the detailed content of How to tell if a point is inside a polygon using JavaScript. For more information, please follow other related articles on the PHP Chinese website!