Calcolare la distanza su una griglia tra 2 punti

Question

Ho bisogno di calcolare la distanza su una griglia tra 2 punti. Il movimento consentito è orizzontale e verticale e diagonale al prossimo vicino (quindi a 45 gradi di rotazione).

Quindi la distanza di Manhattan non è un'opzione. Anche la distanza euclidea non è un'opzione, quindi non si muove correttamente lungo la griglia che può portare a un valore basso (come nella linea rossa).

Sto cercando di ottenere la distanza come nella linea verde in cui si sposta da una cella all'altra.

È preferibile che la formula sia veloce.

Answer 1

Questo è abbastanza semplice:

• si sposta in diagonale verso la porta finché non si è neanche sulla stessa riga o lo stesso col. Questo sarà minimo (dx, dy) passi. chiamata

  Let questo d (per i passi in diagonale)

• Poi si sposta su una linea retta verso la porta. Questo sarà max (dx, dy) - d passaggi.

  Chiamiamo questa s (per gradini rettilinei)

• La distanza è poi √2 × d + s.

in codice:

double distance(int x1, int y1, int x2, int y2) { 
    int dx = abs(x2 - x1); 
    int dy = abs(y2 - y1); 

    int min = min(dx, dy); 
    int max = max(dx, dy); 

    int diagonalSteps = min; 
    int straightSteps = max - min; 

    return sqrt(2) * diagonalSteps + straightSteps; 
}