C 로 구현한 알고리즘 - 3부 알고리즘, 17장. 기하 알고리즘

책의 기하 알고리즘 부분에서는

1. 선분 교차 테스트

2. 컨벡스 헐

3. 구면 위의 호의 길이

를 다룬다.

이전 TSP 에서 선분교차에 대해서 자세한 방법에 대한 이해를 못하여,

대충 직사각형 교차 체크만 하고 넘어갔기에, 거기에 대해 좀 자세히 알아보고,

나머지는 개념만 이해하고 넘어가겠다.

1. 선분 교차 테스트

점 A, B, C, D 에 대하여

선분 AB 와 선분 CD 가 서로 교차하는지,

컴퓨터를 이용하여 확인하는 방법에 대한 것이다.

수학에서라면 간단히 두 선분의 직선의 방정식의 해를 구하여

그 해가 선분의 범위안에 들어가는지 체크하면 쉽지만,

일반적으로 정확한 실수 연산이 되지 않는 컴퓨터 언어로는

그렇게 간단히 되지 않는다.

그래서 다음과 같은 2 단계를 따른다.

i) 선분의 양 끝 점을 대각선으로 하는 직사각형을 그려 교차하는 부분이 있는지 체크 한다.

   교차하는 부분이 없다면 교차하지 않음. 교차하는 부분이 있다면 ii) 로.

ii) 삼각형 ABC와 삼각형 ABD의 Signed Area의 곱이 <= 0, (곱이 0 이라면 선분이 겹치는 경우)

   AND 삼각형 CDA와 삼각형 CDB의 Signed Area의 곱이 <= 0 인지 확인.

i) 조건을 패스하고 ii) 조건이 True 가 된다면 두 선분은 교차한다.

Signed Area 는 세 점으로 만들어지는 면적을 구하는 데,

세 점의 방향에 따라 '+' 나 '-' 값을 가진다.

Signed Area 를 구하는 방법은 다음과 같다.

점 A, B, C 의 (x, y) 좌표를 각각 (a[0], a[1]), (b[0], b[1]), (c[0], c[1]) 이라고 했을 때,

삼각형 ABC의 Signed Area = ( a[0]*b[1] - a[1]*b[0] + b[0]*c[1] - b[1]*c[0] + c[0]*a[1] - c[1]*a[0] ) / 2

공식으로 구할 수 있다.

Signed Area의 공식은 고등학교 때 배운 수학으로 구할 수 있다.

물론 고등학교 때는 Signed Area에 대한 개념이 없이 Signed Area의 절대값을 구하여,

단순히 삼각형의 넓이를 구하는 방법에 대한 것만 나와 있다.

위 공식은 아래와 같은 방법으로 증명할 수 있는데,

말로 간단히는 1/2 x (선분 AB의 길이) x (C에서 직선AB까지의 거리) 가 위와 같은 결과가 나온다.

그래서...

  

2. 컨벡스 헐(Convex Hull)

어떤 점 집합의 컨벡스 헐은 그 집합의 모든 점들을 포함하는 가장 작은 볼록 다각형을 말한다.

(출처: http://en.wikipedia.org/wiki/File:ConvexHull.svg )

위 그림에서 파란색으로 표시된 다각형이 바로 컨벡스 헐이다.

점 집합 P에 대한 컨벡스 헐을 만드는 한 방법은 Jarvis 행진(Jarvis's march)이라는 방법을 사용하는 것이다.

(출처: http://en.wikipedia.org/wiki/File:Jarvis_march_convex_hull_algorithm_diagram.svg )

위와 같이 P0 에서 시작하여 각 점에 대하여 각도가 가장 작거나 큰 점들을 찾아서 계속 연결해 나가면 된다.

3. 구면 위의 호의 길이

구면 위의 두 점이 있을 때, 두 점의 거리(호의 길이를 말함)를 계산하는 방법에 대한 것이다.

자세한 수식은 생략하고 간단히 과정을 설명하겠다.

1. 두 점 A, B 의 좌표가 (x,y,z) 형태가 아닌,

   (구의 중심으로 부터의 거리, xz평면에서 y축 방향으로의 각도, yz평면에서 x축 방향으로의 각도) 형태로

   주어질 경우 (x,y,z) 형태의 좌표로 바꾼다.

2. 벡터의 내적을 이용하여 두 점 A, B의 각도(a)를 구한다.

3. 아래와 같이 원의 호를 구하는 공식을 이용하여, 호의 길이를 구한다.

 

결론

기하 문제들을 컴퓨터로 표현하고 해결하는 것은 흥미로운 과정이다.

특히, 게임 프로그래밍에 관심이 있다면 필수 과목이 아닐까?