Определите, лежит ли множество точек на регулярной сетке

Question

Задача: Предположим, у вас есть набор точек в 2D-плоскости.Я хочу знать, находится ли этот набор точек на регулярной сетке (если они являются подмножеством двумерной решетки).Я хотел бы поделиться некоторыми идеями о том, как это сделать.

А сейчас, скажем, меня интересует только то, образуют ли эти точки прямоугольную сетку с выравниванием по оси (что нижележащая решетка является прямоугольной, выровненной по xи осей y), и что это полный прямоугольник (подмножество решетки имеет прямоугольную границу без отверстий).Любые решения должны быть достаточно эффективными (лучше, чем O (N ^ 2)), поскольку N может быть сотнями тысяч или миллионами.

Контекст: Я написал генератор 2D-векторного векторного графика, которыйработает для произвольно дискретизированного векторного поля.В случае, когда выборка выполняется на регулярной сетке, существуют более простые / более эффективные схемы интерполяции для создания графика, и я хотел бы знать, когда я смогу использовать этот особый случай.Частный случай достаточно лучше, чем он заслуживает.Программа написана на языке C.

Answer 1

Это может быть глупо, но если бы ваши точки лежали на регулярной сетке, разве пики в преобразовании координат Фурье не были бы точным кратным разрешению сетки?Вы можете сделать отдельное преобразование Фурье по координатам X и Y.Если на решетке нет дыр, то FT, я думаю, будет дельта-функцией.БПФ - O (nlog (n)).

ps Я бы оставил это как комментарий, но моя репутация слишком низкая ..

Answer 2

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

чтобы найти прямоугольную сетку, которая соответствует набору точек, вам необходимо найти GCD всех координат x и GCD всех координат y с началом координат в xmin, ymin, это должно быть O (n (log n) ^ 2) Я думаю.

Как вы решите, будет ли эта сетка слишком разреженной, однако неясно

Answer 3

Скажем, сетка определяется ориентацией Or (в пределах 0 и 90 градусов) и разрешением Res. Вы можете вычислить функцию стоимости, которая оценивает, прилипает ли сетка (Or, Res) к вашим точкам. Например, вы можете вычислить среднее расстояние каждой точки до ее ближайшей точки сетки.

Ваша проблема в том, чтобы найти пару (или, Res), которая минимизирует функцию стоимости. Чтобы сузить пространство поиска и улучшить некоторые из них, можно использовать эвристику для проверки «хороших» сеток кандидатов.

Этот подход такой же, как и в преобразовании Хафа, предложенном Джиллесом. Пространство (или Res) сравнимо с гамма-пространством Хафа.

Answer 4

Если все точки берутся только из пересечений на сетке, тогда вам может помочь грубое преобразование из вашего набора точек. Если вы обнаружите, что два взаимно перпендикулярных набора линий встречаются чаще всего (имеется в виду, что вы находите пики при четырех значениях тета на расстоянии 90 градусов друг от друга) и вы обнаруживаете повторяющиеся пики в гамма-пространстве, то у вас есть сетка. В противном случае нет.

Answer 5

Вот решение, которое работает в O (ND log N), где N - количество точек, а D - количество измерений (2 в вашем случае).

1. Выделите массивы D с пробелом для N чисел: X, Y, Z и т. Д. (Время: O (ND))
2. Выполните итерацию по списку точек и добавьте x-координату в список X, y-координату в список Y и т. Д. (Время: O (ND))
3. Сортировка каждого из новых списков. (Время: O (ND log N))
4. Подсчитайте количество уникальных значений в каждом списке и убедитесь, что разница между последовательными уникальными значениями одинакова во всем списке. (Время: O (ND))
5. Если
   • уникальные значения в каждом измерении расположены на одинаковом расстоянии, а
   • если произведение числа уникальных значений каждой координаты равно количеству исходных точек (длина (uniq (X)) * длина (uniq (Y)) * ... == N,

тогда точки находятся в правильной прямоугольной сетке.