Tengo dos listas de coordenadas:
s1 = [(0,0), (0,1), (1,0), (1,1)] s2 = [(3,2), (1,9)]Quiero calcular la distancia mínima de cada punto en s1 a cualquier punto en s2. por ejemplo, los resultados deben ser los siguientes.
result = [3.60, 3.16, 2.82, 2.23]Pregunta: ¿Cuál es la forma más optimizada en términos de tiempo de ejecución para lograr este resultado?
Hasta ahora he intentado esto, pero el tiempo de ejecución no es prometedor:
import math def nearestDistance(boundary, p): minDistList = map(lambda b: (b[0] - p[0])**2 + (b[1] - p[1])**2, boundary) minDist2 = min(minDistList) return math.sqrt(float(minDist2)) d = [] for p in s1: d.append(nearestDistance(s2, p))¿Debo cambiar la estructura de s1 y s2 (en lugar de puntos, use matrices 2d, por ejemplo)?
La forma más fácil es probablemente usar scipy.spatial.distance.cdist :
import numpy as np from scipy.spatial import distance s1 = np.array([(0,0), (0,1), (1,0), (1,1)]) s2 = np.array([(3,2), (1,9)]) print(distance.cdist(s1,s2).min(axis=1)) # array([3.60555128, 3.16227766, 2.82842712, 2.23606798]) Se puede obtener algo más de velocidad al generar directamente 0 para cualquier punto de s1 que también esté en s2 .
¿Has probado a usar cdist :
import numpy as np from scipy.spatial.distance import cdist np.min(cdist(s1,s2))devoluciones
array([ 3.60555128, 3.16227766, 2.82842712, 2.23606798]) También puede obtener un aumento de rendimiento al reemplazar s1 y s2 por np.array s, aunque scipy podría estar haciendo eso internamente, no estoy seguro.
Si esto no está lo suficientemente optimizado, creo que puede hacerlo en O(n s2 *log(n s2 ) + n s1 ) encontrando el diagrama de Voronoi de los puntos en s2 y luego recorriendo s1 para ver en qué región se encuentra el punto cae en el que coincidirá con el punto más cercano en s2 .
Para calcular las N distancias, no hay mejor método que la fuerza bruta de todas las posibilidades. Si quisiera algo de mayor nivel, como quizás la distancia más grande o más pequeña, podría reducir la cantidad de cálculos en función de algún conocimiento externo, pero dada su configuración, lo mejor que obtendrá es el rendimiento O (n ^ 2) .
EDITAR: Dado su comentario, existen métodos que involucran el enfoque general de "divide y vencerás". Wikipedia tiene una buena descripción general , y copiaré un poco quizás relevante aquí:
El problema se puede resolver en tiempo O( n log n ) usando el enfoque recursivo de divide y vencerás, por ejemplo, como sigue:
- Ordena los puntos según sus coordenadas x.
- Divide el conjunto de puntos en dos subconjuntos de igual tamaño mediante una línea vertical x = x mid .
- Resuelva el problema recursivamente en los subconjuntos izquierdo y derecho. Esto produce las distancias mínimas del lado izquierdo y del lado derecho d Lmin y d Rmin , respectivamente.
- Encuentre la distancia mínima d LRmin entre el conjunto de pares de puntos en los que un punto se encuentra a la izquierda de la vertical divisoria y el otro punto se encuentra a la derecha.
- La respuesta final es el mínimo entre d Lmin , d Rmin y d LRmin .