#1 Mon 25 June 2007 17:48
- Yohm
- Juste Inscrit !
- Date d'inscription: 24 Jun 2007
- Messages: 2
Techniques et méthodes de calculs dans les SIG
Bonjour,
Je suis étudiant, et suis actuellement des cours de géo-localisation.
Mon sujet est le suivant : 'Gestion de la topologie et algorithme implémenté'.
Ce sujet est vaste, et nous aimerions avoir confirmation de certains choses, et si possible de nouvelles informations.
Il s'agit "de topologie dans le cadre de la cartographie. Il s'agit de pouvoir effectuer des calculs à partir des différents modèles." (raster, vectoriel)
Nous pensons qu'il s'agit donc d'exposer les algorithmes derrière le calcul de longueurs, surfaces, distances entre points, points polylignes, points polygones, ...
Nous avons donc essayé de décomposer le problème selon les objets élémentaires : points, lignes/polylignes, polygônes
En termes de calculs :
* Pour les longueurs :
Est-ce que c'est possible de le faire en raster ? Par exemple la longueur d'un fleuve, d'une route, ...
En vectoriel, on calcule juste la distance ou somme des distances des segments élémentaires de la droite ou l'arc (pas d'arc à base de courbes genre bézier ou splines dans les SIG, juste des polylignes=ensemble de segments ?)
* Pour les surfaces :
En raster, cela semble possible de le faire.
Si j'ai bien compris, il suffirait de faire la somme des pixels de la surface, en connaissant la "superficie" d'un pixel (résolution de la rasterisation).
http://www.star.ait.ac.th/~souris/publi … nalyse.pdf (p19)
Apparemment, il existe des algos qui permettent de minimiser l'erreur d'incertitude quand à l'appartenance des pixels de contour à la surface ou non.
La seule référence qu'on ait trouvé à ce sujet pour l'instant est la suivante :
http://www.fao.org/docrep/W7320B/w7320b28.htm
D'autres propositions ?
En vectoriel, nous avons bien trouvé des infos :
http://marques.patrice.free.fr/Projets/ … olret.html
http://www.davidchandler.com/AreaOfAGeneralPolygon.pdf
http://peyo.lost-oasis.net/geomatique.php
http://www.star.ait.ac.th/~souris/publi … nalyse.pdf (p19)
Mais est-ce la seule technique utilisée dans les SIG ?
En connaitriez-vous le nom ?
Nous avons entendu parler d'une méthode à base de segments decrivant le contour à partir du centroïde, mais pas moyen de retrouver le nom. Cela vous dirait-il quelque chose ?
Il y a apparemment aussi une histoire de calcul de plus court chemin.
Pour cela, nous avons entendu parler des interpolations genre Floyd, Djikstra (Mappy) et graphes en général.
http://www.nimbustier.net/publications/ … index.html
http://www.forumsig.org/showthread.php?t=1394
http://www.apprendre-en-ligne.net/graphes/
Une idée de ceux qui sont les plus utilisés dans les SIG ?
Nous avons vaguement entendu parler de Delaunay, Voronoi et de "tampons", de jointures, unions, intersections, mais nous avons du mal à nous rendre compte de leur utilisation concrète dans les SIG pour les calculs (à part peut-être les tampons : dénombrement d'objets dans une zone). Et au niveau algorithmique, savez-vous ce que cela donne globalement ? Est-ce utilisable à la fois pour des raster et du vectoriel ?
Merci d'avoir pris la peine de lire ce message.
Guillaume
Hors ligne
#2 Mon 25 June 2007 18:07
- Cartosig
- Participant assidu
- Date d'inscription: 16 Oct 2006
- Messages: 222
Re: Techniques et méthodes de calculs dans les SIG
* Pour les longueurs :
Est-ce que c'est possible de le faire en raster ? Par exemple la longueur d'un fleuve, d'une route, ...
En théorie oui ça doit être possible, maintenant je n'ai pas connaissance que personne ne l'ai jamais tenté. Il faudrait un algo qui progresse dans le raster en cherchant des valeurs très proches... Ensuite il faut trouver la distance, si on la rapporte en nombre de pixels il y aura une marge d'erreur importante, donc il faut trouver un système de pondération. En bref l'intérêt d'une telle méthode est plus que discutable.
Hors ligne
#3 Mon 25 June 2007 18:34
- ChristopheV
- Membre
- Lieu: Ajaccio
- Date d'inscription: 7 Sep 2005
- Messages: 3175
- Site web
Re: Techniques et méthodes de calculs dans les SIG
Bonjour,
La topologie dans un SIG peut-être vue sous l'angle Arc, Face, Noeud. (pour l'aspect vectoriel).
Une face est composée d'arcs (avec le noeud final de l'arc final qui le noeud initial du premier arc)
Un arc est composé de deux noeuds (initial et final) et éventuellement n sommets.
Un noeud est le point d'intersection d'au moins trois arcs.
En utilisant des fonctions de type EstaGaucheDe, Intersection il est facile d'implanter des algorithmes pour déterminer par exemple quel est le nombre de "polygone" traversés par une "polyligne". De plus cette méthode de stockage permet d'accélérer l'affichage et de minimiser la taille des données.
Concernant les calculs sur un raster, ceci correspond aux études de vectorisation automatique en cours actuellement.
Christophe
Christophe
L'avantage d'être une île c'est d'être une terre topologiquement close
Hors ligne
#4 Mon 25 June 2007 19:06
- Yohm
- Juste Inscrit !
- Date d'inscription: 24 Jun 2007
- Messages: 2
Re: Techniques et méthodes de calculs dans les SIG
OK pour les rasters, ça confirme donc bien le peu que nous avions lu sur le sujet.
En ce qui concerne l'explication sur l'intersection, je ne comprend pas vraiment ce que vous voulez dire. Vous faites des opérations ensemblistes sur une face et une ligne !? S'agit-il de la fameuse méthode des "buffers" ?
Comment dans ce cas dénombrer le nombre de polygones, y-a-t-il un algorithme particulier ? Est-ce un ensemble d'opérations 'SQL bas niveau' (jointures, ...) sur les coordonnées dans les tables de points/table des arcs ?
Hors ligne
#5 Tue 26 June 2007 10:35
- ChristopheV
- Membre
- Lieu: Ajaccio
- Date d'inscription: 7 Sep 2005
- Messages: 3175
- Site web
Re: Techniques et méthodes de calculs dans les SIG
Bonjour,
Je ne suis pas un spécialiste, je ne sais donc pas si j'emploie la méthode nommé "buffer" ou autre. Je vous livre mon sentiment au regard des solutions que j'ai adoptées ou étudiées pour ma propre application.
Pour l'instant l'application gére les éléments vectoriels de base (pour les rasters un rectangle):
point (vertex)
Ligne
Polyligne
Polygone (polyligne fermée)
Le rectangle (windows)
Ces objets possèdent des méthodes permettant des opérations sur eux même et entre eux. Ce à l'aide de la géomètrie analytique.
L'élément de base en matière de surface et d'affichage est le rectangle:
Intersection de deux rectangles = un rectangle
Union idem
L'élément de base en "linéaire" : le point
Function
Point est dans Rectangle
Mis à part le point chaque objet est contenu dans un rectangle encadrant. Donc tous les algorithmes cherchant à calculer le résultat de l'intersection de deux objets ou savoir si un objet est contenu dans un autre pourront être optimisés.
Exemple : Point est dans Polygone ?
Si P(x,y) est dans Polygone.RectangleEncadrant Alors
Cherche une solution
Si Non
Solution = Nothing
Fin Si
Cherche une Solution :
Calcul l'intersection de Y=y et de polygone :
Obtient une liste ordonnée des segments(orienté) de polyligne ayant une intersection avec y de P.
Observe la parité de "P est à gauche de segment", les segment étant parcouru selon les X croissant.
Un exemple VB de EstaGaucheDe:
C'est une fonction de l'objet Ligne.
Code:
Public Function VertexEstAGauche(v As Vertex) As Boolean Dim m1 As Double Dim k1 As Double Dim Y As Double If Not mVerticale Then m1 = (mb.Y - ma.Y) / (mb.X - ma.X) k1 = mb.Y - m1 * mb.X Y = v.Y - m1 * v.X - k1 Else If ma.Y <= mb.Y Then Y = v.X - ma.X Else Y = -v.X + ma.X End If If Y < 0 Then VertexEstAGauche = True Else VertexEstAGauche = False End If End If End Function
Lorsque l'on passe à une structuration topologique type arc face noeud l'intérêt est de structurer ces données dans une BD.
Par exemple:
Un arc contiendra 2 champs contenant respectivement le numéro de la parcelle à gauche, le numéro de la parcelle à droite.
Donc l'algo pour calculer les parcelles traversées par un polyligne utilisera la combinaison de la géomètrie et des relations entre objets dans la BD.
Polyligne PL,
Code:
Dans quel polygone est PL.sommet(0) ? On effectue une requete: Quelles Polylignes ont un rectangle encadrant contenant PL.sommet(0) On utilise ensuite l'algo géomètrique sur le résultat (réduit) de la requête. Tant que PL.sommet(i&) => PL.sommet.count Tant que PL.sommet(i&) appartient au polygone résultat i&=i&+1 Boucle Calcul quel arc intersecte PL.sommet(i&-1), PL.sommet(i&) En fonction de l'arc obtient le polygone voisin (si PL.sommet(i&-1) est à droite le polygone voisin est à gauche) par une requête Boucle avec polygone voisin
A+
Christophe
Christophe
L'avantage d'être une île c'est d'être une terre topologiquement close
Hors ligne
#6 Tue 26 June 2007 10:48
- Cartosig
- Participant assidu
- Date d'inscription: 16 Oct 2006
- Messages: 222
Re: Techniques et méthodes de calculs dans les SIG
L'élément de base en matière de surface et d'affichage est le rectangle:
Intersection de deux rectangles = un rectangle
...
Mis à part le point chaque objet est contenu dans un rectangle encadrant. Donc tous les algorithmes cherchant à calculer le résultat de l'intersection de deux objets ou savoir si un objet est contenu dans un autre pourront être optimisés.
C'est ce que l'on appelle la méthode d'indexation spatiale par R-Tree (à la différence des Quad-Tree), qui est utilisée par Oracle Spatial par exemple.
En effet ce type d'indexation permet une accélération importante des requêtes spatiales.
Dernière modification par Cartosig (Tue 26 June 2007 10:48)
Hors ligne