각도를 재서 볼록 껍질을 찾던 걸 두 주쯤 뒤에 다시 썼다. 삼각함수가 전부 사라졌다.
def ccw(a, b, c):
return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
두 벡터의 외적이다. 부호만 보면 a → b → c 가 왼쪽으로 도는지 오른쪽으로 도는지 알 수 있다. 0이면 세 점이 한 직선 위에 있다.
각도를 알 필요가 없었다. 필요한 건 꺾이는 방향뿐이고 그건 곱셈 네 번과 뺄셈 하나로 나온다. 정수 좌표면 계산도 전부 정수라 부동소수점 오차가 없다.
껍질 만들기
def convex(points):
dots = sorted(points, key=lambda p: p[0])
hull = []
for p in dots + dots[:-1][::-1]:
while len(hull) >= 2 and ccw(hull[-2], hull[-1], p) > 0:
hull.pop()
hull.append(p)
return hull
x 순으로 정렬한 뒤, 왼쪽에서 오른쪽으로 갔다가 다시 왼쪽으로 돌아온다. dots[:-1][::-1] 이 돌아오는 길이다. 오른쪽 끝점은 이미 지났으므로 빼고 뒤집는다.
가면서 점을 쌓다가, 마지막 세 점이 잘못된 방향으로 꺾이면 가운데를 빼낸다. 볼록하지 않은 지점을 계속 깎아내는 것이다.
앞의 각도 버전은 다음 점을 고를 때마다 전체를 정렬했다. 이쪽은 정렬을 한 번만 하고 각 점을 최대 한 번씩 넣고 한 번씩 뺀다.
결과가 표준 구현과 다를 때가 있다
무작위 점으로 300번 돌려 일반적인 monotone chain 구현과 비교해봤다. 7번은 결과가 달랐다.
빠뜨리는 건 없었고 있어서는 안 될 점이 하나씩 더 들어갔다. 방향을 3600개로 나눠 각 점이 실제 껍질의 꼭짓점인지 따로 확인해보니, 그 점은 공선점도 아니고 안쪽에 있는 점이었다.
정렬 기준을 x 하나에서 (x, y) 로 바꾸면 7번이 2번으로 줄어든다. 300번 중 102번은 x가 같은 점이 있었으니 동점 처리가 원인의 일부다. 다만 그걸로 다 없어지지는 않으므로, 나갔다 돌아오는 한 번의 반복으로 처리하는 구조 자체에도 문제가 있는 것 같다.
일반적인 구현이 아래쪽 껍질과 위쪽 껍질을 따로 만들고 각각 초기화하는 데는 이유가 있는 셈이다.
반환값에 시작점이 두 번 들어간다
되돌아오는 길이 시작점에서 끝나므로 hull 의 처음과 마지막이 같은 점이다. 선을 이어 그릴 때는 오히려 편해서 그대로 두고 쓰고 있다. 껍질 위의 점 목록으로 쓰려면 하나를 빼야 한다.