Visez GIS Master # 2 Recherchez les routes à proximité à grande vitesse avec R-tree

Dans le post précédent, j'ai extrait la route NW d'OSM

La dernière fois, j'ai essayé d'extraire la route NW d'OSM. Objectif GIS Master # 1 Extraire Road NW d'OpenStreetMap

Si vous regardez de plus près, cela peut inclure des éléments de type POI tels que des feux de signalisation, des bureaux de poste et des cafés. Et vous pouvez également prendre le Polygone sur le site. Oui bien sur. → Cependant, pas tous. Il existe différentes manières de construire le site, dont certaines ne comportent que des bâtiments et d'autres comprennent des parkings. Vous pouvez également créer Polygon. Non, c'est toujours cette qualité, donc je respecte vraiment les mappeurs. Je ne peux pas. Je suis toujours reconnaissant de votre aide.

Vous pouvez obtenir diverses choses. Mais je vais garder cette histoire pour la troisième fois.

Cette fois, je voudrais écrire comment utiliser la route extraite NW.

Ce que je veux faire, c'est trouver une route à proximité de ma position actuelle

Ce que je veux faire, c'est quelle route est la plus proche de cet endroit Il s'agit de tirer de la route extraite NW.

(Si l'erreur GPS n'est pas si grande) Puisqu'il est considéré que la route était la plus proche des informations de localisation obtenues de l'enregistreur GPS, Il ne vous reste plus qu'à tracer la route la plus proche. C'est une correspondance de carte très simple.

Comment faites-vous? (Problème)

Comme prémisse Il y a souvent plusieurs points médians (nœuds) sur la route qui est retirée de l'OSM. Il peut être entré comme un nœud au moment d'une courbe, ou il peut être entré comme une intersection avec une autre route. → Ce dernier est également intéressant. Laisse le.

Dans ce cas, laissons l'erreur GPS pour le moment. Mesurez la distance entre votre emplacement actuel et tous les nœuds, et la route avec le nœud le plus court est celle On peut dire que c'est une route à suivre.

Calculons maintenant la distance entre l'emplacement actuel et tous les nœuds! Juste au cas où, je voudrais mettre environ 3 candidats, alors organisons-les par ordre croissant de distance et obtenons les 3 identifiants de route du haut! Vaut-il mieux mettre tous les nœuds dans la base de données et rechercher par SQL? Disposer par ordre décroissant de distance euclidienne! !!

order by SQRT(POW((lon-Position cible lon),2) + POW((lat-Position cible lat),2)) desc

↑ Je ne l'ai pas essayé, mais je ne sais pas quand cela se terminera. Cela peut être étonnamment rapide, mais Je ne peux voir que le futur tardif. Il est rejeté.

Comment allez-vous (Solution)

C'est une solution "solution" en fuyant w Je pense qu'il y a plusieurs façons de le faire, mais pour moi, c'était relativement facile et rapide.

R-tree À partir de R tree wikipedia

Cette. Le but est d'indexer les données de position. Facile à utiliser avec python. → Cela semble être une version wrapper python de libspatialindex, Vous devez d'abord installer libspatialindex. Je me souviens que j'étais un peu accro à l'installation, mais ... Quand j'ai essayé d'importer avec python comme ci-dessous après l'installation, j'ai eu une erreur comme "libspatialindex-cannot be read". from rtree import index

Cela aurait dû fonctionner si j'avais mis le chemin contenant le fichier so de libspatialindex dans LD_LIBRARY_PATH dans la variable d'environnement. C'est tout pour moi.

Lorsque vous êtes prêt, placez les informations routières OSM dans l'arborescence R et créez un index. Puisque la route NW a été prise dans le post précédent, tous les points intermédiaires (lignes de position qui sont LINE STRING (position 1, position 2, ...)) sont retirés de là. → Comme la distance entre ces positions varie, je pense qu'il est normal d'effectuer une interpolation linéaire.

Je vais l'insérer.

#Exemple d'utilisation avec référence au tutoriel

#propriétés de l'arbre
p = rtree.index.Property()
p.dat_extension = 'data'
p.idx_extension = 'index'
file_idx = index.Index('rtree', properties = p)

#À partir de là, tous les points. Boucle ou tout va bien

#Il est pratique après avoir cherché si vous créez un objet et entrez des informations
hogehogeho = {}
hogehogeho["name"]="test" #Osm ici_Mettez-vous un identifiant ou quelque chose

