This note documents a general approach to calculating the location of Voronoi nodes for point, segment, and arc geometric entities. This is a part of my work for developing CAM software for my CNC Machine.
In a Voronoi diagram, nodes (or vertices) are points that are equidistant from three or more entities (points, lines, arcs, etc.). In most Voronoi literature, these entities are called “sites” or “generators”.
A bisector edge connecting two nodes separates two sites, and all points on that bisector are equidistant from the two sites.
In implementations, nodes may be restricted to 3 bisector edges. In cases where the node actually has more bisectors, the diagram may be represented by nodes connected with zero-length segment. At output time, the implementation may then collapse these coincident nodes into nodes with an arbitrary number of edges.
For the best numerical stability, Voronoi nodes are calculated based on the three defining geometric sites, not by attempting to interset bisectors. For implementing a node solver, there are four cases to consider:
- Line, line, line
- Line, line, arc
- Line, arc, arc
- Arc, arc, arc
(Note: points are merely zero-radius arcs).
However, there are a number of degenerate cases to consider. When each degenerate case is considered for each of the four cases above, the implementation combinatorics can get daunting. This note describes a “general” node-solving approach, that handles all degenerate cases.
Line and Arc Equations
For segments, we use the approach of first adding all segment end-points, then the supporting line is added and used to calculate node distances. In this case, a line can be defined as:
$$a_i x + b_i y + c_i = 0$$
And an offset of the line may be defined as:
$$a_i x + b_i y + c_i + k_i t= 0$$
Where $k_i$ is the offset direction (1 or -1) and $t$ is the offset distance. Note: the line coefficients must be normalized such that $a_i^2 + b_i^2 = 1$ or $k_i t$ will not represent the correct offset distance.
Similarly, an arc (circle) of radius $r$, centered on $(x_i, y_i)$ is defined by:
$$\left(x - x_i\right)^2 + \left( y - y_i \right)^2 - r^2 = 0$$
Note that a point is just a zero-radius arc.
Given this equation, an offset arc can be defined as:
$$\left(x - x_i\right)^2 + \left( y - y_i \right)^2 - (r + k_i t)^2 = 0$$
Where $k_i$ is the offset direction (1 or -1) and $t$ is the offset distance.
Generalized Equation System
Given the line and circle equations above, any site (segment, arc, or point) can be represented in a general form:
$$q_0 (x^2 + y^2 - t^2) + a_0 x + b_0 y + k_0 t + c_0 = 0$$
Where $q_0$ is 0 or 1.
For lines, the generalized coefficients are simply the line coefficients:
$$\begin{align}
q_0 & = 0 \\
a_0 & = a_i \\
b_0 & = b_i \\
k_0 & = k_i \\
c_0 & = c_i \\
\end{align}$$
For arcs, the generalized coefficients are:
$$\begin{align}
q_0 & = 1 \\
a_0 & = -2x_k \\
b_0 & = -2y_k \\
k_0 & = -2 k r_k \\
c_0 & = x_k^2 + y_k^2 - r_k^2 \\
\end{align}$$
And points are merely zero-radius arcs:
$$\begin{align}
q_0 & = 1 \\
a_0 & = -2x_k \\
b_0 & = -2y_k \\
k_0 & = 0 \\
c_0 & = x_k^2 + y_k^2 \\
\end{align}$$
Given this, a Voronoi node is found by solving a three-equation quadratic system of the form:
$$\begin{align}
q_0 (x^2 + y^2 - t^2) + a_0 x + b_0 y + k_0 t + c_0 & = 0 \\
q_1 (x^2 + y^2 - t^2) + a_1 x + b_1 y + k_1 t + c_1 & = 0 \\
q_2 (x^2 + y^2 - t^2) + a_2 x + b_2 y + k_2 t + c_2 & = 0 \\
\end{align}$$
Where $q_0$, $q_1$, and $q_2$ are each 0 or 1. This system can be stored in a 3x5 array.
Solving the System
The generalized system can be solved as follows:
If the system is linear (all q values are zero), solve the 3x3 system using linear methods
Otherwise, reduce the system to a three-equation system with one quadratic equation and two linear equations
Check determinants of that system, and select a substitution
Evaluate the resulting system (2 linear, one quadratic) for the solution
The general three-equation system above can be transformed to a system with one quadratic equation and two linear equations. In one case, the system is already in that form. If there are two or three quadratic equations, one can be subtracted from the other one or two to yield a quadratic-linear-linear system.
At this point, the two linear equations form 2 equation system over 3 variables, and we can solve that system for any two variables in terms of a third, using one of three possible cases:
- $x$ and $y$ in terms of $t$
- $y$ and $t$ in terms of $x$
- $t$ and $x$ in terms of $y$
However, we need to consider degeneracies: any degeneracies in the original system will cause degeneracies in the 2-equation linear system. We need to check the determinants of the 2-equation linear system to pick one of the three substitutions, above.
Now, we can substitute the linear variables and combine that with the quadratic equation to form a system of three variables (here, $u$, $v$ and $w$), with $u$ and $v$ solved for in terms of $w$:
$$\begin{align}
a_0 u^2 + b_0 u + c_0 v^2 + d_0 v + e_0 w^2 + f_0 w + g_0 = 0 \\
u = a_1 w + b_1 \\
v = a_2 w + b_2 \\
\end{align}$$
By substituting $u$ and $v$ into the first equation, we end up with a quadratic equation of the form:
$$\begin{align} a w^2 + b w + c = 0 \end{align}$$
Where:
$$\begin{align}
a &= a_0 a_1^2 + c_0 a_2^2 + e_0 \\
b &= 2 a_0 a_1 b_1 + 2 a_2 b_2 c_0 + a_1 b_0 + a_2 d_0 + f_0 \\
c &= a_0 b_1^2 + c_0 b_2^2 + b_0 b_1 + b_2 d_0 + g_0 \\
\end{align}$$
$w$ can be found as the roots of this quadratic equation (zero, one, or two roots).
Finally, $u$ and $v$ can be calculated from $w$. Substituting back to $x$, $y$ and $t$ yields the one or two Voronoi node solutions.