scipy.spatial: algoritmos y estructuras de datos espaciales

En este artículo, vamos a ver la estructura de datos espaciales y los algoritmos, se utiliza para representar datos en un espacio geométrico.

¿Qué es la estructura de datos espaciales?

El paquete espacial calcula las triangulaciones, los diagramas de Voronoi y los cascos convexos de un conjunto de puntos, aprovechando la biblioteca Qhull. Además, contiene implementaciones de KDTree para consultas de puntos vecinos más cercanos y utilidades para cálculos de distancia en varias métricas.

Ejemplo 1: Triangulaciones de Delaunay

En matemáticas y geometría computacional, una triangulación de Delaunay para un conjunto dado p de puntos discretos en un plano es una triangulación DT(p) tal que ningún punto p está dentro del círculo circunscrito de ningún triángulo en DT(p).

from scipy.spatial import Delaunay
import numpy as np
import matplotlib.pyplot as plt
  
points = np.array([[1, 4], [2, 1], [3, 0], 
                   [0, 2], [4, 3]])
tri = Delaunay(points)
  
plt.triplot(points[:, 0], points[:, 1], tri.simplices.copy())
plt.plot(points[:, 0], points[:, 1], 'o')
plt.show()

Producción:

Ejemplo 2: Puntos coplanares

Los puntos coplanares son tres o más puntos que se encuentran en el mismo plano. Recuerda que un plano es una superficie plana, que se extiende sin fin en todas direcciones.

from scipy.spatial import Delaunay
import numpy as np
  
points = np.array([[0, 0], [0, 1], [1, 0], 
                   [1, 1], [1, 1]])
tri = Delaunay(points)
print(tri.simplices)
print(tri.coplanar)

Producción:

[[3 1 0]
 [2 3 0]]
[[4 0 3]]

Ejemplo 3: cascos convexos

La envolvente convexa o envoltura convexa de un conjunto de puntos X en el espacio euclidiano (o, más generalmente, en un espacio afín sobre los reales) es el conjunto convexo más pequeño que contiene a X.

from scipy.spatial import ConvexHull
import numpy as np
import matplotlib.pyplot as plt
  
points = np.random.rand(10, 2)
hull = ConvexHull(points)
  
plt.plot(points[:, 0], points[:, 1], 'o')
for simplex in hull.simplices:
    plt.plot(points[simplex, 0], points[simplex, 1], 'k-')
  
plt.show()

Producción:

Ejemplo 4: árboles KPT

kd-tree es una búsqueda rápida del vecino más cercano. Y los métodos Kdtree() devuelven el objeto kd-tree

from scipy.spatial import KDTree
  
points = np.random.rand(10, 2)
kdtree = KDTree(points)
result = kdtree.query((1, 1))
print(result)

Producción:

(0.5144859720297681, 9)