보로노이 셀 판정기

평면 위에 사이트(기준점)를 여러 개 찍었을 때, 다른 어떤 사이트보다 특정 사이트에 더 가까운 점들의 영역입니다. 이 영역들이 모여 평면 전체를 나누는 것이 보로노이 다이어그램입니다.

쿼리 점과 모든 사이트 사이의 유클리드 거리를 하나하나 재서 가장 작은 것을 고릅니다. 정의 자체가 «가장 가까운 사이트를 찾는 것»이라 이 전수 비교가 곧 정답이고, 별도의 근사나 지름길이 필요 없습니다.

있습니다. 두 사이트를 잇는 선분의 수직이등분선 위에 있는 점은 정확히 양쪽 사이트로부터 같은 거리입니다 — 이런 점은 어느 한쪽 셀에도 완전히 속하지 않는 «경계»(edge)이고, 세 개 이상과 동시에 같은 거리면 «꼭짓점»(vertex)입니다. 이 계산기는 그런 경우 동점인 사이트를 전부 보여 줍니다.

격자 칸의 중심점이 어느 사이트에 가장 가까운지를 사이트별로 다른 색으로 칠한 것입니다. 실제 보로노이 다이어그램의 경계는 직선(수직이등분선 조각)이지만, 이 계산기는 칸 단위로 색칠하는 래스터 근사라 칸이 클수록 경계가 계단처럼 보입니다.

k-NN·최근접 점 쌍은 «어떤 두 점이 가장 가까운가»를 찾지만, 이 계산기는 «임의의 쿼리 좌표가 어느 사이트의 영역에 속하는가»를 판정합니다. 사이트 집합이 고정된 뒤 평면을 나눈다는 점에서 목적이 다릅니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.