R Древовидный 50 000-футовый обзор?
Я работаю над школьным проектом, который включает взятие точки lat/long и нахождение лучших пяти самых близких точек в известном списке мест. Список должен быть сохранен в памяти с протестом, что мы должны выбрать "appropriate data structure" - то есть, мы не можем просто сохранить все места в массиве и сравнить расстояния один за другим линейным способом. Учитель предложил группировать данные места штатом США для предотвращения вычисления расстояния для мест, которые являются, очевидно, слишком далеко. Я думаю, что могу добиться большего успеха.
От моего исследования онлайн это походит на R-дерево, или один из его вариантов мог бы быть аккуратным решением. К сожалению, то предложение - насколько я добрался с пониманием фактической техники, поскольку литература является просто слишком плотной для моей неакадемической головы.
Кто-то может дать мне действительно высокий обзор того, что процесс для заполнения R-дерева с lat/long данными и затем пересечения дерева для нахождения тех 5 ближайших соседей данной точки?
Дополнительно проект находится в C, и я не должен изобретать велосипед на этом, поэтому если бы Вы использовали существующую реализацию открытого исходного кода C Дерева R, я интересовался бы Вашими событиями.
ОБНОВЛЕНИЕ: Это сообщение в блоге описывает простой алгоритм поиска для разделенного пространства на местах (как дерево квадрантов PR). Надежда, которая помогает будущему читателю.
2 ответа
Рассматривали ли вы альтернативные структуры данных? Я считаю, что вместо R-дерева более эффективным для ваших нужд было бы точечное квадтри. Spatial Index Demos предоставляет несколько демонстраций для списка возможных структур данных, включая R-дерево и Point Quadtree. Надеюсь, это даст вам представление.
Квадратные деревья
Квадратное дерево занимает квадрат пространства и делит его на четыре дочерних элемента с половинными размерами по осям X и Y.
+---+---+
| | | Each square is a child
| | | of the parent; when you
+---+---+ get to leaves a node has
| | | a single point or a list
| | | of points.
+---+---+
Эта структура данных является рекурсивной, и вы ищите точки, проверяя, какой дочерний элемент содержит точку, пока не дойдете до листа. Лист имеет либо один элемент (точка с координатами X, Y), либо список элементов, в зависимости от реализации. Если вы заполняете узел, вы разделяете его на 4 и распределяете дочерние элементы. По сути, структура данных является обобщением двоичного дерева, поэтому она не обязательно сбалансирована.
Балансировка четырехугольного дерева может не понадобиться для ваших целей и оставлена в качестве упражнения для читателя - попробуйте поискать в Интернете «сбалансированное четырехугольное дерево».
Обратите внимание, что эта структура данных не может индексировать элементы, которые могут перекрываться, но если вы сохраняете только очки, это не будет проблемой.
Нахождение ближайших соседей в дереве квадратов
Внезапно я предлагаю быстрый и грязный алгоритм для поиска n ближайших соседей к вашей точке. Это не обязательно оптимально эффективно, но реализовать его будет довольно просто. Если у кого-то есть ссылка на лучшую, не стесняйтесь размещать ее в комментарии или ответе.
Найдите узел дерева квадратов, содержащий вашу точку, сохраняя список его родителей.
Поместите все точки в узле в приоритетную очередь на основе их расстояния от вашей базовой точки (т. Е. Длины гипотенузы {{1}) } по теореме Пифагора).В зависимости от реализации может быть один или несколько на узел. Для простой реализации структуры данных очереди с приоритетами найдите «двоичную кучу».
Если какая-либо из n точек находится дальше, чем края ограничивающего прямоугольника, добавьте содержимое его соседей. т.е. если ваша базовая точка находится близко к краю ограничивающего прямоугольника, возможно, что соседние узлы дерева могут содержать точки, которые находятся ближе, чем точки, найденные в вашем ограничивающем прямоугольнике. Для этого вам нужно будет создать резервную копию дерева, поэтому вам нужно отслеживать свои родительские узлы.
Когда все 'n' ближайших точек ближе, чем края вашего ограничивающего прямоугольника, вы знаете, что не может быть соседей, которых вы пропустили. Следовательно, «n» ближайших точек в этом поле должны быть вашими «n» ближайшими соседями.