재시민

단순 폐쇄 경로 : N 개의 점이 주어졌을 때 이 점들을 모두 경유하고 출발점에 되돌아오는 비 교차 경로

우편배달부 문제를 예로 들어 단순 폐쇄 경로를 찾아보자

방법 

1.  기준점 D 설정
   1. y 좌표가 가장 작은 값으로 설정하되 동일한 값이 있다면 x 좌표도 최소인 점으로 선정
2.  D에서 나머지 점들 P 각각에 대한 반직선 DP 라 할 때, 반직선 Dx 와 DP 사이의 각도들을 계산
3.  각도를 기준으로 P 점들을 오름차순으로 정렬
4.  기준점부터 시작해 정렬된 점들을 순서대로 직선 연결

각도를 구하는 방법을 생각해보자

• 아크탄젠트를 이용해 각도를 구하자
  • 가장 흔한방법이지만 계산속도가 느리다.
• 상대각도
  • 실제각도는 아니지만 효율적인 각도비교가 가능하다.

상대각도 구하는 방법

이 때 점의 사분면 위치에 따라 dx, dy 값이 음수가 되는 경우가 생긴다.

그렇게 되면 점의 정확한 상대각도를 구하기 어려워지기 때문에 식조작이 필요하다.

1사분면에서의 상대각도는 0과 1사이의 값이므로 360도의 상대각도가 4 이므로

2사분면 : 2 - 상대각도

3사분면 : 2 + 상대각도

4사분면 : 4 - 상대각도

이때 상대각도를 구하는 dx, dy 에는 절댓값을 씌워준다.

위의 식을 ComputeAngle 함수로 만들어 표현한 코드는 아래와 같다.

float ComputeAngle(struct point A, struct point B) {
	int Dx, Dy; float Angle;
	Dx = B.x - A.x; Dy = B.y - A.y;
	if ((Dx >= 0) && (Dy == 0)) Angle = 0;
	else {
		Angle = abs(Dy) / (abs(Dx) + abs(Dy));
		if ((Dx < 0) && (Dy >= 0)) Angle = 2 - Angle;
		else if ((Dx <= 0) && (Dy < 0)) Angle = 2 + Angle;
		else if ((Dx > 0) && (Dy < 0)) Angle = 4 - Angle;
	}
    return Angle * 90.0;
}