33. Computational Geometry

몇 개의 계산 기하학 알고리즘을 알아보자.

33.1. Line-segment properties

서로 다른 두 점 p_{1}, p_{2}볼록 결합0 \leq \alpha \leq 1에 대해 p_{3} = \alpha p_{1} + (1 - \alpha) p_{2}가 되는 p_{3}이다. 서로 다른 두 점 p_{1}, p_{2}에 대해 선분 \bar{p_{1}p_{2}}은 볼록 결합의 집합이다. 이 때 p_{1}, p_{2}를 선분의 끝점이라 한다. 둘의 순서가 중요할 경우 이 선분을 방향 선분이라 한다. p_{1}원점일 경우 이 방향 선분을 벡터라 한다. 이 절에서는 다음 질문을 다룬다:

  • 두 방향 선분 \vec{p_{0}p_{1}}\vec{p_{0}p_{2}}가 있을 때 한 쪽이 다른 쪽에 대해 시계방향인지 알려면?
  • 두 선분 \bar{p_{0}p_{1}}\bar{p_{1}p_{2}}를 이 순서로 순회하면 p_{1}에서 좌회전을 하는가?
  • 선분 \bar{p_{1}p_{2}}\bar{p_{3}p_{4}}가 교차하는가?

이 모두 곱셈 덧셈 뺄셈 비교만으로 O(1)에 알 수 있다.

Cross products

벡터 p_{1}, p_{2}외적은 두 벡터가 만드는 평행사변형의 넓이이다. 이는 p_{1} \times p_{2} = x_{1}y_{2} - x_{2}y_{1} = -p_{2} \times p_{1}이 성립한다. 외적이 0인 두 벡터를 공직선성이라 한다. 즉, 같은 방향이거나 반대 방향이다. p_{1} \times p_{2}가 양수면 \vec{p_{0}p_{1}}\vec{p_{0}p_{2}}에 대해 시계 방향이다. 음수면 반시계 방향이다.

Determining whether consecutive segments turn left or right

연속된 선분이 좌회전을 하는지 우회전을 하는지도 시계방향/반시계방향과 같은 질문이다.

Determining whether two line segments intersect

두 선분이 교차하는지를 알려면 어떻게 할까? 선분 \bar{p_{1}p_{2}}는 어떤 직선에 대해 p_{1}은 한 쪽에, p_{2}는 다른 쪽에 있다면 그 직선을 가로지른다고 한다. 이를 통해 두 선분이 교차하는지를 아는 방법은 다음과 같다.

SEGMENTS-INTERSECT(p_1, p_2, p_3, p_4)
d_1 = DIRECTION(p_3, p_4, p_1)
d_2 = DIRECTION(p_3, p_4, p_2)
d_3 = DIRECTION(p_1, p_2, p_3)
d_4 = DIRECTION(p_1, p_2, p_4)
if ((d_1 > 0 and d_2 < 0) or (d_1 < 0 and d_2 > 0)) and ((d_3 > 0 and d_4 < 0) or (d_3 < 0 and d_4 > 0))
    return TRUE
else if d_1 == 0 and ON-SEGMENT(p_3, p_4, p_1)
    return TRUE
else if d_2 == 0 and ON-SEGMENT(p_3, p_4, p_2)
    return TRUE
else if d_3 == 0 and ON-SEGMENT(p_1, p_2, p_3)
    return TRUE
else if d_4 == 0 and ON-SEGMENT(p_1, p_2, p_4)
    return TRUE
else
    return FALSE
DIRECTION(p_i, p_j, p_k)
return (p_k - p_i) × (p_j - p_i)
ON-SEGMENT(p_i, p_j, p_k)
if min(x_i, x_j) ≤ x_k ≤ max(x_i, x_j) and min(y_i, y_j) ≤ y_k ≤ max(y_i, y_j) 
    return TRUE
else
    return FALSE

Other applications of cross products

점들 정렬 등 다른 다양한 부분에도 외적을 이용할 수 있다.

33.2. Determining whether any pair of segments intersects

선분 n개 중 교차하는 선분이 있는지를 탐색하는 O(n \lg n) 알고리즘을 알아보자. 이는 쓸기 알고리즘으로, 쓸기 직선이 대개 왼쪽에서 오른쪽으로 주어진 기하학적 오브젝트들을 쓸고 지나간다.

Ordering segments

쓸기 직선이 두 선분과 모두 교차할 경우 두 선분은 비교 가능하다 한다. 이 때 선분 s_{1}의 쓸기 직선과의 교점이 선분 s_{2}의 쓸기 직선과의 교점보다 위면 s_{1}s_{2} 위에 있다고 한다. 이는 완전 선순서이다.

Moving the sweep line

쓸기 알고리즘은 두 데이터를 유지한다.

  • 쓸기 직선 상태 : 현재 쓸기 직선이 교차하고 있는 오브젝트.
  • 사건-점 일정 : 쓸기 직선이 지나가는 순서에 따라 배치한 사건 점들의 배열.

