유니티 - 다각형 안에 있는 점 판단하기 (How to Check If a Point Is Inside a Polygon)

Unity 전체 링크

 

삼각형 안에 있는 점 또는 사각형 안에 있는 점은 삼각형의 넓이를 이용하여 내부 점을 판단했다.

 

하지만 아래와 같이 복잡한 모양의 다각형은 넓이로 내부와 외부의 점을 판단하기 힘들다.

 

이 경우에는 판단해야하는 점에 대해 적절한 선분(반직선)을 그린다.

그리고 각 다각형의 모서리와 교점의 개수로 내부와 외부를 판단할 수 있다.

 

외부에 있는 큐브의 경우 교점이 2개다. 

즉, 교점이 짝수라면 외부라고 판단할 수 있다.

 

아래의 큐브는 내부에 있다. 

마찬가지로 직선을 그어보면 교점이 3개다.

따라서, 교점이 홀수라면 내부라고 판단할 수 있다.

 

직선을 이을 때, 직선의 교점이 아니라 점과 완전히 일치하는 경우에는 방어코드가 필요하다.

여기서는 적절한 오차를 허용하였으므로 따로 방어코드를 추가하지는 않는다.

매우 정밀도를 요구할 필요가 있는 경우에는 방어코드가 필요하다.

---

구현

 

먼저 Sphere의 집합을 빈 오브젝트 Polygon의 자식으로 설정하고 순서대로 배치하자.

위의 경우는 시계 방향으로 좌표를 설정하였다.

 

그리고 다각형 내부/외부를 판단할 점으로 큐브를 만든다.

빈 오브젝트를 만든 후 PolygonInsideCheck.cs를 추가하고 다각형을 그릴 라인 렌더러도 추가한다.

 

라인 렌더러는 오직 다각형의 모습을 그리기 위해 필요하다.

좌표를 보고 아래와 같이 설정하도록 함수를 만든다.

    void initLineRenderer(LineRenderer lr)
    {
        lr.startWidth = lr.endWidth = .1f;
        lr.material.color = Color.blue;
        lr.loop = true;
    }

    void setLineRenderer(LineRenderer lr, List<Vector3> pos)
    {
        lr.positionCount = pos.Count;

        for (int i = 0; i < pos.Count; i++)
            lr.SetPosition(i, pos[i]);
    }

 

큐브가 내부에 있다면 파란색, 외부에 있다면 빨간색으로 보이게 하기 위해 Renderer와 Material을 설정한다.

Update에서 isInsidePolygon으로 판단하면서 머테리얼을 교체한다.

Polygon의 자식 오브젝트가 좌표이므로 polygonPos 리스트에 담아서 저장한다.

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class PolygonInsideCheck : MonoBehaviour
{
    // 모든 좌표 Y = 0 가정.
    LineRenderer lr;

    public GameObject polygon;

    public GameObject dot;
    public Material red, blue;
    Renderer rd;

    List<Vector3> polygonPos = new List<Vector3>();

    void Start()
    {
        rd = dot.GetComponent<Renderer>();

        lr = this.GetComponent<LineRenderer>();
        initLineRenderer(lr);

        foreach (Transform tr in polygon.transform)
        {
            Vector3 v = tr.transform.position;
            polygonPos.Add(v);
        }

        setLineRenderer(lr, polygonPos);
    }

    void Update()
    {
        if(isInsidePolygon(polygonPos, dot.transform.position))
        {
            rd.material = blue;
        }
        else
        {
            rd.material = red;
        }
    }
}

 

다각형 내부 / 외부 판단 알고리즘은 유한한 직선이 교차하는지 체크해야한다. (설명은 링크를 참고)

checkDotInLine에서 epsilon = 허용 오차가 있기 때문에 여기서는 위에서 언급한 방어코드를 작성하지 않는다.

    bool checkDotInLine(Vector3 a, Vector3 b, Vector3 dot)
    {
        float epsilon = 0.00001f;
        float dAB = Vector3.Distance(a, b);
        float dADot = Vector3.Distance(a, dot);
        float dBDot = Vector3.Distance(b, dot);

        return ((dAB + epsilon) >= (dADot + dBDot));
    }

    bool crossCheck2D(Vector3 a, Vector3 b, Vector3 c, Vector3 d)
    {
        // (x, 0, z)
        float x1, x2, x3, x4, z1, z2, z3, z4, X, Z;

        x1 = a.x; z1 = a.z;
        x2 = b.x; z2 = b.z;
        x3 = c.x; z3 = c.z;
        x4 = d.x; z4 = d.z;

        float cross = ((x1 - x2) * (z3 - z4) - (z1 - z2) * (x3 - x4));

        if (cross == 0 /* parallel */) return false;

        X = ((x1 * z2 - z1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * z4 - z3 * x4)) / cross;
        Z = ((x1 * z2 - z1 * x2) * (z3 - z4) - (z1 - z2) * (x3 * z4 - z3 * x4)) / cross;

        return
            checkDotInLine(a, b, new Vector3(X, 0, Z))
            && checkDotInLine(c, d, new Vector3(X, 0, Z));
    }

 

