Bienvenue! Inscrivez-vous et rejoignez notre communauté :)
  • Login:

Bienvenue sur Forum SIG - Systèmes d'Information Géographique et Géomatique.

Bienvenue sur le forumSIG. S'il s'agit de votre première visite, assurez vous de faire une recherche préalable dans les FAQ SIG. Vous devez vous inscrire avant de pouvoir poster.

Affichage des résultats 1 à 12 sur 12
  1. #1

    Date d'inscription
    juin 2012
    Localisation
    Belgique
    Emploi
    Doctorant
    Organisme
    Université Catholique de Louvain
    Messages
    14

    Par défaut Non Résolu : [Spatialite] Requête spatiale en vue d'un graphe réseau

    Bonjour à tous,

    Je suis en train de débuter en spatialite, et j'aurais quelques questions qui ne devraient pas être très compliquées, c'est juste que je ne sais pas trop par où commencer

    Mon objectif est le suivant :

    Je travaille à partir d'une table ('network') qui a la structure suivante et qui contient 45 arcs :
    IDarc INTEGER PRIMARY KEY
    Origine INTEGER
    Destination INTEGER
    ORNAME TEXT
    DESTNAME TEXT
    Geometry

    Ainsi qu'à partir d'un shapefile virtuel ('Gaume_border')qui contient un seul objet de type LINESTRING.

    Je cherche à détecter quels sont les arcs qui intersectent la courbe présente dans mon shapefile (je ne veux pas garder dans mon réseau des droites qui passeraient par l'extérieur de ma frontière).

    J'ai essayé la requête suivante, mais en vain :
    Code:
    SELECT IDarc 
    FROM network, Gaume_border 
    WHERE intersects(Gaume_border.Geometry,network.Geometry)=1;
    Je parviens à obtenir le résultat que je veux, mais la recherche semble se limiter au premier enregistrement de ma table 'network'. Dès lors, je me demande si le fait que je teste une relation entre 1 courbe d'un côté et 45 de l'autre n'a pas comme résultat que spatialite se limite à une seule comparaison.

    Comment dois-je faire pour tester s'il existe une intersection entre l'objet de mon shapefile et chacun des 45 objets de ma table ?


    Voilà, je suis certain que c'est une bête question, mais c'est là que je coince.

    Merci de votre aide !

  2. #2
    Modérateur et rédacteur
    Date d'inscription
    octobre 2005
    Localisation
    Louvain-la-neuve
    Emploi
    Géologue
    Organisme
    Université Catholique de Louvain - Région Wallonne
    Messages
    2 133

    Par défaut

    Le SQL n'est pas adapté pour traiter les graphes car vous devez faire des requêtes récursives (sinon vous n'obtiendrez toujours qu'une valeur). C'est maintenant possible avec SQLite, mais c'est difficile pour un débutant. Vous devriez plutôt essayer le plugin pgRouting qui est fait pour ça http://underdark.wordpress.com/2011/...-to-pgrouting/
    "Caminante, no hay camino, el camino se hace al andar" A. Machado

  3. #3
    Compte Clos
    Date d'inscription
    septembre 2006
    Âge
    30
    Messages
    1 660

    Par défaut

    Gene, une question innocente à propos du réseau, à quoi correspond la géométrie de la table implémentant le réseau ? Si c'est bien la géométrie d'un tronçon, les intersections devraient fonctionner, non ? Bien sûr, il faudrait créer un objet de type zone tampon autour d'une ligne "origine / destination" et non une simple ligne droite.

    Pour pgRouting, je croyais que ce programme calculait un itinéraire à partir d'une sélection d'un graph, et donc qu'il fallait d'abord sélectionner la partie du graph concerné par l'itinéraire, et non transmettre la table entière du réseau à pgRouting. Me suis-je trompé ?

  4. #4

    Date d'inscription
    juin 2012
    Localisation
    Belgique
    Emploi
    Doctorant
    Organisme
    Université Catholique de Louvain
    Messages
    14

    Par défaut

    Merci pour la réponse.

    Je viens de jeter un oeil à PostgresSQL et pgrouting, et le moins que je puisse dire c'est que je n'y comprend pas grand-chose

    Avant de me lancer dans l'apprentissage de ces deux programmes, j'ai besoin de savoir s'ils sont capables, en principe, de répondre à mes besoins.

    Est-il possible, dans un graphe, d'obtenir le chemin le plus court entre un point donné et tous les autres noeuds du réseau ? Je parle bien de tous les noeuds de manière automatique, car je vais avoir besoin de traiter de très gros graphes (plusieurs milliers de noeuds et encore plus d'arcs ).

    Si ce n'est pas le cas, je compte explorer la piste de Pajek. Mais dans tous les cas, j'ai besoin d'éliminer tous les arcs qui ne sont pas à l'intérieur de ma frontière afin d'éliminer une partie des données inutiles. Je sais que QGIS le fait très bien, mais il a tendance à rendre son tablier face à de très gros ensembles de données.

    Est-ce que, a priori, pgrouting pourra satisfaire mes besoins ?

  5. #5
    Compte Clos
    Date d'inscription
    septembre 2006
    Âge
    30
    Messages
    1 660

    Par défaut

    Est-il possible, dans un graphe, d'obtenir le chemin le plus court entre un point donné et tous les autres noeuds du réseau ?
    C'est une des application des graphes, et de la théorie associée à ces graphes, et donc des applications utilisant ces graphes comme pgRouting.

    Donc ta ligne est bien la droite entre l'origine et la destination. Dans ce cas, normal que tu ne trouves pas tous tes tronçons...

  6. #6
    Modérateur et rédacteur
    Date d'inscription
    octobre 2005
    Localisation
    Louvain-la-neuve
    Emploi
    Géologue
    Organisme
    Université Catholique de Louvain - Région Wallonne
    Messages
    2 133

    Par défaut

    Je viens de jeter un oeil à PostgresSQL et pgrouting,
    Il ne s'agit pas de ça, mais de l'extension de QGIS disponible à https://github.com/anitagraser/pgRoutingLayer

    Avant de me lancer dans l'apprentissage de ces deux programmes, j'ai besoin de savoir s'ils sont capables, en principe, de répondre à mes besoins.
    Votre problème est un problème classique de la théorie des graphes, comme l'a souligné Jerôme C, et donc


    1) De ce fait depuis longtemps les chercheurs ont essayé de modéliser avec plus ou moins de succès ces algorithmes en SQL qui ne permettait pas des requêtes récursives (essayez d'implémenter une simple généalogie et ses traitements en pur SQL...) alors que les langages de programmation comme C, Java ou Python, oui. C'est paradoxalement facile à faire et je fais tous mes traitements sur les graphes en Python qui a de nombreux modules disponibles (voir
    Python : comment transformer un fichier shapefile (ou une feature class d'ESRI) en un réseau topologique (graphe))


    2) Les choses ont changé avec l'apparition de la récursivité dans le SQL d'Oracle, suivi par celui de PostgreSQL depuis la version 9 puis SQLite (plus limité) et SpatiaLite.
    Des extensions ont donc été créées pour enfin traiter efficacement les problèmes de graphes. Il s'agit par exemple de Pgrouting dans PostgreSQL/PostGIS

    3) Dans SpatiaLite, il est aussi possible de le faire, mais de manière plus limitée (voir http://www.gaia-gis.it/spatialite-3..../dijkstra.html ou avec un exemple pratique avec les données OpenStreetMap du Luxembourg:http://www.gaia-gis.it/gaia-sins/Using-Routing.pdf)

    4) D'un autre côté, il y a des SIGs qui permettent de faire directement ces traitements comme GRASS GIS (natif), GvSIG (natif) ou ArcGIS, avec l'extension payante Network Analysis.
    Et donc Anita Grasser a proposé de faire la même chose sur QGIS avec son extension Pgrouting Layer en Python.

    5) les "nouvelles" bases de données de la mouvance NO SQL ne se manipulent pas en SQL et permettent la récursivité. Elles peuvent être utilisées dans QGIS (voir Geocouch avec un exemple de routing natif à Le NoSQL dans le domaine géospatial : CouchDB et GeoCouch (Couchbase), shp2geocouh, importation de shapefiles et serveur cartographique ou MongDB à Le NoSQL dans le domaine géospatial : MongoDB avec JavaScript ou Python, ArcGIS et Quantum Gis)

    A vous de choisir, mais sans un bonne connaissance des principes, je vous souhaite bon courage.

    Pour Jêrome C.
    A ta 1e question, tout dépend de la manière dont sont implémentés les graphes, listes d'adjacence ou matrice d'adjacence mais c'est toujours une relation du genre nœud - nœud valuée. Le fait de lui associer une géométrie est relativement secondaire dans le traitement.
    géométrie
    Cliquez sur l'image pour la voir en taille réelle 

