А поделитесь знанием про индексирование 2-мерных плоскостей. Дано: Прямоугольная область ([x1,

Question

А поделитесь знанием про индексирование 2-мерных плоскостей. Дано: Прямоугольная область ([x1,

y1]; [x2, y2])
На данной области располагаются точки [xN, yN], N = 1..10000 (то есть очень много), координаты не целые (то есть стоят все не по сетке), новые точки не появляются в процессе жизни приложения, точки распределены сильно не равномерно. Область можно "проиндексировать" ....
В определенный момент появляется информация о окружности [[Xp, Yp], Rp] где [Xp, Yp] принадлежит плоскости
Нужно максимально быстро найти все точки [xN, yN], которые попадают внутрь этой окружности.

В какую сторону копать?
Есть какой-то аглоритм индексации 2-мерных пространств, котоый дерево поиска построит?
Или использовать 2 дерева для каждой координаты?
(не касаемо питона)

#backend #programming #python #russian

0

02.04.2022