Convex Hull: 인공지능에 기하학 적용하기

Convex Hull_{(컨벡스 헐)}은 계산 기하학의 기본 개념으로서 인공지능, 컴퓨터 그래픽스, 로보틱스 등 여러 분야에서 중요한 역할을 하고 있다. 이 포스트에서는Convex Hull_{(컨벡스 헐)}이 무엇인지, 어떻게 계산되는지 그리고 인공지능에서는 어떻게 활용되는지 살펴보고자 한다.

Table of Contents　

Convex Hull_{(컨벡스 헐)}이란?

컨벡스 헐은 유클리드 공간에서 주어진 점들을 모두 포함하는 가장 작은 컨벡스 다각형이나 다면체를 말한다. 마치 고무줄을 못 주위에 씌웠다가 놓아주면 고무줄이 못의 가장 바깥쪽을 감싸는 모양이 되는 것을 상상하면 된다.

수학적 정의

점 집합 $X$ 가 주어졌을 때, 컨벡스 헐은 $X$ 를 포함하는 가장 작은 컨벡스 집합이다.

집합이 컨벡스란 이야기는 집합 안의 모든 점 쌍에 대해 그 점들을 잇는 선분이 집합 내에 완전히 포함될 때를 말한다.

Convex Hull_{(컨벡스 헐)} 계산

컨벡스 헐을 계산하는 여러 알고리즘이 있으며, 각각의 복잡성과 효율성이 다르다. 대표적인 알고리즘으로는 다음과 같은 것들이 있다

그레이엄 스캔_{(Graham’s Scan)}: 점들을 정렬한 후 한 번에 처리하여 Hull을 형성하는 알고리즘이다.
퀵헐_(QuickHull): 퀵소트 알고리즘과 유사한 분할 정복 방식으로 계산하는 알고리즘이다.
찬의 알고리즘_{(Chan’s Algorithm)}: 그레이엄 스캔과 퀵헐의 아이디어를 결합한 알고리즘이다.

그레이엄 스캔_{(Graham’s Scan)} 알고리즘

그레이엄 스캔은 1972년 로널드 그레이엄_{(Ronald Graham)}에 의해 개발된, 컨벡스 헐을 찾기 위한 알고리즘이다. 이 방법은 계산 기하학에서 점 집합의 컨벡스 헐을 효율적으로 계산하기 위해 널리 사용된다.

그레이엄 스캔의 주요 단계

점들의 정렬
알고리즘은 먼저 점들을 x 좌표에 따라 정렬한다. x 좌표가 같을 경우 y 좌표에 따라 정렬한다. 이렇게 정렬하는 이유는 알고리즘의 다음 단계에서 스택을 사용하여 헐을 구성하기 위한 기준 점을 설정하기 때문이다.
기준 점 설정
가장 왼쪽 아래에 위치한 점_{(가장 낮은 x 좌표, 그 중에서도 가장 낮은 y 좌표를 가진 점)}을 기준 점으로 선택한다. 이 점은 컨벡스 헐에 항상 포함되며, 다른 모든 점들은 이 점을 기준으로 각도에 따라 정렬된다.
각도에 따른 정렬
기준 점을 중심으로 다른 모든 점들을 각도에 따라 정렬한다. 이 각도는 기준 점에서 다른 점으로의 벡터와 x축과의 사이의 각도로 계산된다. 이는 스택에 점을 효율적으로 Push_(푸시)하고 Pop_(팝)하여 컨벡스 헐을 형성하기 위함이다.
스택을 사용한 컨벡스 헐 생성
정렬된 점들을 순회하면서 스택을 사용하여 컨벡스 헐을 구성한다. 점을 스택에 푸시하기 전에, 현재 스택의 top에 있는 점들이 컨벡스 헐을 만족하는지 검사한다. 즉, 새로운 점을 추가하려고 할 때, 스택의 상위 두 점과 이 점이 반시계 방향을 이루는지 확인한다. 만약 시계 방향이나 일직선을 이룬다면, 컨벡스 헐을 이루지 않으므로 스택의 점을 Pop_(팝)한다.
결과
모든 점을 처리한 후 스택에 남아 있는 점들이 입력 집합의 컨벡스 헐을 형성한다.

그레이엄 스캔의 복잡도

그레이엄 스캔 알고리즘의 시간 복잡도는 $O(n \log n)$ 이다.
이는 점들을 각도에 따라 정렬하는 데 가장 많은 시간이 소요되기 때문이다.

그레이엄 스캔은 그 구현이 비교적 단순하고 효율적이어서 많은 컨벡스 헐 문제나 다른 계산 기하학적 문제를 해결하는 데 자주 사용된다.

퀵헐_(QuickHull) 알고리즘

QuickHull_(퀵헐)은 컨벡스 헐을 찾기 위한 효율적인 알고리즘으로, 그 동작 원리가 퀵소트 알고리즘과 유사하다고 해서 이런 이름이 붙었다. 이 알고리즘은 평균적으로 빠른 실행 속도를 보이는 것이 장점이다.

퀵헐의 주요 단계

