Алгоритм Кастла-Пітвея
Цей алгоритм набагато менш ефективний з обчислювальної крапки зрені, чим алгоритм Брезенхема, однак має гарну математичну структуру. Він заснований на ідеї, схожої з відомим алгоритмом Евкліда знаходження Найбільшого Загального Дільника двох натуральних чисел [19].
Будемо працювати з рядками, що кодують послідовність зафарбування (тобто складаються із символів s і d, певних вище).
Визначимо дві операції над такими рядками:
- 
- конкатенація рядків, наприклад
- 
- "переворот" рядка, наприклад
~ m2; } else { y = y - x; m1 = m2 ~ m1; }} Лістинг 6.3. Алгоритм Кастла-Пітвея
Після завершення роботи алгоритму 
задає потрібну послідовність зрушень. Доказ коректності роботи цього алгоритму ми опустимо через його громіздкість.
Дата добавления: 2015-04-03; просмотров: 869;