푸아송 디스크 표본추출

새 점을 받아들이는 조건

영역 안에서 새 후보를 만들고 기존 점들과 충분히 떨어져 있는지 검사한다. 너무 가까운 후보나 영역 밖의 후보는 버린다. 선택된 점의 주변에서 후보를 만들고 새 점을 다시 후보 생성의 출발점으로 삼는 반복 방식이 대표적이다. 최소 거리 조건이 있으므로 독립적으로 균등 난수를 뽑은 점들과는 서로의 위치 관계가 다르다.

간격 검사 예

평면에서 최소 거리를 0.3으로 정하고 기존 점이 (0.2,0.2)에 있다고 하자. 후보 (0.4,0.2)는 거리가 0.2이므로 받아들일 수 없다. 후보 (0.6,0.2)는 거리가 0.4여서 이 기존 점에 대한 검사를 통과한다. 다만 다른 기존 점과의 거리나 영역 경계도 만족해야 최종 후보가 된다. 한 점과 멀다는 조건만으로 전체 집합에 추가할 수 있는 것은 아니다.

반지름을 해석하는 방법

최소 점 간 거리를 r로 두었다면 각 점을 중심으로 반지름 r/2인 원을 그려 서로 겹치지 않는 모습을 볼 수 있다. 최소 간격 0.3인 예에서 원의 반지름은 0.15다. 이를 점마다 반지름 0.3인 원이 겹치면 안 된다는 조건으로 바꾸면 필요한 중심 간 거리는 0.6이 되어 다른 배치 문제가 된다.

종료와 밀도의 한계

후보를 제한된 횟수만 시도한 뒤 더 이상 점을 찾지 못했다고 해서 수학적으로 추가할 자리가 전혀 없다고 증명한 것은 아니다. 필요한 개수보다 먼저 탐색이 종료될 수도 있다. 최소 간격을 줄이면 더 많은 점을 담을 여지가 생기지만 비용과 메모리 부담도 달라진다. 생성 후 점을 이동하는 최적화를 한다면 최소 거리 조건이 유지되는지 다시 검사해야 한다.