계산기하학

계산기하학(Computational geometry, 計算幾何學)은 컴퓨터 과학과 수학의 한 분야로, 기하학적 문제를 알고리즘적으로 해결하는 방법을 연구한다.

개요

계산기하학은 1970년대 컴퓨터 그래픽스, CAD(Computer-Aided Design), 로보틱스 등의 발전과 함께 독립된 학문 분야로 형성되었다. 이 분야는 주어진 점, 선분, 다각형 등의 기하학적 객체에 대해 다양한 계산 문제를 해결하기 위한 알고리즘을 설계하고 분석하는 것을 주요 목표로 한다. 정렬이나 탐색과 같은 고전적인 알고리즘 기법을 넘어서, 특수한 기하학적 제약조건을 고려해야 하는 경우가 많기 때문에 복잡도 분석과 공간 분할 기법이 핵심 요소로 작용한다.

주요 문제 유형

계산기하학에서 다루는 대표적인 문제들은 다음과 같다.

• 볼록 껍질 문제(convex hull): 평면상의 점 집합 중 가장 바깥쪽 점들로 이루어진 볼록 다각형을 찾는 문제
• 최근접 점 쌍 문제(closest pair of points): 유클리드 거리 기준으로 가장 가까운 두 점을 찾는 문제
• 선분 교차 판별(segment intersection): 주어진 선분들이 서로 교차하는지를 판단하거나 교차점을 구하는 문제
• 포함 여부 테스트(point-in-polygon): 특정 점이 다각형 내부에 있는지 판별하는 문제
• 보로노이 다이어그램(Voronoi diagram): 평면상의 점 집합에 대해 각 점에 가까운 영역을 나누는 분할 구조
• 델로네 삼각분할(Delaunay triangulation): 주어진 점들을 삼각형으로 분할하되, 특정 조건(서로 다른 삼각형의 내접원이 겹치지 않음)을 만족시키는 방법

접근 방식

계산기하학은 크게 두 가지 접근 방식으로 나뉜다.

• 이산 계산기하학(discrete computational geometry): 주로 정수 좌표, 유한한 점의 집합 등 이산적인 기하 데이터를 대상으로 알고리즘을 설계
• 수치 계산기하학(numerical computational geometry): 부동소수점 연산의 오차를 고려하며 기하 알고리즘의 수치적 안정성과 정확성을 분석

또한 차원(dimension)의 증가에 따라 문제의 복잡도가 급격히 증가하는 "차원의 저주(curse of dimensionality)" 현상도 계산기하학에서 중요한 이슈로 다뤄진다.

응용

계산기하학은 이론적 연구뿐 아니라 다양한 실무 분야에서도 응용된다.

• 컴퓨터 그래픽스: 충돌 검출, 모델링, 렌더링 등
• 로보틱스: 경로 계획, 환경 인식
• GIS(지리정보시스템): 공간 분석, 거리 계산, 지도 처리
• 컴퓨터 비전: 이미지 세분화, 형태 인식
• 물리 시뮬레이션 및 CAD

파이썬 예제: 볼록 껍질

import matplotlib.pyplot as plt
from scipy.spatial import ConvexHull
import numpy as np

points = np.random.rand(10, 2)
hull = ConvexHull(points)

plt.plot(points[:,0], points[:,1], 'o')
for simplex in hull.simplices:
    plt.plot(points[simplex, 0], points[simplex, 1], 'k-')
plt.show()

같이 보기

• 기하 알고리즘
• 볼록 껍질
• 보로노이 다이어그램
• 델로네 삼각분할
• 차원의 저주

참고 문헌

• Mark de Berg et al., Computational Geometry: Algorithms and Applications, Springer.
• Franco P. Preparata and Michael Ian Shamos, Computational Geometry: An Introduction, Springer.