Временно недоступен
957 / 228 / 14
Регистрация: 12.04.2009
Сообщений: 926
1

Объясните,пожалуйста,алгоритм DDA-линии

30.10.2009, 02:47. Показов 2881. Ответов 4
Метки нет (Все метки)

В-общем,в своей программе пришлось использовать этот алгоритм,он был взят отсюда: http://ru.wikipedia.org/wiki/%... 0%B8%D0%B8 Это алгоритм рисования линии попиксельно от точки до точки.Мне непонятно,как именно работают все сдвиги в алгоритме,почему выбрано именно 12 позиций,и почему 1<<11 так прокомментировано?И почему мы сдвигаем один раз вначале,а обратно сдвигаем много раз в цикле?Как бы это подробнее представить,а то в программу-то вписал,но понять тоже нужно.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
       int l,dx,dy;
 
       int xr = Math.abs( tx - sx );
       int yr = Math.abs( ty - sy );
 
       if ( xr > yr ) {
          l=xr;
       }
       else {
          l=yr;
       }
       int px = ( sx << 12 ) + ( 1 << 11 );     //  1<<11 аналогично 0.5 у float
       int py = ( sy << 12 ) + ( 1 << 11 );
       int ex = ( tx << 12 ) + ( 1 << 11 );
       int ey = ( ty << 12 ) + ( 1 << 11 );
 
       if ( l != 0 ) {
           dx = ( ex - px ) / l;
           dy = ( ey - py ) / l;
       }
       else  {
           dx = 0;
           dy = 0;
       }
       for(int i = 0; i <= l; i++) {
           drawpoint(px >> 12, py >> 12);
           px += dx;
           py += dy;
       }
Объясните,кто может
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.10.2009, 02:47
Ответы с готовыми решениями:

Алгоритм проверки принадлежности линии к многоугольнику
Подскажите алгоритмы проверки принадлежности линии к многоугольнику (невыпуклом,выпуклом) (можна...

Объясните пожалуйста задачу
Есть такая задача: Объясните(а не просто дайте ответ), пожалуйста, как решить эту задачу!...

Объясните, пожалуйста, чайнику разницу между рекурсией, корекурсией и итерацией
Уважаемые знатоки, Объясните, пожалуйста, несведущему разницу между рекурсией, корекурсией и...

Объясните, пожалуйста, как идиоту: почему байт в HEX обозначается двумя символами?
И как посчитать его значение, имея на руках только эти два значения? FF == 256, но как это...

4
770 / 760 / 59
Регистрация: 06.07.2009
Сообщений: 3,020
30.10.2009, 09:30 2
Все очень просто. Для того что бы не работать с вещественными числами все умножается на 2^12 использую быструю операцию сдвига. 12 выбрано исходя из необходимой точности, и больше не от чего не зависит, можете поставить любую другую. В конце все опять делится на 2^12.
( 1 << 11 ) это 1*2^11 , то есть в данном контексте 1/2 или 0,5 , вообщем константа. Правильнее было бы написать не ( 1 << 11 ) а ( 1 << (12-1) )
1
Временно недоступен
957 / 228 / 14
Регистрация: 12.04.2009
Сообщений: 926
30.10.2009, 11:30  [ТС] 3
Спасибо,немного понятнее,но всё же

> ( 1 << 11 ) это 1*2^11 , то есть в данном контексте 1/2 или 0,5 , вообщем константа.

Как 2 в 11 степени может быть равносильно 1/2? Вот этот момент непонятен.И почему сдвиг при инициализации один раз,а в цикле несколько?
0
770 / 760 / 59
Регистрация: 06.07.2009
Сообщений: 3,020
30.10.2009, 12:49 4
0,5 это 1/2 или 1*2^-1 , в данной задаче все числа умножаются на 2^12. То есть константа 0,5 при вычислениях превращается в 0,5*2^12 или, что тоже самое 1*2^11

Попробую попонятнее обьяснить. Возьмем для примера задачу z=x+y. x и y вещественные числа. Допустим операция + очень долгая для вещественных чисел. Что бы оптимизировать вычисления мы можем из вещественных x и y сделать целые, умножив на одинаковое число. Вообщем то число может быть любым. После сложения целых чисел получилось целый результат. Что бы из этого целого результата получить решение которое мы ищем, нужно разделить его на то же самое число.
По такой аналогии оптимизирована и ваша задача.
Число, на которое все умножается выбрана как степень двойки для еще большей скорости вычислений. Степень 12 взята от балды (реально ее нужно вычислять в зависимости он нужной точности и вообще даже конкретных координат точек)

Далее, первоночально мы имеем координаты двух точек, их и "преобразуем" в целые числа.
Но результатом задачи является множество точек, каждую координату которой нужно опять вернуть в исходную систему измерения. Отсюда и цикл.
1
Временно недоступен
957 / 228 / 14
Регистрация: 12.04.2009
Сообщений: 926
30.10.2009, 13:56  [ТС] 5
Всё,дошло! Спасибо огромное!
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.10.2009, 13:56

Помогите пожалуйста составить алгоритм
Разработать схему алгоритмадля подсчёта кол-ва отриц-ых чисел среди целых чисел...

Объясните пожалуйста по простому, что такое "монитор"?
Тот, что используется в параллельном программировании...

Объясните алгоритм "быстрой сортировки"
Вот мои рассуждения:У нас в начале есть массив, состоящий из N элементов. Определим функцию,которая...

Алгоритм DDA для линии
Как это на Python переписать: procedure DrawLine(); begin while true do begin ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru