Monotone Chain 시뮬레이터

볼록껍질 만드는 알고리즘이다. en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain 파이썬 코드 보고서 이해하는게 제일 쉬웠다.

Graham Scan에 비해서 안유명한 것같은데, 개인적으로는 Graham Scan보다 매우 좋아함.

각도 정렬이 아닌, 좌표가지고 정렬을 하기 때문이다.

 

아래는 이해를 돕기 위해 pygame을 이용해 볼록껍질이 어떻게 만들어지는지 표현한 것이다.

코드는 진짜 구데기니까 이해하지말고 사용만 하자.

FPS가 낮을 수록 천천히 볼 수 있다.(단, 정수여야함)

중간에 나가는게 안된다. 나갈려면 alt+tab누르고 거기서 끄면 된다. 아니면 볼록껍질 완성되고 10초뒤에 꺼진다.

import pygame
import random
import time
def ccw(p1, p2, p3):
    return p1[0]*(p2[1] - p3[1]) + p2[0]*(p3[1] - p1[1]) + p3[0]*(p1[1] - p2[1])

def dotToScreenDot(a):
    return a[0], SCREEN_SIZE[1]-a[1]

def renderDotAndNum(dotNum, color, width=0):
    pygame.draw.circle(screen, color, dotToScreenDot(dots[dotNum]), 5, width)
    screen.blit(coordiFont.render(f'#{dotNum}', True, BLACK), dotToScreenDot((dots[dotNum][0]+5, dots[dotNum][1])))

def drawConnectedLines(dots, color, screen, width):
    for i in range(len(dots)-1):
        pygame.draw.line(screen, color, dotToScreenDot(dots[i]), dotToScreenDot(dots[i+1]), width)
def update():
    screen.fill(WHITE)

if __name__ == '__main__':
    SCREEN_SIZE = [1920, 1080]
    n = int(input("점 개수: "))
    FPS = int(input("FPS: "))
    delayTime = int(input("점 정렬하기까지 기다릴 초(진짜로 정렬되고 싶은지 보고싶은경우, 안보고 싶으면 0)"))
    dots = [[random.randint(0, SCREEN_SIZE[0]), random.randint(0, SCREEN_SIZE[1])] for _ in range(n)]
    RED = (255, 0, 0)
    BLACK = (0, 0, 0)
    BLUE = (0, 0, 255)
    WHITE = (255, 255, 255)
    pygame.init()
    screen = pygame.display.set_mode(SCREEN_SIZE, pygame.FULLSCREEN)
    clock = pygame.time.Clock()
    font = pygame.font.Font(None, 40)
    coordiFont = pygame.font.Font(None, 15)
    startTime = time.time()
    while True:
        screen.fill(WHITE)
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                pygame.quit()
        for i in range(n):
            renderDotAndNum(i, BLACK)
        pygame.display.flip()
        if time.time() - startTime < delayTime:  continue # 정렬후 변하는 것 보기.
        dots.sort(key=lambda x:(x[0],x[1]))
        break

    lower = []
    for d in dots:
        screen.fill(WHITE)
        for i in range(n):
            renderDotAndNum(i, BLACK)
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                pygame.quit()
        drawConnectedLines(lower+[d], RED, screen, 2)
        while len(lower) >= 2 and ccw(lower[-2], lower[-1], d) <= 0:
            lower.pop()
            screen.fill(WHITE)
            for i in range(n):
                renderDotAndNum(i, BLACK)
            drawConnectedLines(lower, RED, screen, 2)
            pygame.display.flip()
            clock.tick(FPS)
        screen.fill(WHITE)
        for i in range(n):
            renderDotAndNum(i, BLACK)
        lower.append(d)
        drawConnectedLines(lower, RED, screen, 2)
        pygame.display.flip()
        clock.tick(FPS)

    upper = []
    for d in reversed(dots):
        screen.fill(WHITE)
        for i in range(n):
            renderDotAndNum(i, BLACK)
        drawConnectedLines(lower, RED, screen, 2)
        drawConnectedLines(upper+[d], RED, screen, 2)
        while len(upper) >= 2 and ccw(upper[-2], upper[-1], d) <= 0:
            upper.pop()
            screen.fill(WHITE)
            for i in range(n):
                renderDotAndNum(i, BLACK)
            drawConnectedLines(lower, RED, screen, 2)
            drawConnectedLines(upper, RED, screen, 2)
            pygame.display.flip()
            clock.tick(FPS)
        screen.fill(WHITE)
        for i in range(n):
            renderDotAndNum(i, BLACK)
        drawConnectedLines(lower, RED, screen, 2)
        upper.append(d)
        drawConnectedLines(upper, RED, screen, 2)
        pygame.display.flip()
        clock.tick(FPS)
    convexHull = lower[:-1] + upper[:-1]
    startTime = time.time()
    while True:
        for i in range(n):
            renderDotAndNum(i, BLACK)
        if time.time()-startTime > 10:
            break
        drawConnectedLines(convexHull, RED, screen, 1)
    print(convexHull)

정렬하기까지 기다릴 초가 0보다 크면, 점 번호가 바뀌는 것을 볼 수 있다. 

아래는 작동 모습이다.

사진에서 빨간선이 깜빡이기만 하면, 사진을 클릭해서 보자.