Tous les voisins les plus proches en 2D, C++

Je dois trouver pour chaque point de l'ensemble de données tous ses voisins les plus proches. L'ensemble de données contient env. 10 millions de points 2D. Les données sont proches de la grille, mais ne forment pas une grille précise ...Tous les voisins les plus proches en 2D, C++

Cette option exclut (à mon avis) l'utilisation de KD Trees, où l'hypothèse de base est qu'aucun point n'a la même coordonnée x et la même coordonnée y . J'ai besoin d'un algorithme rapide O (n) ou mieux (mais pas trop difficile pour l'implémentation :-))) pour résoudre ce problème ... Du fait que le boost n'est pas standardisé, je ne veux pas utiliser il ...

Merci pour vos réponses ou des exemples de code ...

Source

2010-11-13 Ian

Pourriez-vous donner un exemple de ce que vous cherchez? –

duplication possible de [Choix approprié de la structure de données et de l'algorithme pour la recherche rapide de k-plus proche voisin en 2D] (http://stackoverflow.com/questions/3944649/suitable-choice-of-data-structure-and-algorithm-for -fast-k-nearest-neighbor-searc) – ybungalobill

Je ne comprends pas très bien pourquoi vous ne pouvez pas utiliser kd-trees. Je vais résumer ce que je pense que vous dites: faites-moi savoir où je me trompe. Vous avez un ensemble de 10M points distincts. Ils ne se trouvent pas sur une grille d'entiers, mais sont proches, par exemple, il y a un point (2.01, 1.05) et un autre (1.99.1.03).Ne pourriez-vous pas mettre à l'échelle les points de façon à ce qu'ils reposent tous sur une grille d'entiers, puis utiliser des arbres kd? par exemple, les 2 points ci-dessus pourraient être (201 105) et (199 103). – corriganjc

je faire ce qui suit:

Créer une plus grande grille au-dessus des points. Parcourez linéairement les points et, pour chacun d'eux, déterminez la grande "cellule" à laquelle il appartient (et ajoutez les points à une liste associée à cette cellule).

(Cela peut être fait en temps constant pour chaque point, il suffit de faire une division entière des coordonnées des points.)
maintenant passer par les points de façon linéaire à nouveau. Pour trouver les 10 voisins les plus proches, il suffit de regarder les points des cellules adjacentes, plus grandes.

Étant donné que vos points sont répartis de manière assez uniforme, vous pouvez le faire dans le temps proportionnellement au nombre de points dans chaque (grande) cellule.

Voici un pic (laid) décrivant la situation:

enter image description here

Les cellules doivent être assez grand pour (au centre) et les cellules adjacentes pour contenir les plus proches de 10 points, mais assez petit pour accélérer le calcul. Vous pourriez le voir comme une "fonction de hachage" où vous trouverez les points les plus proches dans le même seau.

(Notez que strictement parlant ce n'est pas O (n) mais en modifiant légèrement la taille des cellules plus grandes, vous devriez obtenir assez près. :-)

Source

2010-11-13 11:57:03 aioobe

Pas seulement adjacente, malheureusement (considérons que les points dans la cellule deux à l'est peuvent être plus proches que les points dans la cellule directement nord-est par exemple, ce problème s'aggrave dans les dimensions supérieures). Aussi, que se passe-t-il si les cellules voisines ont moins de 10 points? En pratique, vous devrez "sortir en spirale". –

Pas dans ce cas particulier: * Les données sont proches de la grille, mais ne forment pas une grille précise ... *. En choisissant des cellules suffisamment grandes, vous pouvez le résoudre comme ça. – aioobe

Et qu'en est-il de LSH? – Ian

Je l'ai utilisé une bibliothèque appelée ANN (approximative la plus proche Voisin) avec beaucoup de succès. Il utilise une approche Kd-tree, bien qu'il y ait plus d'un algorithme à essayer. Je l'ai utilisé pour l'emplacement ponctuel sur une surface triangulée. Vous pourriez avoir de la chance avec ça. Il est minime et a été facile à inclure dans ma bibliothèque juste en laissant tomber dans sa source.

Bonne chance avec cette tâche intéressante!

Source

2010-11-16 11:13:20

Tous les voisins les plus proches en 2D, C++

Répondre

Questions connexes