Nom : 		shapefile3ok.png 
Affichages :	8 
Taille :		35,6 Ko 
ID : 			5004
    graphe résultant: le plus court chemin entre les points (4.0,3.0) et (0.0, 0.0) sera calculé suivent le critère retenu (distance dans le cas des SIGs, mais cela pourrait être le temps de parcours, par exemple)
    Cliquez sur l'image pour la voir en taille réelle 

Nom : 		graphe.png 
Affichages :	8 
Taille :		131,1 Ko 
ID : 			5005
    A ta 2e question, non, il suffit de choisir un nœud de départ et un nœud d'arrivée, sans sélection préalable. Le fait de sélectionner une partie du graphe permet seulement d’accélérer le processus
    Dernière modification par gene ; 12/06/2012 à 21h16.
    "Caminante, no hay camino, el camino se hace al andar" A. Machado

  7. #7
    Compte Clos
    Date d'inscription
    septembre 2006
    Âge
    30
    Messages
    1 660

    Par défaut

    A ta 2e question, non, il suffit de choisir un nœud de départ et un nœud d'arrivée, sans sélection préalable. Le fait de sélectionner une partie du graphe permet seulement d’accélérer le processus
    J'avais posé ce genre de question car il me semblait que Dam!en souhaitait réaliser ce genre d'optimisation car sur des réseaux régionaux, ce genre d'optimisation me semble nécessaire.

    Idem pour la première question, associer la géométrie permettrait un pré-traitement plus simple, le traitement d'itinéraire n'ayant lui pas vraiment besoin de ces géométries.


    Je sous-estime toujours les débutants...

  8. #8
    Modérateur et rédacteur
    Date d'inscription
    octobre 2005
    Localisation
    Louvain-la-neuve
    Emploi
    Géologue
    Organisme
    Université Catholique de Louvain - Région Wallonne
    Messages
    2 133

    Par défaut

    il est possible, après sélection du point de départ, de choisir un buffer de traitement mais cela implique de connaître aussi la distance du point d'arrivée, ce qui n'est pas le cas dans le cas des calculs d'itinéraires comme Via Michelin, par exemple. C'est donc un tout autre algorithme qui est mis en œuvre comme la mémorisation des trajets les plus courants, par exemple.
    "Caminante, no hay camino, el camino se hace al andar" A. Machado

  9. #9
    Compte Clos
    Date d'inscription
    septembre 2006
    Âge
    30
    Messages
    1 660

    Par défaut

    J'avais vu aussi qu'il y avait des recherches récursives, le débroussaillage de l'itinéraire étant effectué sur un graphe simplifié, ayant beaucoup moins d'arcs que le graph complet, on affinait alors le trajet par niveaux d'échelle successifs.

  10. #10

    Date d'inscription
    juin 2012
    Localisation
    Belgique
    Emploi
    Doctorant
    Organisme
    Université Catholique de Louvain
    Messages
    14

    Par défaut

    Tout d'abord, je souhaiterais dire un tout grand merci à gene pour sa réponse incroyablement complète

    Je pense toutefois que mes explications ne sont pas très claires. C'est pourquoi j'ai réalisé un petit schéma qui reprend les deux dernières étapes nécessaires à mon analyse, qui sont justement celles sur lesquelles je bloque

    Cliquez sur l'image pour la voir en taille réelle 

