Выбор подмножества из большего 2d набора?

Question

У меня есть некоторые объекты с атрибутами x и y (позиции). Я хотел бы получить и обработать те объекты, которые находятся рядом со мной (!), Но игнорировать те, которые находятся вне диапазона (*).

__________________________ 
| __________    | 
| |  ! | *   | 
|* |   !|  *  | -me = center of subset 
| | me |   | -! = elements of subset 
| | !  |   | -* = elements of full set, not visible 
| |_______!__| *  *| 
|__________________________| 

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

Вместо этого я ищу способ выбора только близлежащих элементов для начала. Может быть, путем сортировки 2d набора в некотором роде и только повторить набор по определенному диапазону (от границы подмножества до границы).

Есть ли хороший способ сделать это?

(примечание: положения объектов, статичны, и набор может быть предварительно обработаны)

Answer 1

Построить quadtree, содержащий все точки.

В данном прямоугольнике запросов R и корневой узел Q дерева квадратов псевдокод для алгоритма запроса выглядит следующим образом.

query(Rectangle R, QuadTreeNode Q) 
    if R and Q.bounds are disjoint 
     yield no points 
    else if R contains Q.bounds 
     yield all points in the subtree of Q 
    else (if R intersects Q.bounds) 
     yield all points in query(R, Q.child[i]) for i = 0, 1, 2, 3 

Это предполагает QuadTreeNode имеет Rectangle bounds и QuadTreeNode child[4].