Algoritmos Espaciales con Python para Dummies

Fundamentos Teóricos del Centro Medio

El Centro Medio (Mean Center) es el algoritmo espacial más básico, equivalente al "promedio" estadístico aplicado a la geografía. Su objetivo es identificar el punto geográfico (centro de gravedad) que minimiza la suma de las distancias al cuadrado hacia todos los puntos del conjunto. Matemáticamente, se calcula promediando las coordenadas X (longitud) y las coordenadas Y (latitud) por separado.

Como el promedio regular, este cálculo es sensible a valores atípicos (outliers). Puede aplicarse en 3D (Z) y afinarse usando "pesos" ponderados (ej: poblaciones o volúmenes de compra), así como calcularse por categorías para obtener múltiples centros de un conjunto de datos.

Lógica y Pseudocódigo

Consideremos el caso de un grupo de amigos en posiciones en la ciudad que buscan encontrarse en un punto óptimo de desplazamiento. La lógica requiere iterar por cada ubicación, sumar todas las coordenadas (X y Y), y finalmente dividirlas entre el número de ubicaciones.

Implementación Básica en Python

A continuación, implementamos el algoritmo de forma manual utilizando Python puro, iterando las coordenadas de una lista de ubicaciones. Aunque es ideal para aprender la lógica básica, para conjuntos grandes no es lo más eficiente computacionalmente.

# Coordenadas de las casas (Latitud, Longitud)
casas_amigos = [
    [4.6097, -74.0817],
    [4.6200, -74.0900],
    [4.5900, -74.0700],
    [4.6100, -74.0800],
    [4.6300, -74.1000]
]

suma_total_x = 0
suma_total_y = 0
cantidad_amigos = len(casas_amigos)

for amigo in casas_amigos:
    # Asumiendo posición 0 es latitud (X) y 1 es longitud (Y) para el ejemplo
    x = amigo[0]
    y = amigo[1]
    suma_total_x += x
    suma_total_y += y

centro_x = suma_total_x / cantidad_amigos
centro_y = suma_total_y / cantidad_amigos

print("Centro Medio:", centro_x, centro_y)

Implementación Avanzada y Visualización con Pandas y Matplotlib

Para simplificar el proceso y preparar los datos de forma escalable (simulando atributos SIG), empleamos pandas. El punto del centro medio se puede calcular rápidamente aplicando el método .mean() directamente sobre las columnas correspondientes del DataFrame.

Para la visualización, utilizamos matplotlib.pyplot. Superponemos las ubicaciones originales como un gráfico de dispersión regular (scatter azul) y destacamos el centro medio (en rojo con forma de estrella) para identificar visiblemente el centro de gravedad o equilibrio del grupo.

import pandas as pd
import matplotlib.pyplot as plt

datos = {
    'Amigo': ['Juan', 'Ana', 'Pedro', 'Carolina', 'Beto'],
    'Latitud': [4.6097, 4.6200, 4.5900, 4.6100, 4.6300],
    'Longitud': [-74.0817, -74.0900, -74.0700, -74.0800, -74.1000]
}

df = pd.DataFrame(datos)

# Cálculo vectorizado con Pandas
centro_lat = df['Latitud'].mean()
centro_lon = df['Longitud'].mean()

print("Centro Medio (Pandas):", centro_lat, centro_lon)

# Visualización
plt.scatter(df['Longitud'], df['Latitud'], c='blue', label='Amigos')
plt.scatter(centro_lon, centro_lat, c='red', marker='*', s=200, label='Centro Medio')
plt.legend()
plt.title('Ubicación Óptima de Encuentro')
plt.grid(True)
plt.show()

La elipse de desviación estándar es una herramienta espacial para identificar tendencias, niveles de dispersión y la dirección de una nube de puntos. A diferencia del centro medio que solo da un punto de equilibrio, la elipse genera una huella que resume la distribución (ej. Norte-Sur, Este-Oeste). Es muy útil para estudiar eventos distribuidos como delitos, clientes o accidentes.

El punto de partida es el Centro Medio (promedio de las coordenadas X e Y). A partir de él se usa la varianza y la desviación estándar para medir la dispersión de los puntos respecto a ese centro. Para saber su tendencia diagonal, se calcula la matriz de covarianza.

A partir de la matriz de covarianza de las coordenadas, extraemos los valores propios (eigenvalues) y vectores propios (eigenvectors) mediante álgebra lineal. Los vectores propios indican el ángulo de rotación de la elipse, mientras que la raíz cuadrada de los valores propios representa el ancho y alto de la desviación estándar (eje mayor y menor).

Implementación en Python con NumPy y Matplotlib (recomendamos fijar semilla para datos simulados):

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Ellipse
np.random.seed(42)

Cálculo del centro, covarianza y componentes de rotación usando NumPy de forma directa:

centro_x = np.mean(puntos[:, 0])
centro_y = np.mean(puntos[:, 1])
covarianza = np.cov(puntos.T)
valores_propios, vectores_propios = np.linalg.eig(covarianza)

