I'm trying to devise an algorithm for enumerating all points on a 2D grid in order of their Euclidean distance to a given target point. I know I could just get a bunch of them that are close to the target and then sort them, but that's not what I want. I want something that will output every point, out to infinity, in order of their distance to the target.
At the bare minimum, I need something that works if the target point is also a grid point. But ideally, I want something that works for any target, even non-grid points. Ideally ideally, I want something that works for grids of an uneven x-y scale.
Any ideas on where to start with this?
Best Answer
Except for the corners of the square your target is in, every grid point has a neighbor that is closer to the target. So you can use a modified breadth-first search:
Maintain a priority queue of points that you have not printed yet but are neighbors to something you have printed, ordered by (squared) distance to the target. Keep taking out the closest point and adding those of its remoter neighbors that are not already in the queue.
This uses $O(\sqrt n)$ space to print $n$ points, and it takes $O(\log n)$ work to print point number $n$.