Строим 4-связную линию.
1 подход: округлим координаты концов до целочисленных, а затем воспользуемся алгоритмом для целочисленного случая.
Недостаток: может вызывать существенные искажения (особенно в случае отрезков небольшой длины).
2 подход:
Рис. 6. Рисование отрезка с нецелочисленными координатами концов.
Перейдем к нашему каноническому случаю, который теперь характеризуется тем, что отрезок лежит в первом октанте, но координаты A (x0,y0) в этом случае: x0 Î [0,1), y0 Î [0,1).
Параметризуем наш отрезок стандартным образом:
(x,y)= A + t*(B-A)/c, t Î [0,c], A и B - наши точки, где c >0 - некий масштабный коэффициент.
Сделаем C достаточно большим целым числом, чтобы избежать ошибок округления.
Тогда берем Dh=c/(xb-xa) (т.е. приращение t, когда мы сдвигаемся на 1 пиксел по x);
Dv=c/(yb-ya) (т.е. приращение t, когда мы сдвигаемся на 1 пиксел по y).
Будем сравнивать текущие значения h и v, а затем в зависимости от этого делать шаг по x или y ипридавать соответствующие приращения h и v. Алгоритм закончится, когда h или v превысит с.
|
|
Алгоритм:
x=0; y=0; // Канонический случай: начальная точка лежит в [0,1)Ä[0,1)
/* Приращения t, соответствующие смещениям от начальной точки до границ
первого пиксела. */
h=Dh*(1-x0); // Dh0
v=Dv*(1-y0); // Dv0
while ((h<c) && (v<c))
{
plot (x,y);
if (h < v)
{
// Сдвиг по горизонтали
x++; h += Dh;
}
else if (h > v)
{
// Сдвиг по вертикали
y++; v += Dv;
}
else
{
// h==v: Вырожденный случай (см. Рис. 6)
рисуем произвольный из 2 возможных пикселов
h += Dh; v += Dv;
}
}
Замечание 1: Алгоритм легко обобщается на n - мерный случай.
Замечание 2: В случае целочисленных координат концов отрезка этот алгоритм также можно сделать целочисленным.