JavaScript를 사용하여 점이 다각형 내부에 있는지 확인하는 방법

프런트 엔드 개발에서는 점이 다각형 내에 있는지 확인해야 하는 상황에 자주 직면합니다. 예를 들어, 지도에 클릭 이벤트를 추가할 때, 사용자가 클릭한 지점이 특정 영역 내에 있는지 여부를 확인하여 해당 작업을 결정해야 합니다. 이 기사에서는 JavaScript를 사용하여 점이 다각형 내에 있는지 확인하는 방법을 소개합니다.

1. 다각형 알고리즘

점이 다각형 내에 있는지 여부를 결정하는 알고리즘에는 여러 가지가 있으며 그 중 광선 방법과 내적 방법이 더 일반적으로 사용됩니다. 이 기사에서는 내적 방법을 예로 소개합니다.

내적법의 핵심 아이디어는 벡터의 성질을 이용하여 다각형의 각 꼭지점에 대한 점 P를 벡터로 간주한 후, 벡터 간의 내적을 통해 점 P가 다각형 내부에 있는지 여부를 계산하는 것입니다. 구체적으로, 점 P가 다각형 내부에 있는지 여부는 P의 내적과 다각형의 측면 벡터의 합의 부호에 따라 달라집니다.

2. 내적 계산식

내적 계산식은 다음과 같습니다.

a · b = ax bx + ay by

여기서 a(x, y)와 b(x, y)는 2입니다. 벡터의 경우, a · b는 내적을 나타냅니다. 내적의 결과는 두 벡터 사이의 각도의 코사인을 나타내는 스칼라입니다.

내적 결과가 0보다 크면 벡터 사이의 각도가 90도보다 작다는 의미이고, 내적 결과가 0보다 작으면 벡터 사이의 각도가 다음과 같다는 의미입니다. 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 =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;
}

그 중 isPointInsidePolygon 함수는 점이 폴리곤 내부에 있는지 확인하는 함수이고 polarAngle 함수는 내적을 계산하는 데 사용됩니다.

4. 요약

이 글에서는 Javascript를 사용하여 점이 다각형 내부에 있는지 확인하는 방법을 소개합니다. 내적 방법은 볼록 다각형에만 적용 가능하며 오목 다각형의 경우 판단을 위해 다른 알고리즘을 사용해야 합니다. 실제 적용에서는 가장자리나 꼭지점이 겹치는 다각형, 다각형 가장자리의 꼭지점 등과 같이 추가적인 판단과 처리가 필요한 몇 가지 특별한 상황을 고려해야 합니다.

위 내용은 JavaScript를 사용하여 점이 다각형 내부에 있는지 확인하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!