Schneller Algorithmus für die Entfernung zwischen 2 Punkten auf einem Gitter?

Question

Gegeben ein Raster von Breite zu Länge (etwa 5 x 4) und ein Array von X- und Y-Koordinaten für Punkte auf diesem Raster, drucken Sie den Abstand von jedem Punkt auf dem Raster zu den Koordinaten wie folgt:

width = 5

LEN = 4

x Koord = (2,4)

y = Koordinaten (2,3)

2123 
1012 
2112 
2101 
3212 

A move "across" + 2 ist, Bewegung vertikal oder horizontal ist +1

Angenommen xCoords.length = yCoords.length

Ich werde meine Lösung veröffentlichen später, oder vielmehr der Versuch einer Lösung. Ich habe stecken versuchen, mit einer Funktion zu kommen Abstand zur Umsetzung von Gitterkoordinaten (i, j) für die Punkte auf Koordinaten ... Also im Grunde

for i .. width 
    for j .. length 
    getDistance(i,j, xCoords,yCoords) 

(0,0) (0,1) (0 , 2) (0,3)

(1,0) (1,1) (1,2) (1,3)

(2,0) (2,1) (2,2) (2,3)

etc ...

um die tatsächlichen Abstandswerte an diesen Koordinaten.

Answer 1

Ich gehe davon aus, dass Sie für die Entfernung zum nächstgelegenen coord unter denen in dem Vektor gegeben suchen, das heißt

for i 0 .. width 
    for j 0 .. length 
     best = distance(i, j, coords[0].x, coords[0].y) 
     for k 1 .. coordVector // Skip first element 
      best = min(best, distance(i, j, coords[k].x, coords[k].y) 
     result[i][j] = best 

Die dritte verschachtelte Schleife prüft der Abstand von dem in dem Vektor zu allen Koordinaten gegebenen Koordinate von (x i , y _i), nimmt die kürzeste, und speichert ihn in der Variable best. Beachten Sie, dass best mit dem Abstand zum ersten Punkt im Vektor initialisiert wird, sodass die verschachtelte Schleife mit dem zweiten Punkt beginnt.

Alles, was Sie jetzt brauchen, ist ein Taschenrechner für distance. Nach der Problembeschreibung, suchen Sie Manhattan Distance weil ein diagonaler Schritt als 2 gewichtet wird, vertikal das gleiche wie ein Schritt ist es horizontal und einen Schritt bedeutet:

distance(x0, y0, x1, y1) 
    horizontal = abs(x1-x0) 
    vertical = abs(y0-y1) 
    return horizontal + vertical 

Answer 2

Sie wollen Pythagoras Theorem verwenden. sqrt((i-xCords)*(i-xCords)+(j-yCords)*(j-yCords))

Answer 3

int getDistance(int x1, int y1, int x2, int y2) { 
    return Math.abs(x1 - x2) + Math.abs(y1 - y2); 
} 

Answer 4

Related: I want to calculate the distance between two points in Java

distance = Math.sqrt (Math.pow ((i-xCords), 2) + Math.pow ((j-yCords), 2));