Реализация алгоритма поиска ближайших объектов с помощью K-D tree



В данной статье разработан алгоритм поиска ближайших объектов с помощью вспомогательной структуры, основанной на K-D tree, а также рассматривается приложение на языке Java, реализующее данный алгоритм.

Ключевые слова: K-D tree, поиск объектов

В современных информационных системах часто появляется необходимость найти объекты в определенной области. Ключевое значение при реализации такой возможности имеют используемые структуры данных и алгоритмы их обработки.

Постановка задачи

В системе будут храниться следующие географические данные: широта, долгота, название объекта.

public class Geo {

private final double latitude;

private final double longitude;

private final String title;

}

Листинг 1. Структура объекта

Реализуем структуру, ускоряющую поиск по данным. При этом основная задача — поиск всех объектов, находящихся в определённом радиусе от указанной точки.

В качестве структуры данных для ускорения поиска выбрано K-D tree.

Структуру узла можно описать с помощью трёх переменных: значение текущего узла, ссылка на левый узел, ссылка на правый узел.

public class Node {

private final Geo item;

private final Node left;

private final Node right;

}

Листинг 2. Структура узла

При этом начальным хранилищем информации будет выступать не корень дерева, а контейнер, реализующий интерфейс List. На каждое удаление/вставку новой точки пространства будет происходить перестроение K-D tree.

Построение K-D tree

Используется разбиение исходного множества точек по широте/долготе. Чтобы разбиение получилось равномерным, при нечётном значении глубины дерева происходит разбиение по долготе, при чётном значении — по широте. Из-за этого, чтобы найти интересующие нас точки пространства, необходимо проверить не все точки (как при полном переборе). Набор данных, которые нужно просмотреть ограничивается теми поддеревьями, которые на определённом шаге удовлетворяют некоторому условию относительно заданной точки. Эти условия зависят от соотношения координат исходной точки и точки, содержащейся в узле.

Построение дерева производится рекурсивно, нам достаточно хранить ссылку на его корень.

public Node(List geoList, int depth) {

if (geoList.size() == 1) {

left = null;

right = null;

item = geoList.get(0);

return;

}

Geo[] list = new Geo[geoList.size()];

geoList.toArray(list);

if ((depth & 1) == 1) {

Arrays.sort(list, LONGITUDE_COMPARATOR);

} else {

Arrays.sort(list, LATITUDE_COMPARATOR);

}

int halfLength = geoList.size() / 2;

item = list[halfLength];

Geo[] leftSide = Arrays.copyOfRange(list, 0, halfLength);

Geo[] rightSide = Arrays.copyOfRange(list, halfLength + 1, list.length);

if (leftSide.length != 0) {

left = new Node(Arrays.asList(leftSide), depth + 1);

} else {

left = null;

}

if (rightSide.length != 0) {

right = new Node(Arrays.asList(rightSide), depth + 1);

} else {

right = null;

}

}

Листинг 3. Формирование K-D tree

Поиск точек в заданной области

Так как мы разбиваем множество не на произвольные области, а на прямоугольные фигуры, то не совсем удобно оперировать координатами исходной точки и радиусом области. Введём следующие обозначения: x1 = point.getLatitude() — radius, y1 = point.getLongitude() — radius, x2 = point.getLatitude() + radius, y2 = point.getLongitude() + radius. Этими переменными мы описываем координаты прямоугольника, в котором и будет осуществляться поиск интересующих нас точек. Важно отметить, что эти координаты являются центрами каждой из сторон искомого прямоугольника.

Однако перед нами встаёт проблема отсечения точек, расстояние до которых больше заданного радиуса, но при этом они входят в прямоугольник, используемый для поиска. Чтобы такие точки не попали в нужное подмножество, можно осуществлять явную проверку расстояния перед тем, как добавлять очередную точку. Исходя из глубины дерева на каждой итерации, мы проводим сравнение широты/долготы точки из текущего узла и границ прямоугольника, по которому мы проводим поиск (x1,x2/y1,y2). В зависимости от их соотношения мы запускаем поиск либо в правое поддерево, либо в левое поддерево, либо в оба.

private void searchGeoPoints(final Node temp, final int depth, List geoList) {

if (temp != null) {

Geo point = temp.getItem();

double pointX = point.getLatitude();

double pointY = point.getLongitude();

double x = x2 - radius;

double y = y2 - radius;

if (Math.sqrt((x - pointX) * (x - pointX) + (y - pointY) * (y - pointY)) <= radius) {

geoList.add(temp.getItem());

}

Node leftSon = temp.getLeft();

Node rightSon = temp.getRight();

if ((depth & 1) == 1) {

if (pointY > y2) {

searchGeoPoints(leftSon, depth + 1, geoList);

} else if (pointY < y1) {

searchGeoPoints(rightSon, depth + 1, geoList);

} else {

searchGeoPoints(leftSon, depth + 1, geoList);

searchGeoPoints(rightSon, depth + 1, geoList);

}

} else {

if (pointX > x2) {

searchGeoPoints(leftSon, depth + 1, geoList);

} else if (pointX < x1) {

searchGeoPoints(rightSon, depth + 1, geoList);

} else {

searchGeoPoints(leftSon, depth + 1, geoList);

searchGeoPoints(rightSon, depth + 1, geoList);

}

}

}

}

Листинг 4. Поиск точек

Заключение

Данный алгоритм позволяет уменьшить количество просматриваемых элементов при поиске. В лучшем случае оно составляет высоту K-D tree, в худшем — число всех узлов дерева. Алгоритм можно усовершенствовать, если хранить в узле массив значений. При этом уменьшится количество элементов дерева, а также значительно увеличится скорость поиска.

Литература:

1.K-мерное дерево // Википедия. URL: https://ru.wikipedia.org/wiki/K-мерное_дерево.