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

#      A' . |
#      .    |
#      .    |  .   .  .  A
#      .    |            .
# -------------------------
#           |
#           |
#           |
#
# When you rotate clockwise a point A 90 degrees from origin,
#   you get A' => f(x,y) = (-y, x)
#
#
#           |         A   
#           |       .
#           |     B
#           |   .
#           | . 
# ----------O-------------
#           |
#           |
#           |
#
# Based on a point A from origin, you can find point B by:
#   By/Ay = Bx/Ax => By = Bx * Ay/Ax
#
#           |
#   A       |
#     .     |
#       .   |
#         . |
# ----------B--------------
#        .  |
#    .      |
# C         |
#
# To make things easier, we can move the points to get point B on origin.
# After Hanna rotate 90 degrees to the right on point B, 
#   she will find eventually point C.
# Lets say that D is a point in a rect that is on B-C.
# Hanna will stop on a point on the lattice when the point (x,y) is integer
# So, from B we need to iterate Dx until we find a Dy integer
#
def rotate_90_clockwise(A):
  return (-A[1], A[0])

def find_B_y(A, x):
  return x * A[1]/A[0] if A[0] else A[1]

def find_next(A, B):
  # make B the origin
  Ao = (A[0] - B[0], A[1] - B[1])
  Bo = (0,0)
  # rotate Ao 90 clockwise
  C = rotate_90_clockwise(Ao)
  if C[0] == 0:
    # C is on y axis
    x = 0
    # Dy is one unit from origin
    y = C[1]/abs(C[1])
  else:
    found = False
    # from origin
    x = 0
    while not found:
      # inc x one unit
      x += C[0]/abs(C[0])
      y = find_B_y(C, x)
      # check if y is integer
      found = y == round(y)
  # move back from origin
  x, y = (x + B[0], y + B[1])
  return x, y

A = (-2, 3)
B = (3, 2)
D = find_next(A, B)
print(D)

B = (-4, 2)
A = (-2, 2)
D = find_next(A, B)
print(D)

B = (1, 20)
A = (1, 5)
D = find_next(A, B)
print(D)

Output:

(2.0, -3.0)
(-4, 3.0)
(2.0, 20.0)

Answer 3

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]