Interpolazione strutturati X, Y, Z Dati sulle migliori griglia in base vicina distanza prossimo per ogni punto

Question

Questa questione è stata modificato dopo risposte per mostra soluzione finale ho usato

Ho insiemi di dati 2D non strutturati provenienti da fonti diverse, come nell'esempio: Questi set di dati sono 3 numpy.ndarray (coordinate X, Y e valore Z).

Il mio obiettivo finale è quello di interpolare questi dati su una griglia per la conversione in immagine/matrice. Quindi, ho bisogno di trovare la "griglia migliore" per i dati di tesi interpolati. E per questo ho bisogno di trovare il miglior passo X e Y tra i pixel di quella griglia.

passo Determinato in base alla distanza euclidea tra i punti:

Utilizzare la media delle distanze euclidee tra ciascun punto e il suo vicino più vicino.

• Usa KDTree/cKDTree da scipy.spacial per l'albero build del X, Y dati.
• Utilizzare il metodo query con k=2 per ottenere le distanze (Se k=1, le distanze sono solo pari a zero perché la query per ogni punto si è trovata).

    # Generate KD Tree 
    xy = np.c_[x, y] # X,Y data converted for use with KDTree 
    tree = scipy.spacial.cKDTree(xy) # Create KDtree for X,Y coordinates. 

    # Calculate step 
    distances, points = tree.query(xy, k=2) # Query distances for X,Y points 
    distances = distances[:, 1:] # Remove k=1 zero distances 
    step = numpy.mean(distances) # Result 

performance tweaking:

• L'uso della scipy.spatial.cKDTree e non scipy.spatial.KDTree perché è davvero più veloce.
• Utilizzare balanced_tree=False con scipy.spatial.cKDTree: Grande velocità nel mio caso, ma potrebbe non essere vero per tutti i dati.
• Utilizzare n_jobs=-1 con cKDTree.query per utilizzare il multithreading.
• Utilizzare p=1 con cKDTree.query per utilizzare la distanza di Manhattan al posto della distanza euclidea (p=2): Più veloce ma potrebbe essere meno preciso.
• Interroga la distanza solo per un sottocampione casuale di punti: grande velocità con dataset di grandi dimensioni, ma potrebbe essere meno preciso e meno ripetibile.

punti Per interpolazione sulla griglia:

punti Interpolazione set di dati sulla rete utilizzando il passo calcolato.

    # Generate grid 
    def interval(axe): 
     '''Return numpy.linspace Interval for specified axe''' 
     cent = axe.min() + axe.ptp()/2 # Interval center 
     nbs = np.ceil(axe.ptp()/step) # Number of step in interval 
     hwid = nbs * step/2 # Half interval width 
     return np.linspace(cent - hwid, cent + hwid, nbs) # linspace 

    xg, yg = np.meshgrid(interval(x), interval(y)) # Generate grid 

    # Interpolate X,Y,Z datas on grid 
    zg = scipy.interpolate.griddata((x, y), z, (xg, yg)) 

Set NaN se pixel troppo lontano dalla sigla punti:

Set NaN a pixel da griglia che sono troppo (Distance> passo) dai punti da iniziale X, Y, Z dati. Viene utilizzato il precedente KDTree generato.

    # Calculate pixel to X,Y,Z data distances 
    dist, _ = tree.query(np.c_[xg.ravel(), yg.ravel()]) 
    dist = dist.reshape(xg.shape) 

    # Set NaN value for too far pixels 
    zg[dist > step] = np.nan 

Answer 1

vi consiglio di andare con KDTree.query.

Cercate di una distanza carachteristic per scalare il binning: vi consiglio di prendere solo sottoinsieme casuale dei tuoi punti, e di utilizzare il Manhattan distanza, becasue KDTree.query è molto lento (eppure è una * log (n) complessità).

Ecco il mio codice:

# CreateTree 
tree=scipy.spatial.KDTree(numpy.array(points)) # better give it a copy? 
# Create random subsample of points 
n_repr=1000 
shuffled_points=numpy.array(points) 
numpy.random.shuffle(shuffled_points) 
shuffled_points=shuffled_points[:n_repr] 
# Query the tree 
(dists,points)=tree.query(shuffled_points,k=2,p=1) 
# Get _extimate_ of average distance: 
avg_dists=numpy.average(dists) 
print('average distance Manhattan with nearest neighbour is:',avg_dists) 

vi consiglio di utilizzare la distanza di Manhattan (https://en.wikipedia.org/wiki/Taxicab_geometry), perché è stato più rapido da calcolare rispetto alla distanza euclidea. E poiché è necessario solo uno stimatore della distanza media, dovrebbe essere sufficiente.

Answer 2

Il problema che si desidera risolvere è chiamato "il problema dei vicini più vicini". Vedere questo articolo per esempio: http://link.springer.com/article/10.1007/BF02187718

Credo che le soluzioni siano O (N log N), quindi sullo stesso ordine di KDTree.query, ma in pratica molto, molto più velocemente di un gruppo di query separate. Mi dispiace, non conosco un'implementazione Python di questo.