Головоломки и логические задачи безусловно полезны программистам, но не будем забывать и об алгоритмах. Хочу предложить задачу-проблему. Или даже тему для обсуждения и решения.

Известно, что уравнение прямой, проходящей через две заданные точки имеет вид: $$\frac{y-y_1}{y_2-y_1}=\frac{x-x_1}{x_2-x_1}$$ а уравнение прямой с угловым коэффициентом: $$y=kx+b$$ На первый взгляд кажется, что построить прямую проще простого (взять уравнение прямой и вычислить координаты точек), но возникает проблема округлений (пиксели дискретны и имеют вполне определенные размеры), поэтому прямая может получиться ступенчатой. И если надо определить принадлежность какой-то точки этой прямой, то можно промазать (опять же округления) и сделать вывод о том, что точка не принадлежит прямой, когда она оказалась рядом с линией. Это введение в проблему.
1) Предложите алгоритм правильного определения принадлежности точки прямой (за лучшую идею - 1 балл в репутацию).
2) Предложите алгоритм для рисования прямой на плоскости (плоскость - матрица пикселей) без использования уравнений прямой (за лучшую идею - 2 балла в репутацию)

Решения предлагается писать в комментариях.
Посетители могут голосовать за лучшую идею или алгоритм.


2010-10-16 • Просмотров [ 1697 ]