Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 04.03.2012, 03:04
Аватар для Vertex
Новичок

Отправить личное сообщение для Vertex Посмотреть профиль Найти все сообщения от Vertex
 
Регистрация: 22.06.2008
Адрес: Узбекистан, Ташкент
Сообщений: 22

Линейное вычисление arctan
Известно, что для линейного вращения матрицы существует
Код:
// Prepare for rotation by 1 degree
    float sine = sin(PI / 180.0);
    float cose = cos(PI / 180.0);
// Init
    float x = 127.0;
    float y = 0.0;
    float tmp;
// Main cycle
    {
        tmp = x * cose - y * sine;
        y = y * cose + x * sine;
        x = tmp;
    }
Но вот никак не могу найти способ линейного вычисления арктангенса. Допустим, имеем
Код:
    float cx, cy; // Circle center
    float xp, yp; // Pixel x,y
    float xv, yv; // Velocity for xp,yp
    float an; // Start angle: arctan((yp - cy) / (xp - cx))
// Main cycle
    {
        xp += xv; // Step by x
        yp += yv; // Step by y
        an += ??? // Что тут писать? Вместо постоянного arctan((yp - cy) / (xp - cx))
    }
Надеюсь, вопрос понятен.
В общем, нужна формула линейной корректировки угла при линейном шаге по x и y.
А также вспомогательные формулы, когда вместо шага по x и y вдруг происходит лишь шаг по x или по y.

Спасибо!

Последний раз редактировалось Vertex, 04.03.2012 в 03:20.
  #2  
Старый 04.03.2012, 10:28
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Первый вопрос - для чего нужно значение угла?
  #3  
Старый 05.03.2012, 04:44
Аватар для Vertex
Новичок

Отправить личное сообщение для Vertex Посмотреть профиль Найти все сообщения от Vertex
 
Регистрация: 22.06.2008
Адрес: Узбекистан, Ташкент
Сообщений: 22

Линейное вычисление арктангенса
Просто нужно знать угол в цикле построения окружности, чтобы разорвать и получить дугу.

P.S.: Кстати, ещё никак не найду исходник построения дуги по аналогу оператора DRAW языка Бейсик из ZX-Spectrum.
Напомню, Draw 64,64,pi рисует полуокружность диаметром 64 пиксела.
Причём так же рисовали и Yamaha-MSX.

Спасибо!
  #4  
Старый 05.03.2012, 06:36
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Сам угол знать не обязательно. Достаточно один раз посчитать, какое соотношение Y-X будет на конечном угле, и останавливать построение, когда оно достигнется.
Пример - в статье по ссылке дуга в 1/8 рисуется while (x < y)
  #5  
Старый 12.03.2012, 08:17
Аватар для Vertex
Новичок

Отправить личное сообщение для Vertex Посмотреть профиль Найти все сообщения от Vertex
 
Регистрация: 22.06.2008
Адрес: Узбекистан, Ташкент
Сообщений: 22

Linear solve of arctan
Прошу прощения, но Вы меня не так поняли.
Алгоритм построения 1/8 дуги я сделал на си и на ассемблере (всего 10 инструкций на пиксел!). Однако, мне обязательно нужно знать точное текущее значение угла. Чтобы разрывать окружность и получать дугу.
Например, если нужно рисовать начиная с 3° до 33°, нужно после 3° включить прорисовку пикселей, а после 33° выключить.
Конечно, можно перед циклом произвести расчёты, чтобы не делать холостых ходов до 3°. Однако, в моём случае так оптимально.

Поэтому я спрашиваю. Какими формулами можно корректировать текущее значение угла, чтобы явно не прибегать к арктангенсу?

Всю остальную работу я сам сделаю (стаж работы с Паскалем и Си - 14 лет). Эвристику знаю нормально. Однако математическое образование-таки у меня практически отсутствует. И простейщее уровнение ставит в тупик! Что усугубляет познание основ графики.
  #6  
Старый 12.03.2012, 10:40
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>мне обязательно нужно знать точное текущее значение угла

Я всё-таки считаю, что угол знать не нужно.
На примере приведенных данных - считаем два тангенса - t3 = tg(3) и t33 = tg(33)
Крутим цикл, y и x меняются, проверяем, не стало ли отношение y/x >= t3 (лучше y - t3*x>=0), начинаем рисовать, и останавливаем, когда достигаем t33
  #7  
Старый 13.03.2012, 08:49
Аватар для Vertex
Новичок

Отправить личное сообщение для Vertex Посмотреть профиль Найти все сообщения от Vertex
 
