Discussion :

[nine]

bonjour

je cherche a faire des calculs de distance a partir de 2 tables.

table 1 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
 
id         X               Y
1    67000    2396000
2    68000    2397000
3    72000    2404000
4    73000    2398000
5    73000    2403000

table 2

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
 
id                  X               Y
130848    372820    2172640    pas dans la grille
130851    67000    2396000    pile
130863    72100    2405000    dedans
130866    73500    2398000    dedans
130850    68000    2397000    pile

ma requete

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
 
select a.x_cal
, a.y_cal
, b.x, b.y
, ((a.x_cal-b.x)^2 + (a.y_cal-b.y)^2)^0.5 as d  
from _1datauser a
, _1couche b 
where ((a.x_cal-b.x)^2 + (a.y_cal-b.y)^2)^0.5 = (select min(((a.x_cal-b.x)^2 + (a.y_cal-b.y)^2)^0.5 ) 
from _1datauser  a, _1couche b)

donne le resulat :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
 
x_cal    y_cal    x    y    d
67000    2396000    67000    2396000    0
68000    2397000    68000    2397000    0

en fait j'aimerai calculer la distance pour tous les points de la table 2 qui ne sont pas dans la table 1

merci d'avance

n

[Waldar]

Quel est votre SGBD ?

[nine]

postgresql 8.1

[rberthou]

en fait j'aimerai calculer la distance pour tous les points de la table 2 qui ne sont pas dans la table 1

merci d'avance

Peux tu préciser quelles distances (mini, toutes, maxi, ...)

[nine]

bien sur, je prend la distance min
merci

[rberthou]

je ne suis pas du tout un expert de Postgres, mais je crois qu'il existe des types de données géometrique (Point, lseg) qui pourrait être tres intéressant dans ce cas la (surtout avec les opérateur géometrique).
Exemple pour la distance

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
Recherche de la longueur
@-@ lseg '((x1,y1),(x2,y2))'
ou de la distance
point '(x1,y1)' <-> point '(x2, y2)'

ou en SQL

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
SELECT a.x_cal, a.y_cal, b.x, b.y, ((a.x_cal-b.x)^2 + (a.y_cal-b.y)^2)^0.5 AS d  
  FROM _1datauser a, _1couche b 
 WHERE ((a.x_cal - b.x)^2 + (a.y_cal - b.y)^2) = 
             ( SELECT min(((a.x_cal-z.x)^2 + (a.y_cal-z.y)^2)) 
                 FROM _1couche z
                where  a.x_cal not = z.x 
                   or  a.y_cal not = z.y
              )

[nine]

merci de ta reponse


en effet postgresql integre postgis cartouche spatial qui gere des objets geometriques avec son lot de fonctions (tq distance)
mais le traitement est plus long

j'ai teste ta requete et ca a l'air de fonctionner, je verifie les resultats.

encore merci !

n

[nine]

les resultats sont :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
 
x_cal	y_cal	x	y	d
68000 2397000 67000 2396000 1414.2135623731
67000 2396000 68000 2397000 1414.2135623731
72100 2405000 72000 2404000 1004.98756211209
372820 2172640 73000 2398000 375072.209047805
73500 2398000 73000 2398000 500

or pour les deux premiers points je devrai avoir 0
pourquoi le min ne retourne t-il pas 0 comme etant la distance la plus petite ?

n

[rberthou]

car j'exclus les points qui sont confondus dans la sous requete

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
WHERE  a.x_cal NOT = z.x 
      OR  a.y_cal NOT = z.y

[nine]

arrf ! merci de ta reactivité

en otant la clause where le resultat est parfait.

peut on faire en une seule fois la recup des donnes et le calcul de distance ?

a partir des 2 tables table1 et table2 creer une table resultat (x_cal,y_cal,x,y, val1, val2,..val12,distance):
pour les points qui tombent pile poil dans la grille je recupere la valeur correspondante et quand ce n'est pas le cas je ne recupere pas la valeur mais je calcul la distance ?

encore merci

n

[nine]

en fait c bon :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
 
