Encontrar el camino de menor elevación entre dos puntos

Question

Digamos que tengo una matriz de valores que representan alturas con función $f(x,y)$ e intento encontrar el "camino de menor valor" entre dos puntos. Así que esto sería lo contrario de subida de la colina, como en la optimización, teniendo gradiente y siguiendo que, etc, pero en cierto modo, supongo que necesito el anti-gradiente - no la dirección de subida más empinada, pero la caminata no más empinada.

Necesito esto para una aplicación de mapas, tengo valores de elevación en una cuadrícula y estoy tratando de encontrar un camino entre esos puntos que requieren amt mínimo de escalada.

Supongo que podría crear una función de coste que diera los valores más altos para la elevación alta + los puntos más lejanos al destino + la no suavidad de los caminos, y hacer la optimización sobre eso. Sólo me preguntaba si alguien ha trabajado con tales funciones de coste antes, o hay otro truco de cálculo que tengo que utilizar.

Palabras clave: ruta más llana

Answer 1

Se trata de una instancia de "problema del "camino más corto . Crea un grafo dirigido con un conjunto de vértices igual a los puntos de tu cuadrícula, y con una arista dirigida desde $a$ a $b$ si $a$ y $b$ son adyacentes, y dar a esa arista un peso $w(a,b)=\min(0,h(b)-h(a))$ donde $h(a)$ es la elevación de $a$ y así sucesivamente. (Es decir, los vértices son celdas de tu matriz, donde el vértice típico tiene 4 vecinos: la celda al Norte, la del Sur, etc.). Las aristas representan cosas como "ir al Norte desde esta celda a su vecina" y el peso es la subida asociada a tal movimiento). Utiliza uno de los algoritmos descritos en el enlace. Atención: algunos de estos algoritmos requieren una codificación intrincada. (Esta función de peso sólo mide la subida, lo cual, como excursionista ocasional que soy, sé que no es necesariamente toda la historia sobre el cansancio de los pies).

Answer 2

Este problema puede considerarse como un problema del camino más corto. Digamos que la matriz tiene datos de elevación, los vecinos de una celda pueden ser recuperados usando el patrón de Queen (8 de ellos), entonces el código es

from pqdict import pqdict
import numpy as np

def get_neighbor_idx(x,y,dims):
    res = []
    for i in ([0,-1,1]):
        for j in ([0,-1,1]):
            if i==0 and j==0: continue
            if x+i<(dims[0]) and x+i>-1 and y+j<(dims[1]) and y+j>-1:
                res.append((x+i,y+j))
    return res

def dijkstra(C,s,e):    
    D = {}
    P = {}
    Q = pqdict() 
    Q[s] = 0

    while len(Q)>0:
        (v,vv) = Q.popitem()
        D[v] = vv
        neighs = get_neighbor_idx(v[0],v[1],C.shape)
        for w in neighs:
            vwLength = D[v] + np.abs(C[v[0],v[1]] - C[w[0],w[1]])
            if w in D:
                if vwLength < D[v]:
                    raise ValueError
            elif w not in Q or vwLength < Q[w]:
                Q[w] = vwLength
                P[w] = v

    path = []
    while 1:
       path.append(e)
       if e == s: break
       e = P[e]
    path.reverse()
    return path   

m = np.array([[999.9, 999.9, 999.9,   0. ],
              [999.9, 999.9, 999.9,   0. ],
              [999.9, 999.9, 999.9,   0. ],
              [  0.,    0.,    0.,    0. ]])

res = dijkstra(m,(3,0),(0,3))

print (res)

Esto imprimirá

[[999.9 999.9 999.9   0. ]
 [999.9 999.9 999.9   0. ]
 [999.9 999.9 999.9   0. ]
 [  0.    0.    0.    0. ]]
[(3, 0), (3, 1), (3, 2), (2, 3), (1, 3), (0, 3)]

Así, partiendo de la esquina inferior izquierda, hasta la esquina superior derecha del objetivo, se informó de la ruta más llana. Los 999 son 'colinas' los 0 son tierra.