Регистрация: 22.06.2008
Адрес: Узбекистан, Ташкент
Сообщений: 22

Сообщение от MBo Посмотреть сообщение
Я всё-таки считаю, что угол знать не нужно.
На примере приведенных данных - считаем два тангенса - t3 = tg(3) и t33 = tg(33)
Крутим цикл, y и x меняются, проверяем, не стало ли отношение y/x >= t3 (лучше y - t3*x>=0), начинаем рисовать, и останавливаем, когда достигаем t33
Извиняюсь, но я никак не могу Вас понять!
Соотношение x/y требует деления. А у меня в самом начале алгоритма производится единственное умножение. А в цикле - вычисление квадрата i формулой next_i^2 = this_i *2 + 1 с помощью единственной x86-инструкции LEA EAX,[EAX*2+1]...
Далее, планирую алгоритм перенести в FPGA и это радикально исключает всякие x/y. Так-как FPGA-версия рисования отрезков обходится без деления.
В моём случае, и в рисовании линий, и в рисовании окружности все сложные вычисления производятся процессором в начале. Далее данные передаются супер простому циклу из 12 инструкций, либо в FPGA (в перспективе) с набором из нескольких счётчиков-сумматоров. А рисование производится заполнением таблицы координат. Т.е. сам алгоритм не строит пиксельную модель линии/дуги, а лишь генерирует цепочку координат.

Итак, теперь Вы понимаете, что Ваши советы по оптимизации, к сожалению, совсем не годятся в моих случаях.
Мне нужно именно то, что я прошу. А не спектр вариантов, как это делать иначе.
Ещё - это не ожидание готового алгоритма, в котором я ничего не пойму и тупо буду copy-paste! Я в скрипте пробовал часами выявить зависимость arctan от x/y. И скрипт выводил таблицу, где реальный arctan отличался от пошагового вычисленного в некоторой прогрессии, которая мне не по зубам!

Например, в бессмысленном цикле
Код:
    float a = 0.0, x = 100.0, y = 0.0, z;
    do {
        z = a;
        a = arctan((y ++) / x);
    } while(FlushTable(a - z)); // Наша функция заполнения таблицы дифференции
строится таблица разности текущего и предыдущего углов при постоянно растущем y пока память под таблицу не исчерпается.
Но до математических уравнений очень мне далеко! Не пойму, как растёт разница и какой формулой её синтезировать
  #8  
Старый 13.03.2012, 09:35
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>Итак, теперь Вы понимаете, что Ваши советы по оптимизации, к сожалению, совсем не годятся в моих случаях

Теперь я понимаю, что Вы ответы не читаете. Для выражения в скобках деления не нужно - только сложение или вычитание.
  #9  
Старый 14.03.2012, 06:06
Аватар для Vertex
Новичок

Отправить личное сообщение для Vertex Посмотреть профиль Найти все сообщения от Vertex
 
Регистрация: 22.06.2008
Адрес: Узбекистан, Ташкент
Сообщений: 22

Сообщение от MBo Посмотреть сообщение
>Итак, теперь Вы понимаете, что Ваши советы по оптимизации, к сожалению, совсем не годятся в моих случаях

Теперь я понимаю, что Вы ответы не читаете. Для выражения в скобках деления не нужно - только сложение или вычитание.
Я понял Ваш совет.
Можно ещё вычислить ya = yc + r * sin, а в цикле сравнивать y и ya. В принципе, разработанный сейчас алгоритм нормально работает.
Так сказать, тему про рисование дуги можно закрыть

Однако, всё-таки, каким образом вычисляется atn? Просто ради интереса, очень хочется знать способ вычисления угла для очередного y.
  #10  
Старый 14.03.2012, 06:43
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Формул для вычисления обратных тригонометрических функций при модификации аргумента (подобно тому, как sin(x+dx) считается) я не видел, тем более, что в данном случае нужно оценивать ArcTan2(y+dy, x+dx), где одно из dx,dy ненулевое.

По поводу вычислений arctan можно посмотреть, что есть в алгоритмах CORDIC
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Вычисление факториала ;) _persicum_ Математические алгоритмы 14 11.11.2010 01:55
вычисление с точностью Shtolz Математические алгоритмы 4 27.03.2010 19:34
Головоломка с линейной алгеброй midi Задачи 3 13.02.2010 18:08
Вычисление exp гость Математические алгоритмы 3 26.01.2010 17:54
Вычисление выражений Andrew Математические алгоритмы 1 27.08.2007 00:45