각도를 정렬해 볼록 껍질 찾기

점들이 흩어져 있을 때 전부를 감싸는 가장 작은 볼록 다각형을 찾는 문제다. 고무줄을 씌웠을 때 걸리는 점들이다.

어디서 시작할지

start = min(dots, key=lambda c: c[1])

y가 가장 작은 점에서 시작한다. 가장 아래에 있는 점은 반드시 껍질 위에 있다. 그 아래에 아무것도 없으므로 안쪽에 갇힐 수 없다.

다음 점을 각도로 고르기

def angle_from_ray(A, B, C):
    if B == C:
        return 0

    AB = (B[0] - A[0], B[1] - A[1])
    BC = (C[0] - B[0], C[1] - B[1])

    angle_AB = (math.degrees(math.atan2(AB[1], AB[0])) + 360) % 360
    angle_BC = (math.degrees(math.atan2(BC[1], BC[0])) + 360) % 360

    angle = (angle_BC - angle_AB + 360) % 360
    return angle

직전에 온 방향 AB 를 기준으로, 다음 점으로 가는 방향 BC 가 얼마나 꺾이는지를 잰다.

atan2 는 -180 부터 180 까지를 돌려준다. 그대로 빼면 음수가 나오고 크기 비교가 뒤집힌다. +360 하고 % 360 을 씌워 0부터 360까지로 눌렀다. 두 각을 각각 눌러두고 뺀 결과에도 한 번 더 씌운다.

def convex(cur, past):
    if cur == start and past != start:
        return

    sorted_dots = sorted(dots, key=lambda coord: angle_from_ray(past, cur, coord))
    line(t, cur, sorted_dots[1])

    convex(sorted_dots[1], cur)

모든 점을 꺾이는 각도로 정렬하고 두 번째를 고른다. 첫 번째가 아니라 두 번째인 이유는 자기 자신이 각도 0으로 맨 앞에 오기 때문이다. angle_from_ray 의 if B == C: return 0 이 그것이다.

가장 적게 꺾이는 점을 계속 고르면 바깥쪽을 따라 돌게 된다. 시작점으로 돌아오면 끝이다.

비용

점을 하나 고를 때마다 전체를 정렬한다. 껍질 위의 점이 h 개면 정렬을 h 번 한다.

정렬까지 할 필요는 없다. 최솟값 하나만 필요하므로 한 번 훑으면 된다. 그런데 sorted_dots[1] 로 두 번째를 꺼내야 해서 정렬을 쓴 것으로 보인다. 자기 자신을 후보에서 빼면 최솟값으로 바꿀 수 있다.

각도로 재는 것의 부담

atan2 를 점마다 두 번 부른다. 삼각함수는 부동소수점 연산이라 값이 아주 가까운 두 점에서 정렬 순서가 흔들릴 수 있다.

실제로 필요한 건 각도의 값이 아니라 어느 쪽이 더 꺾였는가뿐이다. 크기 비교만 하면 되는데 각도를 정확히 구하고 있다.

그 전에 있던 것

같은 폴더에 원을 그리는 파일이 하나 먼저 있다.

for a in range(0, 360):
    rad = a * math.pi / 180
    x = r * math.cos(rad)
    y = r * math.sin(rad)
    t.goto(x, y)

각도를 라디안으로 바꿔 좌표를 구하고 turtle로 찍는 것이다. 볼록 껍질을 그리기 전에 좌표와 각도를 다루는 걸 먼저 익힌 파일로 보인다.