cómo encontrar k-ésimo vecino más cercano de un punto en un conjunto de punto

Tengo un conjunto de puntos (x, y) en un plano 2d. Dado un punto (x0, y0) y el número k, cómo encontrar el k-ésimo vecino más cercano de (x0, x0) en el conjunto de puntos. En detalle, el conjunto de puntos está representado por dos matrices: x e y. El punto (x0, y0) viene dado por el índice i0. Significa x0 = x (i0) y y0 = y (i0).cómo encontrar k-ésimo vecino más cercano de un punto en un conjunto de punto

¿Hay alguna función o algo en Matlab me ayuda este problema. Si Matlab no tiene ese tipo de función, puede sugerir otras formas efectivas.

EDIT: Tengo que calcular este tipo de distancia para cada punto (x0, y0) en el conjunto. El tamaño del conjunto es aproximadamente 1000. El valor de k debe ser aproximadamente sqrt (1500). Lo peor es que hago esto muchas veces. En cada iteración, el conjunto cambia y vuelvo a calcular las distancias. Entonces, el tiempo de ejecución es un problema crítico.

Fuente

2012-02-22 James Do

si va a hacer esta comprobación para muchos puntos es posible que desee construir una tabla de distancias entre puntos en la primera

squareform(pdist([x y]))

Fuente

2012-02-23 01:47:43 zamazalotta

Sí. Haré esto por cada punto del conjunto. Por lo tanto, algún tipo de tabla de distancia ayudaría a ahorrar el tiempo de ejecución. Descubriré cómo funciona la forma cuadrada en mi problema. Muchas gracias. –

la función es pdist en realidad, squareform simplemente hace una matriz cuadrada de salida de vector de pdist – zamazalotta

gracias zamazalotta. Entiendo. –

Si tiene la caja de herramientas de estadísticas, puede usar la función knnsearch.

Fuente

2012-02-22 21:57:39 3lectrologos

knnsearch parece ser una solución, pero no estoy seguro acerca de cómo aplicar a mi knnsearch problema exactamente. Lo encontraré. De todos modos, ¿puedes darme más detalles sobre la forma en que usas knnsearch? Muchas gracias. –

¿Ha mirado la ayuda de Matlab (agregó un enlace a mi respuesta anterior)? – 3lectrologos

Leí el documento en línea sobre knnsearch pero me resulta un poco complicado y realmente no tengo mucho tiempo para entenderlo y usarlo. Intenté el enfoque más simple. Se necesita más tiempo de ejecución, pero intentaré ese enfoque primero. Gracias por tu ayuda. –

Un algoritmo de fuerza bruta sería algo como esto:

array x[n] =() 
array y[n] =() 
array d[n] =() 

... populate x and y arrays with your n points ... 

/* step over each point and calculate its distance from (x0, y0) */ 
for i = 1 to n 
do 
    d[i] = distance((x0, y0), (x[i], y[i]) 
end 

/* sort the distances in increasing order */ 
sort(d) 

/* the k'th element of d, is the k'th nearest point to (x0, y0) */ 
return d[k]

Fuente

2012-02-22 21:59:32 ardnew

gracias por su ayuda! –

El método de fuerza bruta se ve algo como esto:

%Create some points 
n = 10; 
x = randn(n,1); 
y = randn(n,1); 

%Choose x0 
ix0 = randi(n); 

%Get distances 
d = sqrt(... 
    (x - x(ix0)).^2 + ... 
    (y - y(ix0)).^2); 

%Sort distances 
[sorted_Dstances, ixSort] = sort(d); 

%Get kth point 
k = 3; 
kth = [x(ixSort(k+1)); y(ixSort(k+1))]; %+1 since the first element will always be the x0 element.

Fuente

2012-02-22 22:00:28 Pursuit

¿No debería eliminar el elemento en sí? Piensa en el caso k = 1 –

Buen punto. Por lo general, no me gusta cambiar el tamaño de los vectores de partidos como este. Tal vez agregue un '+1' a la indexación final. EDITAR: aunque eso deja un espacio si hay un punto idéntico al punto inicial. Si quiere garantizar que la respuesta es un punto diferente, incluso cuando algún punto sea igual, entonces se necesita más trabajo. – Pursuit

@Pursuit no tiene sentido eliminar también los puntos iguales. si tienes 5 puntos iguales hasta el punto que estás buscando, la tercera distancia más lejana debería ser 0 – ardnew

El libre y de código abierto VLFeat caja de herramientas contiene una implementación kd-árbol, entre otras cosas útiles.

Fuente

2012-02-22 22:34:56 Maurits

muchas gracias. Encontraré si puede ayudar. –

cómo encontrar k-ésimo vecino más cercano de un punto en un conjunto de punto

Respuesta

Cuestiones relacionadas