Calculating Voronoi Nodes

From Payne.org Wiki

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 typically 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 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 that 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:

aix + biy + ci = 0

And an offset of the line may be defined as:

aix + biy + ci + kit = 0

Where ki is the offset direction (1 or -1) and t is the offset distance. Note that the line coefficients must be normalized such that a_i^2 + b_i^2 = 1 or kit will not represent the correct offset distance.

Similarly, an arc (circle) of radius r, centered on (xi,yi) 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 ki 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:

q0(x2 + y2t2) + a0x + b0y + k0t + c0 = 0

Where q0 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 q0, q1, and q2 are each 0 or 1. This system can be stored in a 3x5 numeric array.

Solving the System

The generalized system can be solved as follows:

  1. If the system is linear (all q values are zero), solve the 3x3 system using linear methods
  2. Otherwise, reduce the system to a three-equation system with one quadratic equation and two linear equations
  3. Check determinants of that system, and select a substitution
  4. 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 the 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, this is where we need to consider the 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}

This system has a closed-form solution:


\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}

where w can be found as the roots of this quadratic equation:


\begin{align}
a w^2 + b w + c = 0
\end{align}

Finally, u and v can be calculated from w. Substituting back to x, y and t yields the one or two solutions.

Personal tools