참고
- Vector3.Cross로 평면 위에서 시계 방향 판단하기
- 볼록 껍질 (Convex Hull, Graham Scan)
- 컨벡스 헐로 볼록 다각형을 만드는 점의 좌표 구하기
- 컨벡스 헐로 임의의 점을 모두 포함하는 사각형 구하기
아래와 같이 임의의 다각형(삼각형, 별, 번개)이 있다.
그리고 다각형의 점을 모두 포함하는 사각형이 반드시 존재한다.
다각형의 좌표(y = 0)가 시계 방향으로 주어질 때,
이 다각형의 점을 모두 포함하는 사각형 좌표를 구해보자.
사각형 밑면의 두 점 좌표 찾기
위의 사각형의 예시(왼쪽 번개)의 사각형은 사실 이 알고리즘으로 찾을 수 없다.
실제로 찾을 사각형은 오른쪽의 사각형이 된다.
임의의 다각형을 덮는 사각형의 밑변을 구하는 것이 쉽기 때문이다.
즉, 다각형에서 사각형을 그릴 수 있는 두 점을 구해야 한다.
예를 들어 아래의 두 점은 사각형을 만들지 못한다.
위의 두 점이 사각형을 만들지 못하는 이유는
두 점을 잇는 무한한 직선이 다른 점이 만드는 유한한 직선과 교차하기 때문이다.
나머지 다각형의 점들이 교차하는지 여부는 2차원 평면에서 직선의 교점을 구하는 함수를 이용해서 판단할 수 있다.
무한한 직선 AB와 유한한 직선 CD가 교차한다면 crossCheck2D가 true가 된다.
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));
}
다각형의 좌표가 아래처럼 시계 방향으로 주어졌다고 하자.
0번째 점과 1번째 점을 선택하고, 남은 점들이 만드는 직선과 교차하는지를 체크하면 된다.
이때 점 1과 점 2가 만드는 직선과 점 10과 점 0이 만드는 직선은 당연히 교차점이 생기므로 검사하지 않는다.
그리고 점 0과 점 1이 사각형을 만들 수 있는 점이 아니라면, 다음 순서인 점 1과 점 2를 선택해서 검사해야 한다.
즉, 시계 방향으로 들어온 좌표의 polygon과 시작점 (index, index + 1)부터 모든 점을 검사한다.
참고로 끝 점에서 다시 0번째 점으로 돌아와 검사할 필요가 있기 때문에 index를 기준으로 rotateIndex를 만든다.
(2와 3이 선택된다면, <2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1> 로 좌표를 다시 만든다)
위의 내용을 checkNotAllCrossLine으로 구현할 수 있다.
bool checkNotAllCrossLine(List<Vector3> polygon, int index)
{
Vector3 start0 = polygon[index];
Vector3 start1 = polygon[index + 1];
List<int> rotateIndex = new List<int>();
int count = polygon.Count;
for (int i = 0; i < count; i++) rotateIndex.Add((i + index) % count);
for (int i = 2; 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;
}crossCheck2D가 하나라도 true라면 선택한 점 (index, index + 1)은 사각형을 만들 수 없으므로 false를 리턴한다.
이제 findStandardLine에서 튜플을 이용해 두 개의 점을 구한다.
(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]);
}
Debug.LogError("Wrong!!");
return (Vector3.zero, Vector3.zero);
}사각형 밑면의 두 점 좌표 찾기 개선
하지만 위의 알고리즘은 아래의 별 모양에 대해서는 동작하지 않는다.
어떠한 연속된 두 점을 잡더라도 사각형을 만들 수 없기 때문이다.
이 경우는 기준 점에서 한 칸 떨어진 점을 잡아야 한다.
이때, 두 점 사이의 점을 포함해 선택된 세 개의 점이 반시계 방향이어야 한다.
오른쪽처럼 시계 방향으로 두 점을 잡게 되면 직선이 교차하기 때문에 사각형을 만들 수 없다.
위의 경우는 모두 y = 0인 좌표이므로,
세 점의 좌표가 주어졌을 때 시계 방향을 판단하는 함수를 간결하게 아래와 같이 쓸 수 있다.
bool ccwBy2D(Vector3 a, Vector3 b, Vector3 c)
{
Vector3 p = b - a;
Vector3 q = c - b;
return Vector3.Cross(p, q).y > 0;
}
findStandardLine으로 연속된 두 점으로 좌표를 찾지 못한 경우,
세 점을 선택해서 반시계 방향인 경우 한 칸 건너뛰는 두 점을 선택하면 된다.
(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);
}
세 점을 선택하는 경우에는 세 번째 점 부터 검사해야 된다.
따라서 checkNotAllCrossLine에 jump를 추가하여 아래와 같이 수정한다.
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;
}
findStandardLine가 리턴하는 pos0이 선택된 점의 왼쪽, pos1이 오른쪽 점이다.
가장 위쪽, 왼쪽, 오른쪽의 점 구하기
위에서 두 개의 점을 선택하였으므로 남은 세 개의 점을 구하면 사각형을 만들 수 있다.
이 점은 현재 그려진 빨간 선을 기준으로 가장 왼쪽에 있는 점, 가장 오른쪽에 있는 점, 그리고 가장 위에 있는 점이다.
먼저 가장 위에 있는 점을 구해보자.
점과 직선 사이의 거리 공식을 이용하면 가장 위에 있는 점을 구할 수 있다.
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;
}
findStandardLine으로 구한 점 두 개와 다각형의 좌표를 모두 탐색해서 가장 위에 있는 점 UP을 구한다.
(Vector3 standardPos0, Vector3 standardPos1) = findStandardLine(polygon);
Vector3 UP = getFarthestPoint(standardPos0, standardPos1, polygon);
이제 가장 왼쪽의 점을 구해보자.
이 점들은 선택된 두 점을 기준으로 정렬해야 한다.
그러기 위해서 왼쪽 → 오른쪽을 잇는 직선 중 적절히 먼 점을 기준으로 잡아 정렬한다.
실제 무한일 필요는 없으므로 다각형의 크기를 고려하여 99999를 곱했고,
멀리 있는 점(infinity)을 기준으로 리스트를 정렬하였다.
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;
}
정렬이 잘 되었다면 정렬된 list 중 첫 번째 원소가 가장 왼쪽에 있는 점이고, 가장 끝에 있는 원소가 오른쪽 점이 된다.
List<Vector3> sortList = sortByLine(standardPos0, standardPos1, polygon);
Vector3 LEFT = sortList[0];
Vector3 RIGHT = sortList[sortList.Count - 1];사각형 점 4개 구하기
이제 본격적으로 사각형을 만드는 점 4개를 구해보자.
각 점의 이름은 아래와 같다.
LeftDown은 두 점을 잇는 직선과 위에서 구한 LEFT의 수선의 발이다.
직선 AB와 점 D가 만드는 수선의 발은 아래와 같다.
이때 오른쪽의 점도 마찬가지로 수선의 발이므로, B와 D가 같은 경우는 B를 return 한다.
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);
}
따라서 LeftDown과 RightDown은 아래와 같다.
위 예시는 RightDown이 Right와 일치한다.
Vector3 leftDown = getPerpendicularOntoLine(standardPos0, standardPos1, LEFT);
Vector3 rightDown = getPerpendicularOntoLine(standardPos0, standardPos1, RIGHT);
이제 가장 위에 있는 점 UP을 기준으로 적절히 TempPoint를 잡아 직선을 만든다.
이 직선은 선택된 두 점과 반드시 평행하므로 아래와 같이 구할 수 있다.
Vector3 tempPoint = UP + (standardPos1 - standardPos0);
LeftUp과 RightUp은 이 직선의 수선의 발이므로 아래와 같이 구할 수 있다.
Vector3 leftUp = getPerpendicularOntoLine(UP, tempPoint, LEFT);
Vector3 rightUp = getPerpendicularOntoLine(UP, tempPoint, RIGHT);
그림으로 보면 아래와 같다.
위의 코드를 정리해서 4개의 점을 구하는 함수 getRectanglePosition를 구현하자.
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 };
}테스트
다각형의 시계 방향의 좌표 = Polygon, 사각형의 네 점 Rectangle, 그리고 라인 렌더러를 아래와 같이 구성한다.
빈 오브젝트 Test에 아래와 같이 할당하였다.
게임을 실행하고 다각형 좌표를 임의로 바꾸면 다각형을 모두 포함하도록 사각형이 그려지는 것을 알 수 있다.
재밌는 점은 꼭 시계 방향으로 다각형이 주어지지 않더라도 알고리즘이 사각형을 적절히 만들 수 있다.
하지만 위의 경우 처럼 사각형을 만드는 것이 모든 경우에 성립하는 것은 아니다.
현재 알고리즘은 다각형의 좌표가 시계 방향임을 가정하였다.
아래와 같이 사각형이 만들어지지 않는 경우도 존재한다.
이 경우에는 컨벡스 헐(Convex Hull) 알고리즘을 이용해 바깥의 점만 추출하여 볼록 다각형으로 만들어야 한다.
전체 코드는 다음과 같다.
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class PolygonInSquare : MonoBehaviour
{
public GameObject vertices;
public GameObject rectangle;
public GameObject lineRenderer;
LineRenderer[] lrs;
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;
}
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);
lrs[0].positionCount = position.Count;
lrs[0].SetPositions(position.ToArray());
Vector3[] points = getRectanglePosition(position);
int index = 0;
foreach (Transform tr in rectangle.transform) tr.position = points[index++];
lrs[1].positionCount = 4;
lrs[1].SetPositions(points);
}
}
위의 실행결과는 아래의 unitypackage에서 확인 가능하다.
Unity Plus:
Easy 2D, 3D, VR, & AR software for cross-platform development of games and mobile apps. - Unity Store
Have a 2D, 3D, VR, or AR project that needs cross-platform functionality? We can help. Take a look at the easy-to-use Unity Plus real-time dev platform!
store.unity.com
Unity Pro:
Unity Pro
The complete solutions for professionals to create and operate.
unity.com
Unity 프리미엄 학습:
Unity Learn
Advance your Unity skills with live sessions and over 750 hours of on-demand learning content designed for creators at every skill level.
unity.com
댓글