최소크기 외접원을 구하는 알고리즘 중에는 경사하강법이 있다.
이미 설명이 잘 되어있는 글이 많으므로, 시뮬레이터를 통해 이해에 도움을 주려고 한다.
아래에 설명이 잘 되어있는 글을 링크 걸어놨다.
www.secmem.org/blog/2019/04/08/Smallest-Enclosing-Circle/
Monotone Chain 시뮬레이터보다는 덜 구데기지만, 여전히 구데기니 사용만 하자.
중간에 나가는게 안되니, alt+tab누르고 거기서 끄던가, 목표한 루프수에 도달할때까지 기다리면 된다.
볼록껍질을 이용해 최적화를 했다.
import sys
import math
import pygame
import random
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 monotonechain(dots):
dots.sort(key=lambda x:(x[0],x[1]))
if len(dots) <=2:
return dots
lower = []
for d in dots:
while len(lower) >= 2 and ccw(lower[-2], lower[-1], d) <= 0:
lower.pop()
lower.append(d)
upper = []
for d in reversed(dots):
while len(upper) >= 2 and ccw(upper[-2], upper[-1], d) <= 0:
upper.pop()
upper.append(d)
return lower[:-1] + upper[:-1]
def getDistSquared(d1, d2):
return (d1[0] - d2[0])**2 + (d1[1] - d2[1])**2
def calc(d1,d2,d3):
return getDistSquared(d1, d2) + getDistSquared(d2, d3) + getDistSquared(d1, d3)
def dotToScreenDot(a):
return int(round(a[0])), int(round(SCREEN_SIZE[1]-a[1]))
def drawPoly(dots, color, screen, width):
for i in range(len(dots)):
pygame.draw.line(screen, color, dotToScreenDot(dots[i-1]), dotToScreenDot(dots[i]), width)
def drawDot(x,y,color,size):
pygame.draw.circle(screen, color, dotToScreenDot((x,y)), size)
if __name__ == '__main__':
SCREEN_SIZE = [1920, 1080]
n = int(input("점 개수: "))
LOOP_COUNT = int(input("반복 횟수: "))
ratio = float(input("ratio 시작 값:"))
ratioChange = float(input("ratio 줄이는 값 (1보다 작아야함. 0.995 추천)"))
FPS = int(input("FPS: "))
dots = [[random.randint(100, SCREEN_SIZE[1]-100), random.randint(100, SCREEN_SIZE[1]-100)] 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()
important = monotonechain(dots)
font = pygame.font.Font(None, 40)
xSum = 0
ySum = 0
for i in range(n):
xSum += dots[i][0]
ySum += dots[i][1]
x = xSum/n
y = ySum/n
for nowLoopCount in range(LOOP_COUNT):
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
screen.fill(WHITE)
drawPoly(important, RED, screen, 5)
for i in range(n):
drawDot(dots[i][0], dots[i][1], BLACK, 3)
maxIn = 0
maxVal = (x - important[0][0])**2 + (y - important[0][1])**2
for i in range(len(important)):
if (tmp:= (x - important[i][0])**2 + (y - important[i][1])**2) > maxVal:
maxVal = tmp
maxIn = i
x += (important[maxIn][0] - x)*ratio
y += (important[maxIn][1] - y)*ratio
drawDot(x,y, BLUE, 3)
pygame.draw.circle(screen, BLUE, dotToScreenDot((x,y)), int(round(math.sqrt(maxVal))), 5)
pygame.draw.line(screen, BLUE, dotToScreenDot((x,y)), dotToScreenDot(important[maxIn]), 2)
ratio *= ratioChange
screen.blit(font.render(f'{n=}', True, BLACK), (0, 0))
screen.blit(font.render(f'{FPS=}', True, BLACK), (0, 30))
screen.blit(font.render(f'{nowLoopCount=}', True, BLACK), (0, 60))
screen.blit(font.render(f'{ratio=}', True, BLACK), (0, 90))
screen.blit(font.render(f'{round(x,3)=} {round(y,3)=}', True, BLACK), (0, 120))
screen.blit(font.render(f'{round(math.sqrt(maxVal),3)=}', True, BLACK), (0, 150))
pygame.display.flip()
clock.tick(FPS)
print(f'{x=} {y=}')
pygame.quit()
빨간색은 볼록껍질, 파란색 선은 반지름(중심과 가장 먼 점을 이은 선분), 파란색 원은 최소 크기 외접원이다.
루프를 많이 돌리면 더 정확한 값을 얻을 수 있다.
아래는 작동 모습이다.
ratio값이 안줄어든다 싶으면 사진을 클릭해서 보자.
'Python > 강좌' 카테고리의 다른 글
K-means 시뮬레이터 (0) | 2020.09.15 |
---|---|
Kruskal Algorithm 시뮬레이터 (0) | 2020.09.14 |
Union-Find 시뮬레이터 (0) | 2020.09.14 |
Monotone Chain 시뮬레이터 (0) | 2020.09.13 |