Points on a Lattice

Question

I got this question on a coding interview.

Hanna moves in a lattice where every point can be represented by a pair of integers. She moves from point A to point B and then takes a turn 90 degrees right and starts moving till she reaches the first point on the lattice. Find what's the point she would reach? In essence the problem boils down to finding the first point where the perpendicular to a line will intersect. Can someone provide pseudo-code or code snippets as to how I can solve this?

Answer 1

I'm assuming you mean that she moves in a straight line from A to B and then turns 90 degrees, and that the lattice is a Cartesian grid with the y axis pointing up and the x axis pointing right.

Let (dx,dy) = (Bx,By)-(Ax,Ay), the vector from point A to point B.

We can rotate this by 90 degrees to give (dy,-dx).

After hanna turns right at B, she will head out along that rotated vector toward (Bx+dy,By-dx)

Since she is moving in a straight line, her vector from B will follow (t.dy,-t.dx), and will hit another lattice point when both of those components are integers, i.e...

She will hit another lattice point at: (Bx + dy/GCD(|dx|,|dy|), By - dx/GCD(|dx|,|dy|) )

Answer 2

const findNext = (Ax, Ay, Bx, By) => {
  // Move A to Origin
  const Cx = Bx - Ax;
  const Cy = By - Ay;
  // Rotate by 90 degree clockwise
  const Rx = Cy;
  const Ry = -Cx;
  // Normalize
  const norm = gcd(Math.abs(Rx), Math.abs(Ry));
  const Nx = Rx / norm;
  const Ny = Ry / norm;
  return [Bx + Nx, By + Ny];
};

Here is gcd,

var gcd = function(a, b) {
  if (!b) {
    return a;
  }

  return gcd(b, a % b);
}

Output:

cons result = findNext(1,1,2,2);
console.log(result);
// [3, 1]