matlab - usar - Encontrando vecinos cercanos
title of plot matlab (3)
Estoy de acuerdo en que los bordes de celdas compartidas son un criterio de buen vecino (basado en este ejemplo). Si estuviera utilizando una estructura de datos orientada a la malla (como algo de Gts), la identificación de bordes compartidos sería trivial.
Matlab, por otro lado, hace esto más "interesante". Suponiendo que las celdas voronoi se almacenan como parches, puede intentar obtener la propiedad del parche ''Caras'' (consulte esta referencia ). Eso debería devolver algo así como una matriz de adyacencia que identifica los vértices conectados. A partir de eso (y un poco de magia), deberías poder determinar los vértices compartidos y luego inferir los bordes compartidos. En mi experiencia, este tipo de problema de "búsqueda" no se adapta bien a Matlab; si es posible, recomiendo cambiar a un sistema más adecuado para las consultas de conectividad de malla.
Necesito encontrar vecinos "cercanos" entre un conjunto de puntos.
Hay 10 puntos en la imagen de arriba. Las líneas rojas son bordes de la Triangulación de Delaunay , las estrellas negras marcan las líneas medias de los bordes, las líneas azules son la teselación de Voronoi . El punto 1 tiene tres vecinos "cercanos", es decir, 4, 6 y 7, pero no 2 y 3, que están casi en línea con el borde 1-7, pero mucho más lejos.
¿Cuál es una buena manera de identificar a los vecinos cercanos (o bordes "buenos")? Mirando la figura, me parece que la selección de bordes cuyo punto medio cae en la intersección con las líneas Voronoi, o considerar como vecinos "cercanos" a los que tocan celdas Voronoi podría ser una buena solución (la clasificación de 3-5 puede ir de cualquier manera). ¿Existe una manera eficiente de implementar cualquiera de las soluciones en Matlab (me encantaría obtener un buen algoritmo general que luego pueda traducir a Matlab, por cierto)?
Otra posibilidad, más simple que crear triangulaciones o diagramas de voronoi, es usar una matriz de vecindario .
Primero coloca todos tus puntos en una matriz cuadrada 2D. Luego puede ejecutar una ordenación espacial completa o parcial, por lo que los puntos se ordenarán dentro de la matriz.
Los puntos con una Y pequeña podrían moverse a las filas superiores de la matriz, y de la misma manera, los puntos con una Y grande irían a las filas inferiores. Lo mismo ocurrirá con puntos con pequeñas coordenadas X, que deben moverse hacia las columnas de la izquierda. Y simétricamente, los puntos con un gran valor de X irán a las columnas de la derecha.
Después de realizar el ordenamiento espacial (hay muchas formas de lograrlo, tanto mediante algoritmos en serie como en paralelo), puede buscar los puntos más cercanos de un punto P determinado simplemente visitando las celdas adyacentes donde el punto P se almacena en la matriz de vecindario.
Puede leer más detalles sobre esta idea en el siguiente documento (encontrará copias en PDF de la misma en línea): Supermassive Crowd Simulation en GPU basado en el comportamiento emergente .
El paso de clasificación le da opciones interesantes. Puede usar solo el orden de transposición par impar descrito en el documento, que es muy simple de implementar (incluso en CUDA). Si ejecuta solo una pasada de esto, le dará una ordenación parcial, que ya puede ser útil si su matriz está casi ordenada. Es decir, si sus puntos se mueven lentamente, le ahorrará muchos cálculos.
Si necesita una clasificación completa, puede ejecutar un pase de transposición incluso impar varias veces (como se describe en la siguiente página de Wikipedia):
Puede implementar su primera idea de seleccionar bordes cuyos puntos medios caen en la intersección con las líneas Voronoi haciendo uso de la clase DelaunayTri y sus edges y los métodos más nearestNeighbor . Aquí hay un ejemplo con 10 pares aleatorios de valores x e y :
x = rand(10,1); %# Random x data
y = rand(10,1); %# Random y data
dt = DelaunayTri(x,y); %# Compute the Delaunay triangulation
edgeIndex = edges(dt); %# Triangulation edge indices
midpts = [mean(x(edgeIndex),2) ... %# Triangulation edge midpoints
mean(y(edgeIndex),2)];
nearIndex = nearestNeighbor(dt,midpts); %# Find the vertex nearest the midpoints
keepIndex = (nearIndex == edgeIndex(:,1)) | ... %# Find the edges where the
(nearIndex == edgeIndex(:,2)); %# midpoint is not closer to
%# another vertex than it is
%# to one of its end vertices
edgeIndex = edgeIndex(keepIndex,:); %# The "good" edges
Y ahora, edgeIndex es una matriz N-por-2 donde cada fila contiene los índices en x e y para un borde que define una conexión "cercana". La siguiente gráfica ilustra la triangulación de Delaunay (líneas rojas), el diagrama de Voronoi (líneas azules), los puntos medios de los bordes de triangulación (asteriscos negros) y los bordes "buenos" que permanecen en el edgeIndex de edgeIndex (líneas rojas gruesas):
triplot(dt,''r''); %# Plot the Delaunay triangulation
hold on; %# Add to the plot
plot(x(edgeIndex).'',y(edgeIndex).'',''r-'',''LineWidth'',3); %# Plot the "good" edges
voronoi(dt,''b''); %# Plot the Voronoi diagram
plot(midpts(:,1),midpts(:,2),''k*''); %# Plot the triangulation edge midpoints
Cómo funciona...
El diagrama de Voronoi consta de una serie de polígonos o celdas de Voronoi. En la imagen anterior, cada celda representa la región alrededor de un vértice de triangulación dado que encierra todos los puntos en el espacio que están más cerca de ese vértice que cualquier otro vértice. Como resultado de esto, cuando tiene 2 vértices que no están cerca de ningún otro vértice (como los vértices 6 y 8 en su imagen), el punto medio de la línea que une esos vértices cae en la línea de separación entre las celdas Voronoi para el vértices.
Sin embargo, cuando hay un tercer vértice que está cerca de la línea que une 2 vértices dados, entonces la celda Voronoi para el tercer vértice puede extenderse entre los 2 vértices dados, cruzando la línea que los une y encerrando esas líneas en el punto medio. Este tercer vértice, por lo tanto, puede considerarse un vecino "más cercano" a los 2 vértices dados que los 2 vértices entre sí. En su imagen, la celda Voronoi para el vértice 7 se extiende hacia la región entre los vértices 1 y 2 (y 1 y 3), por lo que el vértice 7 se considera un vecino más cercano al vértice 1 que el vértice 2 (o 3).
En algunos casos, este algoritmo puede no considerar dos vértices como vecinos "cercanos" a pesar de que sus celdas Voronoi se toquen. Los vértices 3 y 5 en su imagen son un ejemplo de esto, donde el vértice 2 se considera un vecino más cercano a los vértices 3 o 5 que los vértices 3 o 5 están entre sí.