Как перебрать кольца в растровой сетке?

Если упрощение до целочисленных координат сетки в порядке (как подсказывает ваше замечание о «почти равном расстоянии»), вы можете пройти по ячейкам по кругу с увеличением расстояния с помощью приведенного ниже кода. Если ваша начальная точка отличается от (0,0), вам просто нужно добавить ее к каждой сгенерированной точке. Ключевые идеи:

1. начиная с (d,0) мы итеративно ищем соседнюю точку с «похожим» расстоянием (целая часть = d) против часовой стрелки вокруг (0,0) пока мы не достигнем отправной точки.
2. каждая точка будет иметь (кроме соседа, из которого мы пришли) не более одного прямого соседа (через ребро) с «одинаковым» расстоянием. Если прямого соседа нет, то существует ровно одна диагональная соседка с «похожим» расстоянием (опять же, за исключением предыдущего соседа).
3. вектор к следующему соседу «почти» ортогонален вектору к началу координат.

Вот код:

#include <cmath>
#include <vector>

template <typename T> int sgn(T val) {
return (T(0) < val) - (val < T(0));
}

int dist(double dx, double dy)
{
return (int)sqrt(dx*dx + dy*dy);
}

typedef std::pair<int,int> TPoint;
typedef std::vector<TPoint> TPoints;

void generateNeighbourRing(int d, TPoints& ring)
{
int dx = d;
int dy = 0;
do
{
ring.push_back(TPoint(dx,dy));
int nx = -sgn(dy);
int ny = sgn(dx);
if (nx != 0 && dist(dx+nx, dy) == d)
dx += nx;
else if (ny != 0 && dist(dx, dy+ny) == d)
dy += ny;
else
{
dx += nx;
dy += ny;
}
} while (dx != d || dy != 0);
}

int main()
{
TPoints points;
const int d_max = 4;
for (int d = 0; d <= d_max; ++d)
generateNeighbourRing(d, points);
printf("spiral for dmax=%d (%d points):\n", d_max, points.size());
for (unsigned int i=0; i<points.size(); ++i)
printf(" (%d,%d),", points[i].first, points[i].second);
printf("\n");
}

Достоверность правильности:

Давайте сначала посмотрим на изображения, где ячейки с равным расстоянием до центральной ячейки имеют одинаковый цвет (после того, как расстояние урезано, как только расстояние округлено):

— — — — — —

С (dx,dy) перебираем ячейки кольца с одинаковым расстоянием; (nx,ny) является видом нормального вектора, который является постоянным вдоль каждой полуоси и внутри каждого квадранта:

Черные стрелки показывают (nx,ny) для каждого региона; синие стрелки показывают направления, в которых сначала ищется (прямой) сосед с равным расстоянием.

Далее нам нужно рассмотреть, какие конфигурации соседей с равным расстоянием возможны. Поскольку квадранты вращательно симметричны, достаточно взглянуть на первый квадрант. Расстояние до центральной ячейки между двумя прямыми соседями может отличаться не более чем на 1; по диагонали к центру или от него расстояние отличается на 1 или 2:

. . .

(Это следует из прямых неравенств.) Важным выводом является то, что блок 2×2 равных расстояний не может быть; самое большее 4 соседа могут иметь одинаковое расстояние, образуя «зигзаг»:

. . .

Другим важным выводом является то, что каждая ячейка имеет как минимум 2 соседей с одинаковым расстоянием, опять же только в определенных конфигурациях. Исходя из этого, можно утверждать, что если соседи вдоль синих стрелок имеют разное расстояние, то соседи по черной стрелке имеют одинаковое расстояние. Таким образом, все точки помещаются в переменную ring иметь расстояние d, (Обратите внимание, что во втором else-отрасли расстояние не проверено.)

Далее мы идем на прекращение do ... while-loop. Обратите внимание, что с каждой итерацией угол между линией (0,0) — (dx, dy) и положительной осью x увеличивается. Поскольку расстояние остается неизменным, мы, наконец, покинем текущий квадрант и перейдем к следующему. И поскольку вдоль полуоси каждое расстояние появляется ровно после того, как мы наконец достигнем начальной точки (d, 0).

Из этого также следует, что точка не берется дважды: в течение одного вызова generateNeighbourRing начиная итерацию do ... while цикл с той же самой точкой снова приведет к бесконечному циклу и, следовательно, противоречит окончанию. Через несколько звонков generateNeighbourRing все точки разные из-за разного расстояния до центральной ячейки.

Глядя на возможные конфигурации с соседями с одинаковым расстоянием, можно также показать, что все точки с заданным расстоянием d будут собраны.