Finalmente, calculamos el ángulo de inclinación, el ancho y alto a partir del Eigenvector y la raíz de los Eigenvalues respectivamente, y mostramos el resultado con el parche de Ellipse de Matplotlib:

angulo = np.degrees(np.arctan2(vectores_propios[1, 0], vectores_propios[0, 0]))
ancho = 2 * np.sqrt(valores_propios[0])
alto = 2 * np.sqrt(valores_propios[1])
elipse_grafica = Ellipse(xy=(centro_x, centro_y), width=ancho, height=alto, angle=angulo, edgecolor='red', fc='none', lw=2, linestyle='--')

El algoritmo del Vecino más cercano evalúa objetivamente si una nube de puntos obedece a un patrón disperso, agrupado (clúster) o puramente aleatorio. Funciona midiendo la distancia mínima euclidiana (en línea recta) de cada punto hacia todos los demás para encontrar el vecino más próximo y promediar la "distancia observada".

Esta métrica se contrasta con una "distancia esperada" (un escenario hipotético de distribución perfectamente aleatoria basada en la densidad y el área). El coeficiente resultante (índice de vecino cercano) revela si los puntos se atraen (< 1), son aleatorios (= 1), o se repelen (> 1). Es útil en múltiples campos como epidemiología, ecología y planificación urbana.

Implementación en Python (preparando datos simulados con NumPy y generando clústers de forma intencional):

import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial import cKDTree, ConvexHull

np.random.seed(42)
grupo_1 = np.random.normal(loc=[10, 10], scale=2, size=(10, 2))
grupo_2 = np.random.normal(loc=[10, 20], scale=2, size=(10, 2))
grupo_3 = np.random.normal(loc=[20, 10], scale=2, size=(10, 2))
puntos = np.vstack((grupo_1, grupo_2, grupo_3))

Para hallar distancias de forma eficiente y evitar altas cargas computacionales al iterar bidireccionalmente todos los puntos, usamos el árbol multidimensional cKDTree de Scipy. Pedimos el segundo vecino más cercano (k=2), ya que el primero siempre es el mismo punto a distancia cero:

arbol = cKDTree(puntos)
distancias, indices = arbol.query(puntos, k=2)

distancias_al_vecino = distancias[:, 1]
indices_al_vecino = indices[:, 1]

promedio_distancia_observada = np.mean(distancias_al_vecino)

Calculamos el polígono de la Envolvente Convexa (ConvexHull) para obtener el área de estudio. Teniendo la densidad (puntos / área), formulamos la "distancia esperada" que teóricamente debería tener; luego las dividimos para obtener el índice:

area_convexa = ConvexHull(puntos)
area_total = area_convexa.volume
numero_puntos = len(puntos)
densidad = numero_puntos / area_total

distancia_esperada = 1 / (2 * np.sqrt(densidad))
indice_vecino_cercano = promedio_distancia_observada / distancia_esperada
print("Índice de vecino cercano:", indice_vecino_cercano)

Finalmente, graficamos los puntos y construimos las conexiones recorriendo los índices que hallamos, trazando líneas rojas desde cada origen a su destino para mapear su "sociabilidad":

plt.figure(figsize=(8, 8))
plt.scatter(puntos[:, 0], puntos[:, 1], color='blue', label='Puntos')

for i in range(len(puntos)):
    punto_origen = puntos[i]
    punto_destino = puntos[indices_al_vecino[i]]
    plt.plot([punto_origen[0], punto_destino[0]], 
             [punto_origen[1], punto_destino[1]], 
             color='red', linestyle='-.')

plt.title('Análisis de Vecino Cercano')
plt.legend()
plt.show()

K-Means es una técnica fundamental de aprendizaje no supervisado que agrupa datos espaciales basándose en la proximidad. El objetivo es minimizar la varianza dentro de cada grupo (cohesión) y maximizar la separación entre clústeres distintos. Es ideal para clasificar respuestas espectrales en imágenes satelitales o segmentar dinámicas urbanas.

El proceso es iterativo: parte de K centroides aleatorios, asigna cada punto al más cercano y luego los recalcula como el centro medio del grupo recién formado. El ciclo se repite hasta que la ubicación espacial de los centroides no presenta cambios (convergencia). Cabe anotar que es sensible a outliers y asume formas de clúster esféricas.

Implementación en Python con Scikit-Learn (configuración inicial y generación de datos sintéticos):

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs

# Generación de 300 puntos en 4 clústeres
puntos, etiquetas_reales = make_blobs(n_samples=300, centers=4, cluster_std=0.6, random_state=0)

Entrenamiento del modelo definiendo el número de clústeres (K=4) y parámetros de convergencia:

mis_grupos = KMeans(n_clusters=4, init='random', n_init=10, max_iter=300, random_state=42)
mis_grupos.fit(puntos)

grupos_estimados = mis_grupos.predict(puntos)
centroides = mis_grupos.cluster_centers_