create table resultat as SELECT a.x_cal, a.y_cal, b.x, b.y, ((a.x_cal-b.x)^2 + (a.y_cal-b.y)^2)^0.5 AS d, b.i_val, b.ii_val, b.iii_val 
  FROM _1datauser a, _1couche b
 WHERE ((a.x_cal-b.x)^2 + (a.y_cal-b.y)^2)^0.5 = 
             ( SELECT min(((a.x_cal-z.x)^2 + (a.y_cal-z.y)^2)^0.5) 
                 FROM _1couche z
 
              )

merci beaucoup !

n

[rberthou]

Pour creer la table resultat je dirais :

Je pense que c est cette syntaxe qui onctionne

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
CREATE TABLE RESULTAT
 AS
SELECT a.x_cal, a.y_cal, b.x, b.y, ((a.x_cal-b.x)^2 + (a.y_cal-b.y)^2)^0.5 AS dist  
  FROM _1datauser a, _1couche b 
 WHERE ((a.x_cal - b.x)^2 + (a.y_cal - b.y)^2) = 
             ( SELECT min(((a.x_cal-z.x)^2 + (a.y_cal-z.y)^2)) 
                 FROM _1couche z )

Ou

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
INSERT into RESULTAT
SELECT a.x_cal, a.y_cal, b.x, b.y, ((a.x_cal-b.x)^2 + (a.y_cal-b.y)^2)^0.5 AS dist  
  FROM _1datauser a, _1couche b 
 WHERE ((a.x_cal - b.x)^2 + (a.y_cal - b.y)^2) = 
             ( SELECT min(((a.x_cal-z.x)^2 + (a.y_cal-z.y)^2)) 
                 FROM _1couche z )

[nine]

oui c ce que j'ai fait au final, mais je me retrouve avec un autre soucis :

le temps de reponse!

le test grandeur nature comprend 3 tables sources de 550 000 lignes environ que je crois avec la table utilisateur : 120 000 points.

j'ai arréte le traitement au bout d'une 1/2 heure.

je penche pour tester 2 choses :

- soit creer un index sur x,y sur chacune des tables (a voir)

- soit finalement faire le traitement en 2 passes : 1ere passe je recupere les resultats pour les poitns qui tombent dans la grille
2eme passe : update sur la table resultat pour les points qui ne tombent pas dans la grille.

n

[rberthou]

Le temps de réponse est normal car tu réalise un produit cartésien.

Un index ne servira a rien dans ton cas car la seule jointure que tu réalise se fait sur des zones calculées et cela ne limitera pas.

Je pense que tu as un problème de conception. Personnellement j'essayerai de réaliser un découpage géographique en zones pour essayer de limiter le traitement à certain sous-secteur.

[SQLpro]

Le seul moyen est d'utiliser effectivement des données de type GEOMETRY d'une base de données incorporant un SIG avec l'indexation qui va avec.

Par exemple sur SQL Server 2008, les calculs de distances sur 100 000 points demandent un temps très inférieur à la seconde à la condition que la colonne soit proprement indexée et que la requête incorpore un prédicat "sargeable"...

A +

[nine]

Merci a vous deux,

j'ai tenté l'approche postgis mais je n'ai malheureusement pas les temps de reposne de SQLpro : qu'entends tu pas "correctement indexé" ?

voici ce que j'avais tenté pour ma part :

AddGeometryColumn pour integrer les poitn sous forme d'objet postgis
create index ....using GIST pour l'index spatial

rberthou tu proposes un decoupage par zone, oui mais sous quel critere ? les points sont aleatoire et se trouve sur toute la france. Retrouver pour chaque point la zone dans laquelle il se trouve puis calculer sa distance ne prendra pas t'il pas autant de temps ?

Les temps de reponses de Postgis sont decevant, c'est pour cela que je me suis tournee vers du sql classique

