14 / 16강

점과 방향을 다루는 기하 알고리즘

위치 데이터는 점으로, 이동은 선분으로 나타낼 수 있습니다. 기하 알고리즘에서는 그림의 인상보다 좌표로 판정할 수 있는 조건을 찾아야 합니다.

일직선 위의 가장 가까운 두 점

좌표가 [1, 4, 5, 12]라면 정렬한 뒤 이웃한 점의 차이만 보면 됩니다. 차이는 3, 1, 7이므로 답은 4와 5입니다. 사이에 다른 점이 있는 두 점을 골랐다면 그 사이의 이웃 쌍 중 더 가까운 쌍이 있기 때문입니다.

이미 정렬되었다면 O(n)이고, 정렬부터 해야 한다면 보통 O(n log n)입니다. 두 점이 같은 위치이면 거리는 0입니다.

평면에서 왼쪽으로 꺾이는지 보기

세 점 A, B, C가 있을 때, A에서 B로 가다가 C로 가는 방향을 봅니다. y축이 위로 증가하는 좌표계에서 다음 값이 양수이면 반시계 방향, 음수이면 시계 방향, 0이면 일직선입니다.

def cross(a, b, c):
    return ((b[0] - a[0]) * (c[1] - a[1])
            - (b[1] - a[1]) * (c[0] - a[0]))

print(cross((0, 0), (3, 0), (1, 2)))

결과는 6이므로 반시계 방향입니다. 이 계산은 두 벡터의 2차원 외적에 해당합니다. 선분 교차나 점들을 둘러싸는 볼록 껍질을 구할 때 쓰입니다. 화면 좌표처럼 y축이 아래로 증가하면 화면에서 보이는 회전 방향은 반대입니다.

차원이 늘면 같은 요령이 통하지 않습니다

평면의 가장 가까운 두 점은 x좌표 정렬에서 바로 이웃하지 않을 수 있습니다. 가령 (0,0), (1,100), (2,0)은 x순서에서 양끝인 두 점이 가장 가깝습니다. 1차원 풀이를 그대로 옮기면 틀립니다. 평면에서는 분할 정복 등으로 경계 주변 후보까지 살펴봐야 합니다.

실수 좌표에서는 반올림 오차 때문에 ‘정확히 0인가’ 판정이 흔들릴 수 있습니다. 입력이 정수라면 정수 계산을 유지하는 것이 도움이 됩니다.

확인 문제

A=(0,0), B=(2,0), C=(1,0)에서 외적이 0이면 C가 AB 선분 안에 있다는 것까지 보장할까요?