# Understanding Jump Flooding Algorithm (JFA) for Voronoi Diagrams

I'm having trouble understanding the JFA. As far as I understood the algorithm, it walks log(n) times through every pixel (no matter if it is a seed or not) and looks at that pixel's neighbors in $(x+i, y+j)$ where $i,j \in \{-step\ length, 0, step\ length\}$.

When finding a seed (i.e., a colored pixel) among those neighbors, it checks whether the distance between the found neighbor seed and the current pixel is less than the distance the current pixel has already stored (after a previous round). If it is, the current pixel will be overwritten with the color of the found seed and the new distance and therefore serves as input seed for the next round.

So I tried to comprehend an example in some slides by the author himself but failed at step length 2, especially with the three bottommost red seeds:

For example, why does the blue circled seed keep its red color even though at step length 2 it finds two green seeds with a smaller distance (in my understanding the circled red pixel has stored a 4 and the distance to its top and bottom green neighbors is 2)? Or why does the other blue circled pixel become red, though its (x+2, y) neighbor is a green one with a smaller distance than its (x+2, y+2) red neighbor?

I also sketched another example on paper but when it comes to step length 1 the algorithm finds more than one neighbor seed with equal distances, so how will it decide? We could also think of a more simple example like this:

What are the diagonal pixels supposed to be according to the algorithm in that case? What am I getting wrong?

• Maybe because the implementation modifies in place running LtR? That would mean the pixel above got changed and one got inserted to the left but not to the right. Commented Mar 9, 2017 at 13:23
• Ok, but modifying in place would mean that, looking at the 2nd picture, the downmost circled blank pixel turns into a red one. Then, the green seed right next to it should take that information and turn into a red one too, but it remains green...
Commented Mar 9, 2017 at 15:06
• Somewhat related but definitely not a duplicate (disclaimer: I wrote an answer to it) Commented Mar 10, 2017 at 21:00

Maybe this helps clarify the algorithm as well. When the a point $p$ with color $s$ finds a neighbor $q$ with color $s'$, he compares the distance $d(p,s)$ with $d(p,s')$ (not $d(p,q)$) to decide his new color. This is why each pixel crucially holds the $(x,y)$ coordinates of his seed color (in the paper they used the r,g channels for this) and not just the distance. In each step this data is also passed to the neighbor.
So in that example, in moving from step length 4 to step length 2, that red square (the circled one that remains red) sees the green square who tells red square that the green seed is at $(8,6)$. Red square then computes his distance to green square to be $\sqrt{2^2 + 4^2}$, which is bigger than the distance to red ($4$), and so remains red.