유니티 - 다각형 좌표의 시계 방향 판단하기 (How to Determine If a Polygon is Clocwise)

Unity 전체 링크

 

참고

- 세 점을 지나는 평면 구하기

- 3차원 세 점의 좌표로 삼각형의 넓이 구하기

- Vector3.Cross로 평면 위에서 시계 방향 판단하기

 

다각형 좌표의 시계 방향 판단하기 = 다각형의 넓이 구하기

---

아래와 같이 별 모양의 다각형이 주어졌다고 가정하자.

 

점의 배치를 보면 시계방향으로 좌표가 정렬되어 있다.

 

처음 3개의 점은 시계 방향이다.

 

하지만 다음 3개의 점은 반시계 방향이다.

 

좌표를 볼 때, 시계 방향으로 배치하였지만, 점 3개씩 방향을 체크하면 시계 방향과 반시계 방향이 같이 존재한다.

즉, 점 3개씩 비교하는 것으로 좌표가 시계 방향인지 반시계 방향인지 판단할 수 없다.

 

좌표가 주어졌을 때 시계 방향인지, 반시계 방향인지 판단하는 함수를 만들어보자.

---

Settings

 

다각형을 그리기 위한 라인 렌더러를 적절히 준비한다.

 

빈 오브젝트를 만들고 자식 오브젝트로 다각형의 좌표를 Sphere로 배치한다.

 

테스트를 확인할 기준점 offset을 큐브로 하나 설정한다. 

 

빈 오브젝트를 하나 만들어 PolygonClockwise.cs를 추가하고 오브젝트를 추가하면 된다.

---

구현

 

방향을 판단하는 방법은 넓이를 구하는 방법과 같다.

다각형의 넓이를 구해서 + 면 시계 방향, - 면 반시계 방향이다.

이 방법은 결국 점 1 ~ N의 외적의 합의 절반이다.

 

 

Update 문에서 clockWisePolygon을 이용하여 시계 / 반시계 방향을 판단한다.

시계 방향이면 다각형의 색이 초록색, 반시계 방향이면 노란색으로 변경하도록 하자.

    void Update()
    {
        polygonPositions.Clear();
        foreach (Transform tr in polygons.transform)
            polygonPositions.Add(tr.position);

        float clockWiseSum 
            = clockWisePolygon(polygonPositions, new Vector3(0, 1, 0), offset.transform.position);

        Debug.Log(clockWiseSum);

        if (clockWiseSum > 0)
        {
            setLineRenderer(lrs[0], polygonPositions, Color.green, 0.5f);
        }
        else
        {
            setLineRenderer(lrs[0], polygonPositions, Color.yellow, 0.5f);
        }
    }

 

clockWisePolygon은 다음과 같다. 

참고로 offset은 디버깅용으로 추가한 것이다.

주어지는 normal 벡터 방향으로 삼각형의 넓이를 구한다.

평면에 대해 주어진 방향으로 방향을 판단하여 삼각형의 넓이를 구한다.

3개의 점이 만드는 삼각형이 시계 방향이면 더하고, 반시계 방향이면 뺀다.

 

위의 Cross All 공식을 구하기 위해 temp에 polygon 좌표를 복사하고 polygon[0]을 추가하였다.

실제 삼각형의 합과 같은지 확인하기 위해 offset을 이용하여 triangleSum에 삼각형의 합을 누적시켰다.

이 예제에서 기준이 되는 평면의 노멀 벡터 normal = y축이 양인 방향이다.

    float clockWisePolygon(List<Vector3> polygon, Vector3 normal, Vector3 offset)
    {
        Vector3 crossSum = Vector3.zero;
        float triangleSum = 0;
        List<Vector3> temp = new List<Vector3>(polygon);

        temp.Add(polygon[0]);

        for (int i = 0; i < polygon.Count; i++)
        {
            crossSum += Vector3.Cross(temp[i], temp[i + 1]);
            if (ccwByPlane(temp[i], temp[i + 1], offset, normal, offset) > 0)
            {
                setLineRenderer(lrs[i + 1], new List<Vector3>() { temp[i], temp[i + 1], offset }, Color.red);
                triangleSum += getAreaOfTriangle(temp[i], temp[i + 1], offset);
            }
            else
            {
                setLineRenderer(lrs[i + 1], new List<Vector3>() { temp[i], temp[i + 1], offset }, Color.blue);
                triangleSum -= getAreaOfTriangle(temp[i], temp[i + 1], offset);
            }

        }

        float ret = Vector3.Dot(crossSum, normal);

        Debug.Log($"Cross Sum : {ret / 2.0f} / triangleSum : {triangleSum}");

        return ret;
    }

 

