Il s'agit d'une version largement simplifiée d'une fonction que j'utilise dans une application créée il y a environ 3 ans. Adapté à la question posée.
-
Trouve des emplacements dans le périmètre d'un point à l'aide d'une boîte . On pourrait le faire avec un cercle pour obtenir des résultats plus précis, mais ce n'est qu'une approximation pour commencer.
-
Ignore le fait que le monde n'est pas plat. Ma candidature n'était destinée qu'à une région locale, de quelques 100 kilomètres de diamètre. Et le périmètre de recherche ne s'étend que sur quelques kilomètres. Rendre le monde plat est assez bon pour le but. (À faire :une meilleure approximation du rapport lat/lon en fonction de la géolocalisation pourrait aider.)
-
Fonctionne avec des géocodes comme ceux que vous obtenez de Google Maps.
-
Fonctionne avec PostgreSQL standard sans extension (aucun PostGis requis), testé sur PostgreSQL 9.1 et 9.2.
Sans index, il faudrait calculer la distance pour chaque ligne de la table de base et filtrer les plus proches. Extrêmement cher avec de grandes tables.
Modifier :
J'ai revérifié et l'implémentation actuelle permet un index GisT sur les points (Postgres 9.1 ou ultérieur). Simplifié le code en conséquence.
La astuce majeure est d'utiliser un index GiST fonctionnel de boîtes , même si la colonne n'est qu'un point. Cela permet d'utiliser l'implémentation existante de GiST
.
Avec une telle recherche (très rapide), nous pouvons obtenir tous les emplacements dans une boîte. Le problème restant :nous connaissons le nombre de lignes, mais nous ne connaissons pas la taille de la boîte dans laquelle elles se trouvent. C'est comme connaître une partie de la réponse, mais pas la question.
J'utilise une recherche inversée similaire approche de celle décrite plus en détail dans cette réponse connexe sur dba.SE . (Seulement, je n'utilise pas d'index partiels ici - cela pourrait également fonctionner).
Parcourez un tableau d'étapes de recherche prédéfinies, de très petites à "juste assez grandes pour contenir au moins suffisamment d'emplacements". Cela signifie que nous devons exécuter quelques requêtes (très rapides) pour obtenir la taille du champ de recherche.
Recherchez ensuite la table de base avec cette zone et calculez la distance réelle uniquement pour les quelques lignes renvoyées par l'index. Il y aura généralement un surplus puisque nous avons trouvé la boîte contenant au moins assez d'emplacements. En prenant les plus proches, nous arrondissons efficacement les coins de la boîte. Vous pouvez forcer cet effet en agrandissant la boîte d'un cran (multipliez le radius dans la fonction par sqrt(2) pour obtenir complètement précis résultats, mais je ne ferais pas tout, car c'est approximatif pour commencer).
Ce serait encore plus rapide et plus simple avec un SP GiST index, disponible dans la dernière version de PostgreSQL. Mais je ne sais pas encore si c'est possible. Nous aurions besoin d'une implémentation réelle pour le type de données et je n'ai pas eu le temps de m'y plonger. Si vous trouvez un moyen, promettez de revenir !
Étant donné ce tableau simplifié avec quelques exemples de valeurs (adr .. adresse):
CREATE TABLE adr(adr_id int, adr text, geocode point);
INSERT INTO adr (adr_id, adr, geocode) VALUES
(1, 'adr1', '(48.20117,16.294)'),
(2, 'adr2', '(48.19834,16.302)'),
(3, 'adr3', '(48.19755,16.299)'),
(4, 'adr4', '(48.19727,16.303)'),
(5, 'adr5', '(48.19796,16.304)'),
(6, 'adr6', '(48.19791,16.302)'),
(7, 'adr7', '(48.19813,16.304)'),
(8, 'adr8', '(48.19735,16.299)'),
(9, 'adr9', '(48.19746,16.297)');
L'index ressemble à ceci :
CREATE INDEX adr_geocode_gist_idx ON adr USING gist (geocode);
Vous devrez ajuster la zone d'accueil, les étapes et le facteur d'échelle à vos besoins. Tant que vous cherchez dans des cases de quelques kilomètres autour d'un point, une terre plate est une assez bonne approximation.
Vous devez bien comprendre plpgsql pour travailler avec cela. Je sens que j'en ai assez fait ici.
CREATE OR REPLACE FUNCTION f_find_around(_lat double precision, _lon double precision, _limit bigint = 50)
RETURNS TABLE(adr_id int, adr text, distance int) AS
$func$
DECLARE
_homearea CONSTANT box := '(49.05,17.15),(46.35,9.45)'::box; -- box around legal area
-- 100m = 0.0008892 250m, 340m, 450m, 700m,1000m,1500m,2000m,3000m,4500m,7000m
_steps CONSTANT real[] := '{0.0022,0.003,0.004,0.006,0.009,0.013,0.018,0.027,0.040,0.062}'; -- find optimum _steps by experimenting
geo2m CONSTANT integer := 73500; -- ratio geocode(lon) to meter (found by trial & error with google maps)
lat2lon CONSTANT real := 1.53; -- ratio lon/lat (lat is worth more; found by trial & error with google maps in (Vienna)
_radius real; -- final search radius
_area box; -- box to search in
_count bigint := 0; -- count rows
_point point := point($1,$2); -- center of search
_scalepoint point := point($1 * lat2lon, $2); -- lat scaled to adjust
BEGIN
-- Optimize _radius
IF (_point <@ _homearea) THEN
FOREACH _radius IN ARRAY _steps LOOP
SELECT INTO _count count(*) FROM adr a
WHERE a.geocode <@ box(point($1 - _radius, $2 - _radius * lat2lon)
, point($1 + _radius, $2 + _radius * lat2lon));
EXIT WHEN _count >= _limit;
END LOOP;
END IF;
IF _count = 0 THEN -- nothing found or not in legal area
EXIT;
ELSE
IF _radius IS NULL THEN
_radius := _steps[array_upper(_steps,1)]; -- max. _radius
END IF;
_area := box(point($1 - _radius, $2 - _radius * lat2lon)
, point($1 + _radius, $2 + _radius * lat2lon));
END IF;
RETURN QUERY
SELECT a.adr_id
,a.adr
,((point (a.geocode[0] * lat2lon, a.geocode[1]) <-> _scalepoint) * geo2m)::int4 AS distance
FROM adr a
WHERE a.geocode <@ _area
ORDER BY distance, a.adr, a.adr_id
LIMIT _limit;
END
$func$ LANGUAGE plpgsql;
Appel :
SELECT * FROM f_find_around (48.2, 16.3, 20);
Renvoie une liste de $3 emplacements, s'il y en a suffisamment dans la zone de recherche maximale définie.
Trié par distance réelle.
Autres améliorations
Construisez une fonction comme :
CREATE OR REPLACE FUNCTION f_geo2m(double precision, double precision)
RETURNS point AS
$BODY$
SELECT point($1 * 111200, $2 * 111400 * cos(radians($1)));
$BODY$
LANGUAGE sql IMMUTABLE;
COMMENT ON FUNCTION f_geo2m(double precision, double precision)
IS 'Project geocode to approximate metric coordinates.
SELECT f_geo2m(48.20872, 16.37263) --';
Les constantes (littéralement) globales 111200 et 111400 sont optimisés pour ma région (Autriche) à partir de la Longueur d'un degré de longitude
et La longueur d'un degré de latitude
, mais en gros, je travaille partout dans le monde.
Utilisez-le pour ajouter un géocode mis à l'échelle à la table de base, idéalement une colonne générée comme indiqué dans cette réponse :
Comment faire des calculs de date qui ignorent l'année ?
Reportez-vous à 3. Version magie noire où je vous guide tout au long du processus.
Ensuite, vous pouvez simplifier davantage la fonction :mettre à l'échelle les valeurs d'entrée une fois et supprimer les calculs redondants.
