2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Критерий попадания точек на целочисленную сетку с поворотом
Сообщение15.08.2022, 21:37 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Критерий попадания точек на целочисленную сетку с поворотом
Сообщение15.08.2022, 22:10 


11/08/18
363
Спасибо slavav!

slavav в сообщении #1562806 писал(а):
Но тогда вектора для ближайших пар однозначно определяют ориентацию.

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

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

slavav в сообщении #1562806 писал(а):
Ближайшие пары можно отыскать быстрее чем за $N^2$.

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

 Профиль  
                  
 
 Re: Критерий попадания точек на целочисленную сетку с поворотом
Сообщение15.08.2022, 22:14 
Заслуженный участник


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

-- 15.08.2022, 22:20 --

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

 Профиль  
                  
 
 Re: Критерий попадания точек на целочисленную сетку с поворотом
Сообщение16.08.2022, 01:23 


11/08/18
363
Спасибо slavav!

slavav в сообщении #1562812 писал(а):
Возьмите любую библиотеку, которая строит диаграмму Вороного или триангуляцию Делоне.

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

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

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


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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 19 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group