Python에서 Convex Hull 계산 및 표시

볼록 껍질은 점 집합을 포함하는 가장 작은 볼록 다각형입니다. Python에서는 SciPy의 ConvexHull로 이를 계산하고 Matplotlib으로 경계를 그릴 수 있습니다. 알고리즘을 공부하려면 간단한 Quickhull 구현을 직접 살펴보는 것도 좋습니다.

볼록 껍질이란?

평면 위의 점들을 생각할 때, 볼록 껍질은 모든 점을 포함하는 가장 작은 볼록 다각형입니다. 점들을 팽팽한 고무줄로 둘러싼 모습을 떠올려 보세요. 고무줄에 닿는 점은 껍질의 꼭짓점이고, 고무줄 안쪽에 있는 점은 경계에 포함되지 않습니다. 다각형의 변은 바깥쪽 꼭짓점을 순서대로 연결합니다.

이 정의는 이미 볼록한 물체의 경계를 뜻하는 것이 아니라 점들의 집합을 대상으로 합니다. 볼록 껍질은 기하학, 충돌 경계, 공간 분석에 활용되지만, 점들의 내부 배치는 의도적으로 드러내지 않습니다.

SciPy로 볼록 껍질 계산하고 그리기

스크립트를 실행할 Python 환경에 NumPy, SciPy, Matplotlib을 설치하세요. 예를 들어 python -m pip install numpy scipy matplotlib 명령을 사용할 수 있습니다. ConvexHull에는 각 행이 한 점을 나타내고 두 열에 각각 x좌표와 y좌표가 들어 있는 배열을 전달합니다. vertices 속성은 경계 꼭짓점의 인덱스를 순서대로 제공하므로, 이 순서대로 점들을 연결하고 첫 점을 끝에 한 번 더 넣으면 다각형의 윤곽이 닫힙니다.

다음 예제를 실행해 보세요.

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

points = np.array([
    [0.0, 0.0], [1.0, 0.0], [2.0, 0.0],
    [2.0, 1.0], [2.0, 2.0], [1.0, 2.0],
    [0.0, 2.0], [0.0, 1.0], [1.0, 1.0],
])
hull = ConvexHull(points)
boundary = points[hull.vertices]
closed_boundary = np.vstack((boundary, boundary[0]))

plt.scatter(points[:, 0], points[:, 1], label="Points")
plt.plot(closed_boundary[:, 0], closed_boundary[:, 1], "r-", label="Hull")
plt.gca().set_aspect("equal", adjustable="box")
plt.xlabel("x")
plt.ylabel("y")
plt.legend()
plt.show()

입력에 포함된 내부 점은 볼록 껍질에 포함되지 않습니다. 여기서는 hull.simplices를 사용해 변을 하나씩 그리는 것보다 hull.vertices를 사용하는 편이 적절합니다. 꼭짓점이 순서대로 제공되므로 하나의 닫힌 윤곽선을 그릴 수 있습니다. 예제는 Matplotlib 창을 엽니다. 노트북 환경에서는 그림이 출력 영역에 표시됩니다. 그래프의 텍스트 레이블은 예제 코드에 그대로 있어 영어로 표시됩니다.

Python으로 Quickhull 구현하기

Quickhull은 2D 볼록 껍질을 찾는 재귀 알고리즘입니다. x좌표가 가장 작은 점과 가장 큰 점에서 시작해 후보 경계를 두 쪽으로 나눕니다. 각 방향의 선분에 대해 알고리즘은 양의 외적 값이 가장 큰 점을 선택합니다. 이 값은 선분에서 점까지의 수직 거리에 비례합니다. 그런 다음 선택한 점의 양쪽에 있는 더 작은 점 집합을 탐색합니다. 선분의 왼쪽에 후보 점이 더 이상 없으면 그 선분은 경계의 일부입니다. 엄격한 방향 판정으로 선택한 점은 이후 재귀 호출에서 제외되므로, 서로 다른 점이 유한 개라면 재귀가 끝납니다.

다음 구현은 2D 좌표 쌍의 반복 가능 객체를 받아 다각형 꼭짓점을 진행 순서대로 반환하며, 첫 점을 끝에 반복하지 않습니다. 재귀 탐색 전에 중복 좌표를 제거합니다. 서로 다른 점이 세 개보다 적거나 모든 점이 한 직선 위에 있으면 사용 가능한 양 끝 점을 반환합니다. 이 예제는 Python 표준 라이브러리만 사용하므로 하나의 스크립트로 실행할 수 있으며, 반환된 목록은 나중에 그래프 라이브러리에 전달할 수 있습니다.

다음 예제를 실행해 보세요.

def cross(a, b, point):
    """Return the signed 2D cross product of AB and A-to-point."""
    return (b[0] - a[0]) * (point[1] - a[1]) - (b[1] - a[1]) * (point[0] - a[0])