je ne dois balayer la table que pour les points tombant en dehors (en fixant un seuil a 10%, au dela le fichier n'est pas traité) j'esperais trouver une solution satisfaisante en me tournant une fois de plus vers du sql standart, et faire ca en 2 passes :

pour la premiere passe (point dans la grille) je ramasse les valeurs en mettant distance à zero. ca c'est OK

pour la deuxieme passe (point en dehors de la grille) : je compte faire un updtate sur distance. ca c'est moins bien.
j'ai un peu de mal a construire la requete d'update :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
update resultat set distance = (SELECT  ((a.x_cal-b.x)^2 + (a.y_cal-b.y)^2)^0.5 AS d  
  FROM _1datauser a, _1couche b 
 WHERE ((a.x_cal-b.x)^2 + (a.y_cal-b.y)^2)^0.5 = 
             ( SELECT min(((a.x_cal-z.x)^2 + (a.y_cal-z.y)^2)^0.5) 
                 FROM _1couche z
                WHERE  a.x_cal <> z.x 
                   OR  a.y_cal <> z.y
              )
) where resultat.id = a.id

mais j'ai une erreru sur a : qu'il ne reconnait pas.

encore un peu d'aide ! merci

n

[rberthou]

Le découpage en zone cela reste fonctionnelle.
Si tu n'as rien qui te semble "naturelle" un simple découpage en "carrés" reste le plus simple et cela te permet relativement simplement de n'effectuer de recherche que dans les carrés adjacents (traitement en plusieurs passes ou tu agrandie le périmètre a chaque passe te limitant au données non traitées).

Concernant ta requete tu dois déjà supprimer la racine carré dans ta clause where cela ne sert a RIEN.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
WHERE ((a.x_cal-b.x)^2 + (a.y_cal-b.y)^2)^0.5 =
( SELECT min(((a.x_cal-z.x)^2 + (a.y_cal-z.y)^2)^0.5)

est equivalent à

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
WHERE ((a.x_cal-b.x)^2 + (a.y_cal-b.y)^2) =
( SELECT min(((a.x_cal-z.x)^2 + (a.y_cal-z.y)^2))

[SQLpro]

Surtout rendre SARGEABLE votre prédicat, c'est à dire qu'il y ait une seule colonne d'un côté de l'égalité.

A +

[nine]

encore merci

voila j'ai fait autrement (j'espere ne pas vous choquez!) car je ne peux pas, a ce stade revenir en arriere, surtout que ma maitrise de postgis, sql n'est pas terrible...

je pars du principe que puisque le calcul des distances ne se fait qu'au deça d'un seuil de 10%, mes points en dehors de la grille ne seront pas si nombreux finalement. ensuite 120000 lignes c'est le maxi.

- importation des donnees utilisateur dans une table tmp_user (x,y)
- creation de la table resultat via un left join sur la table source pour garder la totalite des points utilisateurs, je met distance a zero
-dans un curseur je boucle sur les valeur a null (donc forcement mes poitns en dehors de la grille) et pour chaque point je fais un update sur distance.

voila, c pas tres classieux mais il semblerait que ca marche, sur ma table de test en tout cas ! j'attend mes resultats grandeur nature ...ca tourne encore!

a+

n

[pacmann]

Salut !

Je ne sais pas à quel point c'est viable... mais pour aller dans le sens du découpe, on peut tenter une méthode : découper en carrés ayant le même nombre de points !
J'ai lu que Postgres a fini par implémenter les fonctions analytiques...
... peut être ont-ils également implémenté le n-tile qui permet de subdiviser un ensemble de points en "n" tranches égales ?
Sinon, il faut le faire à la main.

L'idée :
Tu découpes l'ensemble de points référence en 20 parties égales sur les abscisses (un peu comme définir des fuseaux).
Pour chacun de ces fuseaux, qui définissent donc des colonnes de points, tu découpes à nouveau en 20 parties égales, sur les ordonnées cette fois.

=> Tu as donc un découpage de 400 cases contenant le même nombre de points.

Maintenant, il faut que tu références ces cases, par exemple par un numéro, avec pour chacune d'elle x-min y-min x-max y-max.
Cette table des cases devra être indexée de manière à retrouver à quel point appartient un point.
Dans ta table de référence, tu peux affecter à chaque point son numéro de case, puis indexer la table sur ce numéro.

A présent, quand tu itères sur les points users, tu identifies la case dans laquelle il se trouve, ce qui te permet de ne calculer "que" 120000 / 400 = 300 points...

Bon, ça reste assez gros. Bien entendu, quand tu rend les cases plus petites, ça diminue le nombre de distances à calculer... mais ça augmente le travail de préparation !

Maintenant, à défaut de mieux, si tu poses bien le problème (en terme de complexité), tu dois pouvoir ramener la finesse optimale du découpe à un problème de première littéraire.