보로노이 파티션은 화면 속에 분산되어 있는 위치들을 가지고 위치들의 경계를 그려 각 경계가 양쪽에 있는 위치의 정확히 반이 되도록 하는 것입니다.

두 위치 $A$‍와 $B$‍로 시작합니다. 둘을 나누는 선에 있는 모든 점은 $A$‍나 $B$‍에서의 거리가 모두 동일합니다. 이 선이 가지고 있는 다른 특성에는 무엇이 있을까요?

먼저 할 수 있는 것은 $A$‍에서 $B$‍까지 선을 그리는 것입니다. 경계의 모든 점에서 $A$‍의 거리와 $B$‍의 거리가 같으니 경계는 $\overline{AB}$‍의 중점 $M$‍을 지날 것입니다.

중점에 대해서는 여기서 더 배울 수 있습니다.

이제 경계에서 다른 점 $P$‍를 골라 삼각형 두 개를 만들어 봅시다: $\mathrm{△}AMP$‍, $\mathrm{△}BMP$‍

점 $P$‍는 경계에 있기 때문에 $\overline{AP}=\overline{BP}$‍라는 것을 알고 있습니다.
또한 $\overline{AM}=\overline{BM}$‍이라는 것과 두 삼각형 모두 $\overline{MP}$‍를 변으로 삼는다는 것도 압니다.

두 삼각형 모두 세 변의 길이를 공유하기 때문에 두 삼각형은 닮은 삼각형입니다. 닮은 삼각형에 대해서는 여기서 더 배울 수 있습니다.

$\mathrm{△}AMP$‍와 $\mathrm{△}BMP$‍ 가 닮음이기 때문에 $\mathrm{\angle }AMP=\mathrm{\angle }BMP$‍라는 것을 알 수 있습니다. 두 각 모두 직선(선분 $AB$‍) 위에 있기 때문에 $\mathrm{\angle }AMP+\mathrm{\angle }BMP={180}^{\circ }$‍임을 알 수 있습니다. 따라서 두 각 모두 ${90}^{\circ }$‍이어야 합니다.

따라서 $A$‍와 $B$‍의 경계는 선분 $AB$‍의 수직이등분선입니다. 여기서 수직이등분선에 대해 더 배울 수 있습니다.

두 위치 간의 경계는 두 위치를 잇는 선분의 수직이등분선이라는 것을 배웠습니다. 어떻게 이 정보를 이용해 세 위치의 보로노이 파티션을 구할 수 있을까요? 먼저 위치 사이에 선을 그려봅시다.

다음으로 모서리들의 중점을 찾아 각 모서리마다 수직이등분선을 그립니다.

세 수직이등분선이 점 $V$‍에서 만난다는 것을 볼 수 있습니다. 각 수직이등분선은 두 위치로부터 같은 거리에 있고 $V$‍는 세 개 모두 위에 있기 때문에 $V$‍는 모든 세 위치와 같은 거리에 있어야 합니다. 따라서 $V$‍는 이 보로노이 파티션의 꼭짓점입니다. 이 꼭짓점에서 시작해 각 중점을 지나는 것으로 마지막 경계를 그릴 수 있습니다.

이제 간단한 보로노이 파티션에 필요한 기하학을 살펴보았으니 보로노이 파티션의 꼭짓점 좌표를 계산해 봅시다.

세 위치 $A$‍, $B$‍, $C$‍의 좌표는 다음과 같습니다:

먼저 $\overline{AB}$‍의 수직이등분선 방정식을 계산해 봅시다. 이 선은 $\overline{AB}$‍의 중점을 통과하며 $\overline{AB}$‍의 경사도의 역수이고 부호가 반대인 경사도를 가집니다.

여기서 수직선의 방정식을 계산하는 법을 배워보세요.

이제 $\overline{AB}$‍의 수직이등분선에 대한 방정식이 있으니 같은 방식을 이용해 $\overline{BC}$‍의 수직이등분선도 구할 수 있습니다.

이제 수직이등분선 두 개에 대한 방정식이 있으니 둘이 어디서 교차할지 알 수 있습니다. $m_1$‍과 $b_1$‍을 사용해 경사도를 나타내고 $y$‍절편을 사용해 첫 수직이등분선을 나타내고, $m_2$‍, $b_2$‍를 이용해 경사도를 나타내고 $y$‍절편을 사용해 두 번째 수직이등분선을 나타내면 다음과 같습니다:

따라서:
$\begin{array}{rl}{m}_{1}x+b_1& =m_{2}x+b_2\\ \\ m_{1}x-m_{2}x& =b_2-b_1\\ \\ (m_1-m_2)x& =b_2-b_1\\ \\ x& ={\displaystyle \frac{b_2-b_1}{m_1-m_2}}\end{array}$‍

방정식의 경사도와 $y$‍절편에 값을 대입하면 교차점의 $x$‍좌표를 찾을 수 있습니다. 그리고 수직이등분선 방정식 하나에 $x$‍를 대입하면 $y$‍좌표를 구할 수 있습니다.

이제 이런 계산을 몇 백번 하는 것을 상상해 보세요. 이것이 컴퓨터를 사용하는 이유입니다!