Filtrer des entités par distance géographique ?

[Fabien.]

Bonjour,

  Je cherche à récupérer parmis une liste de 100.000 entités mise à jour en temps réel celles qui sont situées à moins d'une certaine distance (ou temps de trajet) d'un point donné. Connaissez-vous un soft/lib/service qui fasse ca efficacement ?

Merci,

Fabien.

PS : voici la version non synthétique de la question :

  J'ai une liste d'entités localisées (pour l'instant c'est une liste de en gros 20.000 entités, localisées par un code postal ; a l'avenir ce sera peut etre des adresse / points GPS) Cette ligne est mise a jour en continu (un ajout ou une suppression toutes les 3-4 secondes aux heures de pointe, en moyenne)

  Ensuite je reçois des événements (un par seconde aux heures de pointe) avec une localisation (un code postal, plus tard un point gps) et une distanceMax (entre 1 et 250km).

  Je cherche à chaque fois que je reçois l'événement à récupérer la liste des entités de la première liste qui sont situées à moins de distanceMax de l'événement.

  J'ai une solution temporaire (mise en cache des 6329x6329, distances  soit une base de 1Go quand elle sera entièrement populée), mais elle n'est valable que parce que ma précision est réduite et que j'ai un petit nombre de code postaux.

[Nicolas Toublanc]

Bonjour Fabien,

Pour simplifier, considérons que tu as les coordonnées GPS, puisque tu les auras plus tard, et puisque tu peux convertir des adresses en points GPS.

Ensuite, tu parles de distance, puis de temps de trajet.

Qu'entends-tu donc par distance? Si c'est à vol d'oiseau, tu peux la calculer directement à partir des coordonnées GPS, dans n'importe quel langage ou même dans un tableur (http://stackoverflow.com/questions/365826/calculate-distance-between-2-gps-coordinates), voir directement dans ta base de données.

Si c'est de temps de trajet, as-tu besoin d'une approximation à la louche, où d'un temps réel. Si oui, est-ce en voiture, où aussi via des moyens de transport?

Enfin, pour mieux orienter la réponse, sur quelle genre de plateforme/techno/langages/stockage est-ce que tu travailles à ce jour?

--
Vous recevez ce message, car vous êtes abonné au groupe Google Groupes "Software Craftsmanship Toulouse".
Pour vous désabonner de ce groupe et ne plus recevoir d'e-mails le concernant, envoyez un e-mail à l'adresse software-craftsmanshi...@googlegroups.com.
Pour obtenir davantage d'options, consultez la page https://groups.google.com/d/optout.

--

Nicolas Toublanc

@toubiweb

[Sylvain Wallez]

Hello Fabien,

La première chose à faire est de convertir les codes postaux en coordonnées géographiques. Tu peux utiliser http://www.geonames.org/postal-codes/codes-postaux-france.html - c'est dispo sous forme de webservice, mais tu peux aussi télécharger les données pour faire la conversion sur ton serveur.

Une fois que tu as les coordonnées, la recherche par proximité est facile avec toute base de données avec un index géographique/2D comme Postgres, MongoDB, Solr, Elasticsearch, etc.

Sylvain

[Fabien.]

Qu'entends-tu donc par distance? Si c'est à vol d'oiseau, tu peux la calculer directement à partir des coordonnées GPS, dans n'importe quel langage ou même dans un tableur (http://stackoverflow.com/questions/365826/calculate-distance-between-2-gps-coordinates), voir directement dans ta base de données.
 

Si c'est de temps de trajet, as-tu besoin d'une approximation à la louche, où d'un temps réel. Si oui, est-ce en voiture, où aussi via des moyens de transport?

Dans un premier temps, une distance à vol d'oiseau est suffisante. Et la effectivement, la solution est super simple (mais curieusement avant de lire le message de Sylvain, je ne m'en etais pas rendu compte :-° )

Dans un second temps, effectivement si je sais estimer un temps de trajet réel en voiture / transports en commun / à vélo et à pied, ca serait un gros plus (Techniquement, c'est pour aider Pole Emploi a proposer les bonnes offres aux bons candidats)

 

Enfin, pour mieux orienter la réponse, sur quelle genre de plateforme/techno/langages/stockage est-ce que tu travailles à ce jour?

Pour l'instant c'est du java 8 sous tomcat, mais le moteur de calcul n'a pas de raison de tourner sous tomcat. S'il y a un intérêt à le faire en Go c'est bon pour moi. Pour les autres langages, je peux m'y (re)mettre.

Merci !

Fabien.

2016-05-14 8:34 GMT+02:00 Fabien. <eliott...@gmail.com>:

Bonjour,

  Je cherche à récupérer parmis une liste de 100.000 entités mise à jour en temps réel celles qui sont situées à moins d'une certaine distance (ou temps de trajet) d'un point donné. Connaissez-vous un soft/lib/service qui fasse ca efficacement ?

Merci,

Fabien.

PS : voici la version non synthétique de la question :

  J'ai une liste d'entités localisées (pour l'instant c'est une liste de en gros 20.000 entités, localisées par un code postal ; a l'avenir ce sera peut etre des adresse / points GPS) Cette ligne est mise a jour en continu (un ajout ou une suppression toutes les 3-4 secondes aux heures de pointe, en moyenne)

  Ensuite je reçois des événements (un par seconde aux heures de pointe) avec une localisation (un code postal, plus tard un point gps) et une distanceMax (entre 1 et 250km).

  Je cherche à chaque fois que je reçois l'événement à récupérer la liste des entités de la première liste qui sont situées à moins de distanceMax de l'événement.

  J'ai une solution temporaire (mise en cache des 6329x6329, distances  soit une base de 1Go quand elle sera entièrement populée), mais elle n'est valable que parce que ma précision est réduite et que j'ai un petit nombre de code postaux.

--
Vous recevez ce message, car vous êtes abonné au groupe Google Groupes "Software Craftsmanship Toulouse".

Pour vous désabonner de ce groupe et ne plus recevoir d'e-mails le concernant, envoyez un e-mail à l'adresse software-craftsmanship-toulouse+unsubscribe@googlegroups.com.

Pour obtenir davantage d'options, consultez la page https://groups.google.com/d/optout.

--

Nicolas Toublanc

@toubiweb

[Xavier Mouton-Dubosc]

Du Java ?
Soit efficace : en PostGreSQL , tu as une extension http://postgis.net/ qui t'offre le type de donnée GIS (point géographique), que tu peux indexer, faire une requete pour trouver la forme complexe qui s'y rapporte (découpage cantonal par exemple) ou même faire un tri en fonction de la distance
http://postgis.net/docs/manual-2.2/using_postgis_dbmanagement.html#examples_spatial_sql

C'était pour le plaisir du troll ;)

Perso, je pense que PostGIS est sûrement overkill, et pas forcément aussi performant que ce que tu avais en tête, mais je pense que c'est assez puissant pour te faciliter la vie

Portez-vous bien !

Oh, BTW, mon émission CPU sera enregistrée tous les jours pendant le THSF entre 11h et 13h. Vous êtes les bienvenus ;)

Pour vous désabonner de ce groupe et ne plus recevoir d'e-mails le concernant, envoyez un e-mail à l'adresse software-craftsmanshi...@googlegroups.com.

Pour obtenir davantage d'options, consultez la page https://groups.google.com/d/optout.

--

Nicolas Toublanc

@toubiweb

--

Vous recevez ce message, car vous êtes abonné au groupe Google Groupes "Software Craftsmanship Toulouse".

Pour vous désabonner de ce groupe et ne plus recevoir d'e-mails le concernant, envoyez un e-mail à l'adresse software-craftsmanshi...@googlegroups.com.

Pour obtenir davantage d'options, consultez la page https://groups.google.com/d/optout.

--

http://dascritch.net c'est pas qu'expérimental, c'est une vraie expérience

CPU , le programme (radio) (des gens) du numérique

[Gregory Salvan]

salut.

J'y connais rien mais si ça peut donner une piste...
En open source une des lib les plus utilisée c'est gdal il y a un binding java qui a servi notamment à faire GeoServer. Pour les données je vois souvent netcdf.

probablement overkill, mais standard.

[didier plaindoux]

Salut,

concernant le code postal tu peux rencontrer un problème simple. En effet,  la fonction "code postal -> coordonnée géographique” 

peut retourner un ensemble de communes et donc plusieurs coordonnées géographiques … et c’est pas cool /o\ (du coup la 

signature est fausse :))

Exemple : http://www.geonames.org/postalcode-search.html?q=31430&country=FR

Pour bien faire il te faudrait soit le nom de la commune soit le code insee si tu ne veux pas être dans l’incertitude … ou bien calculer

le barycentre ou un truc du genre :-)

My two cents

Didier