개념

계산 기하학에서 스위핑, 혹은 스윕 라인 알고리즘이라 불리는 것은 유클리드 기하학에서 여러문제를 풀기위한 알고리즘 패러다임으로 개념적인 스윕 라인/표면을 사용합니다. (출처)

거창하게 적어놓았지만 간단하다. 2차원이면 선이 평면을 쓸면서/훑으면서 (sweep) 지나가는 것이고, 3차원이면 선/면이 훑고 지나가는 것이다. 아래 그림을 보면 이해가 쉽다.

위에서부터 선이 평면을 훑으며 추가적인 작업이 이루어 진다.

2차원을 기준으로 선이 평면을 훑으며 지나가면 선과 닿는 기하 객체들에대해서 기하적인 연산을 한다.

구현

다음과 같은 패턴을 통해서 구현한다.

• 이벤트 정의 (라인이 평면을 쓸면서 만나는 이벤트)
• 이벤트에 맞게 객체들을 정렬
• 활성 집합 유지
• 활성 집합내의 후보군들 확인

가장 가까운 점 (Closest Pair)를 예로 들면

• 라인이 평면을 쓸면서 점들을 만남. 여기서 x좌표를 활용
• x좌표를 기준으로 정렬
• line 근처의 점들 중 x좌표의 차이가 d 미만인 점들만 유지
• 새로운 점을 만나면 후보군들에서 다음을 수행
  • 오래된 점은 제거
  • 새로운점의 y좌표에서 +-d 내부에 있는 점만 확인
  • 거리 갱신시
  • 새로운 점을 집합에 넣기

활용

• 가장 가까운 점 (Closest Pair of Points)
• 선분 교차 여부/개수 판정
• 직사각형 합집합 면적
• 선분들의 합잡합 길이