Кд дерево с прямоугольниками
У меня есть моя реализация дерева kd, работающего с заданными точками. Например, я могу добавить точки к дереву, а затем найти ближайшую точку с заданными координатами x, y, и это здорово.
Я хочу расширить это для работы с прямоугольниками, например, пользователь дает координаты x и a y, ширину и высоту, затем я хочу иметь возможность выполнить запрос диапазона и поиск ближайших соседей по этой структуре. Как мне расширить текущее дерево, с которым мне приходилось работать с прямоугольными данными?
2 ответа
Я знаю большое расширение деревьев kd для обработки прямоугольников. Он называется алгоритмом сортировки коробки и может быть найден здесь. Идея почти такая же, как у деревьев kd. В документе также есть реализация на Pascal, но перевод на Java должен быть простым.
Kd-деревья отлично подходят для низкоразмерных точечных данных. Для всего, что состоит из нескольких точек (линий, прямоугольников и т. Д.), Я бы предложил использовать R-дерево.