Wave propagation in digital image I believe the following question in summary is: How to approximate Euclidean distance in a digital plane?


  When a pebble falls on a calm surface of water a circular wave propagates. I want to color the pixels with time to show this effect. So I discretize the time and in each time step, starting  from the center, I color one pixel away in all directions. But this gives a square wave. I guess what is wrong is that I have approximated the Euclidean distance with the infinity norm.


How do I approximate Euclidean distance to get the a circular wave on the pixels? I don't want to measure the distance from each pixel to the center in each time slot. That will be very heavy. I am looking for a simple algorithm like coloring the next pixel adjacent to last colored pixel.
Here's a trick that video game designers have used for years. A computationally cheaper approximation to Euclidean distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ is to use
$$
d=\max(|x_1-x_2|, |y_1-y_2|)+\min(|x_1-x_2|, |y_1-y_2|)/2
$$
The relative error between this and the Euclidean distance is no more than 11.8%, which might be good enough for your purposes.