최대, 최소 점 찾기
먼저 주어진 점 집합에서 가장 왼쪽_{(x 좌표가 가장 작은)}과 가장 오른쪽_{(x 좌표가 가장 큰)}점을 찾는다. 이 두 점은 컨벡스 헐의 일부가 확실하므로, 이 두 점을 연결하는 선분을 컨벡스 헐의 초기 경계로 설정한다.
선분을 기준으로 점 집합 분할
찾은 선분을 기준으로 나머지 점들을 두 그룹으로 나눈다. 한 그룹은 선분 위쪽에 위치한 점들, 다른 그룹은 아래쪽에 위치한 점들이다.
재귀적으로 Hull_(헐) 확장
각 그룹에 대해 다음을 수행한다.
– 선분에서 가장 멀리 떨어진 점_{(컨벡스 헐을 최대로 확장시킬 수 있는 점)}을 찾는다.
– 이 점과 선분의 양 끝점을 연결하여 새로운 삼각형이나 다각형의 경계를 형성한다.
– 이 새로운 선분들을 기준으로, 새로 형성된 다각형 내부에 있지 않은 점들만을 다시 그룹화하고 같은 과정을 반복한다.
종료 조건
더 이상 추가할 점이 없을 때까지 위 과정을 반복한다. 즉, 어떤 선분에 대해 그 선분과 멀리 떨어진 외부의 점이 더 이상 없을 때까지 계속한다.
결과:
모든 외곽의 점들이 연결되어 최종적인 컨벡스 헐을 형성한다.

퀵헐의 복잡도

일반적인 경우에 $O(n \log n)$ 의 시간 복잡도를 보이지만, 모든 점이 컨벡스 헐 경계에 가까울 경우, 재귀적 접근 방식 때문에 최악의 시간 복잡도인 $O(n^2)$ 까지 늘어날 수 있다.

퀵헐 알고리즘은 그 이름에서 알 수 있듯이, 빠르고 효율적인 컨벡스 헐 계산 방법을 제공하여 다양한 계산 기하학적 문제 해결에 적합하다.

찬의 알고리즘_{(Chan’s Algorithm)}

찬의 알고리즘_{(Chan’s Algorithm)}은 Convex Hull을 찾기 위한 효율적인 알고리즘으로, 1996년 티머시 찬_{(Timothy Chan)}에 의해 개발되었다. 이 알고리즘은 그레이엄 스캔_{(Graham’s Scan)}과 자비스_{(Jarvis March)}의 아이디어를 결합하여 구성되어 있다.

찬의 알고리즘의 주요 단계

초기 분할
전체 데이터 집합을 크기가 m인 여러 부분 집합으로 나눈다. 이 때 m은 최대 h의 값, 즉 Convex Hull에 포함될 수 있는 최대 점의 수를 예측하여 설정한다.
부분 Convex Hull 계산
각 부분 집합에 대해 독립적으로 Convex Hull을 계산한다. 일반적으로 그레이엄 스캔이나 기타 Convex Hull 알고리즘을 사용할 수 있다.
Convex Hull의 병합:
자비스_{(Jarvis March)} 알고리즘을 사용하여 모든 부분 볼록 껍질들을 병합한다. 이 과정에서 각 단계에서 h번의 연산을 수행하여 최종 Convex Hull을 구성한다.

특징 및 장점

찬의 알고리즘은 특정 상황에서 매우 효율적이며, Convex Hull을 구성하는 점의 수 h가 작은 경우 특히 좋은 성능을 보인다.
알고리즘은 동적으로 h의 값을 예측하고 조절하면서 계산을 진행하므로, 다른 Convex Hull 알고리즘에 비해 더 유연하다.
찬의 알고리즘은 크고 복잡한 데이터 세트에 대해 빠르게 실행된다.

찬의 알고리즘은 Convex Hull 문제를 해결하기 위한 강력하고 효율적인 방법을 제공하며, 컴퓨터 그래픽, 로봇 공학, 지리 정보 시스템 등 다양한 분야에서 유용하게 활용될 수 있다.

인공지능에서의 응용

패턴 인식: Convex Hull은 특징 공간에서 데이터 집합의 경계를 인식하는 데 도움을 줄 수 있다.
클러스터링 알고리즘: 클러스터링에서 Convex Hull을 사용하여 클러스터의 “형태”를 결정하고 이상치 탐지에 활용할 수 있다.
로보틱스 및 경로 계획: 로보틱스에서 Convex Hull을 사용하여 객체 주변의 경계 상자를 구성하고, 이를 충돌 감지 및 동작 계획에 활용한다.
컴퓨터 그래픽스: Convex Hull 알고리즘은 메쉬 생성, 와이어프레임 모델링, 3D 객체 렌더링 등 다양한 그래픽 응용 프로그램에서 중요 하다.

Python을 사용한 Convex Hull 예시

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

# 무작위 점 생성
points = np.random.rand(30, 2)

# Convex Hull 계산
hull = ConvexHull(points)

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

결론

Convex Hull을 이해하는 것은 공간적 및 기하학적 추론을 포함하는 복잡한 문제를 해결하는 데 있어 견고한 기반을 제공한다. 효율적인 알고리즘을 사용하여 Convex Hull을 계산함으로써, AI 시스템은 객체 인식부터 최적 경로 찾기까지의 작업을 더 효과적으로 수행할 수 있다.

Convex Hull: 인공지능에 기하학 적용하기

Convex Hull_{(컨벡스 헐)}이란?

수학적 정의