내가 아는 convex hull을 구하는 알고리즘은 제일 외곽에 있는(y 좌표가 가장 작은) 한 점을 잡고, 그 점을 지나는 직선(수평선)을 기준으로 모든을 각도 순으로 정렬한 다음 차례대로 스택에 넣어가면서 볼록한 점만 살리는 방법인데, 검색해보니 방법의 이름은 Graham’s Scan 이라고 한다. 이 녀석은 스택 처리 부분이 o(N)인데 그 전에 정렬이 들어가서 nlogn의 시간 복잡도를 갖는다. 한국어 위키를 보니, 시간 복잡도는 output point들이 clockwise와 같은 순서를 가지도록 하는 경우, 정렬 알고리즘의 복잡도를 따라간다고 한다. (근거: 2차 곡선에 존재하는 점들이 랜덤한 순서로 입력으로 주어진 경우).
복잡도를 보고 있자니 드는 생각이 n개의 점들을 갖는 공간에 점들은 n^2개 만큼 존재 가능하기 때문에, 밀도가 높은 점들의 convex hull을 구할 때는 정렬 부분에서 병목이 생길 수 있겠다는 생각이었다. 그렇다면 정렬 부분을 radix, bucket sort 등으로 바꾸는게 낫지 않을까 하는 생각이 들었다.
그래서 opencv로 점 개수에 따른 속도를 테스트해봤다. 1~2000 사이의 값을 갖는 점들을 만들어서 돌려봤는데, 점의 개수가 10배 늘어날 때마다 속도가 16배 정도 늘어나서 o(nlogn)을 따르는 듯한 느낌을 주었다. output format에 관여하는 clockwise라는 옵션은 속도에 영향이 없었다.
import cv2
import numpy as np
points = {n: np.random.randint(0, 2000, (n, 2))
for n in [10**3, 10**4, 10**5, 10**6, 10**7, 10**8]}
%timeit hull = cv2.convexHull(points[10**3])
%timeit hull = cv2.convexHull(points[10**4])
%timeit hull = cv2.convexHull(points[10**5])
%timeit hull = cv2.convexHull(points[10**6])
%timeit hull = cv2.convexHull(points[10**7])
%timeit hull = cv2.convexHull(points[10**8])
# 40.7 µs ± 1.61 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
# 681 µs ± 32.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
# 9.89 ms ± 848 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
# 161 ms ± 8.25 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
# 2.6 s ± 51.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
# 40 s ± 166 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
그런데 opencv 내부적으로도 저 그라함 스캔을 쓰는가하면 답은 아니오이고 Sklansky의 알고리즘을 쓴다고 하는데, 이는 틀린(?) 방법이라고 한다. 영문 위키에 따르면, 2d simple polygon에 대해서는 convex hull을 구하는 것이 linear time에 해결된다고 한다(?). 그래서 더 검색해보니 linear time 알고리즘에 대해 정리해둔 사이트가 있었다 -> A History of Linear-time Convex Hull Algorithms for Simple Polygons
진짜 O(N)이 되나 싶어서 opencv에서 사용한다는 Sklansky의 논문(Finding the convex hull of a simple polygon)을 보니, 입력 좌표들이 counterclockwise sequence일 것을 요구하고 있었다. 일단 좌표들을 그레이햄 스캔에서 하듯이 각도순으로 정렬해서 넣어보니 cv.convexHull() 돌리는 시간이 30% 정도 줄어들었다. clockwise로 넣어주면 확실히 더 줄듯하다.
애초에 컨벡스헐 함수를 도형의 좌표에 대해 적용하는 케이스가 많다고하면 별로 중요한 문제는 아니겠다.
Think 