선분을 정렬할 때 두 선분의 오른쪽 x좌표가 같으면 왼쪽 x좌표를 기준으로 순서를 매긴다.

Segment-intersection pseudocode

이를 통해 선분 n개 중 교차하는 선분이 있는지를 탐색하는 O(n \lg n) 알고리즘은 다음과 같다.

ANY-SEGMENTS-INTERSECT(S)
T = Φ
sort the endpoints of the segments in S from left to right, breaking ties by putting left endpoints before right endpoints and breaking further ties by putting points with lower y-coordinates first
for each point p in the sorted list of endpoints
    if p is the left endpoint of a segment s
        INSERT(T, s)
        if (ABOVE(T, s) exists and intersects s) or (BELOW(T, s) exists and intersects s)
            return TRUE
    if p is the right endpoint of a segment s
        if both ABOVE(T, s) and BELOW(T, s) exist and ABOVE(T, s) intersects BELOW(T, s)
            return TRUE
        DELETE(T, s)
return FALSE

Correctness

ANY-SEGMENTS-INTERSECT가 true를 반환하는 것과 n개 선분 중 교차하는 선분이 있는지가 동치임을 보일 수 있다.

Running time

정렬에 O(n \lg n)이 들고, 루프 내부가 O(\lg n)인데 이것이 O(n)번만큼 돌기 때문에 총 시간 복잡도는 O(n \lg n)이다.

33.3. Finding the convex hull

점의 집합 Q의 볼록 껍질 CH(Q)는 Q의 모든 점들을 경계 또는 내부에 포함하는 볼록다각형이다. 이를 O(n \lg n)이나, O(nh) (h는 볼록 껍질의 점들 수)에 구하는 알고리즘을 알아보자. 다음 방법들이 있다.

  • 증가법에서는 점들을 정렬한 뒤 왼쪽에서부터 i – 1개 점의 볼록 껍질에 i번째 점을 더해 업뎅트한다. O(n \lg n)에 구현 가능하다.
  • 분할정복법에서는 점들을 반씩 분할해 각각의 볼록 껍질을 구한 뒤 이를 \Theta(n)으로 합친다. 역시 O(n \lg n)이다.
  • 가지치기-탐색법은 최악 시간 중위값 탐색 알고리즘과 비슷하다. 점들 수가 h개라면 점근적으로 O(n \lg h)가 든다.

볼록 껍질 문제는 가장 먼 쌍 문제 등에도 응용될 수 있다.

Graham’s scan

볼록 껍질을 찾는 그라함의 스캔은 다음과 같다.

GRAHAM-SCAN(Q)
Let p_0 be the point in Q with the minimum y-coordinate, or the leftmost such point in case of a tie
Let <p_1, p_2, ..., p_m> be the remaining points in Q, sorted by polar angle in counterclockwise order around p_0 
(if more than one point has the same angle, remove all but
 the one that is farthest from p_0)
Let S be an empty stack
PUSH(p_0, S)
PUSH(p_1, S)
PUSH(p_2, S)
for i = 3 to m
    while the angle formed by points NEXT-TO-TOP(S), TOP(S),
 and p_i makes a nonleft turn
        POP(S)
    PUSH(p_i, S)
return S

Theorem. (Correctness of Graham’s scan) GRAHAM-SCAN이 점의 집합 Q에 실행되면, \lvert Q \rvert \geq 3이면 종료 시 스택 S는 CH(Q)의 꼭지점들을 반시계방향으로 갖는다.

점들을 정렬하는 데 있어 \Theta(n \lg n)이 들고, 볼록 껍질을 형성하는 데는 O(n)이 드므로 수행 시간은 O(n \lg n)이다.

Jarvis’s march

자비스의 행진포장 싸기 (선물 싸기) 로 알려진 방법으로 볼록 껍질을 계산한다. 이는 볼록 껍질의 꼭지점 수가 h일 때 O(nh)에 볼록 껍질을 계산한다. 이는 시작점으로부터 각이 가장 적은 꼭지점을 탐욕적으로 선택해서 오른쪽 사슬왼쪽 사슬을 각각 계산한다.

33.4. Finding the closest pair of points

점들 n개 중에 가장 가까운 쌍을 O(n \lg n)에 찾아 보자.

The divide-and-conquer algorithm

점들을 한 수직선을 기준으로 왼쪽 절반, 오른쪽 절반으로 나눈다. 두 집단에서 가장 가까운 쌍들을 각각 계산한 뒤 이들이 반환한 최소 거리값 중 더 작은 값을 \delta라 한다. 이후 점들을 나눈 수직선을 기준으로 반경 2 \delta 내에 있는 점들의 쌍을 조사해 최소값을 찾는다.

Correctness

최소 거리가 나올 수 있는 후보군을 조사해 보면 이 알고리즘의 정당성은 명확하다.

Implementation and running time

수행 시간은 O(n \lg n)이다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중