Manipulación eficiente de una lista de coordenadas cartesianas en Python

Fondo:

Estoy escribiendo un progtwig que maneja grandes cantidades de datos relacionados con las redes de vértices de varias formas regulares. Tengo un generador de trabajo que produce una lista de coordenadas cartesianas correspondientes a los vértices de dichas formas en función de un rango de parámetros de entrada del usuario. Luego, los datos se pasan a los filtros que borran las entradas duplicadas, clasifican los datos y varias otras funciones, desde donde los datos limpiados se envían a un módulo de canvas que recorre y dibuja los vértices.

Pregunta:

Necesito implementar un nuevo filtro que se desplace de manera eficiente a través de las coordenadas, comparando cada par con cada otro par, es decir (x1,y1) -> (x2,y2) a (x1,y1) -> (xn,yn) , (x2,y2) -> (x3,y3) a (x2,y2) -> (xn,yn) etc. para todas las entradas y, por ejemplo, si la relación entre (x1,y1) y (x5,y5) ajusta [(x5-x1)^2+(y5-y1)^2]=vertex_spacing^2 , luego los dos conjuntos de coordenadas se emparejan con sus respectivos números de entrada de lista y se anexan a una nueva lista donde una entrada sería de forma: [(x1,y1), (x5,y5), 0, 4] por ejemplo. ¿Cuál es el método más eficiente para lograr esto?

Mis bashs:

He visto bastantes métodos para manejar listas aquí y en varias guías. He intentado bucles nesteds ‘para’ y ‘si’, pero encontrar mientras este método puede funcionar conduce a tiempos de ejecución excesivamente largos, además de intentar dividir el problema en muchos bucles más pequeños para bucles.

Notas adicionales:

El objective final de esto es utilizar las coordenadas resultantes para los elementos de la interfaz de usuario, y guardarlas e importarlas según sea necesario. La función de las posiciones de lista 0 y 4 en [(x1,y1), (x5,y5), 0, 4] es permitir que la interfaz agrupe las coordenadas para su uso posterior en objetos de canvas. El método debería poder procesar potencialmente miles de coordenadas.

Gracias de antemano por cualquier ayuda. Naturalmente, estoy dispuesto a mejorar la redacción / información que he proporcionado y / o agregar código de ejemplo si no está claro lo que estoy preguntando de alguna manera. ¡Todavía soy bastante nuevo en esto! 🙂

Lo que básicamente estás comprobando es:

para cada vértice v , encuentre todos los vértices u manera que u esté en el círculo del radio vertex_spacing alrededor de v .

Si la distribución de sus puntos es tal que no todos los puntos están juntos, pienso en dos enfoques para acelerar la búsqueda:

  1. La forma más sencilla de acelerar este proceso sería ordenar los puntos por coordenada x. De esa manera, es posible que puedas saltarte muchas comparaciones. Como ejemplo simple, supongamos que las coordenadas x son [1, 2, 10, 15, 18, 20, 21] y vertex_spacing = 5 . Solo necesitas comparar el primer vértice con el segundo, porque todos los otros vértices están obviamente fuera del círculo alrededor del primer vértice.

    Tenga en cuenta que este enfoque es inútil si todos los puntos están muy juntos. En otras palabras, si vertex_spacing = 25 , no puedes omitir ninguna comparación.

  2. En la misma línea, podrías usar un árbol kd bidimensional. Esto es equivalente al enfoque de clasificación, pero en dos dimensiones. Dado un vértice (x, y) y vertex_spacing = v , tendría que verificar todos los puntos en el rango ([xv, x+v], [yv, y+v]) . Usando el mismo ejemplo que antes, suponga que el primer punto tenía coordenadas (1, 0) y el segundo (2, 10) , no habría necesidad de comparar el primer vértice con nada.

Ambos enfoques son heurísticos y no ofrecen ninguna mejora en el peor tiempo de ejecución (todo lo contrario: también tiene la sobrecarga de la clasificación / construcción del árbol kd), pero si los vértices suelen vertex_space separados al menos por vertex_space , esto podría acelerar su búsqueda mucho

Fui demasiado lento para vencer la descripción de Heuster del algoritmo, pero aquí hay una implementación del enfoque de coordinar ordenado por x:

 def pairs(coords, vertex_spacing): results = [] vsquared = vertex_spacing * vertex_spacing coords = sorted(coords) for ia, (xa, ya) in enumerate(coords): for ib, (xb, yb) in enumerate(coords[ia:]): dx = xb - xa if dx > vertex_spacing: break dy = yb - ya if dx * dx + dy * dy == vsquared: results.append([(xa, ya), (xb, yb), ia, ia + ib]) return results 

… y aquí está en acción:

 >>> coords = list((x, y) for x in range(100) for y in range(100)) >>> p = pairs(coords, 5) >>> from random import choice >>> choice(p) [(93, 36), (96, 40), 9336, 9640] >>> choice(p) [(9, 57), (13, 54), 957, 1354] >>> choice(p) [(46, 69), (46, 74), 4669, 4674] 

En mi máquina, los pairs(coords, 5) toman 1.5 segundos para verificar 10,000 pares de coordenadas (y 0.15 segundos para verificar 2,500).

EDITAR : Olvidé agregar ia a ib para compensar la enumeración a través de una porción – corregida ahora.

Las partes más lentas de su algoritmo son el manejo separado de las coordenadas x e y el cálculo de la hipotenusa. Ambos pueden acelerarse utilizando el tipo de número complejo nativo de Python:

 >>> from itertools import starmap >>> parray = list(starmap(complex, [(5, 1), (8.5, 3), (3.75, 4.25)])) >>> a = parray[0] >>> b = parray[1] >>> a (5+1j) >>> b (8.5+3j) >>> ab (-3.5-2j) >>> abs(ab) 4.031128874149275 

Una forma de acelerar las cosas es usar algún tipo de índice espacial, de modo que descarte puntos de búsqueda que obviamente están muy separados. Aquí hay un módulo que podría ser útil: http://toblerity.org/rtree/ . Véase también http://en.wikipedia.org/wiki/R-tree .