Вход | Регистрация
 
Информационные технологии :: Математика и алгоритмы

Список точек по расстоянию.

Список точек по расстоянию.
Я
   Dirk Diggler
 
02.06.20 - 11:39
Есть плоскость XY, на ней множество точек A1...An , координаты всех известны.

Задача: для заданной новой точки B с координатами X1, Y1 определить все точки, попадающие в круг с центром (X1, Y1) радиусом R, и отсортировать по возрастанию расстояния.

Перебор не подходит, исходное множество велико - медленно.

Какие еще варианты? Какие-то вариации BSP, может?
   Волшебник
 
Модератор
1 - 02.06.20 - 11:42
Используй квадраты
   Dmitry1c
 
2 - 02.06.20 - 11:43
ох уж эти скучающие математики
   Dirk Diggler
 
3 - 02.06.20 - 11:43
(1) квантовать всю плоскость в квадраты и индексировать?
   Dirk Diggler
 
4 - 02.06.20 - 11:44
(2) это практическая задача
   NorthWind
 
5 - 02.06.20 - 11:44
   Dirk Diggler
 
6 - 02.06.20 - 11:47
(5) это рядом, но не совсем то. Из того, что предлагает яндекс, можно организовать только перебор. Перебор неприемлем в данном случае, уж лучше действительно квантовать плоскость, найти квадрат, в котором новая точка, и собрать точки из соседних. Погрешность более допустима, чем перебор.
   Волшебник
 
Модератор
7 - 02.06.20 - 11:47
(3)
Сначала выбрать точки, которые попали в квадрат с вершинами (X1-R, Y1-R) - (X1+R, Y1+R)
Потом посчитать точное расстояние для входящих точек.
   Garykom
 
8 - 02.06.20 - 11:48
(3) С учетом R
   Dirk Diggler
 
9 - 02.06.20 - 11:50
(7) для этого надо перебрать все точки и вычислить, попали ли они в квадрат. Т.е. опять перебор/

Для ухода от перебора надо порезать всю плоскость(она ограничена) на квадраты, каждой точке приписать квадрат, найти тот, в который попала новая, собрать соседние квадраты в пределах радиуса, в них собрать точки, для них уже делать операции.
   Волшебник
 
Модератор
10 - 02.06.20 - 11:51
(9) Сначала ЗАПРОСОМ выбрать точки, которые попали в квадрат с вершинами (X1-R, Y1-R) - (X1+R, Y1+R). Условие на простое неравенство без сложных вычислений
   Garykom
 
11 - 02.06.20 - 11:51
(6) Если погрешность тогда полярные координаты по сетке.
Делаешь сетку из точек.
Заранее для всех точек находишь их полярные координаты принимая точки сетки за центр.
Далее банально для X1, Y1 берешь ближайшую точку сетки и готово.
   Волшебник
 
Модератор
12 - 02.06.20 - 11:52
в PostgreSQL есть готовые типы данных и библиотеки для решения подобных задач
   arsik
 
13 - 02.06.20 - 11:54
(9) Используйте базу постгре с дополнением - там можно запросом быстро выбирать нужную вам информацию.
   Волшебник
 
Модератор
14 - 02.06.20 - 11:56
(13) Дай пять!
   МихаилМ
 
15 - 02.06.20 - 12:09
в мс скл тип геоданных появился задолго о постгреса
   МихаилМ
 
16 - 02.06.20 - 12:11
в 1с для такой задачи можно задействовать "новый" функционал решения слау. а для решения "квадратами" подойдет механизм анализ данных.кластеризация.
   vde69
 
17 - 02.06.20 - 12:17
в MySQL есть функции для сабжа, работают с типом "геометрия"

(0) твоя зада решается совмещением двух патентов "строй и престраивай" и "разделяй и властвуй".
Почитай "Триангуляция Делона" - я реализовывал, алгоритм не очень сложный...
   polosov
 
18 - 02.06.20 - 12:32
(0) Попробуй копнуть в сторону полярных координат.
   vde69
 
19 - 02.06.20 - 12:40
(18) квадраты самое лучшее...

банально
1. быстрая проверка прямо в запросе "если (х в диапазоне х_точки-радиус и х_точки+радиус) И (у в диапазоне у_точки-радиус и у_точки+радиус)"
2. дальше вторая итерация с перебором точек которые прошли первое условие
   polosov
 
20 - 02.06.20 - 12:52
   МихаилМ
 
21 - 02.06.20 - 12:56
(20) нет .это аппроксимация. подошла бы для ближайших к окружности


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.