JavaScript を使用して点がポリゴン内にあるかどうかを確認する方法

フロントエンド開発では、点がポリゴン内にあるかどうかを判断する必要がある状況によく遭遇します。たとえば、マップにクリック イベントを追加する場合、対応する操作を決定するには、ユーザーがクリックした点が特定の領域内にあるかどうかを判断する必要があります。この記事では、JavaScript を使用して点がポリゴン内にあるかどうかを判断する方法を紹介します。

1. 多角形アルゴリズム

点が多角形内にあるかどうかを判断するアルゴリズムは数多くありますが、中でも光線法と内積法がより一般的に使用されます。この記事では例としてドット積法を紹介します。

内積法の中心的な考え方は、ベクトルのプロパティを使用して、多角形の各頂点の点 P をベクトルとみなして、点 P が点を介して多角形の内側にあるかどうかを計算することです。ベクトル間の積。具体的には、点 P が多角形の内側にあるかどうかは、P の内積と多角形の辺ベクトルの和の符号に依存します。

2. 内積の計算式

内積の計算式は次のとおりです:

a · b = ax bx ay by

ここで、a(x, y) と b(x, y) は 2 つのベクトルであり、a・b はそれらの内積を表します。ドット積の結果は、2 つのベクトル間の角度の余弦を表すスカラーです。

ドット積の結果が 0 より大きい場合は、ベクトルの角度が 90 度未満であることを意味し、ドット積の結果が 0 より小さい場合は、ベクトルの角度が 90 度未満であることを意味することに注意してください。 90 度より大きい; 内積の結果が 0 に等しい場合、ベクトルが垂直、つまり 90 度であることを意味します。

3. 点が多角形内にあるかどうかを判断する

次に、点 P が多角形内にあるかどうかを内積法を使用して判断する方法を紹介します。

1. ベクトルの構築

多角形の各頂点の点 P をベクトルとして考え、そのベクトルの座標差を計算することでベクトルを構築できます。具体的には、点 P の座標が (xp, yp) で、多角形の i 番目の頂点の座標が (xi, yi) である場合、ベクトル P->i の座標は (vx, vy) となります。その計算式は次のとおりです:

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

この計算を通じて、多角形の各辺のベクトルを取得できます。また、多角形の頂点への点 P ベクトルを取得することもできます。

2. 内積の計算

次に、点 P と多角形の各辺のベクトルの内積の合計を計算する必要があります。内積の合計が正の場合、点 P は多角形の外側にあり、内積の合計が負の場合、点 P は多角形の内側にあります。

内積式のベクトルを最初に正規化する必要があること、つまりベクトルの長さを 1 にスケールする必要があることに注意してください。これにより、内積の結果が角度のみに関連することが保証されます。ベクトル間の長さはベクトルの長さの影響を受けません。

内積を計算するコードは次のとおりです。

function isPointInsidePolygon(point, Polygon) {
var angle = 0,

i,
vertex1,
vertex2;

var n = ポリゴン。 length;

for (i = 0; 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;
}

関数 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

diff += 2 * Math.PI;

}

return diff;
}

このうち、isPointInsidePolygon 関数は、点が多角形の内側にある場合、polarAngle 関数を使用して内積を計算します。

4. 概要

この記事では、JavaScript を使用して点が多角形の内側にあるかどうかを判断する方法を紹介します。なお、内積法は凸多角形のみに適用され、凹多角形の場合は他のアルゴリズムで判定する必要があります。実際のアプリケーションでは、重なり合うエッジまたは頂点を持つポリゴン、ポリゴン エッジ上の頂点など、追加の判断と処理が必要ないくつかの特殊な状況を考慮する必要があります。

以上がJavaScript を使用して点がポリゴン内にあるかどうかを確認する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。