линейная-алгебра - Как узнать координаты через которые проходит вектор? Продолжение вопроса

Рассмотрим частный случай задачи, когда надо соединить точку $%(0;0)$% с точкой $%(a;b)$%. Если $%a=b$%, то соединяем всё по диагонали. Пусть $%a > b$%. Тогда каждому $%x=0,1,2,\ldots,a$% мы сопоставляем координату $%y$% по следующей простой формуле: $%y={\mathop{\rm trunc}}\frac{bx}a$%, где trunc означает округление до ближайшего целого. Полуцелые числа стандартно можно округлять в сторону увеличения, то есть $%{\mathop{\rm trunc}}(3.5)=4$%.

Пример: пусть $%a=13$%, $%b=8$%. Тогда при $%x=5$% мы получим $%y={\mathop{\rm trunc}}\frac{40}{13}=3$%, а при $%x=8$% будет $%y={\mathop{\rm trunc}}\frac{64}{13}=5$%.

Для случая $%a < b$% поступаем аналогично, только теперь уже каждому $%y=0,1,2,\ldots,b$% сопоставляем координату $%x$% по формуле $%x={\mathop{\rm trunc}}\frac{ay}{b}$%.

Заметим, что в обоих случаях должно иметь место приближённое равенство $%ay\approx bx$%, и в таком виде его легко запомнить как "ключевое".

Теперь сведём общую задачу к этому случаю. Допустим, нам надо соединить точку $%(a;b)$% с точкой $%(c;d)$%. Вычитая из обоих точек $%(a;b)$% покоординатно, мы сводим всё к случаю соединения точек $%(0;0)$% и $%(c-a,d-b)$%. У второй точки одна или обе координаты могут быть отрицательны. Тогда отбрасываем знаки, то есть переходим к абсолютным величинам. Это даёт точки $%(0;0)$% и $%(|c-a|,|d-b|)$%, а такую задачу мы решать уже умеем. Составляем для неё путь по описанному выше алгоритму, а потом возращаем знак минус там, где мы его убирали. После этого ко всем полученным координатным точкам прибавляем $%(a,b)$%, и это даёт искомый путь из $%(a;b)$% в $%(c;d)$%.

Пример: пусть надо соединить $%(4;17)$% и $%(11;12)$%. Вычитаем координаты первой точки. Получается задача соединения $%(0;0)$% и $%(7;-5)$%. Меняем знак у второй координаты, соединяя $%(0;0)$% и $%(7;5)$%. Берём дробь $%\frac57$% и умножаем её на числа от 0 до 7 включительно, округляя получающиеся при этом дроби до ближайшего целого. Получаются числа 0, 1, 1, 2, 3, 4, 4, 5. Это значит, что у нас получился такой путь: $%(0;0)$%, $%(1;1)$%, $%(2;1)$%, $%(3;2)$%, $%(4;3)$%, $%(5;4)$%, $%(6;4)$%, $%(7;5)$%.

Теперь возвратим знак минус у второй координаты, поскольку мы его убирали. Получится путь $%(0;0)$%, $%(1;-1)$%, $%(2;-1)$%, $%(3;-2)$%, $%(4;-3)$%, $%(5;-4)$%, $%(6;-4)$%, $%(7;-5)$%. Осталось прибавить ко всем точкам этого пути начальную точку, то есть $%(4;17)$%. Это даёт путь $%(4;17)$%, $%(5;16)$%, $%(6;16)$%, $%(7;15)$%, $%(8;14)$%, $%(9;13)$%, $%(10;13)$%, $%(11;12)$%, который и требовалось создать.