Encoder un polygone avec l’algo de Google dans Mysql

Dans la droite lignée d’autres articles que j’avais écrits, il y a plusieurs mois, je vais encore écrire sur l’encodage de la géométrie avec l’algorithme de Google afin de réduire le poids des données géographiques complexes (polygones, polylignes) et donc d’accélérer leur transfère côté client.

L’objectif était de créer une fonction qui génère cette géométrie encodée directement du côté de la base de données MySql

À la base l’algorithme est fait uniquement pour des polylignes (des points qui se suivent) ou de simples polygones. Pour les polygones à trou ou des multipolygones, il est nécessaire de faire quelques modifications afin de pouvoir les stocker dans une seule chaîne de caractères. La solution est donc d’insérer des délimiteurs pour indiquer les trous et les parties multiples.

Après quelques recherches sur le web, je suis tombé sur une personne sur Cartometric Blog qui avait exactement le même objectif et avait déjà réfléchi à cela, mais avec Postgis. Je suis donc parti sur les deux mêmes délimiteurs.

‡ : pour un trou (inner ring)
† : pour un autre polygone(multi polygone)

Les fonctions ci dessous permettent d’encoder la géométrie pour une précision de 5 chiffres après la virgule (environ 1 mètre)

Les fonctions se font référence entre elles le la plus petite entité (la coordonnée) à la plus grande

googleEncodeGeom : encode une géométrie (pour les multipolygones notamment)

googleEncodePolygon : encode un polygone

googleEncodeLineString : encode une ligne

googleEncodePoint : encode une coordonnée

La fonction googleEncodePoint n’est pas des plus propres… j’ai un peu buté avec la conversion en byte, car Mysql en utilise 64 et non 32. J’ai donc été obligé de manipuler du texte, c’est pas très élégan mais ça fonctionne.

Le code:

googleEncodePoint : encode une coordonnée

DELIMITER $$
CREATE FUNCTION `googleEncodePoint`(`coord` DOUBLE) 
RETURNS text 
BEGIN
DECLARE s VARCHAR(100);
 
DECLARE val1e5 INT ;
DECLARE deci DECIMAL (65,0);
DECLARE abs1e5 INT;
DECLARE roundAbs1e5 INT;
DECLARE e VARCHAR(255);
DECLARE toadd INT(11);
 
DECLARE b1 VARCHAR(6);
DECLARE b2 VARCHAR(6);
DECLARE b3 VARCHAR(6);
DECLARE b4 VARCHAR(6);
DECLARE b5 VARCHAR(6);
DECLARE b6 VARCHAR(6);
DECLARE b7 VARCHAR(6);
 
DECLARE n1 INT(4);
DECLARE n2 INT(4);
DECLARE n3 INT(4);
DECLARE n4 INT(4);
DECLARE n5 INT(4);
DECLARE n6 INT(4);
DECLARE n7 INT(4);
 
SET val1e5 = ROUND(coord*1e5);
SET abs1e5 = ABS(val1e5);
                                                 
IF val1e5 < 0 AND coord <0 THEN SET deci =~(((~abs1e5)+1)<<1);
ELSEIF val1e5 < 0 AND coord >0 THEN SET deci = ((~abs1e5)+1)<<1;
ELSEIF val1e5 > 0 AND coord <0 THEN SET deci = ~(abs1e5<<1);
ELSEIF val1e5 > 0 AND coord >0 THEN SET deci = abs1e5<<1;
END IF;
SET s = RIGHT((BIN(deci)),32);
SET s = INSERT(s,1,0, REPEAT('0',32 -CHAR_LENGTH(s)));
                                                                                                  
SET b1 = SUBSTR(s,28,5);
SET b2 = SUBSTR(s,23,5);
SET b3 = SUBSTR(s,18,5);
SET b4 = SUBSTR(s,13,5);
SET b5 = SUBSTR(s,8,5);
SET b6 = SUBSTR(s,3,5);
SET b7 = SUBSTR(s,1,3);
 
SET b1 = INSERT(b1,1,0,'0');
SET b2 = INSERT(b2,1,0,'0');
SET b3 = INSERT(b3,1,0,'0');
SET b4 = INSERT(b4,1,0,'0');
SET b5 = INSERT(b5,1,0,'0');
SET b6 = INSERT(b6,1,0,'0');
SET b7 = INSERT(b7,1,0,'0000');
 
SET toadd = 0;
SET n7 = CONV(b7,2,10)+63+toadd;
IF b7 != '000000' AND toadd = 0 THEN SET toadd = 32; END IF;
SET n6 = CONV(b6,2,10)+63+toadd;
IF b6 != '000000' AND toadd = 0 THEN SET toadd = 32; END IF;
SET n5 = CONV(b5,2,10)+63+toadd;
IF b5 != '000000' AND toadd = 0 THEN SET toadd = 32; END IF;
SET n4 = CONV(b4,2,10)+63+toadd;
IF b4 != '000000' AND toadd = 0 THEN SET toadd = 32; END IF;
SET n3 = CONV(b3,2,10)+63+toadd;
IF b3 != '000000' AND toadd = 0 THEN SET toadd = 32; END IF;
SET n2 = CONV(b2,2,10)+63+toadd;
IF b2 != '000000' AND toadd = 0 THEN SET toadd = 32; END IF;
SET n1 = CONV(b1,2,10)+63+toadd;
 
