Recherche Du Voisin Le Plus Proche: Python

j'ai un 2 dimensions tableau:

MyArray = array([6588252.24, 1933573.3, 212.79, 0, 0],
                [6588253.79, 1933602.89, 212.66, 0, 0],
                 etc...)

Les deux premiers éléments MyArray[0] et MyArray[1] sont les X et O coordonnées des points.

pour chaque élément du tableau, je voudrais trouver le plus rapide façon de rendre son plus proche voisin dans un rayon de X unités. Nous supposons que c'est dans L'espace 2D.

disons pour cet exemple X = 6.

j'ai résolu le problème en comparant chaque élément à chaque autre élément, mais cela prend environ 15 minutes lorsque votre liste est longue de 22k points. Nous espérons pouvoir éventuellement l'exécuter sur des listes d'environ 30 millions de points.

j'ai lu sur les arbres K-d et je comprends le concept de base, mais j'ai eu du mal à comprendre comment les écrire.

19
demandé sur Dlinet 2012-10-17 01:20:09

1 réponses

merci à John Vinyard d'avoir suggéré scipy. Après quelques bonnes recherches et essais, voici la solution à cette question:

préalables: Installez Numpy et SciPy

  1. importer les Modules SciPy et Numpy

  2. faites une copie du tableau en 5 dimensions incluant les valeurs X et Y.

  3. Créer une instance d'un cKDTree comme exemple:

    YourTreeName = scipy.spatial.cKDTree(YourArray, leafsize=100)
#Play with the leafsize to get the fastest result for your dataset

  4. interrogez le 

    for item in YourArray:
    TheResult = YourTreeName.query(item, k=1, distance_upper_bound=6)

    pour chaque élément YourArray,TheResult sera un tuple de la distance entre les deux points, et l'index de l'emplacement du point dans YourArray.

23
répondu Dlinet 2018-04-27 14:37:01