ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Nick Kovaliov                        2:5020/400     14 Feb 2003  10:41:09
 To : Igor Kasyanchuk
 Subject : Re: line
 -------------------------------------------------------------------------------- 
 

     IK> Вот например есть линия AD которая
     IK> задается двумя точками.
     IK> Координаты их известны.
     IK> Вопрос : Как найти координаты всех промежуточных точек.
 
 Hу конечно же ты говоришь о
 компьютерных точках, то есть пикселях.
 
 Я так понял, что тебе нужно нарисовать
 на экране прямую линию (отрезок) ?
 
 Вертикальные-горизонтальные понятно, как рисовать.
 
 Вычисляем ур-ние прямой на плоскости,
 проходящей через 2 точки (x0, y0) и (x1, y1) -
 
 (y-y0)*(x1-x0) = (x-x0)*(y1-y0)
 
 Причём (x1-x0) >= (y1-y0),
 и будем строить зависимость y от x.
 (другой случай сам додумаешься,
 нужна будет зависимость x от y)
 
 Зависимость y от x приводится к виду
 y = k*x + b, где k и b сам посчитаешь.
 Можно брать иксы между x0 и x1 по единичке,
 и получать соответствующие им координаты y.
 
 Конечно, для такой простой операции,
 как рисование линии, такая дорогая операция,
 как умножение на каждую точку, явно тормозно.
 
 Предложим же функцию, которая
 будет вычислять следующую точку,
 исходя из предыдущей, начальная точка,
 понятно, будет (x0, y0).
 Следующая точка отличается от предыдущей
 на некую константу, как правило 1.
 
 Итак, есть точка на линии (x, y),
 это некое y(x) = k*x + b,
 икс изменяется на единицу,
 игрек становится равным y(x+1) = k*(x+1) + b
 Hа сколько будет изменился y,
 когда мы именили икс на 1 ?
 Он изменился на y(x+1) - y(x),
 или на k*(x+1) + b - k*x - b =
 k*x + k + b - k*x - b = k
 
 То есть, меняя x на единицу, y изменяется на k.
 
 То есть,
 Xследующий = Xпредыдыдыщий + 1
 Yследующий = Yпредыдыдыщий + k
 
 Иными словами, для "более пологих" линий
 ты просто прибавляй x на единицу, а y на k.
 
 Hо k-то число дробное ! ...
 А значит, для рисования нужно постоянно
 приводить Y и X к целому виду ...
 Да и во floating point считать не всегда возможно.
 
 Тогда будем хранить y и k как fixed point числа.
 Иначе, представленные как y / q и k / q
 q выберем красивыми, например,
 q = 65536, или же q = 4294967296.
 
 Тогда для того же самого для вычисления
 коэффициента k просто изначально умножаем
 входые числа на это самое q,
 и вычисляем просто в целых числах.
 
 Hу всё, доходчивее я объяснять не умею ;-))
 До конкретного кода как-нить сам додумаешься.
 
 Есть ещё алгоритм Брезенхема,
 там тебе даже деления перед прорисовкой не нужно,
 правда, сама прорисовка происходит медленнее.
 
 Hо об этом как-нить в другой раз ...........
 
 До встречи, всего наилучшего !
 --- ifmail v.2.15dev5
  * Origin: Demos online service (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    line   Igor Kasyanchuk   13 Feb 2003 20:50:00   Re: line   Vitaly Lugovsky   14 Feb 2003 03:54:35   line   Igor Kasyanchuk   14 Feb 2003 16:07:00   Re: line   Nick Kovaliov   14 Feb 2003 10:41:09   line   Igor Kasyanchuk   14 Feb 2003 16:10:00   Re: line   Ivan Boldyrev   14 Feb 2003 12:10:20   Re: line   Alexei Philippov   15 Feb 2003 04:25:44   line   Igor Kasyanchuk   15 Feb 2003 10:53:00