Trouver les voisins les plus proches entre deux tables avec des emplacements de points dans SpatiaLite?

10

J'ai commencé à jouer avec SpatiaLite aujourd'hui et j'ai déjà rencontré un problème.

Pour chaque emplacement de point stocké dans tableOne, je voudrais sélectionner un point (distance linéaire) le plus proche de tableTwo.

Jusqu'à présent, j'ai trouvé une solution maladroite qui utilise VIEW:

CREATE VIEW testview AS 
SELECT 
A.id , 
B.myValue, 
Distance(A.Geometry, B.Geometry) AS distance
FROM tableOne AS A, tableTwo AS B
WHERE distance < 10000
ORDER BY A.Id, distance;

Et alors:

SELECT * FROM testview
WHERE distance = (SELECT MIN(distance) FROM testview AS t WHERE t.id = testview.id)

semble faire le travail.

Deux questions:

Existe-t-il un moyen d'effectuer une telle requête sans créer de VUE?

Existe-t-il un autre moyen d'optimiser cette requête pour de meilleures performances? Dans un scénario réel, tableOne aura des enregistrements de plusieurs centaines de milliers de couples, et tableTwo - 1,3 million.

radek
la source
Je peux vous donner une approche plus rapide de plusieurs ordres de grandeur, mais cela vous obligerait à utiliser un index knngist postgresql 9 au lieu de spatialite ...
Ragi Yaser Burhum
en fait plus rapide que GRASS, ArcGIS, QGIS, SQLServer et à peu près tout autre SIG spatial de base de données / bureau (cependant, je n'ai pas essayé la fonctionnalité de voisin le plus proche d'Oracle). Faites-moi savoir si c'est une option.
Ragi Yaser Burhum
@Ragi: Je suis conscient que PostGIS serait un moyen beaucoup plus efficace de travailler avec un tel problème. Cependant, l'objectif ultime de cet exercice serait de créer une petite application portable et dans ce cas, SpatiaLite est un gagnant.
radek
Quelle est votre plateforme de développement pour votre application portable?
Allan Adair
@Allan: Fonctionne sur les deux: Windows Server 2008 et Ubuntu pour le moment.
radek

Réponses:

5

Je viens de tester ce SQL et ça marche:

SELECT g1.OGC_FID As id1, g2.OGC_FID As id2, MIN(ST_Distance(g1.GEOMETRY,g2.GEOMETRY)) AS DIST
FROM table_01 As g1, table_02 As g2   
WHERE g1.OGC_FID <> g2.OGC_FID
AND ST_Contains(ST_Expand(g1.geometry,50),g2.geometry)
GROUP BY id1
ORDER BY id1

Comme vous pouvez le lire ici "La façon naïve d'effectuer une requête de voisin le plus proche est d'ordonner la table candidate par distance de la géométrie de la requête, puis de prendre l'enregistrement avec la plus petite distance".

Meilleures salutations,

Andrea

aborruso
la source
J'essaie d'utiliser cette requête mais j'obtiens des résultats inattendus - j'obtiens une table résultante mais avec des ID pour les lignes que je peux voir ne sont pas le voisin le plus proche. J'essaie de trouver la ligne la plus proche dans un calque de chaîne multiligne à chaque point dans un autre calque. Je suis nouveau avec spatiaLite. Aucune suggestion? De plus, je veux finalement exécuter cela sur 1 million de points +
kflaw
Je ne suis pas sûr non plus de comprendre le but de cette déclaration: OERE g1.OGC_FID <> g2.OGC_FID
kflaw
De plus, dans mon résultat, je reçois une distance nulle. J'ai joué avec cette ligne: AND ST_Contains (ST_Expand (g1.geometry, 50), g2.geometry) ainsi que je l'ai supprimée et je n'ai toujours aucune valeur de distance, même si
j'obtiens
6

Si vous ne souhaitez pas calculer les distances entre toutes les combinaisons de points, vous pouvez utiliser un index spatial sur l'une des tables:

SELECT 
  A.id , 
  B.myValue, 
  MIN(Distance(A.Geometry, B.Geometry)) AS distance
FROM tableOne AS A, tableTwo AS B
WHERE A.ROWID IN (
  SELECT ROWID
  FROM SpatialIndex WHERE
    f_table_name = 'A' 
    AND search_frame = BuildCircleMbr(ST_X(B.Geometry), ST_Y(B.Geometry), 10000))
GROUP BY A.id, B.myValue
Samuel
la source
J'ai essayé d'utiliser la solution que vous avez publiée car j'ai besoin d'utiliser un index spatial, mais elle ne renvoie aucune valeur? pour la ligne f_table_name = 'A', dois-je remplacer «A» par le nom réel de la table (table un)? J'ai essayé de toute façon et cela ne retourne toujours rien, pourquoi cela pourrait-il être
kflaw
Vous avez raison f_table_name = 'A'devrait l'être f_table_name = 'tableOne'. Notez que cette demande suppose une spatialite> 4.x ( SpatialIndexune table virtuelle est utilisée). Avez-vous essayé d'ajuster le search_framepour votre cas d'utilisation? Dans l'exemple ci-dessus, les points sont supposés être à une distance maximale de 10000 mètres.
Samuel
J'ai joué avec la valeur du cadre de recherche, je suppose que cela signifie à moins de 10000 mètres, ce qui devrait fonctionner pour moi. Je ne sais pas vraiment quelle version de spatialite, j'ai créé la base de données via qgis et j'utilise l'interface graphique dans qgis. Laissez-moi voir si je peux comprendre cela
kflaw
Il s'agit de la version 4.1.1 avec la version 3.7.17 de sqlite, alors cela devrait fonctionner alors? Je me demande ce qui ne va pas, je vais le tester un peu plus
kflaw
3

Depuis la version 4.4.0, SpatiaLite prend en charge un index de table virtuelle KNN pour les problèmes de voisin le plus proche. Voici une requête qui recherche la ligne la plus proche dans une table de chaîne de lignes de chaque point d'une table de points.

SELECT k.* FROM knn k, points p
WHERE f_table_name = 'linestrings' 
AND ref_geometry = p.geometry
AND max_items = 1;
Greg Krakow
la source
2

Vous pouvez simplifier votre requête comme ceci.

SELECT 
   A.id , 
   B.myValue, 
   MIN(Distance(A.Geometry, B.Geometry)) AS distance
FROM tableOne AS A, tableTwo AS B
GROUP BY A.id, B.myValue

Pour une solution plus générique, il pourrait être utile d'essayer de convertir cette fonction PostGIS Nearest Neighbour: http://blog.mackerron.com/2011/03/postgis-nearest-neighbour/

obscur
la source
malheureusement, le code se traduit par:SQL error: "misuse of aggregate: MIN()"
radek
En ce qui concerne PostGIS, il existe également quelques exemples sur le site Web de BostonGIS, mais jusqu'à présent, je n'ai pas réussi à les traduire en SpatiaLite: /
radek