점이 다각형 안에 있는지 확인하기

지바고 · 2월 18, 2024, 5:08오후

문제 상황

선로를 클릭할 수 있도록 선로에 Bezier Curve 모양의 Collider를 붙이려고 한다. 그러려면 Bezier Curve와 ray가 충돌했는지를 판별하는 알고리즘이 필요하다.

내 게임에서 Bezier Curve는 기본적으로 다각형으로 근사한다. 그리고 어떤 직선과 평면의 교점을 구하는 것은 그리 어렵지 않다. 즉 이 문제는,

같은 평면 위에 있는 다각형과 점이 있을 때, 점이 다각형 안에 있는지 판별하는 문제

이다.

이 문제가 단순하지 않은 이유는

다각형이 볼록하지 않다.
평면이 Axis aligned가 아니다.
이왕이면 C#으로 쓰기 편한 Vector3.Dot와 Vector3.Cross로 문제를 풀고 싶다.

1번이 참인 경우는 좀이따 다룰 것이고
2번이 참인 경우는 (즉, 문제가 2차원인 경우는) 인터넷에 솔루션이 많다. 플레티넘 4 수준의 문제라고 하니 PS쟁이들은 도전해 보시길 바란다. 1688번: 지민이의 테러
3번은 혹시 이 문제를 푸는 개쩌는 행렬식 같은 게 있을 경우를 대비한 자기방어

내가 푸신 것은 아니고 Bing Chat 님께서 푸셨는데, 혹시 버그 없나 알고리즘 체크한 시간이 아깝기도 하고 나중에 여기서 버그나면 지금 이해한 것을 리마인드해야하기 때문에 글로 쓴다.

오답

전지전능하신 Bing Chat 님께 다각형이 볼록하지 않을 수 있다는 조건을 빼고 드렸더니 주신 알고리즘이다.

public static bool IsPointInsideConvexPolygon(Vector3 point, List<Vector3> polygon)
{
    Vector3 normal = Vector3.Cross(polygon[2] - polygon[1], polygon[1] - polygon[0]);

    for (int i = 0; i < polygon.Count; i++)
    {
        Vector3 edgeStart = polygon[i];
        Vector3 edgeEnd = polygon[(i + 1) % polygon.Count];
        Vector3 crossProduct = Vector3.Cross(edgeEnd - edgeStart, point - edgeStart);

        if (Vector3.Dot(crossProduct, normal) < 0) // Check the sign of the cross product
            return false; // Point is outside
    }

    return true; // Point is inside
}

코드가 짧기 때문에 쉽게 이해할 수 있을 것이다. 개인적으로는 CCW를 활용한 알고리즘보다 훨씬 잘 읽히고 좋지 않나 생각한다. 하지만 180도를 넘는 내각이 있다면 사용할 수 없다. 베지어 커브를 근사한 다각형이 볼록한 경우는 직선인 경우밖에 없기 때문에 내 상황에서는 쓸 수가 없다.

정답

private bool IsPointInsidePolygon(Vector3 point)
{
    int count = vertices.Length;
    bool inside = false;

    for (int i = 0, j = count - 1; i < count; j = i++)
    {
        // it reverts {inside} if
        // any of two straight lines which are drawn to +x and +z side, from point, collides with edge (i, j)

        // y coord should be between two vertices
        if ((vertices[i].Y > point.Y) == (vertices[j].Y > point.Y))
            continue;

        // finding intersection of y = point.y and edge (i, j)
        var tx = (vertices[j].X - vertices[i].X) * (point.Y - vertices[i].Y) / (vertices[j].Y - vertices[i].Y);
        var tz = (vertices[j].Z - vertices[i].Z) * (point.Y - vertices[i].Y) / (vertices[j].Y - vertices[i].Y);
        if (point.X < tx + vertices[i].X + 1e-6 && point.Z < tz + vertices[i].Z + 1e-6)
        {
            inside = !inside;
        }
    }

    return inside;
}

점에서 y축에 평행한 +xz 반평면을 그어서 만나는 교점의 개수를 센다고 생각하면 된다. 홀수라면 안에 있는 것.

추가

(n-1, 0) (0, 1) (1, 2) (2, 3) … (n-2, n-1)이 나오도록 반복문을 돌리고 싶을 때…

for (int i = 0; i < n; i++)
    ( (i - 1) % n, i )

도 좋지만…

for (int i = 0, j = count - 1; i < count; j = i++)
    (j, i)

가 연산이 하나 적고 깔끔하다!