유니티 - 컨벡스 헐로 임의의 점을 모두 포함하는 사각형 구하기 (Points in a Rectangle with Convex Hull)

Unity 전체 링크

 

참고

- 스택

- 임의의 다각형을 포함하는 사각형 구하기

- 볼록 껍질 (Convex Hull, Graham Scan)

- 컨벡스 헐로 볼록 다각형을 만드는 점의 좌표 구하기

 

임의의 다각형을 포함하는 사각형을 구할 때, 다각형의 좌표가 시계 방향이 아닌 경우,

아래와 같이 사각형을 제대로 만들지 못하는 경우가 발생한다.

 

따라서 컨벡스 헐로 볼록 다각형을 만들고, 다시 볼록 다각형을 포함하는 사각형을 만들자.

---

구현

 

PolygonInSquare.cs에서 아래의 내용을 추가한다.

기존의 함수랑 이름이 겹치기 때문에 함수 이름(ccwBy2D → ccw, compare → compare2)을 변경하였다.

    Vector3 findMinXZ(List<Vector3> position)
    {
        Vector3 min = new Vector3(100000, 0, 100000);

        foreach (Vector3 p in position)
        {
            if (min.z >= p.z)
            {
                if (min.z == p.z)
                {
                    if (min.x > p.x)
                    {
                        min = p;
                    }
                }
                else
                {
                    min = p;
                }
            }
        }

        return min;
    }

    float ccw(Vector3 a, Vector3 b, Vector3 c)
    {
        Vector3 p = b - a;
        Vector3 q = c - b;

        return Vector3.Cross(p, q).y;
    }

    int compare2(Vector3 a, Vector3 b)
    {
        float tmp = ccw(minXZ, a, b);
        if (tmp > 0) return -1;
        else if (tmp == 0 && (Vector3.Distance(minXZ, a) < Vector3.Distance(minXZ, b))) return -1;
        return 1;
    }

    (List<Vector3> convexHull, bool allCheck) getConvexHullVertices(List<Vector3> position, int depth = int.MaxValue)
    {
        List<Vector3> convexHull = new List<Vector3>();
        bool allCheck = true;

        int index, sp;
        Vector3[] stack = new Vector3[position.Count];

        index = sp = 0;

        stack[sp++] = position[index++];
        stack[sp++] = position[index++];

        while (sp < 3)
        {
            float tmp = ccw(stack[sp - 2], stack[sp - 1], position[index]);

            if (tmp > 0) stack[sp++] = position[index++];
            else if (tmp == 0) // 직선인 경우는 점을 교체
            {
                sp--;
                stack[sp++] = position[index++];
            }
            else index++;
        }

        while (index < position.Count)
        {
            if (sp == depth)
            {
                allCheck = false;
                break;
            }

            float tmp = ccw(stack[sp - 2], stack[sp - 1], position[index]);
            if (tmp > 0) stack[sp++] = position[index++];
            else sp--;
        }

        for (int i = 0; i < sp; i++) convexHull.Add(stack[i]);

        return (convexHull, allCheck);
    }

 

Update에서 현재의 좌표를 바탕으로 ConvexHull로 교체하도록 코드를 수정한다.

    minXZ = findMinXZ(position);

    position.Sort(compare2);

    List<Vector3> convexHull = getConvexHullVertices(position);

 

게임을 실행하면 좌표가 시계 방향이 아니더라도 볼록 다각형을 먼저 만든 후, 사각형을 만든다.

 

전체 코드는 다음과 같다.

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

