<p>I think that there is a bit of confusion in terminology. My understanding is that only the initially colored points, before step 1, are called seeds. </p>

<p>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. </p>

<p>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.</p>

CC BY-SA 3.0
2017-03-10T21:23:25.777Z
Ahh, that's it! So when a pixel finds a colored neighbor it computes the distance between that pixel and the initial seed (whose position it knows from the neighbor). This wasn't clear to me that there is a difference between a colored pixel and a seed. Thank you, you helped me a lot with that!

But one question remains: what about the diagonal pixels in the 4x4 example? They have the same distance to both initial seeds...
Muad
CC BY-SA 3.0
2017-03-10T21:36:46.803Z
Glad it makes sense now! The diagonals are ambiguous in the definition of the voronoi diagram: the paper mentions (on the first page) that for equidistant seeds, they choose the seeds arbitrarily. Maybe it will look nicer if you consistently choose one color over the other, I have no idea!
StinkySkunk
CC BY-SA 3.0
2017-03-10T20:33:09.150Z
2017-03-10T20:38:28.327Z
2017-03-10T20:38:28.327Z
StinkySkunk
<p>I'm having trouble understanding the <a href="http://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf" rel="noreferrer">JFA</a>. As far as I understood the algorithm, it walks <em>log(n)</em> 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\}$. </p>

<p>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. </p>

<p>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:</p>

<p><a href="https://i.sstatic.net/dGXJd.png" rel="noreferrer"><img src="https://i.sstatic.net/dGXJd.png" alt="complex example"></a></p>

<p>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 <em>(x+2, y)</em> neighbor is a green one with a smaller distance than its <em>(x+2, y+2)</em> red neighbor? </p>

<p>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:</p>

<p><a href="https://i.sstatic.net/mWkzJs.jpg" rel="noreferrer"><img src="https://i.sstatic.net/mWkzJs.jpg" alt="simple example"></a></p>

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

CC BY-SA 3.0
2017-03-09T13:23:47.710Z
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.
ratchet freak
CC BY-SA 3.0
2017-03-09T15:06:11.080Z
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...
Muad
CC BY-SA 3.0
2017-03-10T21:00:23.380Z
[Somewhat related](http://computergraphics.stackexchange.com/questions/2102/is-jump-flood-algorithm-separable) but definitely not a duplicate (disclaimer: I wrote an answer to it)
trichoplax is on Codidact now
<algorithm><color><mathematics><2d><distribution>
Understanding Jump Flooding Algorithm (JFA) for Voronoi Diagrams
Muad
# Understanding Jump Flooding Algorithm (JFA) for Voronoi Diagrams

(Asked by: username_0 on 2017-03-09)

I'm having trouble understanding the [JFA](http://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf). 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:

[![complex example](https://i.sstatic.net/dGXJd.png)](https://i.sstatic.net/dGXJd.png)

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:

[![simple example](https://i.sstatic.net/mWkzJs.jpg)](https://i.sstatic.net/mWkzJs.jpg)

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

**Tags:** algorithm, color, mathematics, 2d, distribution

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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...  
> **username_2**: [Somewhat related](http://computergraphics.stackexchange.com/questions/2102/is-jump-flood-algorithm-separable) but definitely not a duplicate (disclaimer: I wrote an answer to it)  

---

## 1 answers

### Answer by username_3 on 2017-03-10. Score: 8 | Accepted answer

I think that there is a bit of confusion in terminology. My understanding is that only the initially colored points, before step 1, are called seeds.

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.

> **Comments:**
> **username_0**: Ahh, that's it! So when a pixel finds a colored neighbor it computes the distance between that pixel and the initial seed (whose position it knows from the neighbor). This wasn't clear to me that there is a difference between a colored pixel and a seed. Thank you, you helped me a lot with that!  But one question remains: what about the diagonal pixels in the 4x4 example? They have the same distance to both initial seeds...  
> **username_3**: Glad it makes sense now! The diagonals are ambiguous in the definition of the voronoi diagram: the paper mentions (on the first page) that for equidistant seeds, they choose the seeds arbitrarily. Maybe it will look nicer if you consistently choose one color over the other, I have no idea!  

---

