[알고리즘2] Convex Hull 구현 with Sorting - 실습

복습하기 위해 학부 수업 내용을 필기한 내용입니다.
이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다.
그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다.

▶프로그램 입출력 조건

• xy 좌표계에 속한 점의 list(points)를 입력으로 받는 함수 정의
• points는 tuple (x, y)의 리스트임 (예: [(3,2), (4,-1), (0,0), (-2,2)])
• points에 속한 점은 모두 좌표가 서로 다름
  • def grahamScan(points):
• 위 함수는 Graham’s Scan을 사용해 convex hull에 속한 점의 좌표를 구한 후 입력과 같은 형식으로 반환
• 최초로 convex hull에 포함하는 점 p는 y 값이 가장 작은 점 중 x 값이 가장 큰 점
• 이후에 convex hull에 포함하는 점은 p로부터 반시계 방향으로 거쳐가는 차례로 포함되어야 함
• Hint: convex hull에 포함하는 점은 stack에 push, pop 하면 편리함 (optional)

728x90

 

 

import math


def grahamScan(points):
    def ccw(i, j, k):
        area2 = (j[0] - i[0]) * (k[1] - i[1]) - (j[1] - i[1]) * (k[0] - i[0])
        if area2 > 0:
            return True
        else:
            return False

    answer = []
    p = []
    points.sort(key=lambda x: (x[1], -x[0]))
    answer.append(points[0])
    p.append([0, points[0]])
    for i in range(1, len(points)):
        a = math.atan2(points[i][1] - points[0][1], points[i][0] - points[0][0])
        p.append([a, points[i]])
    p.sort(key=lambda x: x[0])
    for i in range(1, len(points)):
        point = p[i][1]
        if i == 1:
            answer.append(point)
        else:
            jj = answer.pop()
            ii = answer.pop()
            while True:
                if ccw(ii, jj, point):
                    answer.append(ii)
                    answer.append(jj)
                    answer.append(point)
                    break
                else:
                    jj = ii
                    ii = answer.pop()
    return answer


if __name__ == "__main__":
    print(grahamScan([(0, 0), (-2, -1), (-1, 1), (1, -1), (3, -1), (-3, -1)]))
    print(grahamScan([(4, 2), (3, -1), (2, -2), (1, 0), (0, 2), (0, -2), (-1, 1), 
                      (-2, -1), (-2, -3), (-3, 3), (-4, 0), (-4, -2), (-4, -4)]))
    print(grahamScan([(4, 2), (3, -1), (2, -2), (1, 0), (0, 2), (0, -2), (-1, 1), 
                      (-2, -1), (-2, -3), (-3, 3), (-4, 0), (-4, -2), (-4, -4), (0, -3)]))