이제 dotPos를 기준으로 outsidePos를 임의로 만든다. 

이때 반드시 다각형의 크기를 기준으로 적절히 점을 잘 찍어야 한다.

여기서는 다각형의 직선이 짧으므로 넉넉히 임의의 점을 dotPos의 +x 방향으로 100을 주었다.

 

이제 모든 다각형을 만드는 직선과 임의로 만든 직선의 교차 여부를 카운팅하면 된다.

polygonPos가 시계방향으로 좌표가 저장되어 있으므로 마지막 점과 첫번째 점은 따로 비교한다.

교차여부에 대한 횟수가 홀수면 내부의 점이 된다.

    bool isInsidePolygon(List<Vector3> polygonPos, Vector3 dotPos)
    {
        Vector3 outsidePos = dotPos;
        outsidePos.x += 100.0f;

        int count = polygonPos.Count;
        int crossCount = 0;
        for (int i = 0; i < count - 1; i++)
        {
            if (crossCheck2D(polygonPos[i], polygonPos[i + 1], dotPos, outsidePos))
            {
                crossCount++;
            }
        }

        if (crossCheck2D(polygonPos[0], polygonPos[count - 1], dotPos, outsidePos))
            crossCount++;

        return (crossCount % 2) == 1; // 홀수면 inside
    }

 

이제 게임을 실행해서 큐브를 움직여보자.

외부에 있을 때는 빨간색 큐브가, 내부에 있을 때는 파란색 큐브가 된다.

 

전체코드는 다음과 같다.

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class PolygonInsideCheck : MonoBehaviour
{
    // 모든 좌표 Y = 0 가정.
    LineRenderer lr;

    public GameObject polygon;

    public GameObject dot;
    public Material red, blue;
    Renderer rd;

    List<Vector3> polygonPos = new List<Vector3>();

    bool checkDotInLine(Vector3 a, Vector3 b, Vector3 dot)
    {
        float epsilon = 0.00001f;
        float dAB = Vector3.Distance(a, b);
        float dADot = Vector3.Distance(a, dot);
        float dBDot = Vector3.Distance(b, dot);

        return ((dAB + epsilon) >= (dADot + dBDot));
    }

    bool crossCheck2D(Vector3 a, Vector3 b, Vector3 c, Vector3 d)
    {
        // (x, 0, z)
        float x1, x2, x3, x4, z1, z2, z3, z4, X, Z;

        x1 = a.x; z1 = a.z;
        x2 = b.x; z2 = b.z;
        x3 = c.x; z3 = c.z;
        x4 = d.x; z4 = d.z;

        float cross = ((x1 - x2) * (z3 - z4) - (z1 - z2) * (x3 - x4));

        if (cross == 0 /* parallel */) return false;

        X = ((x1 * z2 - z1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * z4 - z3 * x4)) / cross;
        Z = ((x1 * z2 - z1 * x2) * (z3 - z4) - (z1 - z2) * (x3 * z4 - z3 * x4)) / cross;

        return
            checkDotInLine(a, b, new Vector3(X, 0, Z))
            && checkDotInLine(c, d, new Vector3(X, 0, Z));
    }

    bool isInsidePolygon(List<Vector3> polygonPos, Vector3 dotPos)
    {
        Vector3 outsidePos = dotPos;
        outsidePos.x += 100.0f;

        int count = polygonPos.Count;
        int crossCount = 0;
        for (int i = 0; i < count - 1; i++)
        {
            if (crossCheck2D(polygonPos[i], polygonPos[i + 1], dotPos, outsidePos))
            {
                crossCount++;
            }
        }

        if (crossCheck2D(polygonPos[0], polygonPos[count - 1], dotPos, outsidePos))
            crossCount++;

        return (crossCount % 2) == 1; // 홀수면 inside
    }

    void initLineRenderer(LineRenderer lr)
    {
        lr.startWidth = lr.endWidth = .1f;
        lr.material.color = Color.blue;
        lr.loop = true;
    }

    void setLineRenderer(LineRenderer lr, List<Vector3> pos)
    {
        lr.positionCount = pos.Count;

        for (int i = 0; i < pos.Count; i++)
            lr.SetPosition(i, pos[i]);
    }

    void Start()
    {
        rd = dot.GetComponent<Renderer>();

        lr = this.GetComponent<LineRenderer>();
        initLineRenderer(lr);

        foreach (Transform tr in polygon.transform)
        {
            Vector3 v = tr.transform.position;
            polygonPos.Add(v);
        }

        setLineRenderer(lr, polygonPos);
    }

    void Update()
    {
        if(isInsidePolygon(polygonPos, dot.transform.position))
        {
            rd.material = blue;
        }
        else
        {
            rd.material = red;
        }
    }
}

 

위의 실행결과는 아래의 unitypackage에서 확인 가능하다.

PolygonInsideCheck.unitypackage

0.03MB

 

Unity Plus:

Easy 2D, 3D, VR, & AR software for cross-platform development of games and mobile apps. - Unity Store

 

Unity Pro:

Unity Pro

 

Unity 프리미엄 학습:

Unity Learn