Структура данных для googlemap как приложение?

Question

Я делаю мапрутинг-приложение. Несколько человек предложили мне, чтобы я сделал структуру данных, где я разделил карту в сетке. Теоретически это звучит очень хорошо, но я не уверен, что из-за плохой производительности, которую я получаю, когда внедряю ее.

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

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

Есть ли какие-либо предположения относительно того, какую структуру данных мне следует использовать и / или что я могу делать неправильно?

Answer 1

Более оптимальным, чем использование сетки в качестве структуры пространственных данных, может быть квадродерево, поскольку оно логарифмически разбивает карту. И из изучения источника я могу предположить, что Google использует (ту или иную) похожую структуру данных.

Что касается получения указаний, вам может потребоваться поиск иерархических путей, чтобы сначала приблизить направление и ускорить процесс; общие алгоритмы поиска пути имеют тенденцию быть довольно медленными на этом уровне сложности.

Answer 2

Google не рисует каждую дорогу каждый раз, когда обновляется экран. Они использовали предварительно нарисованные тайлы карты. Они могут перерисовать их по мере необходимости. например когда есть обновление карты. Они даже используют прозрачные наложения, стопки плиток для добавления и удаления слоев деталей.

Очень умно, но очень просто.

Возможно, вы захотите взглянуть на библиотеку javascript openlayers. Бесплатно и может делать практически все, что вам нужно сделать с картой.

Maptraction JS также доступен - он не такой полный, как OpenLayers

Answer 3

См. Этот вопрос для связанной информации:

Какие алгоритмы вычисляют направления от точки A к точке B на карте?

Кто-то, кто пишет этот вид программного обеспечения для жизни, ответил на него.

Также для рендеринга см .:

Как лучше всего читать, представлять и отображать данные карты?

Я не совсем уверен, пытаетесь ли вы быстро выполнить маршрутизацию или рендеринг!

Answer 4

Если вы хотите, чтобы все шло быстро, вам лучше организовать свои дороги на основные и второстепенные дороги.

Используйте список второстепенных дорог, чтобы найти маршрут до ближайшей главной дороги. Используйте основные дороги, чтобы добраться до места назначения. Затем вернитесь на второстепенные дороги, чтобы завершить маршрут.

Без такого раскола существует множество дорог для поиска, большинство из которых довольно медленные.