파이썬 점찍기에서 최소거리 관련 질문입니다.
조회수 1436회
-
(•́ ✖ •̀)
알 수 없는 사용자
2 답변
-
2차원이라 가정하고
랜덤한 x, y 좌표를 얻었을 때, 이미 찍혀있는 각 점에 대해서 비교 연산이 들어가야 합니다.
현재 그리려는 점의 좌표와 이미 그려진 각 좌표의 거리를 비교해서 모든 점에 대해 일정 거리 이상 떨어져 있음이 확인되면(Pass) 그 때 점을 그려넣는 작업을 반복하는거죠.
점과 점 사이의 거리는 위대한 피타고라스의 정리로 쉽게 구할 수 있기 때문에 문제가 되지 않습니다.
찍어야 할 점의 갯수가 많지 않다면 단순 brute-force 방식으로도 간단히 구현 가능합니다. 문제 없죠.
from random import randint from math import sqrt N = 100 # 구해야 할 점의 갯수 w, h = 512, 512 # viewport의 size min_dist = 5 # 최소 거리 points = [] # 결과 def dist(p1, p2): return sqrt(((p1[0] - p2[0]) ** 2) + ((p1[1] - p2[1]) ** 2)) while len(points) < N: candidate = (randint(0, w), randint(0, h)) dists = map(lambda point: dist(point, candidate), points) passed = map(lambda d: d > min_dist, dists) if all(passed): points.append(candidate) print(points)
다만 일정 수준을 넘어선 대량의 점을 찍어야 할 때 가 문제가 됩니다.
매 번 이미 찍힌 점에 대해서 비교 연산이 들어가야 하는데
무작위로 샘플링 된 N개의 점을 가지고 수행한다고 가정하면,
그 비교 연산은
(n-1) + (n-2) + ... + 3 + 2 + 1 = O(n^2)
이므로 시간 복잡도가 높습니다.
위의 케이스는 찍히든 말든 상관하지 않고 N개만 비교했지만
N개의 점을 무조건 찍어야 하는 상황이라면 심각합니다. 랜덤으로 뽑은 점이 항상 Pass한다는 보장이 없기 때문입니다.
점이 많아질수록 새로운 점이 들어갈 자리는 점점 없어지는 것도 문제가 되고요. 확률적으로 이 경우까지 따지면 훨씬 느릴 겁니다. (경우에 따라서는 못 구할 수도 있습니다.)
이를 해결하기 위해서 알고리즘을 쓰거나 특별한 전략을 짜야 합니다.
공간 좌표를 위한 tree 구조를 써서 비교 연산을 할 점들의 갯수를 적절하게 샘플링 할 수 있도록 만들 수 있습니다. 공간 분할 알고리즘(R-tree, KD-tree 등등)들을 변형하여 사용하면 될 것 같네요.
좀 더 균일하게 분포된 점들을 구하고 싶다면 N개의 포인트를 위해 미리 viewport 구역을 나누어 놓는 전략도 세울 수 있겠네요.
viewport를 최소 간격(buffer)을 고려한 사이즈로 구역을 균일하게 나눈 뒤에 그 buffer 안쪽에서만 랜덤한 위치를 잡는 방법을 생각해 볼 수 있습니다.
분할 정복도 방법이 될 수 있을 거고요.
아무튼 점을 많이 찍으시려면 여러모로 고민하셔야 할 겁니다.
-
random.uniform(a, b)
를 사용하시면
a
와b
사이의 랜덤한 값이 생성됩니다최소 간격을 a값으로 전달하시면 될 듯 합니다.
댓글 입력