Как распространить два вектора u и v, чтобы эффективно заполнить прямоугольник

Question

Для иллюстрации см. Изображение ниже.

Учитывая точку p и два вектора u а также vмы можем получить линейную комбинацию u а также v, t = m*u + n*v, m а также n являются целыми числами, и t должно быть в рамке. Решить эту проблему не так уж сложно. Как m а также n может быть как положительным, так и отрицательным. Это можно обсудить:

1. m> 0 и n> 0
2. m> 0 и n < 0
3. m <0 и n> 0
4. m <0 и n < 0

Вот код Python для случая 1:

m = 0 
n = 0 
t = m*u+n*v
x = t[0]
y = t[1]
l = []
while (x>0 and x < 1024 and y > 0 and y < 1024):
    l.append(t)
    m  = m + 1
    t = m*u+n*v
    x = t[0]
    y = t[1]
    while (x>0 and x < 1024 and y > 0 and y < 1024):
        l.append(t)
        n = n +1
        t = m*u+n*v
        x = t[0]
        y = t[1]

Использование двух петель для 4 комплектов может решить проблему.

Другой способ - сгенерировать слишком много точек, а затем удалить точки за пределами поля.

Я думаю, может быть, есть другой простой и элегантный способ сделать это?

Answer 1

Преобразуйте блок в систему координат, определенную с p как начало координат, и u как направление оси x, а v как направление оси y. Результатом будет параллелограмм. Достаточно найти целочисленные координаты, которые находятся внутри этого параллелограмма. Это может быть сделано путем нахождения минимального и максимального m, который находится внутри параллелограмма, и поиска каждого m между минимальным и максимальным, какой диапазон значений n находится внутри параллелограмма.