1

The goal is to find a closest pixel with a certain value. To do that, I want to loop over the pixel, starting from the closest, with increasing distance, untill I reach a pixel which matches my requirements (edge of the grid or the desired value).

I believe this is not a duplicate, although very similar question have appeared before.

Looping in a spiral or another spiral answer are useful, but they won't result in the points ordered by distance to the center.

Justin L. actually mentions his application to find the closest point, but overlook the actual distance.

For example the algorithm in this image would find [1, 1] before [0, 1] although [0, 1] is much closer (distance of 1) compared to [1, 1] (distance of √2).

enter image description here

I'd like to get the points ordered by distance [1, 0] [0, 1] [-1, 0] [0, -1] [1, 1] ... otherwise it wouldn't be a real spiral.

This answer suggests spiraling with a very small step size, but since I don't know how far I need to spiral, this sounds very inefficient.

I hope this graphic makes the order clearer.

enter image description here

Leander
  • 508
  • 6
  • 21

1 Answers1

0

I wouldn't name it a spiral loop what you are describing. A spiral is a (connected) path. What you are looking for is not a path. Anyways, I would do the following:

  1. In a pre-process step, add all coordinates of the grid including their distance to the center to an e.g. std::vector and have it sorted by the distance to the center. Then build an index table by storing the offset in the grid for each coordinate.

  2. At runtime use the index table to walk through the grid.

I am not sure though, if this pragmatic approach is what you are looking for. The runtime relevant step 2 is fast for sure.

Pedro
  • 842
  • 6
  • 16
  • I couldn't find a better method. I ended up storing the distances in a file, because the calculation was rather slow on a 2048x2048 grid. – Leander May 08 '18 at 14:43