[C++]백준 - 16135번 문제

16135번: OBB(Oriented bounding box) (acmicpc.net)

16135번: OBB(Oriented bounding box)

 

16135번 : OBB(Oriented bounding box)

---

안녕! 요즘 2차원 슈팅 게임을 만들고 있는데, 좀 어려운 부분이 생겼어. 플레이어가 적이 쏘는 총알에 맞으면 데미지를 입는 것을 구현하고 싶은데, 혹시 네가 도와줄 수 있니? 히트박스(실제로 두 물체의 충돌이 인식되는 공간)는 얼마든지 회전할 수 있는 직사각형 모양이야.

[분리축 이론]

두 볼록다각형이 겹쳐 있지 않으면, 반드시 두 도형을 분리하는 직선이 존재한다. 또한, 그 직선의 방향으로 투영하면 그림자가 겹치지 않을 것이다. 두 도형이 겹쳐 있다면 어떤 방향으로 투영하더라도 반드시 그림자가 겹친다.

 

입력

---

첫 줄에 두 직사각형 A와 B의 모든 꼭짓점의 좌표가 시계방향 또는 반시계방향으로 주어진다. 좌표의 절댓값은 2,000이하이다. 넓이가 0인 직사각형이 주어질 수도 있다.

 

출력

---

두 직사각형이 겹치면 1, 겹치지 않으면 0을 출력한다. 자세한 내용은 문제를 참고한다.

서브태스크 1 (15점)

---

직사각형의 변이 축과 평행하다.

 

 

서브태스크 2 (85점)

---

추가 제한 없음.

 

---

 

생각해 볼 점

---

기하 문제입니다.

 

함수를 하나씩 만들어가면서 풀면 생각보다 어렵지 않습니다.

 

 

우선, 핵심은 OBB 충돌 판정입니다.

 

OBB 충돌 판정이란 두 볼록 다각형의

 

모든 변에 대한 투영구간이 겹치는지 확인하여 충돌을 검사하는 방법입니다. 

 

 

위 그림과 같이 변에 평행한 기준 벡터를 구합니다.

 

원래라면 총 8개의 벡터가 나오겠지만, 직사각형이므로 총 4개의 기준 벡터만 구하면 됩니다.

 

그 중 하나인 빨간 벡터를 기준으로 OBB 과정을 진행하면

 

위 그림과 같이 기준 벡터에 대해 사각형을 투영하여

 

그림자가 서로 겹치지 않으면 충돌하지 않은 것으로 판단합니다. 

 

이 때, 이를 판단하는 근거로 사각형 두 중심점을 잇는 벡터 d를 구합니다.

 

d를 기준 벡터에 정사영하여 d'을 위 그림과 같이 구했습니다.

 

 

 

위 그림과 같이 사각형을 벡터에 투영하여 나온 그림자의 길이 중,

 

중심으로 부터의 길이 L1과 L2의 합이 d'보다 클경우 그림자가 겹쳤다고 판단합니다.

 

그리고 이 과정을 모든 기준 벡터에 대해 실행하여

 

모든 그림자가 겹치면 두 사각형은 충돌했다고 볼 수 있습니다.

 

그림자가 1회라도 겹치지 않으면 충돌하지 않았습니다.

 

 

* 정사영에 대하여

 

- 정사영은 본래 단위벡터(길이가 1)에 내려야 하는 것이 맞습니다.

 

하지만, 부동 소수점에서의 Normalize 과정은 오차를 만들게 됩니다.

 

따라서, 본 문제에서는 굳이 Normalize 과정을 거치지 않습니다.

 

왜냐하면, OBB 판정과정에서는 단순히 크기 비교만 하기 때문에 정확한 값을 구하지 않아도 되기 때문입니다.

 

 

코드

---

#include <iostream>
#include <cmath>
#define Point pair<double, double>
#define X first
#define Y second
using namespace std;

//사각형 중심을 구함
Point GetSquareCenter(Point const& A, Point const& B, Point const& C, Point const& D)
{
	return { (A.X + B.X + C.X + D.X) / 4, (A.Y + B.Y + C.Y + D.Y) / 4 };
}

//A->B 벡터를 구함
Point GetVectorAB(Point const& A, Point const& B)
{
	return { B.X - A.X, B.Y - A.Y };
}

//내적
double DotProduct(Point const& A, Point const& B)
{
	return A.X * B.X + A.Y * B.Y;
}

int main()
{
	Point a1, a2, a3, a4;
	Point b1, b2, b3, b4;

	scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &a1.X, &a1.Y, &a2.X, &a2.Y, &a3.X, &a3.Y, &a4.X, &a4.Y);
	scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &b1.X, &b1.Y, &b2.X, &b2.Y, &b3.X, &b3.Y, &b4.X, &b4.Y);

	Point a_Center = GetSquareCenter(a1, a2, a3, a4);
	Point b_Center = GetSquareCenter(b1, b2, b3, b4);
	Point unitVectors[4] = { GetVectorAB(a1, a2), GetVectorAB(a2, a3), GetVectorAB(b1, b2), GetVectorAB(b2, b3) };
	Point dVector = GetVectorAB(a_Center, b_Center);


	//유닛 벡터에 대한 정사영 후 크기 비교
	for (int i = 0; i < 4; i++)
	{
		float dotDU = abs(DotProduct(dVector, unitVectors[i]));
		float sumDotVectors = 0.0f;
		for (int j = 0; j < 4; j++)
			sumDotVectors += abs(DotProduct(unitVectors[i], unitVectors[j]));
		
		//그림자가 겹치지 않음
		if (dotDU >= (sumDotVectors / 2))
		{
			printf("0");
			return 0;
		}
	}
	printf("1");
	return 0;
}

 

그 외

---