Structure de données idéale pour stocker des données cartographiques?

On m'a posé cette question lors d'un test d'entrevue. J'ai bien réussi le test, mais je n'en savais pas assez pour répondre à cette question. Je suis curieux de savoir quelles structures de données je peux utiliser pour interroger rapidement les données.

Fondamentalement, l'idée est qu'il y aurait des sections de route (lignes, constituées de points) stockées dans une sorte de structure de données. Il devrait être rapide de rechercher quelles sections de route (ou points) se trouvent à une certaine distance d'un point (rayon).

La manière typique de stocker des données géographiques consiste à utiliser une structure de données spatiales telle qu'un arbre R (ou une variante, telle que l'arbre R +, l'arbre R *, etc.). C'est ainsi que les types de données géographiques sont normalement implémentés dans un SIG-capable RDBMS. (Je sais que SQL Server 2008 et PostGIS de Microsoft utilisent des arborescences R pour les types géographiques.) Ils répondent à toutes les exigences de base que vous avez décrites et prennent en charge de manière triviale l'intersection, l'emplacement, la distance et d'autres types de requêtes.

Selon le type de données, vous pouvez également trouver des éléments tels que les arbres kD, les quadruples, les octrois, les hiérarchies de volume de délimitation (y compris les cadres de délimitation alignés sur les axes), etc., couramment utilisés. C'est en fait beaucoup plus courant dans les jeux 3D, car la taille et la forme d'un objet sont plus pertinentes pour les requêtes d'intersection. Ils sont moins souvent utilisés pour les SIG que les arbres R.

Différents types d'opérations sur les données cartographiques nécessiteront différents formats de stockage pour des résultats optimaux. Considérez, par exemple, les trois tâches suivantes:

1. Étant donné un point, trouvez la route la plus proche de ce point
2. Étant donné une zone géographique d'une certaine taille, trouvez toutes les routes qui se trouvent dans cette zone.
3. Étant donné deux routes, trouvez l'itinéraire le plus court entre elles.

Les différences dans les exigences sont suffisamment importantes pour que, à moins que l’on n’ait besoin d’adapter les modifications «en direct» à la carte, il sera probablement préférable de stocker trois copies distinctes des données - chacune optimisée pour l’une des tâches ci-dessus - que d’essayer pour trouver un format qui peut bien gérer les trois tâches.