algorithm - 格子上的点

Question

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

Hanna 在一个格子中移动，其中每个点都可以用一对整数表示。她从 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)