Visualización cartográfica del resultado con centroides destacados con una estrella:

plt.figure(figsize=(10, 8))
plt.scatter(puntos[:, 0], puntos[:, 1], c=grupos_estimados, cmap='viridis', alpha=0.5, label='Puntos')
plt.scatter(centroides[:, 0], centroides[:, 1], c='red', marker='*', s=200, label='Centroides')
plt.legend()
plt.show()

DBSCAN es una técnica de agrupamiento espacial que identifica regiones de alta densidad. A diferencia de K-Means, permite crear grupos con formas irregulares y categoriza automáticamente los elementos solitarios como ruido (datos atípicos).

Funciona mediante dos parámetros: Epsilon (eps), que es el radio de búsqueda, y Min Samples, la cantidad mínima de puntos para formar un núcleo. Clasifica los puntos en tres categorías: Corazón (núcleos densos), Frontera (vecinos de núcleos) y Ruido (puntos aislados).

Implementación en Python usando Scikit-Learn y el dataset de medialunas (make_moons):

import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons

# Generación de datos sintéticos en forma de medialunas
X, y = make_moons(n_samples=300, noise=0.05, random_state=42)

Configuración del modelo con un radio (eps) de 0.2 y 5 puntos mínimos:

dbscan = DBSCAN(eps=0.2, min_samples=5)
cluster_predichos = dbscan.fit_predict(X)

Visualización cartográfica demostrando la capacidad del algoritmo para detectar formas no circulares:

plt.figure(figsize=(10, 6))
plt.scatter(X[:, 0], X[:, 1], c=cluster_predichos, cmap='plasma')
plt.title('DBSCAN Clustering')
plt.show()

El algoritmo de Dijkstra es un pilar fundamental de los SIG para el análisis de redes. Su objetivo es encontrar la ruta más eficiente entre un origen y un destino dentro de un grafo, optimizando variables como la distancia física, el tiempo de viaje o el costo de combustible.

Un grafo se compone de nodos (vértices) y aristas (conexiones). Cada arista tiene un peso (el costo). El algoritmo explora iterativamente los vecinos, actualiza los pesos acumulados y marca como permanentes las rutas mínimas encontradas hasta completar el análisis.

Implementación en Python utilizando las librerías NetworkX para el manejo de redes y Matplotlib para la visualización:

import matplotlib.pyplot as plt
import networkx as nx

# Creación del grafo y definición de conexiones con pesos
grafo = nx.Graph()
grafo.add_edge('casa', 'parque', weight=2)
grafo.add_edge('casa', 'tienda', weight=5)
grafo.add_edge('parque', 'tienda', weight=1)
grafo.add_edge('parque', 'escuela', weight=4)
grafo.add_edge('tienda', 'cine', weight=3)
grafo.add_edge('escuela', 'cine', weight=1)

Cálculo de la ruta óptima y longitud total del recorrido:

inicio = 'casa'
destino = 'cine'

ruta_mas_corta = nx.dijkstra_path(grafo, source=inicio, target=destino, weight='weight')
longitud_ruta = nx.dijkstra_path_length(grafo, source=inicio, target=destino, weight='weight')

print("Ruta:", ruta_mas_corta)
print("Costo total:", longitud_ruta)

Este algoritmo es la base de aplicaciones como Google Maps o Waze y es esencial para el diseño de servicios públicos y optimización de logística territorial.

El Problema del Viajero (TSP) es un desafío fundamental en logística que busca encontrar la ruta más corta para visitar una serie de puntos exactamente una vez y regresar al origen. Dado que su complejidad es factorial, resolverlo por fuerza bruta es inviable para muchos nodos, por lo que se emplean heurísticas para obtener soluciones cercanas al óptimo en tiempos razonables.

En esta clase implementamos el TSP explorando algoritmos como el del Vecino más Cercano y la Aproximación Codiciosa (Greedy). Utilizamos NetworkX para la gestión de grafos y SciPy para el cálculo eficiente de matrices de distancias.

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
from scipy.spatial import distance_matrix

np.random.seed(42)
coordenadas = np.random.rand(20, 2) * 100
distancias = distance_matrix(coordenadas, coordenadas)
grafo = nx.from_numpy_array(distancias)

Una vez construido el grafo, procedemos a calcular la ruta óptima definiendo el método de aproximación y visualizando el recorrido secuencial de los nodos:

ruta_corta = nx.approximation.traveling_salesman_problem(grafo, cycle=True, method=nx.approximation.greedy_tsp)

# Extracción de coordenadas para visualización
x_ruta = coordenadas[ruta_corta, 0]
y_ruta = coordenadas[ruta_corta, 1]

plt.figure(figsize=(10, 6))
plt.scatter(coordenadas[:, 0], coordenadas[:, 1], c='blue')
plt.plot(x_ruta, y_ruta, c='orange')
plt.show()

Esta metodología permite visualizar cómo el algoritmo conecta los nodos de forma secuencial, facilitando la optimización de recursos en planes de movilidad y diseño de rutas de servicio.