Критерий попадания точек на целочисленную сетку с поворотом

[slavav]

Но тогда вектора для ближайших пар однозначно определяют ориентацию. Ближайшие пары можно отыскать быстрее чем за $N^2$.

[ilghiz]

Спасибо slavav!

slavav в сообщении #1562806 писал(а):

Но тогда вектора для ближайших пар однозначно определяют ориентацию.

Да, верно, я изначально строил точки так, что этого условия не было, думал, что с этим условием я не смогу их построить. Попробовав без этого условия все это сделать понял, что арифметическая сложность алгоритма получается очень не маленькой.

Проблема численной устойчивости в принципе так и осталась. Пока не решил как к ней подойти.

slavav в сообщении #1562806 писал(а):

Ближайшие пары можно отыскать быстрее чем за $N^2$.

это верно, но, так как точек у меня обычно довольно мало (однозначно меньше ста), боюсь, что кластеризация или предварительная сортировка по осям не сильно ускорит такое вычисление.

[slavav]

Возьмите любую библиотеку, которая строит диаграмму Вороного или триангуляцию Делоне. Из них все ближайшие пары извлекаются не сложно. Я не говорю что это просто сделать, но есть готовые библиотеки, которые решат задачу за почти линейное время.

-- 15.08.2022, 22:20 --

Численная устойчивость: по ближайшей паре получите расстояние, умножьте его на $\sqrt{\sqrt{2}}$. Отберите все пары расстояния между которыми меньше этой границы. Они распадутся на два семейства с почти ортогональными направлениями. Среднее направление по любому семейству даст хорошую отправную точку.

[ilghiz]

Спасибо slavav!

slavav в сообщении #1562812 писал(а):

Возьмите любую библиотеку, которая строит диаграмму Вороного или триангуляцию Делоне.

Да, верно. Есть своя самописная Делоне триангуляция, лет десять-пятнадцать назад мой вариант слегка обыгрывал по скорости построения обычный qhull на больших сетках и там все было очень и очень вылизано, чтобы нигде не поиметь квадратичную асимптотику, последнее время не сравнивался, так как особо не надо было и давно не триангулирую. На том множестве точек, что у меня сейчас есть, моя Делоне-триангуляция реально проигрывает простому перебору, так как в среднем у меня 20-30 точек всего и тут сложно что-то придумать лучше. Если бы точек было бы существенно больше 100 - полностью с Вами соглашусь, надо строить или триангуляцию, или использовать хотя бы кластеризацию точек.

slavav в сообщении #1562812 писал(а):

Численная устойчивость: по ближайшей паре получите расстояние, умножьте его на $\sqrt{\sqrt{2}}$. Отберите все пары расстояния между которыми меньше этой границы. Они распадутся на два семейства с почти ортогональными направлениями. Среднее направление по любому семейству даст хорошую отправную точку.

Очень идейно! Спасибо! Я примерно в этом направлении думал, но у Вас быстрее мысли материализовались в правильное утверждение.


Ой... сейчас смотрю я на все это и боюсь, что все снова придется придумывать.

Я не учел тот факт, что набор точек может содержать не только точки на целочисленной сетке, но также еще один или несколько наборов не попадающий на целочисленную сетку. Более точно - другие наборы - это проекции точек с других целочисленных сеток в 3Д пространстве на эту плоскость. Единственно, что мне точно известно, эти наборы не пересекаются, но в других наборах расстояния между точками могут быть существенно меньше, чем в этом наборе.

Похоже придется сортировать все наблюдаемые расстояния, кластеризовать эти длины, если при одинаковой длине есть хаос в направлении, то их отбрасывать, иначе - строить сетку, и, если на сетке все распознается, то рапортовать, что сетка найдена, иначе - переходить на следующее большее расстояние и так до получения результата.