#Si vous le mettez dans un rectangle, lon1,lat1,lon2,Bien que ce soit lat2, je vais mettre un point, donc je vais continuer à mettre la même valeur pour le moment
file_idx.insert(id=id, bounds=(lon1, lat1, lon1, lat1), obj=hogehogeho)

J'ai exécuté file_idx.insert (~) à tous les points pour créer un index. Je pense que ce sera plusieurs dizaines de Go rien qu'au Japon. Faites attention à la capacité du disque dur.

Une fois que vous arrivez ici, recherchez simplement.

#Vous pouvez rechercher comme ça
# - target_lon,target_lat est les informations de localisation que vous souhaitez rechercher
# -3 est le nombre de recherches
# -En gros, vous pouvez les prendre par ordre de proximité(Confirmation requise)
#→ Lors du calcul de la distance avec la terre à l'esprit, j'ai l'impression qu'il y avait des choses qui étaient légèrement déréglées.
#Mais je ne pense pas que ça va changer de 1m, alors je veux penser que ça va!
for pdat in file_idx.nearest((target_lon,target_lat), 3, objects=True):
    print(pdat.object['name'])
    #L'index de hit est pdat.Puisqu'il peut être pris avec bbox, ciblez_lon,target_lat et pdat.Lorsque vous calculez la distance de bbox, la distance réelle sort.

Application de contrôle de fonctionnement

J'ai donc essayé de vérifier le fonctionnement. J'ai fait un prototype d'outil qui dessine la route à proximité lorsque vous cliquez sur la carte. Vous pouvez voir que la route à proximité est dessinée à l'endroit où le marqueur de losange rouge est cliqué. Les couleurs sont rouge-> orange-> vert-> bleu clair-> bleu-> noir, et les routes proches de la position cliquée sont affichées. Les couronnes sont affichées dans l'ordre de 1 à 5. Eh bien, je ne pense pas qu'il y ait un 2, mais je pense que c'est sous le 3.

À propos, la vitesse de recherche est presque imperceptible. Je pense qu'il n'est pas exagéré de dire que c'est un moment. Cela ne devrait pas être le cas si vous avez calculé la distance avec tous les points.

Maintenant tu es prêt pour le combat

Il est désormais possible de rechercher des routes à proximité de ce point à grande vitesse. Après cela, il est nécessaire de faire correspondre en regardant l'angle de route acquis en fonction des données. → Hé, c'est le plus gênant ... Si la précision du GPS est bonne, la route la plus proche doit être décidée à la majorité. .. .. C'est difficile. Oui. J'ai aussi du mal.

Mais nous sommes prêts pour le combat! Je voudrais dire cela.

Parler plus tard?

Les routes OSM sont assez bizarres, et même après avoir traversé une intersection, l'identifiant reste inchangé et prend souvent la forme d'un L. Pour mon usage, je veux le diviser par une intersection en une seule route, donc J'ai mis en place un pré-processus pour diviser les données d'origine. J'ai également utilisé l'arbre R créé ci-dessus pour cela. → Combien tu aimes ... Recherchez tous les nœuds dans l'ordre par rtree et extrayez les nœuds avec une distance de 0. Une route avec un nœud avec une distance de 0 peut être considérée comme une intersection si c'est un point où plusieurs osm_ids uniques se chevauchent. Alors dans ce cas, coupez la route. Il est sculpté et donné quelque chose comme sub_id pour générer quelque chose d'unique.

De côté

J'ai utilisé la bibliothèque rtree dans un autre cas, mais la recherche de données proches et la recherche par plage sont extrêmement rapides. De plus, à l'époque, il s'agissait d'une recherche à distance de données en 8 dimensions. En passant, plusieurs dimensions peuvent être réalisées en spécifiant des propriétés. p.dimension = 3 La principale raison pour laquelle j'ai choisi cette bibliothèque est qu'elle prend en charge plusieurs dimensions. → Si la 2D est dite multidimensionnelle, elle est probablement entièrement multidimensionnelle. Je pense qu'il y avait peu de choses qui pouvaient être faites en 8 dimensions.

À l'origine, j'ai utilisé une base de données pour faire un calcul de distance en 8 dimensions (qui aurait dû être une distance euclidienne). J'ai fait une requête pour obtenir 5 éléments par ordre croissant de distance. Le nombre d'enregistrements est de centaines de milliers, mais une recherche prend moins de 10 secondes. Cependant, lorsque j'ai cherché sur R-tree, cela a pris moins de 3 secondes et j'ai pu obtenir le résultat en 1/3 du temps. génial!

Depuis, je me suis habitué à utiliser R-tree pour tout.