Discussion :

[yoshï]

Bonjour,
Je stocke dans une BDD des coordonnées de points sous la forme (X,Y).
L'utilisateur de mon service va émettre une requête avec des coordonnées concernant sa localisation sous cette même forme (X,Y) et un rayon de recherche (un entier).

Il s'agit pour moi ensuite de renvoyer le premier élément (point) de la base inclus dans le périmètre de recherche.

Pour cela, la première méthode qui me vient à l'esprit c'est de calculer la norme du vecteur que forme le pointUtilisateur avec chacun des points de la BDD. Si cette norme est inférieure au rayon alors le point est dans le périmètre de recherche.

Le pb évident, c'est que le temps de traitement va exploser si la BDD est grosse.
Est ce que vous voyez un moyen d'organiser les données de manière à optimiser ce type de traitement ou est ce que vous voyez une méthode plus simple pour renvoyer le premier élément inclus dans le périmètre.

Je continue à réfléchir de mon côté. Merci d'avance pour votre aide

[ToTo13]

Bonsoir,

je sais qu'il y a des optimisations de ce type utilisées dans l'algorithmes des k plus proches voisins.
C'est des partitions de l'espace afin de limiter la recherche.
Mais je n'ai rien programmé de ce genre... donc je ne peux t'aider plus.

[Graffito]

Soit X0 et Y0 les coordonées point et R la distance.
On peut faire une préselection ainsi

Code :

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

1
2
 
SELECT * WHERE (X<= X0+D) AND (X>= X0-D) AND (Y<= Y0+D) AND (Y>= Y0-D)

Puis sur les quelques records selectionnés, faire le vrai calcul de la norme
ou si le gestionnaire de la base de donnée est rapide et optimise les "AND" :

Code :

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

1
2
3
4
 
D2=D*D
SELECT * WHERE (X<= X0+D) AND (X>= X0-D) AND (Y<= Y0+D) AND (Y>= Y0-D) 
AND ( (X0-X)(X0-X)+(Y0-Y)(Y0-Y)<D2 )

Si on veut encore plus optimiser, on peut :
- diviser l'espace en carrés,
- associer un nombre à chacun des carrés et ajouter ce champs à la table de la base de donnée,
- indexer ce champ,
- lors d'une recherche, déterminer les carrés C1, C2, Cn qui peuvent être concernées,
Exemple :

Code :

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

1
2
 
SELECT * WHERE (CARRE=C1 OR CARRE=C2 ....) AND ( (X0-X)(X0-X)+(Y0-Y)(Y0-Y)<D2 )-

[10_GOTO_10]

Tu peux aussi utiliser les quadtree, qui sont en principe assez performants pour ce genre de recherche.

Attention, il faut tester la proximité par rapport aux segments du périmètre, et non par rapport aux sommets comme tu semble le faire: si les segments sont grands, un point peut être très proche d'un segment tout en étant éloigné des sommets.

[Nebulix]

Les algos de recherche sont performants si les données sont triées
mais
il n'existe pas de relation d'ordre à 2 dimensions
Un bon compromis serait de trier tes données selon X
la recherche des points entre X-R et X+R serait d'ordre log(N)
Passer les points de cet intervalle en revue devrait être possible en un temps raisonnable

[pseudocode]

il n'existe pas de relation d'ordre à 2 dimensions

?

(a,b) ≤ (c,d) <==> (a < c) ou (a = c et b ≤ d)

[Nebulix]

(a,b) ≤ (c,d) <==> (a < c) ou (a = c et b ≤ d)

Je voulais dire pas de relation d'ordre ayant une quelconque utilité dans R²
Qui a entendu parler d'une relation d'ordre pour les nombres complexes ?
(1,1)<(1,99999999)<(2,1)

[souviron34]

Un bon compromis serait de trier tes données selon X

Un meilleur compromis encore serait de trier les points en "matrice-like", selon X, et à X égal selon Y..

En un seul quick sort (N logN)

[Nebulix]

Un meilleur compromis encore serait de trier les points en "matrice-like", selon X, et à X égal selon Y..

En un seul quick sort (N logN)

Si les X sont des réels, le cas d'égalité n'arrivera jamais (tu connais le problème des tests d'égalité de réels )
Si les X prennent un nombre fini de valeurs, il faudra quand même chercher les bons Y pour un nombre >1 de valeurs de X donc dans une liste non triée...

[Aleph69]

Bonjour,

l'approche classique consiste à utiliser des KD-trees et on peut trouver tout ce qu'il faut d'un point de vue informatique pour le calcul rapide des plus proches voisins dans la troisième édition des Numerical Recipes (celle de 2007).

[souviron34]

Si les X sont des réels, le cas d'égalité n'arrivera jamais (tu connais le problème des tests d'égalité de réels )
Si les X prennent un nombre fini de valeurs, il faudra quand même chercher les bons Y pour un nombre >1 de valeurs de X donc dans une liste non triée...

D'une part un seuil en précision règle le problème d'égalité.

D'autre part, cela réduit quand même considérablement...

On n'explore plus que dans un rayon R... (avec des raccourcis possibles et un arrêt si on explore dans chaque sens autour du X le plus proche)..

Mais ma formulation n'était pas tout à fait exacte...

[Nebulix]

D'une part un seuil en précision règle le problème d'égalité.

D'autre part, cela réduit quand même considérablement...

Un tri grossier peut être fait en 2D et se révèle donc plus efficace qu'un tri fin.
Joli !