Nom : 		network.png 
Affichages :	8 
Taille :		97,3 Ko 
ID : 			5006

    La première étape (identifier les arcs qui intersectent ma frontière) devrait normalement être possible en spatialite, c'est pour cela que je suis un peu étonné que ça semble si difficile.
    Je peux très bien le faire en mode graphique sous QGIS, mais comme ce programme a du mal avec les shapefiles contenant un grand nombre d'objets, j'aime autant éviter de devoir afficher le réseau.

    Pour la seconde étape, je ne préjuge d'aucune solution. Je suis ouvert à toute les propositions qui d'après vous fonctionneraient pour la réaliser. J'ai regardé à pgrouting layer hier, mais il semble qu'il faille identifier le point d'arrivée pour calculer l'itinéraire. Moi je voudrais faire une boucle sur chaque point d'arrivée possible pour récolter les résultats.

    Voilà, je vais continuer à chercher des idées de mon côté, mais j'espère que ce petit schéma va vous éclairer un peu

    Dam!en

  11. #11
    Modérateur et rédacteur
    Date d'inscription
    octobre 2005
    Localisation
    Louvain-la-neuve
    Emploi
    Géologue
    Organisme
    Université Catholique de Louvain - Région Wallonne
    Messages
    2 133

    Par défaut

    La première étape (identifier les arcs qui intersectent ma frontière) devrait normalement être possible en spatialite, c'est pour cela que je suis un peu étonné que ça semble si difficile.
    non, une fois que votre démarche a été précisée. Il faut utiliser la fonction ST_Intersection et non intersects. La démarche a alors été expliquée dans
    http://www.forumsig.org/showthread.php?t=29616, notamment le problème des géométries résultantes qu'il est important de saisir.

    ce qui donnerait dans votre cas
    SELECT ST_Multi(ST_Intersection( "network".'Geometry', "Gaume_border".'Geometry')) AS 'Geometry'
    FROM "network", "Gaume_border"
    WHERE ST_Intersects( "network".'Geometry', "Gaume_border".'Geometry')
    situation de départ (rapidement en QGIS avec des lignes (network) et un polygone (gaume_Border)
    Cliquez sur l'image pour la voir en taille réelle 

Nom : 		depart.png 
Affichages :	32 
Taille :		16,8 Ko 
ID : 			5008

    résultat du select et création d'une nouvelle couche
    Cliquez sur l'image pour la voir en taille réelle 

Nom : 		arrivee.png 
Affichages :	32 
Taille :		15,6 Ko 
ID : 			5009

    Dans le cas de données volumineuses, vous devriez passer par les requêtes avec des index spatiaux
    "Caminante, no hay camino, el camino se hace al andar" A. Machado

  12. #12

    Date d'inscription
    juin 2012
    Localisation
    Belgique
    Emploi
    Doctorant
    Organisme
    Université Catholique de Louvain
    Messages
    14

    Par défaut

    Désolé pour le silence radio

    Finalement, j'ai contourné (du moins je l'espère) le problème en me tournant vers Matlab avec lequel j'ai un peu plus l'habitude de travailler.

    Grâce à cela, je suis parvenu à créer une nouvelle table qui ne contient que les arcs qui n'intersectent jamais la frontière.

    Le seul problème qu'il me reste à surmonter maintenant est d'obtenir, pour chaque noeud autre que A, la distance par le plus court chemin entre ce noeud et A (Dijkstra ou A*).

    Là je suis en train de chercher du côté de Pajek, mais si vous avez des idées de programmes qui pourraient me calculer cela je suis preneur (Matlab ne voudra pas me laisser jouer avec une matrice 20.000*20.000)

 

 

Discussions similaires

  1. [SpatiaLite 3.x] Créer une vue spatiale avec un type de géométrie différent
    Par Bescu dans le forum Assistance et Programmation
    Réponses: 1
    Dernier message: 10/01/2013, 15h00
  2. [SpatiaLite] Jointure Spatiale avec l'index spatial RTree
    Par Bescu dans le forum Assistance et Programmation
    Réponses: 2
    Dernier message: 05/06/2012, 10h55
  3. [MapInfo 11.x] Requete attributaire et spatiale
    Par Elsane dans le forum Assistance Technique
    Réponses: 1
    Dernier message: 03/05/2012, 16h01
  4. [Spatialite-guiv1.4.0] Requête avec buffer
    Par Ted dans le forum Assistance et Programmation
    Réponses: 2
    Dernier message: 23/04/2012, 16h05
  5. [MapInfo 9.x] Requête spatiale
    Par emilk dans le forum Assistance Technique
    Réponses: 6
    Dernier message: 04/09/2009, 14h03

Les tags pour cette discussion

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •