在二维平面上给定两个点，有多少个格点位于这两个点之间？
例如，对于A (3, 3)和B (-1, -1)，输出为5。这些点是：(-1, -1), (0, 0), (1, 1), (2, 2)和(3, 3)。
1个回答
5
显然，“格点在两点之间”指的是（让LP代表格点）在线段AB上的LP。
线段AB的方程为y=m*x+b，其中m和b是一些斜率和截距数字。对于感兴趣的情况，我们可以假设m、b是有理数，因为如果其中一个是无理数，AB上最多只有1个LP。（证明：如果2个或更多的LP在直线上，则它具有有理斜率，例如e/d，其中d、e是整数；然后y=b+x*e/d，因此在直线上的LP（X，Y），d*b=d*Y-X*e，这是一个整数，因此b是有理数。）
以下，我们假设A =（u，v）和B =（w，z），其中u、w和v、z具有有理差异，并通常写作y = mx + b，其中m = e / d，b = g / f。
情况1. A、B都是LP：取q = gcd（u-w，v-z）；取d =（u-w）/ q和e =（v-z）/ q，很容易看出AB上有q + 1个格点。
情况2a. A是LP，B不是：如果u-w = h/i且v-z = j/k，则m = j*i/（h*k）。取q = gcd（j*i，h*k），d = h*k / q，e = j*i / q，w'= u + d*floor((w-u)/d)，z'同理，然后像情况1一样解决（u，v），（w'，z'）。对于情况2b，交换A和B。
情况3. A和B都不是LP：在找到通过A、B的扩展线上的LP C之后，使用类似情况2的算术方法来找到线段AB内的LP A'并应用情况2。要找到A'，如果m = e / d，b = g / f，则f * d * y = d * g + e * f * x具有p * x + q * y = r的形式，这是一个简单的Diophantine方程，当gcd（p，q）除以r时，它可以解决C =（x，y）。
复杂度：gcd（m，n）为O（ln（min（m，n））因此算法复杂度通常为O（ln（Dx））或O（ln（Dy）），如果A，B之间的距离为Dx，Dy。
- James Waldby - jwpat7
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接