Angle Sort

Angle Sort

2D 좌표계에서 외판원 문제를 생각해보자. 정점 $P_1$, $P_2$, …, $P_N$을 임의의 순서로 전부 순회하고 다시 출발한 정점으로 돌아온다고 할 때, 해당 경로의 휴리스틱적인 최단거리는 어떻게 될 것인가?

휴리스틱적으로는 이렇게 생각할 수 있다. 모든 좌표의 평균을 내서 가상의 점 $P_0$가 있다고 해보자. 그러면 주변의 점들은 이 가상의 점을 둘러싼 원의 형태를 가지게 된 것으로 생각할 수 있다. 그러면 이 좌표들을 원을 그리듯 순회하는 방법이 최단거리는 아니더라도 어느 정도 휴리스틱적 정답에 유효하다고 추측해볼 수 있다.

이를 구체적으로 구현하기 위해서는 각도 정렬이 필요하다. 평균점 $P_0$ 부터의 각 점의 $x$, $y$ 좌표의 거리 차이를 $dx$, $dy$라 하자. 그러면, 임의의 점과 $x$축이 이루는 각도를 $\theta$라 할때, $\sin$함수의 정의에 의해, $\sin^2 \theta$는 아래와 같이 구할 수 있다.

• $\displaystyle \sin^2 \theta = \frac {dy^2} {dr^2} = \frac {dy^2} {(dx^2 + dy^2)}$

또한 이 함수값의 범위는 $\sin$함수 정의에 따라 아래 범위로 bound 된다.

• $0 \leq \sin^2 \theta \leq 1$

이 성질을 활용하면, x축으로부터 시계 반대방향으로 돌아가는 순서로 좌표를 정렬되게 하려면, 아래처럼 분기시킬 수 있다.

• 1사분면: $dx > 0$, $dy > 0$
  • $\sin^2 \theta$ 사용
• 2사분면: $dx < 0$, $dy > 0$
  • $2 - \sin^2 \theta$ 사용
• 3사분면: $dx < 0$, $dy < 0$
  • $2 + \sin^2 \theta$ 사용
• 4사분면: $dx > 0$, $dy < 0$
  • $4 - \sin^2 \theta$ 사용

이는 $\sin$ 함수의 개형과, 그 최대 / 최소값을 생각해보면 명백하다. 축에 있는 좌표는 그 어떤 쪽을 선택해도 값이 같다.

이로서 우리는, 그 어떤 math library를 쓰지 않고도, 각도로 좌표들을 정렬했다. 예시 동작코드는 아래와 같이 간단히 작성해보았다.

struct Point {
	int x, y;
};

double getKey(Point& a) {
	int ret = 0;
	int x = a.x, y = a.y;

	if (x == 0 && y == 0) return 0;

	double sin2 = 1.0 * y * y / (x * x + y * y);

	if (x >= 0 && y > 0) {
		return sin2;
	}
	else if (x < 0 && y >= 0) {
		return 2 - sin2;
	}
	else if (x <= 0 && y < 0) {
		return 2 + sin2;
	}
	else {
		return 4 - sin2;
	}

	return ret;
}
void test() {
	vector<Point> v;
	v.push_back({ 3, 1 });
	v.push_back({ 1, 2 });
	v.push_back({ 0, 4 });
	v.push_back({ -1, 3 });
	v.push_back({ -5, 2 });
	v.push_back({ -6, 0 });
	v.push_back({ -1, -1 });
	v.push_back({ 0, -3 });
	v.push_back({ 2, -3 });
	v.push_back({ 5, -1 });
	v.push_back({ 1, 0 });

	random_shuffle(v.begin(), v.end()); // 랜덤으로 섞어서 위 순서로 복구되는지 보자

	sort(v.begin(), v.end(), [&](Point& a, Point& b) {
		return getKey(a) < getKey(b);
	});

	for (auto& p : v) {
		printf("%d, %d\n", p.x, p.y);
	}
}

vector에 넣고 있는 순서대로 출력이 나오면 정상적으로 정렬된 것이다. 만약 각도와 스칼라의 크기가 적절히 배분되면서 정렬되기를 원한다면, 그 또한 key값을 조절하면 가능하다.