Trouver les cellules voisines dans une grille

Salut à toutes et à tous!

Un marcheur aléatoire se déplace dans une grille géospatialisée. Aux débuts du projet on s'intéressait à définir les probabilités de saut d'une case à l'autre avec une version discrétisée d'une loi de proba continue: le marcheur pouvait sauter plusieurs cases, la probabilité associée au passage à ce saut étant fonction de la distance géographique entre les deux cases (en fait entre les deux centroides des deux cases). Puisqu'on avait régulièrement besoin de calculer des distances entre deux coordonnées, j'ai beaucoup utilisé une classe LongitudeLattiude à travers le projet, mais suivant les bons conseils d'une forumeuse bien connue de ces contrées, j'ai pris soin de mettre des templates sur tout ce qui pouvait concerner le référentiel spatial.

Les besoins changeant (didju que j'aime pouvoir enfin dire cette phrase...) , il a fallu passer à une version où l'espace d'arrivée du marcheur aléatoire est restreint à 5 cases: case de départ + les 4 cases nord/sud/est/ouest.
Un peu naïvement j'ai voulu "juste" ajouter la résolution spatiale du quadrillage en longitude/latitude pour pouvoir à partir des cordonnées d'une case X, trouver les coordonnées des 4 voisines. Par "coordonnées de la case", j'entends "coordonnées du centroide de la case".

Les ordinateurs ne calculant décidément pas juste, il m'a fallu reprojeter les points obtenus après addition de la latitude (longitude) avec une formule un peu relou. Le tout étant décidément très peu efficace, le temps de simulation a (évidemment ? :aie: ) explosé.

Comment vous y prendriez-vous ?

Est-ce que le moment est arrivé de repasser à un référencement type matrice (numéro de ligne / numéro de colonne) plutôt que de m'embêter à recalculer des coordonnées à tout va ?

En vous remerciant d'avance!

Je ne comprends pas.
Si tu as des cases, et donc un quadrillage, depuis ta case (X,Y) la case suivante c'est la case c'est (X+1, Y), la précédente (X-1, Y). Au-dessus on est à Y-1 et en-dessous à Y+1.
La seule subtilité est si tu es déjà arrivé au bord, alors il faut éviter de prendre une case qui n'existe pas.

Si tu as déjà des coordonnées, peut-être pouvoir tomber dans le cercle de centre la case trouvée et travailler en distances et non en cases ?

Citation:

---

Les ordinateurs ne calculant décidément pas juste

---

? C'est même la seule chose qu'ils savent faire :weird:

Merci de ta reponse :)

Citation:

---

Envoyé par Bousk

Je ne comprends pas.
Si tu as des cases, et donc un quadrillage, depuis ta case (X,Y) la case suivante c'est la case c'est (X+1, Y), la précédente (X-1, Y). Au-dessus on est à Y-1 et en-dessous à Y+1.
La seule subtilité est si tu es déjà arrivé au bord, alors il faut éviter de prendre une case qui n'existe pas.
Si tu as déjà des coordonnées, peut-être pouvoir tomber dans le cercle de centre la case trouvée et travailler en distances et non en cases ?

---

En fait j'ai a la fois une sémantique d'espace discret ( donnée par des données stockées dans un fichier geotiff, avec des valeurs stockées pour chaque case, valeurs qui ont leur importance dans la simulation) et une sémantique de coordonnées dans un espace continu (les positions initiales des marcheurs aléatoires qui sont données en LonLat, les sorties consoles en lon lat, notre intuition en lon/lat), donc je me perds parfois dans la sémantique a privilégier.

Devoir calculer des distances entre coordonnées géographiques lointaines m'avait incité a manipuler des types ayant une sémantique lonlat pour pouvoir calculer la "great circle distance", et j'avais ramener le concept de "case" a la coordonnée géographique du centre de cette case. Donc en gros ca revient a dire j'avais pleins de points dispersés régulièrement dans un espace géographique continu, et que le marcheur aléatoire pouvait sauter d'un point a n'importe quel autre. C'était ma façon de discrétiser l'espace, l'avantage étant qu'on pouvait imaginer d'autre patrons de discrétisation.

Maintenant que je suis plutôt préoccupé par les notions de cases adjacentes et de bord, cette histoire d'ensemble de points ne marche plus très bien et je cherche une solution pas trop sale. Une solution sale serait d'utiliser mon ancien code en disant que la proba de sauter de x a y est de 0 si la distance entre x et y est supérieure a un certain seuil. Ca permettrait de rester dans l'optique que x et y sont exprimées en coordonnées continues (lonlat) plutôt que discret (ligne/colonne) mais ça implique calculer beaucoup de fois les distances, donc je cherchais une alternative :)

Citation:

---

Envoyé par Bousk

? C'est même la seule chose qu'ils savent faire :weird:

---

Pardon, je me suis mal exprimé. Je voulais dire que je lui ai très mal expliqué ce qu'il devait calculer et la précision que j'attendais, et que je me plains qu'il a mal compris. Oui oui. :pastaper:

Salut

Je ne suis pas certain d'avoir complètement compris ta problématique donc désolé d'avance si je dis n'importe quoi.

Perso, je ne suis pas fan de la sur-conception "au cas où ça pourrait servir dans le futur potentiel". A mon avis, il vaut mieux répondre correctement et simplement au problème actuel, et, si le besoin évolue, généraliser et refactorer plus tard. Du coup, repasser à une implémentation plus spécifique ne me choque pas, d'ailleurs ça arrive assez souvent quand le besoin de performance est prioritaire (même s'il est certainement possible de faire une jolie implémentation à la fois générique et performante, en s'arrachant quelques cheveux).

Sinon, tu as regardé des bibliothèques comme gdal ou cgal ?

Je ne saisis toujours pas. Le passage de coordonnées à cases se fait normalement en 2 opérations : une division et un modulo. :koi:

Citation:

---

Envoyé par SimonDecoline

Du coup, repasser à une implémentation plus spécifique ne me choque pas, d'ailleurs ça arrive assez souvent quand le besoin de performance est prioritaire (même s'il est certainement possible de faire une jolie implémentation à la fois générique et performante, en s'arrachant quelques cheveux).

---

Ok bon bah allons y gaiement pour des indices de lignes/colonne.

Citation:

---

Envoyé par SimonDecoline

Sinon, tu as regardé des bibliothèques comme gdal ou cgal ?

---

On utilise GDAL pour manipuler les geotiff, oui. J'avais un peu galérer avec cette bibliothèque. A la même époque j'avais jeté un coup d’œil a CGAL pour voir a quel point ce serait difficile d'imaginer d'autre modèles de tesselation qu'une simple grille. Merci de m'en avoir rappelé le nom, je n'arrivais plus a la retrouver.

Citation:

---

Je ne saisis toujours pas. Le passage de coordonnées à cases se fait normalement en 2 opérations : une division et un modulo.

---

Mhhh je ne saisis pas non plus. Pour passer des points de longitude/latitude a des indices de cases, j'utilise l'API de gdal justement.

Petit principe que j'ai appris sur notre forum: "si le problème est dans la performance, diagnostique avec un profileur."

Lui seul pourra te dire quel est ta perte de temps.

Je parie sur les conversions trop nombreuses.