Optimiser un calcul de voisin le plus proche à l'aide de PostGIS

J'utilise PostGIS pour calculer les voisins les plus proches des polygones. Ce que je veux calculer, c'est la distance minimale entre chaque polygone et le polygone le plus proche.

Jusqu'à présent, j'ai obtenu une grande aide de la réponse de Mike Toews (que je cite avec un changement mineur) ici:

SELECT 
  a.hgt AS a_hgt,
  b.hgt AS b_hgt,
  ST_Distance(a.the_geom, b.the_geom) AS distance_between_a_and_b
FROM 
  public."TestArea" AS a, public."TestArea" AS b
WHERE
  a.hgt !=  b.hgt AND ST_Distance(a.the_geom, b.the_geom) < 400

Ensuite, j'ai calculé le minimum:

SELECT a_hgt, MIN(distance_between_a_and_b)
FROM public."lon_TestArea"
GROUP BY a_hgt

Cependant, mon défi est de calculer cela pour un grand nombre de polygones (1 000 000). Comme le calcul ci-dessus compare chaque polygone à tous les autres polygones, je me suis demandé comment améliorer le calcul afin de ne pas avoir à effectuer 10 ^ 12 calculs.

J'ai pensé que je devais tamponner chaque polygone, puis calculer les voisins les plus proches de toutes les valeurs dans le tampon pour ce polygone et enregistrer le minimum. Je ne sais pas si c'est la meilleure approche, ou s'il y a une fonction dans PostGIS que je devrais utiliser.

EDIT: En utilisant l'une des suggestions de Nicklas, j'expérimente avec ST_Dwithin():

CREATE TABLE mytable_withinRange AS SELECT 
  a.hgt AS a_hgt,
  b.hgt AS b_hgt,
  ST_DWithin(a.the_geom, b.the_geom, 400)
FROM 
  public."lon_TestArea" AS a, public."lon_TestArea" AS b

Cela renvoie un tableau de l'ID de chaque polygone, et s'il se trouve dans une certaine distance ou non. Est-il possible de construire une IF/ELSEinstruction de type en utilisant SQL? (J'ai lu comment utiliser la CASEcondition) Ou dois-je essayer de joindre la table que je produis à la table d'origine, puis d'exécuter à nouveau la requête à l'aide de ST_Distance?

Il y a une grande section "Nearest Neighbour" sur la page BostonGIS .

ÉDITER:

Que diriez-vous

CREATE TABLE mytable_withinRange AS SELECT 
 a.hgt AS a_hgt,
 b.hgt AS b_hgt
FROM 
 public."lon_TestArea" AS a, public."lon_TestArea" AS b
WHERE 
 ST_DWithin(a.the_geom, b.the_geom, 400)

Concernant la déclaration CASE :

SELECT a,
   CASE WHEN a=1 THEN 'one'
        WHEN a=2 THEN 'two'
        ELSE 'other'
   END
FROM test;

Bonjour

Il y a certaines choses à considérer pour accélérer les choses et certaines choses qui pourraient être possibles à l'avenir.

Tout d'abord , vous avez mentionné que vous envisagez d'utiliser un tampon pour trouver des polygones dans une plage minimale afin d'éviter de calculer toutes les combinaisons.

Comme indiqué dans un autre lien de Boston, la bonne façon de le faire dans PostGIS est d'utiliser ST_Dwithin . ST_Dwithin utilise l'index pour trouver les voisins dans une certaine plage.

Cela dépend bien sûr du jeu de données s'il suffit d'utiliser une valeur fixe pour st_DWithin pour tous les polygones ou si vous devez faire quelque chose comme underdark et wildintellect.

Une deuxième chose consiste à utiliser PostGIS 1.5+ ici. En effet, les calculs de polygone à polygone sont beaucoup plus rapides depuis 1,5 si leurs boîtes englobantes ne se croisent pas. Vous pouvez en savoir plus ici. .

La troisième chose à mentionner est l'avenir.

Dans PostgreSQL 9.1, il y aura quelque chose appelé knn-gist. C'est un index qui peut non seulement répondre oui ou non mais aussi renvoyer le résultat ordonné directement à partir de l'index. Vous pouvez en lire plus ici .

Mais il y aura encore beaucoup de travail à faire du côté de PostGIS avant que knn gist ne vous aide pour des choses comme ça. Il y a un ticket pour ça ici.

Cordialement

Nicklas

Les pages suivantes relatives au travail des maîtres de Nathan Kerr donnent un bon aperçu de ce problème direct. Mon collègue a essayé la méthode Bostongis ici et ici , mais a eu quelques problèmes pour la faire fonctionner correctement.

Une autre approche à penser qui est similaire au tampon consiste à faire un rectangle en expansion / contraction. Fondamentalement, passez 1 faire une zone de délimitation (c'est une unité droite + x à la bbox de votre polygone d'origine) que vous pensez attraper au moins une intersection. Pour les données qui ont obtenu une intersection, effectuez une sous-requête qui teste ces correspondances pour la plus proche. Pour les données, la correspondance n'a pas réussi à développer la zone de délimitation et à répéter.

C'est clairement un problème de programmation récursif, et il pourrait être préférable de le faire en Python avec Shapely que 100% directement dans postgis.