Ho 2 liste con coordinate X, Y di punti. L'elenco 1 contiene più punti rispetto all'elenco 2.Trovare i migliori punti di abbinamento da 2 vettori
Il compito è trovare coppie di punti in modo che la distanza euclidea complessiva sia ridotta al minimo.
Ho un codice funzionante, ma non so se questo è il modo migliore e mi piacerebbe avere un suggerimento su cosa posso migliorare per risultato (algoritmo migliore per trovare il minimo) o velocità, perché la lista è circa 2000 elementi ciascuno.
Il round nei vettori di esempio è implementato per ottenere anche punti con le stesse distanze. Con la funzione "rdist" tutte le distanze sono generate in "distanze". Il minimo della matrice è usato per collegare 2 punti ("dist_min"). Tutte le distanze di questi 2 punti sono ora sostituite da NA e il ciclo continua cercando il minimo successivo fino a quando tutti i punti della lista 2 hanno un punto dalla lista 1. Alla fine ho aggiunto un grafico per la visualizzazione.
require(fields)
set.seed(1)
x1y1.data <- matrix(round(runif(200*2),2), ncol = 2) # generate 1st set of points
x2y2.data <- matrix(round(runif(100*2),2), ncol = 2) # generate 2nd set of points
distances <- rdist(x1y1.data, x2y2.data)
dist_min <- matrix(data=NA,nrow=ncol(distances),ncol=7) # prepare resulting vector with 7 columns
for(i in 1:ncol(distances))
{
inds <- which(distances == min(distances,na.rm = TRUE), arr.ind=TRUE)
dist_min[i,1] <- inds[1,1] # row of point(use 1st element of inds if points have same distance)
dist_min[i,2] <- inds[1,2] # column of point (use 1st element of inds if points have same distance)
dist_min[i,3] <- distances[inds[1,1],inds[1,2]] # distance of point
dist_min[i,4] <- x1y1.data[inds[1,1],1] # X1 ccordinate of 1st point
dist_min[i,5] <- x1y1.data[inds[1,1],2] # Y1 coordinate of 1st point
dist_min[i,6] <- x2y2.data[inds[1,2],1] # X2 coordinate of 2nd point
dist_min[i,7] <- x2y2.data[inds[1,2],2] # Y2 coordinate of 2nd point
distances[inds[1,1],] <- NA # remove row (fill with NA), where minimum was found
distances[,inds[1,2]] <- NA # remove column (fill with NA), where minimum was found
}
# plot 1st set of points
# print mean distance as measure for optimization
plot(x1y1.data,col="blue",main="mean of min_distances",sub=mean(dist_min[,3],na.rm=TRUE))
points(x2y2.data,col="red") # plot 2nd set of points
segments(dist_min[,4],dist_min[,5],dist_min[,6],dist_min[,7]) # connect pairwise according found minimal distance
Trovare la domanda sulla competizione con la materia oscura, forse? –
Pseudo codice sarebbe facile da scrivere: 'for (i in 1st.set.points) {per (j in j 2nd.set.points) {calcola: sqrt ((x1st.set.ponint-x2nd.set.points)^2 + (y1st.set.ponint-y2nd.set.points)^2), salva ogni valore risultante quindi chiama la funzione min() per determinare quale ha il valore più basso}} ' –
Ciao java_xof, penso che sia il modo in cui io aveva fatto.? 'distanze <- rdist (x1y1.data, x2y2.data)' fornisce la matrice di tutte le distanze e 'che (distanze == min (distanze, na.rm = TRUE), arr.ind = TRUE)' cerca i minuti in la matrice. Ma nel caso ci siano coppie con lo stesso min. distanza non so se quale coppia scegliere. – user1716533