주어진 평면에 대해 시계 / 반시계 판단 함수는 다음과 같다. (설명은 링크 참고)

    float distancePlaneToPoint(Vector3 normal, Vector3 planeDot, Vector3 point)
    {
        Plane plane = new Plane(normal, planeDot);
        return plane.GetDistanceToPoint(point);
    }

    Vector3 getPositionOnthePlane(Vector3 normal, Vector3 planeDot, Vector3 position)
    {
        float distance = distancePlaneToPoint(normal, planeDot, position);
        return position - normal * distance;
    }

    float ccwByPlane(Vector3 a, Vector3 b, Vector3 c, Vector3 normal, Vector3 planeDot)
    {
        Vector3 d = getPositionOnthePlane(normal, planeDot, a);
        Vector3 e = getPositionOnthePlane(normal, planeDot, b);
        Vector3 f = getPositionOnthePlane(normal, planeDot, c);

        Vector3 p = e - d;
        Vector3 q = f - e;

        return Vector3.Dot(Vector3.Cross(p, q), normal);
    }

 

세 점이 주어질 때 삼각형의 넓이는 다음과 같다.

    float getAreaOfTriangle(Vector3 dot1, Vector3 dot2, Vector3 dot3)
    {
        Vector3 a = dot2 - dot1;
        Vector3 b = dot3 - dot1;
        Vector3 cross = Vector3.Cross(a, b);

        return cross.magnitude / 2.0f;
    }

---

 

게임을 실행하면 offset(Cube)을 기준으로 삼각형이 생성된다.

 

Cross Sum과 triangleSum의 값이 비슷한 것을 알 수 있다.

 

실제 게임을 실행하고 offset을 움직여보자.

offset 위치가 바뀌어서 offset을 포함한 3개의 점이 반시계 방향이면 파란색으로 라인 렌더러가 그려진다.

파란색 삼각형의 넓이는 빼게 되므로 전체 합은 일정하다.

 

점을 옮겨서 반시계 방향으로 바꾸면 Cross / 삼각형의 넓이가 마이너스로 바뀌고,

라인 렌더러 또한 노란색으로 바뀐다.

 

디버깅용 코드를 제거하고 코드를 정리하면 다각형의 넓이를 구하는 함수는 다음과 같다.

    float getAreaOfPolygon(List<Vector3> polygon, Vector3 normal)
    {
        Vector3 crossSum = Vector3.zero;
        List<Vector3> temp = new List<Vector3>(polygon);

        temp.Add(polygon[0]);

        for (int i = 0; i < polygon.Count; i++)
            crossSum += Vector3.Cross(temp[i], temp[i + 1]);

        return Mathf.Abs(Vector3.Dot(crossSum, normal)) / 2.0f;
    }

 

방향 판단 함수는 다음과 같다.

    bool isClockWisePolygon(List<Vector3> polygon, Vector3 normal)
    {
        Vector3 crossSum = Vector3.zero;
        List<Vector3> temp = new List<Vector3>(polygon);

        temp.Add(polygon[0]);

        for (int i = 0; i < polygon.Count; i++)
        {
            crossSum += Vector3.Cross(temp[i], temp[i + 1]);
        }

        return Vector3.Dot(crossSum, normal) > 0;
    }

 

전체 코드는 다음과 같다.

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

public class PolygonClockwise : MonoBehaviour
{
    public GameObject offset;
    public GameObject polygons;
    public GameObject lineRendererManager;
    LineRenderer[] lrs;
    List<Vector3> polygonPositions = new List<Vector3>();

    float distancePlaneToPoint(Vector3 normal, Vector3 planeDot, Vector3 point)
    {
        Plane plane = new Plane(normal, planeDot);
        return plane.GetDistanceToPoint(point);
    }

