what3words
►http://what3words.com
Fonctionnement
w3w est un quadrillage géant de la planète, composé de 57 000 milliards de carrés de 3 mètres de côté. Chacun de ces carrés a été associé à une adresse composée de 3 mots du dictionnaire. Un exemple d’adresse w3w est bulbe.relaxer.poche
Pas complètement convaincu par un système qui reste commercial, mais l’idée n’est pas inintéressante.
voir aussi #openlocationcode
et surtout #geohash
►https://en.wikipedia.org/wiki/Geohash
▻http://postgis.net/docs/ST_GeoHash.html
Les deux font la même chose que what3words, en moins intelligible, mais sans nécessiter une base de données distante : la #position est contenue dans le code.
En découvrant openlocationcode on pourrait se demander « pourquoi un nouveau système ? », voici les raisons avancées sur leur site :
- The codes aren’t case sensitive and don’t include easily confused characters. We’ve selected the characters to make it difficult to impossible to spell words in any language.
– Codes are generated from latitude and longitude, so they already exist for everywhere. Nobody has to set them up or pay for them. Each place has only one code.
– Codes that are similar are located closer together than codes that are different.
– Open Location Codes represent an area, not a point.
– The size of the area depends on the length of the code. Long codes are more accurate than short codes.
– Dropping characters from the end of a code gives you a larger area that contained the original code.
– Codes are 10 or 11 characters long (8FMGP9FW+6M), but if you’re in the local area (within 50km), the leading four characters of the code can be omitted (P9FW+6M) making the codes even shorter.
– The short code can be used together with a place name (like P9FW+6M Pisa, Italy).
Aucune différence avec geohash sur ces 8 points-là.
@severo merci pour la confirmation, on est donc bien devant le cas classique illustré par xkcd :p
De fait, je n’ai pas l’impression que quelqu’un utilise openlocationcode.
#Openlocationcode a été becté par Google…
▻https://maps.google.com/pluscodes
Je suis désolée, mais je trouve mon adresse en 3 mots plus #poétique qu’avec le code triste de #Google.
L’INE (l’INSEE bolivien) est en train d’élaborer un code pour référencer de manière unique les quartiers (urbains) et les communautés (rurales).
Pour éviter toute interprétation politique dans un pays où les limites territoriales ne sont pas définies partout, il a été décidé que le code n’aurait pas de référence administrative (dans tel département, dans telle ville) mais au contraire seulement une référence géographique.
Dans un premier temps, il a été décidé que, pour chaque quartier ou communauté (auquel correspond un polygone de limite territoriale), la référence sera le centroïde du polygone (en gros, le centre de gravité, toujours inclus dans le polygone). Et une des possibilités est d’utiliser le geohash de ce point central comme code de référence du quartier ou de la communauté.
GeoHash est un algorithme qui transforme (latitude,longitude) en un code, par exemple : (57.64911,10.40744) devient u4pruydqqvj. Chaque caractère additionnel augmente la précision.
►https://en.wikipedia.org/wiki/Geohash
Le GeoHash est réversible, ce qui signifie que la connaissance du code permet de retrouver latitude et longitude avec une certaine précision, qui dépend du nombre de caractères du geohash. Par exemple, avec 8 caractères, la précision est d’à peu près 50m.
Par contre, ayant réduit le polygone à un simple point, il n’est pas possible de revenir au polygone à partir du geohash, même pas à une approximation grossière.
Dans la deuxière étape, on aimerait donc pouvoir coder les polygones, et non pas simplement leurs centroïdes.
Le souci, évidemment, est la taille du code résultant. Imaginons la méthode suivante : simplifier le polygone en le remplaçant par sa « bounding box », c’est à dire le « rectangle » qui contient le polygone (latitudes et longitudes min et max). Pour coder le polygone à partir de ces 4 points en concaténant leurs geohash, il faut 4 fois plus de caractères, disons 8x4=32 caractères. On peut imaginer comprimer pour arriver à 16 caractères, puisque les 4 geohash auront une grande partie en commun.
Pour coder très grossièrement le polygone, on multiplie déjà par deux la longueur du code. Et on aimerait pouvoir définir de façon beaucoup plus précise les polygones, avec 10 points par exemple. Plusieurs possibilités :
– geohash de chaque point du polygone, concaténation de tous les geohashs, puis compression de cette concaténation - un seul code, mais très long et pas directement utilisable pour indexer
– méthode RecursivePrefixTree : on liste tous les geohash contenus dans le polygone - autant de codes que de polygones inclus dans la géométrie, très facile à utiliser pour indexer - plus adapté aux machines qu’aux humain.e.s
Avez-vous déjà vu et essayé des méthodes pour coder la géométrie d’un polygone avec une seule chaîne de caractères, et qui soit utilisable par un humain (recopier, entrer la valeur dans une application) ?
Quelques références
GeoHash :
– ►https://en.wikipedia.org/wiki/Geohash
– ▻http://postgis.net/docs/ST_GeomFromGeoHash.html
– ▻https://github.com/davetroy/geohash-js
– ▻https://github.com/yinqiwen/ardb/blob/master/doc/spatial-index.md
– ▻http://blog.notdot.net/2009/11/Damn-Cool-Algorithms-Spatial-indexing-with-Quadtrees-and-Hilbert-Curves
GeoHash pour polygones :
– ▻https://www.npmjs.org/package/polygon-hash
– ▻http://elasticsearch-users.115913.n3.nabble.com/Doing-bounding-box-filtering-using-a-geohash-p
– ▻https://github.com/jillesvangurp/geogeometry
– ▻https://github.com/derrickpelletier/geohash-poly
Utilisation comme index de bases de données :
– ▻http://lucene.apache.org/core/4_7_1/spatial/org/apache/lucene/spatial/serialized/SerializedDVStrategy.html
– ▻http://lucene.apache.org/core/4_7_1/spatial/org/apache/lucene/spatial/prefix/RecursivePrefixTreeStrategy.html
– ▻http://blog.safe.com/2014/03/dynamodb-s3-geoindex-big-data
– ►http://www.opensourceconnections.com/2014/04/11/indexing-polygons-in-lucene-with-accuracy
– ▻http://www.lucenerevolution.org/2013/Lucene-Solr4-Spatial-Deep-Dive
– ▻http://www.slideshare.net/lucenerevolution/search-with-polygons-another-approach-to-solr-geospatial-search
– ▻http://www.elasticsearch.org/guide/en/elasticsearch/reference/current/mapping-geo-shape-type.html
voir aussi la question sur gis stackexchange
▻http://gis.stackexchange.com/questions/102941/what-methods-exist-for-geohash-of-polygon
Déjà tu pourrais définir les coordonnées des sommets par rapport au centroïde, ça éliminerait (par translation) toute la phase que tu appelles de « compression ».
Plus tu veux de précision, plus il te faudra de « dimensions », mais commençons par le plus simple, la dimension 1 :
– « un disque de x km de rayon autour de C » => (c,x)
où c est le geohash du point C.
Note que je parle de disque et de km, mais ça peut aussi être un carré de n surfaces de base (hectares par exemple)…
Un autre truc possible (et humainement compréhensible) pour coder une forme, c’est de fournir un alphabet de base et de dire « en forme de U », « en forme de N », etc. Ou encore les formes de tetris.
Bonne idée le tetris :)
Mais avant de tenter la #révolution #mathématique, je cherche déjà des pointeurs vers des méthodes existantes. Je n’ai pas trouvé grand chose pour l’instant.
Pour préciser l’objectif de ce code, l’INE veut pouvoir fournir une API de consultation de ses données, avec un code pivot pour les géométries, indexable et facile à copier manuellement.
Peut être aussi chercher du côté de la représentation et compression de contours en traitement d’image ou vidéos. Ce qui revient plus ou moins à utiliser un alphabet de base (le « sparse coding ») comme tu le proposes @fil.
Ça avance :
– GeoRaptor, un outil #python qui applique la méthode RecursivePrefixTree référencée plus haut :
▻https://gis.stackexchange.com/a/228496/32749
– ElasticSearch utilise le geohash comme une des deux stratégies (avec « quadtree ») pour indexer les polygones :
▻https://www.elastic.co/guide/en/elasticsearch/reference/current/geo-shape.html
