Головоломки и логические задачи безусловно полезны программистам, но не будем забывать и об алгоритмах. Хочу предложить задачу-проблему. Или даже тему для обсуждения и решения.
Известно, что уравнение прямой, проходящей через две заданные точки имеет вид: $$\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 • Просмотров [ 3024 ]
без использования алгоритмов прямой, используются алгоритмы, которые основаны на вычислении координат следующей точки прибавляя к предыдущей вычисленное значение координат - вычисляют разницу между конечными точками (известными) и текущей последней посчитанной, таким образом находя точку (пиксель) которая будет максимально приближена к искомому отрезку. у таких методов есть даже название отдельное, один из самых популряных из них алгоритм Брезенхема код пишется буквально в несколько точек, и в алгоритме кроме целочисленных операций прибавления и вычитания ничего нет - соответственно точность должна максимальная, допустимая в такой ситуации. а так что б своё придумать, то по идеи все варианты буду основаны на нахождение пикселя максимально приближенному к искомому, путём вычислению таких вот прирощений.