我似乎找不到解决这个问题的方法。让我们将 Z^2 设置为 R^2 中的整数格。给定一条有理射线(意味着具有有理斜率的向量)，是否有一种快速方法可以根据正交距离计算最接近该向量的格点？这个方法可以推广到R^n中的超平面吗？
最佳答案
您的问题似乎没有明确定义。你如何定义到向量的距离？ 如果您要求从晶格到方向为有理向量的直线的最近距离(如您的概括所建议的那样)，那么答案为零，这要归功于合理性:您的方向是 D = (n1/d1, n2/d2).那么，点(d2*n1,d1*n2)就在线上了。
对于最小的非零距离:
我们可以假设 d1=d2=d : D = (n1/d, n2/d)(您可以通过设置例如 d = d1*d2 获得)。现在，单位网格格子到直线的可能距离的形式为 (Z*n1 + Z*n2)/d = (Z*gcd(n1,n2))/d，其中 Z 是整数集。 (这是 Bézout 定理的结果)。所以最小非零距离是 gcd(n1,n2)/d 其中 gcd(.,.) 给出两个整数的最大公约数。
关于algorithm - 最近格点类型题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7002848/