Автор оригинала: Mohan Sundararaju.
1. Обзор
В этом уроке мы рассмотрим концепцию поиска соседей в двумерном пространстве . Затем мы рассмотрим его реализацию на Java.
2. Одномерный поиск против двумерного поиска
Мы знаем, что двоичный поиск-это эффективный алгоритм для поиска точного совпадения в списке элементов с использованием подхода “разделяй и властвуй”.
Давайте теперь рассмотрим двумерную область, где каждый элемент представлен координатами XY (точками) на плоскости .
Однако вместо точного совпадения предположим, что мы хотим найти соседей данной точки на плоскости. Понятно, что если нам нужны ближайшие n совпадения, то двоичный поиск не будет работать . Это связано с тем, что двоичный поиск может сравнивать два элемента только по одной оси, в то время как мы должны иметь возможность сравнивать их по двум осям.
В следующем разделе мы рассмотрим альтернативу структуре данных двоичного дерева.
3. Квадратное дерево
Квадродерево-это пространственная древовидная структура данных, в которой каждый узел имеет ровно четыре дочерних элемента. Каждый дочерний элемент может быть либо точкой, либо списком, содержащим четыре поддерева.
A точка хранит данные — например, координаты XY. область представляет собой замкнутую границу, в пределах которой может храниться точка. Он используется для определения области досягаемости квадродерева.
Давайте разберемся в этом подробнее, используя пример 10 координат в некотором произвольном порядке:
(21,25), (55,53), (70,318), (98,302), (49,229), (135,229), (224,292), (206,321), (197,258), (245,238)
Первые три значения будут сохранены в виде точек под корневым узлом, как показано на крайнем левом рисунке.
Корневой узел теперь не может вместить новые точки, так как он достиг своей емкости в три точки. Поэтому мы разделим область корневого узла на четыре равных квадранта .
Каждый из этих квадрантов может хранить три точки и дополнительно содержать четыре квадранта в пределах своей границы. Это можно сделать рекурсивно, в результате чего получится дерево квадрантов, в котором структура данных квадрата получает свое имя.
На среднем рисунке выше мы видим квадранты, созданные из корневого узла, и то, как следующие четыре точки хранятся в этих квадрантах.
Наконец, самое правое изображение показывает, как один квадрант снова подразделяется, чтобы разместить больше точек в этой области, в то время как другие квадранты все еще могут принимать новые точки.
Теперь мы посмотрим, как реализовать этот алгоритм в Java.
4. Структура данных
Давайте создадим структуру данных квадродерева. Нам понадобятся три класса доменов.
Во-первых, мы создадим класс Point для хранения координат XY :
public class Point {
private float x;
private float y;
public Point(float x, float y) {
this.x = x;
this.y = y;
}
// getters & toString()
}Во-вторых, давайте создадим класс Region для определения границ квадранта :
public class Region {
private float x1;
private float y1;
private float x2;
private float y2;
public Region(float x1, float y1, float x2, float y2) {
this.x1 = x1;
this.y1 = y1;
this.x2 = x2;
this.y2 = y2;
}
// getters & toString()
}Наконец, давайте создадим класс QuadTree для хранения данных в виде точечных экземпляров и дочерних элементов в виде QuadTree классов :
public class QuadTree {
private static final int MAX_POINTS = 3;
private Region area;
private List points = new ArrayList<>();
private List quadTrees = new ArrayList<>();
public QuadTree(Region area) {
this.area = area;
}
} Чтобы создать экземпляр объекта QuadTree , мы указываем его область с помощью класса Region через конструктор.
5. Алгоритм
Прежде чем мы напишем нашу основную логику для хранения данных, давайте добавим несколько вспомогательных методов. Они окажутся полезными позже.
5.1. Вспомогательные методы
Давайте изменим наш Регион класс.
Во-первых, давайте иметь метод containsPoint , чтобы указать, попадает ли данная точка внутрь или за пределы области региона :
public boolean containsPoint(Point point) {
return point.getX() >= this.x1
&& point.getX() < this.x2
&& point.getY() >= this.y1
&& point.getY() < this.y2;
}Далее, давайте рассмотрим метод Перекрывается , чтобы указать, перекрывается ли данный регион с другим регионом :
public boolean doesOverlap(Region testRegion) {
if (testRegion.getX2() < this.getX1()) {
return false;
}
if (testRegion.getX1() > this.getX2()) {
return false;
}
if (testRegion.getY1() > this.getY2()) {
return false;
}
if (testRegion.getY2() < this.getY1()) {
return false;
}
return true;
}Наконец, давайте создадим метод getQuadrant , чтобы разделить диапазон на четыре равных квадранта и вернуть указанный:
public Region getQuadrant(int quadrantIndex) {
float quadrantWidth = (this.x2 - this.x1) / 2;
float quadrantHeight = (this.y2 - this.y1) / 2;
// 0=SW, 1=NW, 2=NE, 3=SE
switch (quadrantIndex) {
case 0:
return new Region(x1, y1, x1 + quadrantWidth, y1 + quadrantHeight);
case 1:
return new Region(x1, y1 + quadrantHeight, x1 + quadrantWidth, y2);
case 2:
return new Region(x1 + quadrantWidth, y1 + quadrantHeight, x2, y2);
case 3:
return new Region(x1 + quadrantWidth, y1, x2, y1 + quadrantHeight);
}
return null;
}5.2. Хранение Данных
Теперь мы можем написать нашу логику для хранения данных. Давайте начнем с определения нового метода addPoint в классе QuadTree для добавления новой точки. Этот метод вернет true , если точка была успешно добавлена:
public boolean addPoint(Point point) {
// ...
}Далее, давайте напишем логику, чтобы справиться с этим вопросом. Во-первых, нам нужно проверить, содержится ли точка в пределах границы экземпляра QuadTree . Нам также необходимо убедиться, что экземпляр QuadTree не достиг емкости MAX_POINTS points.
Если оба условия выполнены, мы можем добавить новую точку:
if (this.area.containsPoint(point)) {
if (this.points.size() < MAX_POINTS) {
this.points.add(point);
return true;
}
}С другой стороны, если мы достигли значения MAX_POINTS , то нам нужно добавить новую точку в один из подквадрантов . Для этого мы перебираем дочерний список quadTrees и вызываем тот же метод addPoint , который вернет значение true при успешном добавлении. Затем мы немедленно выходим из цикла, так как точка должна быть добавлена точно в один квадрант .
Мы можем инкапсулировать всю эту логику в вспомогательный метод:
private boolean addPointToOneQuadrant(Point point) {
boolean isPointAdded;
for (int i = 0; i < 4; i++) {
isPointAdded = this.quadTrees.get(i)
.addPoint(point);
if (isPointAdded)
return true;
}
return false;
}Кроме того, у нас есть удобный метод создания квадрантов для разделения текущего квадранта на четыре квадранта:
private void createQuadrants() {
Region region;
for (int i = 0; i < 4; i++) {
region = this.area.getQuadrant(i);
quadTrees.add(new QuadTree(region));
}
}Мы вызовем этот метод для создания квадрантов только в том случае, если мы больше не сможем добавлять новые точки . Это гарантирует, что наша структура данных использует оптимальное пространство памяти.
Собрав все это вместе, мы получили обновленный метод addPoint :
public boolean addPoint(Point point) {
if (this.area.containsPoint(point)) {
if (this.points.size() < MAX_POINTS) {
this.points.add(point);
return true;
} else {
if (this.quadTrees.size() == 0) {
createQuadrants();
}
return addPointToOneQuadrant(point);
}
}
return false;
}5.3. Поиск данных
Определив нашу структуру квадродерева для хранения данных, мы теперь можем думать о логике выполнения поиска.
Поскольку мы ищем соседние элементы, мы можем указать область поиска в качестве отправной точки . Затем мы проверяем, перекрывается ли он с корневой областью. Если это так, то мы добавляем все его дочерние точки, которые попадают в область поиска /.
После корневой области мы попадаем в каждый из квадрантов и повторяем процесс. Это продолжается до тех пор, пока мы не достигнем конца дерева.
Давайте запишем приведенную выше логику как рекурсивный метод в классе QuadTree :
public Listsearch(Region searchRegion, List matches) { if (matches == null) { matches = new ArrayList (); } if (!this.area.doesOverlap(searchRegion)) { return matches; } else { for (Point point : points) { if (searchRegion.containsPoint(point)) { matches.add(point); } } if (this.quadTrees.size() > 0) { for (int i = 0; i < 4; i++) { quadTrees.get(i) .search(searchRegion, matches); } } } return matches; }
6. Тестирование
Теперь, когда у нас есть наш алгоритм, давайте его протестируем.
6.1. Заполнение данных
Во-первых, давайте заполним квадратное дерево теми же 10 координатами, которые мы использовали ранее:
Region area = new Region(0, 0, 400, 400);
QuadTree quadTree = new QuadTree(area);
float[][] points = new float[][] { { 21, 25 }, { 55, 53 }, { 70, 318 }, { 98, 302 },
{ 49, 229 }, { 135, 229 }, { 224, 292 }, { 206, 321 }, { 197, 258 }, { 245, 238 } };
for (int i = 0; i < points.length; i++) {
Point point = new Point(points[i][0], points[i][1]);
quadTree.addPoint(point);
}6.2. Поиск диапазона
Затем давайте выполним поиск диапазона в области, ограниченной координатами нижней границы (200, 200) и верхней границы (250, 250):
Region searchArea = new Region(200, 200, 250, 250); Listresult = quadTree.search(searchArea, null);
Запуск кода даст нам одну ближайшую координату, содержащуюся в области поиска:
[[245.0 , 238.0]]
Давайте попробуем другую область поиска между координатами (0, 0) и (100, 100):
Region searchArea = new Region(0, 0, 100, 100); Listresult = quadTree.search(searchArea, null);
Запуск кода даст нам две близлежащие координаты для указанной области поиска:
[[21.0 , 25.0], [55.0 , 53.0]]
Мы наблюдаем, что в зависимости от размера области поиска мы получаем ноль, одну или несколько точек. Итак, если бы нам дали точку и попросили найти ближайших n соседей, мы могли бы определить подходящую область поиска, где данная точка находится в центре .
Затем из всех полученных точек поисковой операции мы можем вычислить евклидовы расстояния между заданными точками и отсортировать их, чтобы получить ближайших соседей .
7. Временная Сложность
Временная сложность запроса диапазона просто O(n) . Причина в том, что в худшем случае он должен пройти через каждый элемент, если указанная область поиска равна или больше, чем населенная область.
8. Заключение
В этой статье мы впервые поняли концепцию квадродерева, сравнив его с двоичным деревом. Затем мы увидели, как его можно эффективно использовать для хранения данных, распределенных по двумерному пространству.
Затем мы увидели, как хранить данные и выполнять поиск по диапазону.
Как всегда, исходный код с тестами доступен на GitHub .