Очевидно, что "точки решетки лежат в двух точках", которые вы имеете в виду (позволяя LP обозначать точку решетки), LP на линии между двумя точками (A и B).
Уравнение прямой AB имеет вид y = m * x + b для некоторого наклона и числа пересечения m и b. Для интересующих случаев мы можем предположить, что m, b рациональны, потому что, если любой из них иррационален, на AB не более 1 LP. (Доказательство: если 2 или более ЛП находятся в линии, у них есть рациональный наклон, скажем, e / d, с целыми числами d, e; тогда y = b + x * e / d, так что в ЛП (X, Y) на линии, d * b = d * YX * e, которое является целым числом, поэтому b рационально.)
Далее мы предполагаем, что A = (u, v) и B = (w, z), где u, w и v, z имеют рациональные различия, и обычно пишем y = mx + b с m = e / d. и б = г / ф.
Случай 1. A, B оба являются LP: пусть q = gcd (u-w, v-z); возьмите d = (u-w) / q и e = (v-z) / q, и легко увидеть, что на AB имеются q + 1 точки решетки.
Дело 2а. 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 ((wu) / d) и аналогично для z' , затем решите (u, v), (w ', z'), как в случае 1. Для случая 2b поменяйте местами A и B.
Случай 3. Ни A, ни B не являются LP: После нахождения LP C на расширенной линии через A, B используйте арифметику, как в случае 2, чтобы найти LP A 'внутри отрезка AB и применить случай 2. Найти A ', если m = e / d, b = g / f, обратите внимание, что f * d * y = d * g + e * f * x имеет форму p * x + q * y = r, простой диофантов Уравнение, которое разрешимо для C = (x, y) тогда и только тогда, когда gcd (p, q) делит r.
Сложность: gcd (m, n) - это O (ln (min (m, n))), поэтому сложность алгоритма обычно составляет O (ln (Dx)) или O (ln (Dy)), если A, B разделены x, y расстояния Dx, Dy.