Утилиты Quadtree на картах Android

Я разрабатываю приложение для Android с картами Google v2, которые рисуют многоугольники на картах Google. Но теперь мне нужно определить щелчок по определенному полигону и открыть всплывающее окно.

Я нашел эту полезную библиотеку на github

В этой библиотеке реализован метод containsLocation. Этот метод получает LatLng (от щелчка по карте) и список (многоугольник). Это нормально, но если у меня на карте 1 миллион полигонов, я не могу перебрать все и проверить, принадлежит ли определенный LatLng определенному полигону. Я помню, что я могу использовать quadtree для повышения производительности, и эта библиотека также реализует quadtree, но использует точку. Как лучше всего это сделать? Могу ли я переопределить это дерево квадрантов для дерева квадрантов LatLng? Или в каждом щелчке я должен преобразовать этот щелчок в точку и выполнить поиск по квадродереву точек?

С Уважением


google-maps android polygon quadtree
person mistic    schedule 29.01.2014    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Я думаю, вам нужно реализовать дерево квадрантов, в котором хранятся полигоны, а затем запросить дерево, чтобы увидеть, какой полигон (если он есть) содержит LatLng. Если вы будете искать вокруг, я уверен, что вы сможете найти достойную реализацию.

person Jonno_FTW    schedule 29.01.2014
comment
Я ищу, но не могу найти ни одного дерева квадрантов, реализованного для хранения полигонов с помощью LatLng. Лучшее, что я смог найти, это ссылкадерево квадрантов, хранящее элементы с баллами[/link] . Но у меня есть несколько вопросов. Каковы границы этого дерева квадрантов с LatLng? Если я храню многоугольники (с несколькими точками LatLng), какой LatLng я использую для хранения многоугольника? - person mistic; 29.01.2014
comment
LatLng совпадает с x,y. Прочтите эту статью о хранении полигонов в деревьях квадрантов: infolab.usc.edu/csci585 /Spring2008/den_ar/p182-samet.pdf . Вы можете использовать дерево квадрантов PM, чтобы найти область, в которой находится точка (это то, что вы хотите сделать): cs.umd.edu/users/meesh/420/Notes/KingaNotes/ Я уверен, что вы можете найти больше ресурсов в Интернете, если посмотрите PM quadtree. - person Jonno_FTW; 30.01.2014

arrow_upward
3
arrow_downward

вы не можете использовать Point-Quadtree, вам нужно Object-Quadtree для ваших полигонов. Квадрат объекта использует ограничивающую рамку полигона или любого объекта для добавления в дерево.

вам не нужно учитывать latLong, используйте x, y с x = долготой, а y = широтой.

Рекомендуем прочитать Ханан Саммет: Основы многомерных структур данных.

person AlexWien    schedule 30.01.2014
comment
С помощью дерева квадрантов могу ли я хранить в дереве квадрантов полилинии, полигоны и точки (нарисованные на карте маленьким кружком)? У меня будут все эти формы на карте, и когда я щелкаю по карте, мне нужно указать точку щелчка LatLng для дерева квадрантов, и она должна дать мне список точек, полилиний или полигонов, которые могут содержать это LatLng. Итак, после этого я попробую каждый элемент в этом возвращаемом списке и проверю, содержится ли LatLng в элементе, и таким образом идентифицирую щелчок по определенной фигуре. Я правильно думаю? Это лучший способ сделать это? Могу ли я найти любую библиотеку реализации с открытым исходным кодом, которая может это сделать? - person mistic; 30.01.2014