Алгоритми побудови відрізка
Алгоритми побудови відрізка — графічні алгоритми апроксимації відрізка на дискретному графічному пристрої (растеризація), наприклад, моніторі або принтері.
На суцільних (не дискретних) графічних пристроях, такі алгоритми не потрібні. Наприклад, для осцилографу використовують природні феномени для малювання ліній і кривих.
Стандартними вимогами до алгоритмів є швидкість роботи, рівномірна яскравість та прямий вид отриманих відрізків, збіг початкових та кінцевих координат отриманої та ідеальної лінії. Для дискретного пристрою дані вимоги часто нездійсненні. Відрізок не можна провести з однієї точки в іншу однозначно (крім горизонтальних, вертикальних та нахилених під кутом 45° відрізків), початок та кінець відрізка мають координати найближчих до них пікселів, відстань між пікселями діагональних відрізків більше, ніж між вертикальними та горизонтальними пікселями.
Список алгоритмів малювання відрізків
- Алгоритм DDA-лінії — простий алгоритм, що використовує дійсні числа.
- Алгоритм Брезенхема — оптимізований алгоритм, що використовує лише цілі числа та операції додавання і віднімання.
- Алгоритм Ву — модифікований алгоритм Брезенхема, що забезпечує згладжування відрізка.
Література
- Роджерс Д. Алгоритмічні основи машинної графіки. — М. : Світ, 1989. — 548-73 с. — ISBN 5-03-000476-9.