point in polygon algorithm (insidePolygon)
javascript
function pointInPolygon(mouseX, mouseY) {
var inside = false
var i,j = 0
for(i = 0,j = vertexCount - 1; i < vertexCount; j = i++) {
if (((vertexList[i].y > mouseY) != (vertexList[j].y > mouseY))
&&
(mouseX < (vertexList[j].x - vertexList[i].x) * (mouseY - vertexList[i].y) / (vertexList[j].y - vertexList[i].y) + vertexList[i].x)) {
inside = !inside;
}
}
return inside;
}
[Kor]
알고리즘 개요:
이번 글에서는 사용자가 입력한 점이 주어진 다각형 내부에 있는지를 판별하는 자바스크립트 알고리즘에 대해 알아보겠습니다. 이 알고리즘은 주어진 다각형의 꼭지점 좌표들과 사용자의 입력 좌표가 주어졌을 때, 해당 점이 다각형 내부에 있는지를 판별하는 것을 목적으로 합니다.
변수와 함수 설명:
- `mouseX`, `mouseY`: 사용자의 마우스 입력 좌표를 나타내는 변수입니다.
- `vertexCount`: 다각형의 꼭지점 개수를 나타내는 변수입니다.
- `inside`: 점이 다각형 내부에 있는지 여부를 나타내는 변수입니다.
알고리즘 설명:
1. `for` 루프를 이용하여 다각형의 모든 선분을 검사합니다.
2. 다음 선분의 시작점과 끝점을 `vertexList[i]`와 `vertexList[j]`로 설정합니다.
3. 만약 현재 선분과 수평선(점의 y 좌표와 같은)이 만난다면, 다음 선분을 검사합니다.
4. 만약 현재 선분의 시작점의 y 좌표가 점의 y 좌표보다 크거나 작고, 끝점의 y 좌표가 점의 y 좌표보다 작거나 크다면, 점이 선분을 가로지르는 것이므로 다각형의 내부에 있을 가능성이 있습니다.
5. 이제 점의 x 좌표가 현재 선분의 시작점과 끝점을 연결한 직선과 만나는지 확인합니다.
6. 만약 점의 x 좌표가 직선을 가로지르면, `inside` 변수를 토글하여 다각형 내부에 있는지를 업데이트합니다.
7. 모든 선분에 대해 검사를 완료한 후, 최종적으로 `inside` 변수를 반환합니다.
왜 점의 상태를 inside 변수로 체크할까요?
다각형 내부를 판별할 때, 점이 다각형의 선분과 만나는 횟수가 홀수인지 짝수인지에 따라 내부와 외부를 판별할 수 있습니다. 따라서 `inside` 변수는 점이 다각형 내부에 있는지 여부를 추적하는데 사용됩니다.
이렇게 작동하는 알고리즘을 이용하면, 사용자가 입력한 점이 다각형 내부에 있는지를 효율적으로 판별할 수 있습니다.
[Eng]
Algorithm overview:
In this article, we will learn about a JavaScript algorithm that determines if a point entered by the user is inside a given polygon. The purpose of this algorithm is to determine if a point is inside a polygon, given the coordinates of the vertices of a given polygon and the user's input coordinates.
Variables and function descriptions:
- `mouseX`, `mouseY`: Variables representing the user's mouse input coordinates.
- vertexCount`: A variable representing the number of vertices in the polygon.
- Inside: A variable that indicates whether the point is inside the polygon.
Algorithm description:
1. Use a `for` loop to examine all line segments in the polygon.
2. set the start and end points of the next line segment to `vertexList[i]` and `vertexList[j]`.
3. If the current vertex meets a horizontal line (such as the y coordinate of a point), the next vertex is examined.
4. If the y-coordinate of the start of the current line segment is greater than or equal to the y-coordinate of the point, and the y-coordinate of the end of the line segment is less than or equal to the y-coordinate of the point, the point crosses the line segment and is likely inside the polygon.
5. Now check to see if the x-coordinate of the point intersects the straight line connecting the start and end points of the current line segment.
6. If the point's x coordinate crosses the straight line, toggle the `inside` variable to update whether it is inside the polygon.
7. After completing the check for all line segments, finally return the `inside` variable.
Why check the status of a point with the inside variable?
When determining whether a point is inside or outside a polygon, we can distinguish between inside and outside based on whether the number of times the point meets a line segment of the polygon is odd or even. Therefore, the `inside` variable is used to keep track of whether a point is inside the polygon or not.
With an algorithm that works like this, we can efficiently determine if a point entered by the user is inside a polygon.
