Алгоритми побудови відрізка

Алгоритми побудови відрізка — графічні алгоритми апроксимації відрізка на дискретному графічному пристрої (растеризація), наприклад, моніторі або принтері.

Ідеальна лінія і результат розкладання в растр

На суцільних (не дискретних) графічних пристроях, такі алгоритми не потрібні. Наприклад, для осцилографу використовують природні феномени для малювання ліній і кривих.

Стандартними вимогами до алгоритмів є швидкість роботи, рівномірна яскравість та прямий вид отриманих відрізків, збіг початкових та кінцевих координат отриманої та ідеальної лінії. Для дискретного пристрою дані вимоги часто нездійсненні. Відрізок не можна провести з однієї точки в іншу однозначно (крім горизонтальних, вертикальних та нахилених під кутом 45° відрізків), початок та кінець відрізка мають координати найближчих до них пікселів, відстань між пікселями діагональних відрізків більше, ніж між вертикальними та горизонтальними пікселями.

Список алгоритмів малювання відрізків

• Алгоритм DDA-лінії  — простий алгоритм, що використовує дійсні числа.
• Алгоритм Брезенхема  — оптимізований алгоритм, що використовує лише цілі числа та операції додавання і віднімання.
• Алгоритм Ву  — модифікований алгоритм Брезенхема, що забезпечує згладжування відрізка.

Література

• Роджерс Д. Алгоритмічні основи машинної графіки. — М. : Світ, 1989. — 548-73 с. — .