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

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

공식으로 구할 수 있다.


  



2. 컨벡스 헐(Convex Hull)

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


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


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


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

 File:Jarvis march convex hull algorithm diagram.svg
(출처: 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. 아래와 같이 원의 호를 구하는 공식을 이용하여, 호의 길이를 구한다.

 



결론

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

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

반응형

설정

트랙백

댓글