public class PolygonInSquare : MonoBehaviour
{
    public GameObject vertices;
    public GameObject rectangle;
    public GameObject lineRenderer;
    LineRenderer[] lrs;
    Vector3 minXZ;

    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(c, d, new Vector3(X, 0, Z));
    }

    bool checkNotAllCrossLine(List<Vector3> polygon, int index, int jump = 1)
    {
        Vector3 start0 = polygon[index];
        Vector3 start1 = polygon[index + jump];

        List<int> rotateIndex = new List<int>();
        int count = polygon.Count;

        for (int i = 0; i < count; i++) rotateIndex.Add((i + index) % count);

        int start = (jump == 1) ? 2 : 3;

        for(int i = start; i < count - 1; i++)
        {
            Vector3 dot0 = polygon[rotateIndex[i]];
            Vector3 dot1 = polygon[rotateIndex[i + 1]];

            if (crossCheck2D(start0, start1, dot0, dot1) == true) return false;
        }

        return true;
    }

    bool ccwBy2D(Vector3 a, Vector3 b, Vector3 c)
    {
        Vector3 p = b - a;
        Vector3 q = c - b;

        return Vector3.Cross(p, q).y > 0;
    }

    (Vector3 pos0, Vector3 pos1) findStandardLine(List<Vector3> polygon)
    {
        int count = polygon.Count;

        for(int i = 0; i < count - 1; i++)
        {
            if (checkNotAllCrossLine(polygon, i) == true)
                return (polygon[i], polygon[i + 1]);
        }

        for(int i = 0; i < count - 2; i++)
        {
            if(ccwBy2D(polygon[i], polygon[i + 1], polygon[i + 2]) == false)
            {
                if(checkNotAllCrossLine(polygon, i, 2) == true)
                    return (polygon[i], polygon[i + 2]);
            }
        }

        Debug.LogError("Wrong!!");
        return (Vector3.zero, Vector3.zero);
    }

    float getDistancePointAndLine(Vector3 A, Vector3 B, Vector3 point)
    {
        Vector3 AB = B - A;
        return (Vector3.Cross(point - A, AB)).magnitude / AB.magnitude;
    }

    Vector3 getFarthestPoint(Vector3 pos0, Vector3 pos1, List<Vector3> polygon)
    {
        float maxLength = .0f;
        Vector3 point = Vector3.zero;

        foreach(Vector3 v in polygon)
        {
            float length = getDistancePointAndLine(pos0, pos1, v);
            if(maxLength < length)
            {
                maxLength = length;
                point = v;
            }
        }

        return point;
    }

    int compare(Vector3 a, Vector3 b, Vector3 target)
    {
        float lengthA = Vector3.Distance(a, target);
        float lengthB = Vector3.Distance(b, target);

        return lengthA < lengthB ? -1 : 1;
    }

    List<Vector3> sortByLine(Vector3 pos0, Vector3 pos1, List<Vector3> polygon)
    {
        List<Vector3> copy = new List<Vector3>(polygon);

        Vector3 infinity = (pos1 - pos0) * 99999;

        copy.Sort(delegate (Vector3 a, Vector3 b)
        {
            return compare(a, b, infinity);
        });

        return copy;
    }

    Vector3 getPerpendicularOntoLine(Vector3 A, Vector3 B, Vector3 D)
    {
        if (B == D) return B; // 예외

        Vector3 line1 = A - B;
        Vector3 line2 = D - B;

        float cos = Vector3.Dot(line1, line2) / (line1.magnitude * line2.magnitude);
        float lengthBD = Vector3.Distance(B, D);
        float projectionLength = lengthBD * cos;

        Vector3 normalAB = (B - A).normalized;

        return (B - normalAB * projectionLength);
    }

    Vector3[] getRectanglePosition(List<Vector3> polygon)
    {
        (Vector3 standardPos0, Vector3 standardPos1) = findStandardLine(polygon);
        Vector3 UP = getFarthestPoint(standardPos0, standardPos1, polygon);
        List<Vector3> sortList = sortByLine(standardPos0, standardPos1, polygon);
        Vector3 LEFT = sortList[0];
        Vector3 RIGHT = sortList[sortList.Count - 1];

        Vector3 leftDown = getPerpendicularOntoLine(standardPos0, standardPos1, LEFT);
        Vector3 rightDown = getPerpendicularOntoLine(standardPos0, standardPos1, RIGHT);

        Vector3 tempPoint = UP + (standardPos1 - standardPos0);

        Vector3 leftUp = getPerpendicularOntoLine(UP, tempPoint, LEFT);
        Vector3 rightUp = getPerpendicularOntoLine(UP, tempPoint, RIGHT);

        return new Vector3[] { rightDown, leftDown, leftUp, rightUp };

    }

    void setLineRenderer(LineRenderer lr, Color color)
    {
        lr.startWidth = lr.endWidth = .2f;
        lr.material.color = color;

        lr.loop = true;
    }

    Vector3 findMinXZ(List<Vector3> position)
    {
        Vector3 min = new Vector3(100000, 0, 100000);

        foreach (Vector3 p in position)
        {
            if (min.z >= p.z)
            {
                if (min.z == p.z)
                {
                    if (min.x > p.x)
                    {
                        min = p;
                    }
                }
                else
                {
                    min = p;
                }
            }
        }

        return min;
    }

    float ccw(Vector3 a, Vector3 b, Vector3 c)
    {
        Vector3 p = b - a;
        Vector3 q = c - b;

        return Vector3.Cross(p, q).y;
    }

    int compare2(Vector3 a, Vector3 b)
    {
        float tmp = ccw(minXZ, a, b);
        if (tmp > 0) return -1;
        else if (tmp == 0 && (Vector3.Distance(minXZ, a) < Vector3.Distance(minXZ, b))) return -1;
        return 1;
    }

    List<Vector3> getConvexHullVertices(List<Vector3> position)
    {
        List<Vector3> convexHull = new List<Vector3>();

        int index, sp;
        Vector3[] stack = new Vector3[position.Count];

        index = sp = 0;

        stack[sp++] = position[index++];
        stack[sp++] = position[index++];

        while (sp < 3)
        {
            float tmp = ccw(stack[sp - 2], stack[sp - 1], position[index]);

            if (tmp > 0) stack[sp++] = position[index++];
            else if (tmp == 0) // 직선인 경우는 점을 교체
            {
                sp--;
                stack[sp++] = position[index++];
            }
            else index++;
        }

        while (index < position.Count)
        {
            float tmp = ccw(stack[sp - 2], stack[sp - 1], position[index]);
            if (tmp > 0) stack[sp++] = position[index++];
            else sp--;
        }

        for (int i = 0; i < sp; i++) convexHull.Add(stack[i]);

        return convexHull;
    }
    private void Start()
    {
        lrs = lineRenderer.GetComponentsInChildren<LineRenderer>();
        setLineRenderer(lrs[0], Color.blue);
        setLineRenderer(lrs[1], Color.red);
    }

    private void Update()
    {
        List<Vector3> position = new List<Vector3>();
        foreach (Transform tr in vertices.transform) position.Add(tr.position);

        minXZ = findMinXZ(position);

        position.Sort(compare2);

        List<Vector3> convexHull = getConvexHullVertices(position);

        lrs[0].positionCount = convexHull.Count;
        lrs[0].SetPositions(convexHull.ToArray());

        Vector3[] points = getRectanglePosition(convexHull);

        int index = 0;
        foreach (Transform tr in rectangle.transform) tr.position = points[index++];

        lrs[1].positionCount = 4;
        lrs[1].SetPositions(points);
    }
}

 

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

ConvexHull.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