What data structure should we use to create a map, such as a Google map?

Question

If you needed to visually indicate routes on a map (for example, Google maps), what data structure would you use to store it? How could you save the map?

Answer 1

Without thinking about it,

At a minimum level, a geographic map is a set of peaks with connected edges, peaks are the intersections and dead ends of the roads, and the edges are the roads that connect them.

Directions are just a series of links to the vertices that you need to go through to go from vertex A to vertex B.

So, to save a geographical map, you use a tree / map. To indicate directions, you use a list of links to vertices or an initial vertex and a list of edges to get to the final vertex.

By linking more information to each vertex / edge, you get everything you need to create a complete map. (IE, the weight of each edge to get the shortest path).

Answer 2

I don't know anything about this particular domain, but recently I heard about road XML , an open file format for describing road networks.

Perhaps the format itself may give you an idea of ​​how suh data can be represented.

Answer 3

For external file formats, consider the GPX ; This is a well-known XML format with extensible schema.