    Vector3 getPositionOnthePlane(Vector3 normal, Vector3 planeDot, Vector3 position)
    {
        float distance = distancePlaneToPoint(normal, planeDot, position);
        return position - normal * distance;
    }

    float ccwByPlane(Vector3 a, Vector3 b, Vector3 c, Vector3 normal, Vector3 planeDot)
    {
        Vector3 d = getPositionOnthePlane(normal, planeDot, a);
        Vector3 e = getPositionOnthePlane(normal, planeDot, b);
        Vector3 f = getPositionOnthePlane(normal, planeDot, c);

        Vector3 p = e - d;
        Vector3 q = f - e;

        return Vector3.Dot(Vector3.Cross(p, q), normal);
    }

    float getAreaOfTriangle(Vector3 dot1, Vector3 dot2, Vector3 dot3)
    {
        Vector3 a = dot2 - dot1;
        Vector3 b = dot3 - dot1;
        Vector3 cross = Vector3.Cross(a, b);

        return cross.magnitude / 2.0f;
    }

    float getAreaOfPolygon(List<Vector3> polygon, Vector3 normal)
    {
        Vector3 crossSum = Vector3.zero;
        List<Vector3> temp = new List<Vector3>(polygon);

        temp.Add(polygon[0]);

        for (int i = 0; i < polygon.Count; i++)
            crossSum += Vector3.Cross(temp[i], temp[i + 1]);

        return Mathf.Abs(Vector3.Dot(crossSum, normal)) / 2.0f;
    }

    bool isClockWisePolygon(List<Vector3> polygon, Vector3 normal)
    {
        Vector3 crossSum = Vector3.zero;
        List<Vector3> temp = new List<Vector3>(polygon);

        temp.Add(polygon[0]);

        for (int i = 0; i < polygon.Count; i++)
        {
            crossSum += Vector3.Cross(temp[i], temp[i + 1]);
        }

        return Vector3.Dot(crossSum, normal) > 0;
    }

    float clockWisePolygon(List<Vector3> polygon, Vector3 normal, Vector3 offset)
    {
        Vector3 crossSum = Vector3.zero;
        float triangleSum = 0;
        List<Vector3> temp = new List<Vector3>(polygon);

        temp.Add(polygon[0]);

        for (int i = 0; i < polygon.Count; i++)
        {
            crossSum += Vector3.Cross(temp[i], temp[i + 1]);
            if (ccwByPlane(temp[i], temp[i + 1], offset, normal, offset) > 0)
            {
                setLineRenderer(lrs[i + 1], new List<Vector3>() { temp[i], temp[i + 1], offset }, Color.red);
                triangleSum += getAreaOfTriangle(temp[i], temp[i + 1], offset);
            }
            else
            {
                setLineRenderer(lrs[i + 1], new List<Vector3>() { temp[i], temp[i + 1], offset }, Color.blue);
                triangleSum -= getAreaOfTriangle(temp[i], temp[i + 1], offset);
            }

        }

        float ret = Vector3.Dot(crossSum, normal);

        Debug.Log($"Cross Sum : {ret / 2.0f} / triangleSum : {triangleSum}");

        return ret;
    }

    void setLineRenderer(LineRenderer lr, List<Vector3> list, Color color, float height = .0f)
    {
        lr.startWidth = lr.endWidth = .2f;     
        lr.material.color = color;
        lr.positionCount = list.Count;

        for (int i = 0; i < list.Count; i++)
            lr.SetPosition(i, new Vector3(list[i].x, height, list[i].z));

        lr.loop = true;
    }

    void Start()
    {
        lrs = lineRendererManager.GetComponentsInChildren<LineRenderer>();
    }

    void Update()
    {
        polygonPositions.Clear();
        foreach (Transform tr in polygons.transform)
            polygonPositions.Add(tr.position);

        float clockWiseSum 
            = clockWisePolygon(polygonPositions, new Vector3(0, 1, 0), offset.transform.position);

        if (clockWiseSum > 0)
        {
            setLineRenderer(lrs[0], polygonPositions, Color.green, 0.5f);
        }
        else
        {
            setLineRenderer(lrs[0], polygonPositions, Color.yellow, 0.5f);
        }
    }
}

 

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

PolygonClockwise.unitypackage

0.01MB

 

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