def quickhull(points):
    """Return the vertices of a 2D convex hull in boundary order."""
    unique = sorted(set(tuple(point) for point in points))
    if len(unique) <= 2:
        return unique

    left = min(unique, key=lambda point: (point[0], point[1]))
    right = max(unique, key=lambda point: (point[0], point[1]))

    def chain(start, end, candidates):
        candidates = [point for point in candidates if cross(start, end, point) > 0]
        if not candidates:
            return []
        farthest = max(candidates, key=lambda point: cross(start, end, point))
        first = [point for point in candidates if cross(start, farthest, point) > 0]
        second = [point for point in candidates if cross(farthest, end, point) > 0]
        return chain(start, farthest, first) + [farthest] + chain(farthest, end, second)

    upper = chain(left, right, unique)
    lower = chain(right, left, unique)
    return [left] + upper + [right] + lower


points = [
    (0, 0), (1, 0), (2, 0), (2, 1), (2, 2),
    (1, 2), (0, 2), (0, 1), (1, 1),
]
hull_points = quickhull(points)
closed_hull = hull_points + hull_points[:1]
print(hull_points)

외적의 부호는 점이 방향이 정해진 직선의 어느 쪽에 있는지 판별하고, 외적의 크기는 그쪽 후보들의 순위를 정합니다. 재귀 호출에는 새 선분 두 개의 바깥쪽에 엄격히 놓인 점만 남습니다. 반환 목록은 다각형 경계를 따라 정렬되므로 닫힌 선을 그릴 때는 첫 점을 목록 끝에 추가하세요. 이 교육용 구현은 2D 점을 대상으로 하며, 운영 환경에서 검증된 기하 라이브러리를 대체하지 않습니다. 단순한 재귀 방식은 일부 점 분포에서 상당한 계산이 필요할 수도 있습니다.

접근 방식 선택과 예외 상황 처리

유지 관리되는 라이브러리 함수, 껍질의 인덱스 또는 2차원 이상의 입력 지원이 필요하다면 SciPy를 사용하세요. 재귀적 분할을 이해하거나 작은 2D 루틴을 수정하려는 경우에는 Quickhull을 직접 구현해 볼 수 있습니다. 속도가 더 빠를 것이라고 가정해 방식을 선택하지는 마세요. 성능은 데이터와 실행 환경에 따라 달라지며, 이 글에서는 벤치마크 결과를 주장하지 않습니다.

입력 배열의 형태와 점들의 기하학적 배치가 중요합니다. SciPy로 2D 다각형을 만들려면 서로 한 직선 위에 있지 않은 점이 최소 세 개 필요합니다. 점이 너무 적거나 모두 한 직선 위에 있으면 해당 다각형을 정의할 수 없으며, Qhull은 기하 오류를 보고합니다. 애플리케이션에서 이 상황을 처리해야 한다면 scipy.spatial.QhullError를 잡거나 ConvexHull을 호출하기 전에 입력을 확인하세요. 중복 점은 경계 꼭짓점을 늘리지 않습니다. 위의 사용자 정의 함수는 중복을 제거하고 한 직선 위의 점에 대해서는 사용 가능한 양 끝 점을 반환하지만, 좌표가 유한한 숫자 쌍이라고 가정합니다. 신뢰할 수 없는 데이터를 전달하기 전에 검증하세요. 3D 또는 그 이상의 차원에서 볼록 껍질을 구하려면 이 2D 사용자 정의 알고리즘 대신 SciPy 라이브러리 구현을 사용하세요.

자주 묻는 질문

Quickhull은 어떻게 경계를 찾나요?

먼저 양 끝 점을 찾고, 각 방향에서 가장 멀리 있는 후보 점을 선택한 뒤 새 선분 바깥의 점 집합을 재귀적으로 살펴봅니다. 남은 후보가 없는 쪽은 볼록 껍질의 변이 됩니다.

3D에서도 볼록 껍질을 계산할 수 있나요?

네. SciPy의 ConvexHull은 좌표 열이 두 개보다 많은 점 배열도 지원합니다. 여기서 소개한 사용자 정의 구현은 2D 외적을 사용하므로 3D 입력을 처리하지 않습니다.

점들이 한 직선 위에 있으면 어떻게 되나요?

이 점들로는 2D 다각형을 만들 수 없습니다. SciPy는 Qhull 기하 오류를 보고하고, 사용자 정의 함수는 양 끝 점 두 개를 반환합니다. 서로 다른 점이 더 적으면 그 수만큼 반환합니다.

어떤 방식을 선택해야 하나요?

애플리케이션 코드나 고차원 입력에는 SciPy를 선택하세요. 2D 알고리즘을 공부하려면 사용자 정의 버전을 살펴보세요. 더 큰 시스템에 적용하기 전에는 입력 검증과 테스트를 추가하세요.