Цикл по реальной спирали на дискретной сетке

Question

Цель состоит в том, чтобы найти ближайший пиксель с определенным значением. Чтобы сделать это, я хочу перебрать пиксель, начиная с ближайшего, с увеличением расстояния, пока не достигну пикселя, который соответствует моим требованиям (край сетки или желаемое значение).

Я считаю, что это не дубликат, хотя очень похожие вопросы уже появлялись раньше.

Цикл по спирали или другой спиральный ответ полезны, но они не приведут к точкам, упорядоченным по расстоянию до центра.

Джастин Л. фактически упоминает о своем заявлении, чтобы найти ближайшую точку, но не учитывает фактическое расстояние.

Например, алгоритм на этом изображении нашел бы [1, 1] перед [0, 1], хотя [0, 1] намного ближе (расстояние 1) по сравнению с [1, 1] (расстояние √2).

Я хотел бы получить очки, упорядоченные по расстоянию[1, 0] [0, 1] [-1, 0] [0, -1] [1, 1] ...иначе это не было бы настоящей спиралью.

Этот ответ предполагает спираль с очень маленьким размером шага, но, поскольку я не знаю, как далеко я должен спирали, это звучит очень неэффективно.

Я надеюсь, что этот рисунок делает порядок чище.

Answer 1

Я бы не назвал это спиральной петлей, которую вы описываете. Спираль - это (связанный) путь. То, что вы ищете, не путь. В любом случае, я бы сделал следующее:

1. На шаге предварительной обработки добавьте все координаты сетки, включая их расстояние до центра, например, std::vector и отсортировать его по расстоянию до центра. Затем создайте таблицу индексов, сохранив смещение в сетке для каждой координаты.

2. Во время выполнения используйте индексную таблицу, чтобы пройти через сетку.

Я не уверен, однако, если этот прагматичный подход - то, что вы ищете. Шаг 2, соответствующий времени выполнения, очень быстрый.