[알고리즘2] Ch3. Sorting 실습 - Convex Hull

• 문제 설명

-점의 좌표를 입력으로 받아 Graham's Scan을 사용해 convex hull에 속한 점의 좌표를 반환하는 함수 구현 "def grahamScan(points):"

-입력 points: xy 좌표계에 속한 점의 list, 각 점의 좌표는 2-tuple(x,y) 형식
예: [(3,2), (4,-1), (0,0), (-2,2)]
리스트 길이 >= 3
반드시 convex hull 존재, points에 속한 점은 모두 좌표가 서로 다름.

-반환값: 입력 중 convex hull에 속한 점의 좌표를 list 형식으로 반환
convex hull에 포함되는 최초의 점 p는 y값이 가장 작은 점 중 x값이 가장 큰 점
이후 p로부터 반시계방향으로 거쳐가는 차례로 포함

-두 점이 이루는 각도 계산 : math.atan2()
-정렬 기능 필요 시 : sorted()
-convex hull에 포함하는 점은 stack list에 push, pop
append() 함수로 가장 뒤에 원소 추가, pop()으로 가장 뒤 원소 제거 후 반환

• Python 코드

def grahamScan(points):
    def dir(a, b, c):
        width = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])
        if width > 0:  # 면적이 양수라면,
            return True  # 반시계 방향 반환
        else:  # 면적이 0 또는 음수라면,
            return False  # 일직선 상 또는 시계 방향 반환

    convex_hull = []  # convex hull에 해당하는 점들을 저장할 리스트 생성 (반환값)
    p = []  # 기준점과 나머지 점들의 각도와 거리 저장할 리스트 생성

    # points 리스트를 y좌표 오름차순 & x좌표 내림차순으로 정렬한 결과를 points에 저장
    points = sorted(points, key=lambda x: (x[1], -x[0]))

    #points[0] = 정렬 후 첫 번째 요소(y좌표 가장 작고, 동일한 경우 x좌표 가장 큰 점) => 시작점
    convex_hull.append(points[0])  # convex_hull 리스트에 시작점 추가
    p.append([0, points[0]])  # p 리스트에 각도 0(초기값)과 시작점 points[0] 추가

    for a in range(1, len(points)):  #모든 점에 대해 시작점과의 상대적 각도 계산
        #angle = 시작점과 해당 점 사이의 상대적인 각도
        angle = math.atan2(points[a][1] - points[0][1], points[a][0] - points[0][0])
        p.append([angle, points[a]])  # p 리스트에 [각도, 점] 쌍 추가

    p = sorted(p, key=lambda x: x[0])  # p 리스트에서 '각도'를 기준으로 정렬

    for a in range(1, len(points)):
        point = p[a][1]
        if a == 1:  # 시작점과 연결되는 점
            convex_hull.append(point)  # convex_hull 리스트에 추가
        else:  # convex_hull 리스트에서 마지막 두 개의 점 제거
            end2 = convex_hull.pop()
            end = convex_hull.pop()
            while True:
                if dir(end, end2, point):  # 방향(시계/반시계) 판단
                    # convex_hull 리스트에 제거했던 두 개의 점과 새 점 추가
                    convex_hull.append(end)
                    convex_hull.append(end2)
                    convex_hull.append(point)
                    break
                else:  # 점이 convex hull 내부에 위치하는 경우
                    end2 = end  # 마지막에서 두 번째 점이 마지막 점이 됨
                    end = convex_hull.pop()  # 마지막 점을 convex_hull 리스트에서 제거

    return convex_hull  # 최종 convex_hull 리스트를 반환