Какую структуру данных мы должны использовать для создания карты, такой как карта Google?

Question

Если бы вам пришлось визуально указывать направления движения на карте (например, карты Google), какую структуру данных вы бы использовали для ее хранения?Как бы вы сохранили саму карту?

Answer 1

Не вдаваясь в подробности;

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

Направления - это просто набор ссылок на вершины, которые необходимо пройти, чтобы добраться от вершины A к вершине B.

Таким образом, чтобы сохранить географическую карту, вы используете дерево / карту.Чтобы указать направления, вы используете список ссылок на вершины или начальную вершину и список ребер, чтобы добраться до конечной вершины.

Связывание дополнительной информации с каждой вершиной / ребром дает вам все, что вам нужно для созданияполная карта.(IE, вес каждого ребра, чтобы получить кратчайший путь).

Answer 2

Что касается внешних форматов файлов, рассмотрим GPX ;это хорошо известный формат на основе XML с расширяемой схемой.

Answer 3

Я ничего не знаю об этом конкретном домене, но недавно я слышал о road XML , открытом формате файлов для описания дорожных сетей.

Возможно, сам формат может дать вампонимание того, как такие данные могут быть представлены.