Plane Sweeping(평면 소거법)

평면 소거법

• 평면을 수평선 or 수직선(sweep line)으로 아래에서 위 or 왼쪽에서 오른쪽으로 쓸어가며 주어진 문제를 해결하는 기법
• 2차원의 복잡한 문제를 단순한 1차원 문제로 나누어 해결하는 방식 (sweep line이 1차원 표현)
• 2가지 자료구조 필요
  1. Event point 순서 결정하는 자료구조
     • sweep line의 움직임에 따라 그 상태 변경 필요
     • 상태가 변화되는 sweep line의 위치(event point)의 순서를 가지는 자료구조
  2. Sweep line의 상태를 나타내는 자료구조
     • 해결하고자 하는 데이터와 현 위치의 sweep line이 교차하고 있는 상태 표현

문제

• X축과 Y축에 각 변이 평행한 직사각형들이 N개 주어질 때, 이들의 합집합의 면적 구하기

해결

1. 왼쪽에서 오른쪽으로 쓸고 지나가는 수직선(sweep line)
2. sweep line의 좌표 x가 주어질 때, 사각형들을 수직선으로 잘랐을 때 단면의 길이를 반환하는 함수 cutLength()가 있다면 합집합의 넓이는 이 함수를 x에 대해 정적분한 결과 (실제로 적분할 필요X)

평면 소거법 설계

1. Event point의 순서 결정
   • 위 그림에서 단면의 길이가 변하는 지점은 직사각형의 왼쪽 끝점 or 오른쪽 끝점
   • 이 점들을 x 좌표 순으로 정렬
2. Sweep line의 상태를 나타내는 자료구조
   • sweep line이 지나는 좌표 x의 단면에서 사각형과 겹치는 부분 표시
   • 사각형의 위/아래 변의 y좌표 값드로 단면의 부분 구분
   • 배열 count을 유지해서 단면의 각 부분에서 겹치는 사각형 개수 저장
     

알고리즘

1. 직사각형 표현

struct Rectangle { int x1, y1, x2, y2; }; // x1 < x2, y1 < y2

1. 배열 Q[i]: event point 들의 집합, 직사각형들의 왼쪽, 오른쪽 변의 x좌표 정렬해서 저장
2. 배열 S[i]: sweep line에 의한 단면 정보, 직사각형들의 위쪽, 아래쪽 변의 y좌표 정렬해서 저장

FOR i in 0 → m1-1              //m1 : # of events
    x ← Q[i]
    IF sweep-line touches a left side of rectangle at Q[i] // 왼쪽에서 오른쪽으로 sweep
        delta ← 1
    ELSE    delta ← -1 // 사각형의 오른쪽 변 터치

    R ← the rectangle at Q[i]
    y1 ← R.y1    y2 ← R.y2  
    area ← 0 
    
    // count[i] = S[i] ~ S[i+1] 구간에 겹쳐진 사각형의 수
    FOR j in 0 → m2-1           //m2 : size of the array S 
    IF y1 <= S[j] AND S[j] < y2
        count[j] += delta
    
    cutlength ← 0 
    FOR j in 0 → m2-1 
    IF count[j] > 0 
        cutLength+= S[j+1] – S[j] 
    // the length between Q[i] and Q[i+1] * cutLength
    IF i+ 1 < m1
        area += cutLength* (Q[i+1] – x)
    

return area