Algorithme pour trouver des points proches?

Question

Avec un ensemble de plusieurs millions de points avec les coordonnées x, y, quel est l'algorithme de choix pour trouver rapidement les 1000 meilleurs points les plus proches d'un emplacement? " rapidement " signifie ici environ 100 ms sur un ordinateur à la maison.

La force brute impliquerait de faire des millions de multiplications puis de les trier. Même si une simple application Python peut le faire en moins d’une minute, cela reste trop long pour une application interactive.

Le cadre de sélection des points sera connu, il serait donc possible de partitionner l’espace en une simple grille. Cependant, les points étant répartis de manière inégale, je suppose que la plupart des carrés de la grille seraient vides et que, par la suite, certains d'entre eux contiendraient une grande partie des points.

Éditer: Il n'est pas nécessaire que les réponses soient exactes, elles peuvent en réalité être assez imprécises. Ce ne serait pas un gros problème si les 1000 meilleurs ne sont en réalité que quelques points aléatoires parmi les 2000 meilleurs, par exemple.

Modifier: l'ensemble des points change rarement.

Answer 1

Pourquoi ne pas utiliser quadtree ?

Vous divisez une zone en rectangles. Si la zone a une faible densité de points, les rectangles sont grands et si une zone a une densité élevée de points, les rectangles seront petits. Vous subdivisez chaque rectangle de manière récursive en quatre sous-rectangles jusqu'à ce que les rectangles soient suffisamment petits ou ne contiennent que peu de points.

Vous pouvez alors commencer à regarder des points dans des rectangles proches de l'emplacement et vous déplacer vers l'extérieur jusqu'à ce que vous ayez trouvé vos 1 000 points.

Le code pour cela pourrait devenir un peu complexe, alors peut-être devriez-vous d'abord essayer avec la grille simple et voir si elle est assez rapide.

Answer 2

Les

Quadtrees sont bien, mais les arbres BSP sont garantis pour fonctionner dans le temps O (log n) . Je pense que les quadtrees nécessitent un volume limite fini et qu'il existe certains cas dégénérés où les quadtrees échouent lamentablement, par exemple lorsqu'un grand nombre de points occupe le même espace relativement petit.

Cela étant dit, les quadruples sont sans doute plus faciles à mettre en oeuvre et assez efficaces dans la plupart des situations courantes. C'est ce que UPS utilise dans ses algorithmes de routage, car ses inconvénients ne posent pas de problèmes majeurs dans la pratique, probablement parce que les villes ont tendance à être réparties sur la région d'intérêt.

Answer 3

Vous voulez utiliser une structure comme un arbre quadrilatéral ou un RTree. Ce sont des structures d’index multidimensionnelles.

La clé consiste à utiliser une & bonne "courbe de remplissage d'espace &", ce qui permet de définir la proximité des points. Une courbe de remplissage d'espace simple est un Zorder, mais vous seriez plus intéressé par quelque chose comme une courbe d'Hilbert.

http://en.wikipedia.org/wiki/Space_filling_curve

Je ne connais aucune implémentation de ce type de produit pré-emballée. J'ai récemment mis en place mon propre RTree en 2 dimensions qui ne prend en charge que le chargement en bloc et les recherches (via un cadre de sélection fourni).

Un inconvénient ici est que vos points doivent être contenus dans une région finie. Il existe des courbes de remplissage d’espace qui fonctionnent pour des espaces qui ne sont pas finis, mais je ne les connais pas.

Answer 4

Outre les suggestions d'arborescence QuadTree et BSP, vous devez rechercher la recherche du voisin le plus proche . . Le choix de l'algorithme dépend de la fréquence à laquelle vous ajoutez des données à votre jeu de données de base. Si vous ajoutez et supprimez souvent, les solutions d'arborescence sont supérieures. Si les données sont plus statiques, la recherche par le voisin le plus proche et les diagrammes de voronoï peuvent être beaucoup plus rapides et mieux dimensionnés.

Answer 5

Si l'ensemble de points change rarement, vous pouvez également envisager d'utiliser un diagramme de voronoï. Je ne suis pas sûr que cela aide à retrouver plus rapidement le premier point, mais cela devrait faciliter la recherche des 999 points suivants.

Answer 6

Je suppose que les points se trouvent dans une base de données ou dans un emplacement indexé pouvant faire l'objet d'une recherche? Si c'est le cas, cela devrait être assez rapide. A partir du point donné, vous pouvez avoir une plage sur les axes x et y et obtenir tous les emplacements compris dans cette plage (c.-à-d. Spécifier le coin supérieur gauche x (a) et y (b) et le coin inférieur droit x (c) et y (ré)).

Puis faites une requête où pour des points où y > = b ET y < = d ET x > = a ET x < = c. ce sera rapide en supposant que vous ayez des index sur les coordonnées x et y séparément. (en supposant que l'origine est 0,0 en haut à gauche).

Vous pouvez ensuite augmenter (ou diminuer si le résultat est énorme) cette plage de z jusqu'à ce que le nombre de points dans le jeu de résultats soit > = 1000. Grâce à certains essais, vous devriez pouvoir obtenir un écart type et autres nombres statistiques qui vous aideront à déterminer la taille du rectangle pour commencer. Votre programme peut également se régler lui-même en fonction des résultats obtenus.

Une fois que vous avez défini les données brutes, vous aurez besoin de quelques calculs simples pour calculer la distance entre chaque point et le point source.

Answer 7

Je sais que cela a été dit comme n'étant pas le plus rapide si vous voulez des résultats VRAIMENT VRAIMENT rapides en voyant que j'ai trouvé cet article de Google, je pensais ajouter ma solution SQL que j'avais utilisée il y a quelque temps sous la forme d'un proc . Il recherche les emplacements proches du coord et les renvoie par la distance.

J'espère que ça aide quelqu'un:)

CREATE PROCEDURE [dbo].[getstores] @lat float,  @lng float AS
DECLARE @radius float, @DegToRad float
SET @DegToRad = 57.29577951
SET @radius = 25000
SELECT TOP 10
    name
    ,sto_lat
    ,sto_lng
    ,postcode
    ,ROUND((ACOS((SIN(@lat/57.2958) * SIN(sto_lat/@DegToRad)) +(COS(@lat/@DegToRad) * COS(sto_lat/@DegToRad) *COS(sto_lng/@DegToRad - @lng/@DegToRad))))* 6387.7, 2) AS distance
FROM store
WHERE (sto_lat >= @lat - (@radius/111))
And (sto_lat <= @lat + (@radius/111))
AND (sto_lng >= @lng - (@radius/111))
AND (sto_lng <= @lng + (@radius/111))
AND (
     ISNUMERIC(sto_lat) = 1
    AND
    ISNUMERIC(sto_lat) = 1
)
ORDER BY distance

REMARQUE: j'ai déjà indiqué qu'il ne s'agissait pas de la meilleure solution pour cette question simplement peut-être pour quelqu'un qui l'a trouvé sur Google comme moi

.