Использование QuadTree для получения всех точек в пределах ограничительного круга - PullRequest
Новая
       23

Использование QuadTree для получения всех точек в пределах ограничительного круга

10 голосов
/ 14 июля 2011

У меня есть набор от 100 до 200 баллов (х, у).Я должен проверить, какие из них находятся на определенном расстоянии от других.Конкретное расстояние фиксировано для всей программы, скажем, 50. Скажем, точка 1 находится в диапазоне точек 5,7,25,90,96,105 ... и т. Д.Точно так же точка 2 находится в диапазоне 23,45 и т. Д. Хранение объектов для определения местоположения по координатам x, y

Здесь предлагается QuadTree, но его можно использовать для получения всехуказывает на ограничивающий прямоугольник.Но как получить все точки в пределах ограничительного круга?есть метод, который возвращает точку, ближайшую к широте / долготе на максимальном расстоянии, но как получить все точки на расстоянии?http://openmap.bbn.com/doc/api/com/bbn/openmap/util/quadtree/QuadTree.html#QuadTree(float, float, float, float, int)

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

1 Ответ

22 голосов
/ 15 июля 2011

Предположим, что у вас есть круг с центром в (x, y) с радиусом r, и вы хотите найти все точки в дереве квадрантов, которые находятся в круге.Одна идея заключается в следующем:

  1. Построить ограничивающий прямоугольник с надписью круга.Это самый маленький прямоугольник, содержащий круг, который имеет верхний левый угол (x - r, y - r) и нижний правый угол (x + r, y + r).Любая точка в круге также должна быть в квадрате, но не наоборот.

  2. Запросите дерево квадрантов для набора точек, лежащих в этом прямоугольнике.Пусть эти точки будут P.

  3. Для каждой точки в P, которая, как известно, находится в прямоугольнике, проверьте, находится ли она также в окружности.Вы можете сделать это, проверив, не больше ли расстояние от этой точки до (x, y), чем r.Другими словами, учитывая точку (x 0 , y 0 ), вы бы вычислили (x - x 0 ) 2 +(y - y 0 ) 2 , и если это значение меньше или равно r 2 , то точка содержится в окружности.

Хотя это может показаться неэффективным, на самом деле это довольно быстро.Отношение площади квадрата к площади круга составляет 4 / π ≈ 1,27.Другими словами, предполагая, что ваши очки распределены несколько равномерно, вы найдете только на 27% больше очков, чем нужно.

...