Зображення відрізка із цілочисловими координатами кінців

Нехай наш відрізок - це AB. Перейдемо від системи координат Oxy до Ax'y' (див. мал. 6.2, етап 1). Відрізок може лежати в кожному з 8 октантів, але завжди існують симетрії щодо осей, що розділяють ці октанти, симетрії визначаються матрицями

і

що дозволяють звести завдання до випадку відрізка, що лежить у першому октанті (приклад див. на мал. 6.2, етап 2, у ньому матриця має вигляд

Назвемо такий випадок канонічним, надалі будуть розглянуті алгоритми для цього випадку. У канонічному випадку процес малювання 8-зв'язної лінії можна закодувати послідовністю виду: sdssd... (див. мал. 6.3), де

s - горизонтальний зсув;

d - діагональний зсув.

Рис. 6.2. Перехід до канонічного випадку у два етапи.

Еквівалентно цієї послідовності можна зіставити бінарний код, де 0 відповідає s, а 1 відповідає d. Такий код для малювання відрізка називається кодом Ротштейна [46] для .

Нехай plot(x,y) - функція, що зафарбовує крапку растра з координатами (x,y).

Рис. 6.3. Кодування зафарбовування відрізка (або код Ротштейна).