R Дерево 50000 футов обзор?

Question

Я работаю над школьным проектом, который включает в себя определение широты / долготы и нахождение пяти самых близких точек в известном списке мест.Список должен храниться в памяти с оговоркой, что мы должны выбрать «подходящую структуру данных», то есть мы не можем просто хранить все места в массиве и сравнивать расстояния один за другим линейным образом.Учитель предложил сгруппировать данные о местах по штатам США, чтобы избежать расчета расстояния для мест, которые явно находятся слишком далеко.Я думаю, что могу добиться большего успеха.

Из моих исследований в Интернете кажется, что R-Tree или один из его вариантов может быть изящным решением.К сожалению, это предложение настолько далеко, насколько я понял из-за реальной техники, так как литература слишком плотна для моей неакадемической головы.

• Может кто-нибудь дать мне действительноВысокий обзор того, что представляет собой процесс для заполнения R-дерева с данными широты / долготы и последующего обхода дерева, чтобы найти 5 ближайших соседей данной точки?

• Дополнительно проектнаходится в C, и мне не нужно заново изобретать колесо, поэтому, если вы использовали существующую реализацию дерева R с открытым исходным кодом на C, я бы заинтересовался вашим опытом.

ОБНОВЛЕНИЕ: В этом сообщении в блоге описан простой алгоритм поиска для разделенного на области пространства (например, PR-дерево).Надеюсь, что это поможет будущему читателю.

Answer 1

Рассматривали ли вы альтернативные структуры данных? Я полагаю, что вместо R-дерева точечный Quadtree будет более эффективным для ваших нужд. Пространственные демонстрационные индексы предоставляет некоторые демонстрационные материалы для списка возможных структур данных, включая R-дерево и Point Quadtree. Надеюсь, что это дает представление.

Answer 2

Четырехъядерные деревья

Четырехъядерное дерево занимает квадрат пространства и делит его на четыре дочерних элемента с половиной размеров по осям 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' ближайших соседей к вашей точке.Это не обязательно эффективно с точки зрения оптимизации, но это будет довольно просто реализовать.Если у кого-то есть ссылка на лучшую ссылку, отправьте ее в комментарии или ответе.

• Найдите узел дерева четырехугольников, содержащий вашу точку, и сохраните список его родителей.

• Поместите все точки в узле в приоритетную очередь на основе их расстояния от вашей базовой точки (т.е. по длине гипотенузы согласно теореме Пифагора).В зависимости от реализации может быть один или несколько на узел.Для простой реализации структуры данных очереди с приоритетами ищите «двоичную кучу».

• Если какая-либо из точек 'n' находится дальше, чем края ограничительной рамки, добавьтесодержимое своих соседей.т.е. если ваша базовая точка находится близко к краю ограничивающей рамки, возможно, что соседние узлы дерева могут содержать точки, которые находятся ближе, чем точки, найденные в пределах вашей ограничительной рамки.Для этого вам необходимо создать резервную копию дерева, поэтому вам необходимо отслеживать родительские узлы.

• Когда все n ближайших точек находятся ближе, чемКрая вашей ограничительной рамки, вы знаете, что не может быть соседей, которых вы пропустили.Следовательно, 'n' ближайшие точки в этом поле должны быть вашими 'n' ближайшими соседями.