SET e = CHAR(n1, n2, n3, n4,n5, n6,n7);
SET e = REPLACE(e, '?', '');
IF e = '' THEN SET e = '?'; END IF;
RETURN e;
END
$$
DELIMITER ;

googleEncodeLineString : encode une polyline

DELIMITER $$
CREATE FUNCTION googleEncodeLineString(`linestring` LINESTRING)
RETURNS TEXT
LANGUAGE SQL
 
BEGIN
DECLARE line_encoded TEXT;
DECLARE nb_points INT;
DECLARE point1 POINT;
DECLARE X_old FLOAT;
DECLARE Y_old FLOAT;
DECLARE X_to_encode FLOAT;
DECLARE Y_to_encode FLOAT;
DECLARE Xenc TEXT;
DECLARE Yenc TEXT;
DECLARE i INT;
DECLARE enc_point_latlng VARCHAR(50);
 
SET line_encoded = '';
SET X_old =0;
SET Y_old = 0;
SET i =1;
SET nb_points = NumPoints(linestring);
 
WHILE i <= nb_points DO
SET point1 = PointN(linestring,i);
SET X_to_encode = X(point1) - X_old;
SET Y_to_encode = Y(point1) - Y_old;
SET Xenc = googleEncodePoint(X_to_encode);
SET Yenc = googleEncodePoint(Y_to_encode);
SET line_encoded = CONCAT (line_encoded, Yenc, Xenc);
SET X_old = X(point1);
SET Y_old = Y(point1);
SET i = i+1;
 
END WHILE;
return line_encoded;
END
 
$$
DELIMITER ;

googleEncodePolygon : encode un polygon

DELIMITER $$
CREATE FUNCTION googleEncodePolygon(`polygon` POLYGON)
RETURNS TEXT
LANGUAGE SQL
 
BEGIN
DECLARE polygon_encoded TEXT;
DECLARE nb_int_ring INT;
DECLARE ls_ext_enc TEXT;
DECLARE ls_int_enc TEXT;
 
DECLARE i INT;
SET polygon_encoded = '';
SET nb_int_ring = NumInteriorRings(polygon);
SET ls_ext_enc = googleEncodeLineString(ExteriorRing(polygon));
SET polygon_encoded = CONCAT(polygon_encoded, ls_ext_enc );
SET i =1;
 
WHILE i <= nb_int_ring DO
SET ls_int_enc = googleEncodeLineString (InteriorRingN(polygon,i));
SET polygon_encoded = CONCAT(polygon_encoded,'‡', ls_int_enc);
SET i = i+1;
END WHILE;
 
return polygon_encoded;
 
END
 
$$
DELIMITER ;

googleEncodeGeom : encode une géométrie (polygon ou multi polygon)

DELIMITER $$
CREATE FUNCTION googleEncodeGeom(`geom` GEOMETRY)
RETURNS TEXT
LANGUAGE SQL
BEGIN
DECLARE geom_encoded TEXT;
DECLARE nb_geom INT;
DECLARE geometryt_type TEXT;
DECLARE polygon_encoded TEXT;
DECLARE i INT;
SET geom_encoded = '';
 
SET geometryt_type = GeometryType(geom);
SET i =1;
IF geometryt_type = 'MULTIPOLYGON' THEN
SET nb_geom = NumGeometries(geom);
 
WHILE i <= nb_geom DO
SET polygon_encoded = googleEncodePolygon(GeometryN(geom,i));
 
IF i > 1 THEN
 
SET geom_encoded = CONCAT(geom_encoded,'†', polygon_encoded);
 
ELSE
SET geom_encoded = CONCAT(geom_encoded, polygon_encoded);
END IF;
SET i = i+1;
END WHILE;
END IF;
 
 
 
IF geometryt_type = 'POLYGON' THEN
SET polygon_encoded = googleEncodePolygon(geom);
SET geom_encoded = polygon_encoded;
END IF;
return geom_encoded;
END
$$
DELIMITER ;

Et voilà, il est donc maintenant possible mettre en place un trigger pour faire la conversion sans avoir besoin de passer par du PHP intermédiaire par exemple.

La fonction googleEncodeGeom prend comme paramètre une géométrie et plus précisément un polygone ou un multipolygone.

exemple d’utilisation pour un update :

UPDATE ma_table SET geom_encoded = googleEncodeGeom(geom)

où geom_encoded est de type TEXT et geom est de type GEOMETRY

Très prochainement, le code pour utiliser ce type de géométrie sur LeafLet 0.8