Nik Nik - 5 months ago 26
Java Question

Quick algorithm for distance between 2 points on a grid?

Given a grid of width by length (say 5 x 4) and an array of X and Y coords for points on that grid, print the distance from each point on the grid to the coords as below:

width = 5

len = 4

x coords = (2,3)

y coords = (2,4)

2123
1012
2112
2101
3212


A move "across" is + 2, vertical or horizontal move is +1

Assume xCoords.length = yCoords.length

I will post my solution later, or rather an attempt at a solution. I got stuck trying to come up with a function to transpose distance from grid coordinates (i,j) to coordinates for the points... So basically

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...

To the actual distance values at those coordinates.

Answer

I assume that you are looking for the distance to the nearest coord among the ones given in the vector, i.e.

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

The third nested loop checks the distance from the given coordinate to all coordinates in the vector of (xi, yi), picks the shortest one, and stores it in the variable best. Note that best is initialized with the distance to the first point in the vector, so the nested loop starts with the second point.

All you need now is a calculator for distance. According to the problem description, you are looking for Manhattan Distance because a diagonal step is weighted as 2, meaning it's the same as one step horizontally plus one step vertically:

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