Error correction

Once we know where the corners of the digital Voronoi diagram are, we can correct all errors done by the approximate signed Euclidean DT algorithm by checking if the real corner of the VP contains any pixel.

  

Figure 5.2: Neighbors to consider during error correction.

In figure , p₁ is a corner pixel, neighbored by p₂ = p₁+(0,1) and p₃ = p₁+(1,0). The nearest object pixels of p₁, p₂ and p₃ are q₁, q₂ and q₃, respectively. The signed distances are SD(p₁)=(dp_x1,dp_y1), SD(p₂)=(dp_x2,dp_y2) and SD(p₃)=(dp_x3,dp_y3). With that knowledge, we can actually compute the limits of the corner of the continuous Voronoi diagram analytically, since lines L₁₂ and L₁₃ are the mid-perpendicular of q₁q₂ and q₁q₃ respectively.
Using pixel p₁ as the center of our coordinate system, we have

$$L_{12} \; : \; \; n_y \leq \alpha_{12}.n_x + \beta_{12}$$ (5.7)

$$L_{13} \; : \; \; n_y \geq \alpha_{13}.n_x + \beta_{13}$$ (5.8)

L₁₂ is the mid-perpendicular of q₁q₂, so that

  

$$\alpha_{12} \frac{dp_{x2}-dp_{x1}}{dp_{y1}-dp_{y2}+1}$$ = (5.9)

$$\beta_{12} \frac{1}{2} . ( \alpha_{12} . (dp_{x1}+dp_{x2}) - dp_{y1}-dp_{y2}+1 )$$ = (5.10)

and L₁₃ is the mid-perpendicular of q₁q₃, so that

  

$$\alpha_{13} \frac{dp_{x3}-dp_{x1}-1}{dp_{y1}-dp_{y3}}$$ = (5.11)

$$\beta_{13} \frac{1}{2} . ( \alpha_{13} . (dp_{x1}+dp_{x3-1}) - dp_{y1}-dp_{y3} )$$ = (5.12)

Finally, we are interested in the location of the true corner of the Voronoi diagram, i.e. the intersection of L₁₂ and L₁₃. The true corner, (c_x,c_y), gives us the maximum values of (n_x,n_y) to consider. In particular, for n_x, there is no need to go further than

$$n_{x\max} = c_x = \frac{\beta_{12} - \beta_{13}}{\alpha_{13} - \alpha_{12}}$$ (5.13)

Equations (), () and () require some more attention. In (), a singularity could occur if dp_y1 = dp_y2-1. Fortunately this never happens with $q_1 \neq q_2$. In (), there is a singularity if dp_y1 = dp_y3. When this happens, it means that L₁₃ is a vertical line, for which $\alpha_{13} = \infty$ is an appropriate slope. Finally, in (), a singularity occurs when $\alpha_{13} = \alpha_{12}$. This means that L₁₂ and L₁₃ are parallels, which only occurs for $\alpha_{13} = \alpha_{12} = \pm 1$. In that case, the pixels in the diagonal direction should be tested until the first one that does not change value.