点在晶格上

Question

我在一次编码面试中得到了这个问题。

汉纳在晶格中移动，其中每个点都可以用一对整数表示。她从A点移动到B点，然后向右转90度并开始移动，直到到达格子上的第一个点。找到她会达到什么程度？从本质上讲，问题归结为找到垂直于直线相交的第一个点。有人可以提供伪代码或代码片段来说明我如何解决这个问题吗？

Answer 1

我假设你的意思是她从 A 到 B 直线移动，然后旋转 90 度，并且晶格是一个笛卡尔网格，y 轴指向上方，x 轴指向右。

设 (dx，dy( = (Bx，By(-(Ax，Ay(，从 A 点到 B 点的向量。

我们可以将其旋转 90 度以给出 (dy，-dx(。

在汉娜在 B 处右转后，她将沿着旋转的矢量朝 (Bx+dy，By-dx( 前进

由于她是直线移动的，她从 B 的向量将遵循 (t.dy，-t.dx(，并且当这两个分量都是整数时，将达到另一个格点，即......

她将在以下位置击中另一个格子点：(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];
};

这是gcd，

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

输出：

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

Answer 3

#      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)

输出：

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